C++ Reference

C++ Reference: Graph

Namespaces | Classes | Typedefs | Enumerations | Functions | Variables
operations_research Namespace Reference

Namespaces

 or_internal
 

Classes

class  AnnotatedGraphBuildManager
 
class  ArcFunctorOrderingByTailAndHead
 
class  ArcIndexOrderingByTailNode
 
class  BronKerboschAlgorithm
 
class  ChristofidesPathSolver
 
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 (::PROTOBUF_NAMESPACE_ID::ConstStringParam 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 75 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 89 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 115 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 104 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 138 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 87 of file flow_problem.pb.h.

◆ FlowModel_ProblemType_Parse()

bool operations_research::FlowModel_ProblemType_Parse ( ::PROTOBUF_NAMESPACE_ID::ConstStringParam  name,
FlowModel_ProblemType *  value 
)
inline

Definition at line 94 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_
extern

◆ _FlowModel_default_instance_

FlowModelDefaultTypeInternal _FlowModel_default_instance_
extern

◆ _Node_default_instance_

NodeDefaultTypeInternal _Node_default_instance_
extern

◆ FlowModel_ProblemType_ProblemType_ARRAYSIZE

constexpr int FlowModel_ProblemType_ProblemType_ARRAYSIZE = FlowModel_ProblemType_ProblemType_MAX + 1
constexpr

Definition at line 83 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 82 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 81 of file flow_problem.pb.h.