Namespaces
	or_internal

Classes
class	AnnotatedGraphBuildManager

class	ArcFunctorOrderingByTailAndHead

class	ArcIndexOrderingByTailNode

class	BronKerboschAlgorithm

class	ChristofidesPathSolver

class	ConnectedComponents

class	CostValueCycleHandler

class	EbertGraph

class	EbertGraphBase

class	ElementIterator

class	ForwardEbertGraph

class	ForwardStaticGraph

class	GenericMaxFlow

class	GenericMinCostFlow

struct	graph_traits

struct	graph_traits< ForwardEbertGraph< NodeIndexType, ArcIndexType > >

struct	graph_traits< ForwardStaticGraph< NodeIndexType, ArcIndexType > >

struct	Graphs

struct	Graphs< operations_research::StarGraph >

class	HamiltonianPathSolver

class	HeldWolfeCrowderEvaluator

class	LatticeMemoryManager

class	LinearSumAssignment

class	MaxFlow

class	MaxFlowStatusClass

class	MinCostFlow

class	MinCostFlowBase

class	PermutationIndexComparisonByArcHead

class	PriorityQueueWithRestrictedPush

class	PROTOBUF_FINAL

class	PruningHamiltonianSolver

class	Set

class	SetRangeIterator

class	SetRangeWithCardinality

class	SimpleMaxFlow

class	SimpleMinCostFlow

class	StarGraphBase

class	TailArrayManager

struct	TravelingSalesmanLowerBoundParameters

class	VolgenantJonkerEvaluator

Typedefs
typedef int32	NodeIndex

typedef int32	ArcIndex

typedef int64	FlowQuantity

typedef int64	CostValue

typedef EbertGraph< NodeIndex, ArcIndex >	StarGraph

typedef ForwardEbertGraph< NodeIndex, ArcIndex >	ForwardStarGraph

typedef ForwardStaticGraph< NodeIndex, ArcIndex >	ForwardStarStaticGraph

typedef ZVector< NodeIndex >	NodeIndexArray

typedef ZVector< ArcIndex >	ArcIndexArray

typedef ZVector< FlowQuantity >	QuantityArray

typedef ZVector< CostValue >	CostArray

typedef int	PathNodeIndex

Enumerations
enum	CliqueResponse { CONTINUE, STOP }

enum	BronKerboschAlgorithmStatus { COMPLETED, INTERRUPTED }

enum	FlowModel_ProblemType : int { FlowModel_ProblemType_LINEAR_SUM_ASSIGNMENT = 0, FlowModel_ProblemType_MAX_FLOW = 1, FlowModel_ProblemType_MIN_COST_FLOW = 2 }

Functions
template<typename WeightFunctionType , typename GraphType >
std::vector< std::pair< typename GraphType::NodeIndex, typename GraphType::NodeIndex > >	ComputeMinimumWeightMatching (const GraphType &graph, const WeightFunctionType &weight)

template<typename WeightFunctionType , typename GraphType >
std::vector< std::pair< typename GraphType::NodeIndex, typename GraphType::NodeIndex > >	ComputeMinimumWeightMatchingWithMIP (const GraphType &graph, const WeightFunctionType &weight)

void	FindCliques (std::function< bool(int, int)> graph, int node_count, std::function< bool(const std::vector< int > &)> callback)

void	CoverArcsByCliques (std::function< bool(int, int)> graph, int node_count, std::function< bool(const std::vector< int > &)> callback)

template<typename GraphType >
bool	BuildLineGraph (const GraphType &graph, GraphType *const line_graph)

template<typename Graph >
bool	IsEulerianGraph (const Graph &graph)

template<typename NodeIndex , typename Graph >
bool	IsSemiEulerianGraph (const Graph &graph, std::vector< NodeIndex > *odd_nodes)

template<typename NodeIndex , typename Graph >
std::vector< NodeIndex >	BuildEulerianPathFromNode (const Graph &graph, NodeIndex root)

template<typename NodeIndex , typename Graph >
std::vector< NodeIndex >	BuildEulerianTourFromNode (const Graph &graph, NodeIndex root)

template<typename Graph >
std::vector< typename Graph::NodeIndex >	BuildEulerianTour (const Graph &graph)

template<typename Graph >
std::vector< typename Graph::NodeIndex >	BuildEulerianPath (const Graph &graph)

template<typename CostType , typename CostFunction >
HamiltonianPathSolver< CostType, CostFunction >	MakeHamiltonianPathSolver (int num_nodes, CostFunction cost)

template<typename Graph >
std::vector< typename Graph::ArcIndex >	BuildKruskalMinimumSpanningTreeFromSortedArcs (const Graph &graph, const std::vector< typename Graph::ArcIndex > &sorted_arcs)

template<typename Graph , typename ArcComparator >
std::vector< typename Graph::ArcIndex >	BuildKruskalMinimumSpanningTree (const Graph &graph, const ArcComparator &arc_comparator)

template<typename Graph , typename ArcValue >
std::vector< typename Graph::ArcIndex >	BuildPrimMinimumSpanningTree (const Graph &graph, const ArcValue &arc_value)

template<typename CostFunction >
std::set< std::pair< int, int > >	NearestNeighbors (int number_of_nodes, int number_of_neighbors, const CostFunction &cost)

template<typename CostFunction >
void	AddArcsFromMinimumSpanningTree (int number_of_nodes, const CostFunction &cost, std::set< std::pair< int, int >> *arcs)

template<typename CostFunction , typename GraphType , typename AcceptFunction >
int	GetNodeMinimizingEdgeCostToSource (const GraphType &graph, int source, const CostFunction &cost, AcceptFunction accept)

template<typename CostFunction , typename GraphType , typename CostType >
std::vector< int >	ComputeOneTree (const GraphType &graph, const CostFunction &cost, const std::vector< double > &weights, const std::vector< int > &sorted_arcs, CostType *one_tree_cost)

template<typename CostFunction , typename Algorithm >
double	ComputeOneTreeLowerBoundWithAlgorithm (int number_of_nodes, int nearest_neighbors, const CostFunction &cost, Algorithm *algorithm)

template<typename CostFunction >
double	ComputeOneTreeLowerBoundWithParameters (int number_of_nodes, const CostFunction &cost, const TravelingSalesmanLowerBoundParameters &parameters)

template<typename CostFunction >
double	ComputeOneTreeLowerBound (int number_of_nodes, const CostFunction &cost)

bool	DijkstraShortestPath (int node_count, int start_node, int end_node, std::function< int64(int, int)> graph, int64 disconnected_distance, std::vector< int > *nodes)

bool	StableDijkstraShortestPath (int node_count, int start_node, int end_node, std::function< int64(int, int)> graph, int64 disconnected_distance, std::vector< int > *nodes)

bool	BellmanFordShortestPath (int node_count, int start_node, int end_node, std::function< int64(int, int)> graph, int64 disconnected_distance, std::vector< int > *nodes)

bool	AStarShortestPath (int node_count, int start_node, int end_node, std::function< int64(int, int)> graph, std::function< int64(int)> heuristic, int64 disconnected_distance, std::vector< int > *nodes)

bool	FlowModel_ProblemType_IsValid (int value)

const ::PROTOBUF_NAMESPACE_ID::EnumDescriptor *	FlowModel_ProblemType_descriptor ()

template<typename T >
const std::string &	FlowModel_ProblemType_Name (T enum_t_value)

bool	FlowModel_ProblemType_Parse (const std::string &name, FlowModel_ProblemType *value)

Variables
ArcDefaultTypeInternal	_Arc_default_instance_

FlowModelDefaultTypeInternal	_FlowModel_default_instance_

NodeDefaultTypeInternal	_Node_default_instance_

constexpr FlowModel_ProblemType	FlowModel_ProblemType_ProblemType_MIN = FlowModel_ProblemType_LINEAR_SUM_ASSIGNMENT

constexpr FlowModel_ProblemType	FlowModel_ProblemType_ProblemType_MAX = FlowModel_ProblemType_MIN_COST_FLOW

constexpr int	FlowModel_ProblemType_ProblemType_ARRAYSIZE = FlowModel_ProblemType_ProblemType_MAX + 1

Typedef Documentation

◆ ArcIndex

typedef int32 ArcIndex

Definition at line 201 of file ebert_graph.h.

◆ ArcIndexArray

typedef ZVector<ArcIndex> ArcIndexArray

Definition at line 208 of file ebert_graph.h.

◆ CostArray

typedef ZVector<CostValue> CostArray

Definition at line 210 of file ebert_graph.h.

◆ CostValue

typedef int64 CostValue

Definition at line 203 of file ebert_graph.h.

◆ FlowQuantity

typedef int64 FlowQuantity

Definition at line 202 of file ebert_graph.h.

◆ ForwardStarGraph

typedef ForwardEbertGraph<NodeIndex, ArcIndex> ForwardStarGraph

Definition at line 205 of file ebert_graph.h.

◆ ForwardStarStaticGraph

typedef ForwardStaticGraph<NodeIndex, ArcIndex> ForwardStarStaticGraph

Definition at line 206 of file ebert_graph.h.

◆ NodeIndex

typedef int32 NodeIndex

Definition at line 200 of file ebert_graph.h.

◆ NodeIndexArray

typedef ZVector<NodeIndex> NodeIndexArray

Definition at line 207 of file ebert_graph.h.

◆ PathNodeIndex

typedef int PathNodeIndex

Definition at line 450 of file hamiltonian_path.h.

◆ QuantityArray

typedef ZVector<FlowQuantity> QuantityArray

Definition at line 209 of file ebert_graph.h.

◆ StarGraph

typedef EbertGraph<NodeIndex, ArcIndex> StarGraph

Definition at line 204 of file ebert_graph.h.

Enumeration Type Documentation

◆ BronKerboschAlgorithmStatus

enum BronKerboschAlgorithmStatus

strong

Enumerator
COMPLETED
INTERRUPTED

Definition at line 68 of file cliques.h.

◆ CliqueResponse

enum CliqueResponse

strong

Enumerator
CONTINUE
STOP

Definition at line 58 of file cliques.h.

◆ FlowModel_ProblemType

enum FlowModel_ProblemType : int

Enumerator
FlowModel_ProblemType_LINEAR_SUM_ASSIGNMENT
FlowModel_ProblemType_MAX_FLOW
FlowModel_ProblemType_MIN_COST_FLOW

Definition at line 76 of file flow_problem.pb.h.

Function Documentation

◆ AddArcsFromMinimumSpanningTree()

void operations_research::AddArcsFromMinimumSpanningTree	(	int	number_of_nodes,
		const CostFunction &	cost,
		std::set< std::pair< int, int >> *	arcs
	)

Definition at line 293 of file one_tree_lower_bound.h.

◆ AStarShortestPath()

bool operations_research::AStarShortestPath	(	int	node_count,
		int	start_node,
		int	end_node,
		std::function< int64(int, int)>	graph,
		std::function< int64(int)>	heuristic,
		int64	disconnected_distance,
		std::vector< int > *	nodes
	)

◆ BellmanFordShortestPath()

bool operations_research::BellmanFordShortestPath	(	int	node_count,
		int	start_node,
		int	end_node,
		std::function< int64(int, int)>	graph,
		int64	disconnected_distance,
		std::vector< int > *	nodes
	)

◆ BuildEulerianPath()

std::vector<typename Graph::NodeIndex> operations_research::BuildEulerianPath ( const Graph & graph )

Definition at line 138 of file eulerian_path.h.

◆ BuildEulerianPathFromNode()

std::vector<NodeIndex> operations_research::BuildEulerianPathFromNode	(	const Graph &	graph,
		NodeIndex	root
	)

Definition at line 74 of file eulerian_path.h.

◆ BuildEulerianTour()

std::vector<typename Graph::NodeIndex> operations_research::BuildEulerianTour ( const Graph & graph )

Definition at line 128 of file eulerian_path.h.

◆ BuildEulerianTourFromNode()

std::vector<NodeIndex> operations_research::BuildEulerianTourFromNode	(	const Graph &	graph,
		NodeIndex	root
	)

Definition at line 116 of file eulerian_path.h.

◆ BuildKruskalMinimumSpanningTree()

std::vector<typename Graph::ArcIndex> operations_research::BuildKruskalMinimumSpanningTree	(	const Graph &	graph,
		const ArcComparator &	arc_comparator
	)

Definition at line 91 of file minimum_spanning_tree.h.

◆ BuildKruskalMinimumSpanningTreeFromSortedArcs()

std::vector<typename Graph::ArcIndex> operations_research::BuildKruskalMinimumSpanningTreeFromSortedArcs	(	const Graph &	graph,
		const std::vector< typename Graph::ArcIndex > &	sorted_arcs
	)

Definition at line 50 of file minimum_spanning_tree.h.

◆ BuildLineGraph()

bool operations_research::BuildLineGraph	(	const GraphType &	graph,
		GraphType *const	line_graph
	)

Definition at line 2088 of file ebert_graph.h.

◆ BuildPrimMinimumSpanningTree()

std::vector<typename Graph::ArcIndex> operations_research::BuildPrimMinimumSpanningTree	(	const Graph &	graph,
		const ArcValue &	arc_value
	)

Definition at line 117 of file minimum_spanning_tree.h.

◆ ComputeMinimumWeightMatching()

std::vector< std::pair<typename GraphType::NodeIndex, typename GraphType::NodeIndex> > operations_research::ComputeMinimumWeightMatching	(	const GraphType &	graph,
		const WeightFunctionType &	weight
	)

Definition at line 106 of file christofides.h.

◆ ComputeMinimumWeightMatchingWithMIP()

std::vector< std::pair<typename GraphType::NodeIndex, typename GraphType::NodeIndex> > operations_research::ComputeMinimumWeightMatchingWithMIP	(	const GraphType &	graph,
		const WeightFunctionType &	weight
	)

Definition at line 140 of file christofides.h.

◆ ComputeOneTree()

std::vector<int> operations_research::ComputeOneTree	(	const GraphType &	graph,
		const CostFunction &	cost,
		const std::vector< double > &	weights,
		const std::vector< int > &	sorted_arcs,
		CostType *	one_tree_cost
	)

Definition at line 331 of file one_tree_lower_bound.h.

◆ ComputeOneTreeLowerBound()

double operations_research::ComputeOneTreeLowerBound	(	int	number_of_nodes,
		const CostFunction &	cost
	)

Definition at line 480 of file one_tree_lower_bound.h.

◆ ComputeOneTreeLowerBoundWithAlgorithm()

double operations_research::ComputeOneTreeLowerBoundWithAlgorithm	(	int	number_of_nodes,
		int	nearest_neighbors,
		const CostFunction &	cost,
		Algorithm *	algorithm
	)

Definition at line 378 of file one_tree_lower_bound.h.

◆ ComputeOneTreeLowerBoundWithParameters()

double operations_research::ComputeOneTreeLowerBoundWithParameters	(	int	number_of_nodes,
		const CostFunction &	cost,
		const TravelingSalesmanLowerBoundParameters &	parameters
	)

Definition at line 452 of file one_tree_lower_bound.h.

◆ CoverArcsByCliques()

void operations_research::CoverArcsByCliques	(	std::function< bool(int, int)>	graph,
		int	node_count,
		std::function< bool(const std::vector< int > &)>	callback
	)

◆ DijkstraShortestPath()

bool operations_research::DijkstraShortestPath	(	int	node_count,
		int	start_node,
		int	end_node,
		std::function< int64(int, int)>	graph,
		int64	disconnected_distance,
		std::vector< int > *	nodes
	)

◆ FindCliques()

void operations_research::FindCliques	(	std::function< bool(int, int)>	graph,
		int	node_count,
		std::function< bool(const std::vector< int > &)>	callback
	)

◆ FlowModel_ProblemType_descriptor()

const ::PROTOBUF_NAMESPACE_ID::EnumDescriptor* operations_research::FlowModel_ProblemType_descriptor ( )

◆ FlowModel_ProblemType_IsValid()

bool operations_research::FlowModel_ProblemType_IsValid ( int value )

◆ FlowModel_ProblemType_Name()

const std::string& operations_research::FlowModel_ProblemType_Name ( T enum_t_value )

inline

Definition at line 88 of file flow_problem.pb.h.

◆ FlowModel_ProblemType_Parse()

bool operations_research::FlowModel_ProblemType_Parse	(	const std::string &	name,
		FlowModel_ProblemType *	value
	)

inline

Definition at line 95 of file flow_problem.pb.h.

◆ GetNodeMinimizingEdgeCostToSource()

int operations_research::GetNodeMinimizingEdgeCostToSource	(	const GraphType &	graph,
		int	source,
		const CostFunction &	cost,
		AcceptFunction	accept
	)

Definition at line 310 of file one_tree_lower_bound.h.

◆ IsEulerianGraph()

bool operations_research::IsEulerianGraph ( const Graph & graph )

Definition at line 40 of file eulerian_path.h.

◆ IsSemiEulerianGraph()

bool operations_research::IsSemiEulerianGraph	(	const Graph &	graph,
		std::vector< NodeIndex > *	odd_nodes
	)

Definition at line 55 of file eulerian_path.h.

◆ MakeHamiltonianPathSolver()

HamiltonianPathSolver<CostType, CostFunction> operations_research::MakeHamiltonianPathSolver	(	int	num_nodes,
		CostFunction	cost
	)

Definition at line 599 of file hamiltonian_path.h.

◆ NearestNeighbors()

std::set<std::pair<int, int> > operations_research::NearestNeighbors	(	int	number_of_nodes,
		int	number_of_neighbors,
		const CostFunction &	cost
	)

Definition at line 262 of file one_tree_lower_bound.h.

◆ StableDijkstraShortestPath()

bool operations_research::StableDijkstraShortestPath	(	int	node_count,
		int	start_node,
		int	end_node,
		std::function< int64(int, int)>	graph,
		int64	disconnected_distance,
		std::vector< int > *	nodes
	)

Variable Documentation

◆ _Arc_default_instance_

ArcDefaultTypeInternal _Arc_default_instance_

◆ _FlowModel_default_instance_

FlowModelDefaultTypeInternal _FlowModel_default_instance_

◆ _Node_default_instance_

NodeDefaultTypeInternal _Node_default_instance_

◆ FlowModel_ProblemType_ProblemType_ARRAYSIZE

constexpr int FlowModel_ProblemType_ProblemType_ARRAYSIZE = FlowModel_ProblemType_ProblemType_MAX + 1

constexpr

Definition at line 84 of file flow_problem.pb.h.

◆ FlowModel_ProblemType_ProblemType_MAX

constexpr FlowModel_ProblemType FlowModel_ProblemType_ProblemType_MAX = FlowModel_ProblemType_MIN_COST_FLOW

constexpr

Definition at line 83 of file flow_problem.pb.h.

◆ FlowModel_ProblemType_ProblemType_MIN

constexpr FlowModel_ProblemType FlowModel_ProblemType_ProblemType_MIN = FlowModel_ProblemType_LINEAR_SUM_ASSIGNMENT

constexpr

Definition at line 82 of file flow_problem.pb.h.

C++ Reference

C++ Reference: Graph

Namespaces

Classes

Typedefs

Enumerations

Functions

Variables

Typedef Documentation

◆ ArcIndex

◆ ArcIndexArray

◆ CostArray

◆ CostValue

◆ FlowQuantity

◆ ForwardStarGraph

◆ ForwardStarStaticGraph

◆ NodeIndex

◆ NodeIndexArray

◆ PathNodeIndex

◆ QuantityArray

◆ StarGraph

Enumeration Type Documentation

◆ BronKerboschAlgorithmStatus

◆ CliqueResponse

◆ FlowModel_ProblemType

Function Documentation

◆ AddArcsFromMinimumSpanningTree()

◆ AStarShortestPath()

◆ BellmanFordShortestPath()

◆ BuildEulerianPath()

◆ BuildEulerianPathFromNode()

◆ BuildEulerianTour()

◆ BuildEulerianTourFromNode()

◆ BuildKruskalMinimumSpanningTree()

◆ BuildKruskalMinimumSpanningTreeFromSortedArcs()

◆ BuildLineGraph()

◆ BuildPrimMinimumSpanningTree()

◆ ComputeMinimumWeightMatching()

◆ ComputeMinimumWeightMatchingWithMIP()

◆ ComputeOneTree()

◆ ComputeOneTreeLowerBound()

◆ ComputeOneTreeLowerBoundWithAlgorithm()

◆ ComputeOneTreeLowerBoundWithParameters()

◆ CoverArcsByCliques()

◆ DijkstraShortestPath()

◆ FindCliques()

◆ FlowModel_ProblemType_descriptor()

◆ FlowModel_ProblemType_IsValid()

◆ FlowModel_ProblemType_Name()

◆ FlowModel_ProblemType_Parse()

◆ GetNodeMinimizingEdgeCostToSource()

◆ IsEulerianGraph()

◆ IsSemiEulerianGraph()

◆ MakeHamiltonianPathSolver()

◆ NearestNeighbors()

◆ StableDijkstraShortestPath()

Variable Documentation

◆ _Arc_default_instance_

◆ _FlowModel_default_instance_

◆ _Node_default_instance_

◆ FlowModel_ProblemType_ProblemType_ARRAYSIZE

◆ FlowModel_ProblemType_ProblemType_MAX

◆ FlowModel_ProblemType_ProblemType_MIN