C++ Reference

C++ Reference: Graph

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

Namespaces

namespace  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  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 class  CliqueResponse { CONTINUE , STOP }
 
enum class  BronKerboschAlgorithmStatus { COMPLETED , INTERRUPTED }
 

Functions

template<typename WeightFunctionType , typename GraphType >
absl::StatusOr< std::vector< std::pair< typename GraphType::NodeIndex, typename GraphType::NodeIndex > > > ComputeMinimumWeightMatching (const GraphType &graph, const WeightFunctionType &weight)
 
template<typename WeightFunctionType , typename GraphType >
absl::StatusOr< 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)
 

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 class BronKerboschAlgorithmStatus
strong
Enumerator
COMPLETED 
INTERRUPTED 

Definition at line 68 of file cliques.h.

◆ CliqueResponse

enum class CliqueResponse
strong
Enumerator
CONTINUE 
STOP 

Definition at line 58 of file cliques.h.

Function Documentation

◆ AddArcsFromMinimumSpanningTree()

void 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 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 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 > BuildEulerianPath ( const Graph &  graph)

Definition at line 138 of file eulerian_path.h.

◆ BuildEulerianPathFromNode()

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

Definition at line 74 of file eulerian_path.h.

◆ BuildEulerianTour()

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

Definition at line 128 of file eulerian_path.h.

◆ BuildEulerianTourFromNode()

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

Definition at line 116 of file eulerian_path.h.

◆ BuildKruskalMinimumSpanningTree()

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

Definition at line 89 of file minimum_spanning_tree.h.

◆ BuildKruskalMinimumSpanningTreeFromSortedArcs()

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

Definition at line 50 of file minimum_spanning_tree.h.

◆ BuildLineGraph()

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

Definition at line 2088 of file ebert_graph.h.

◆ BuildPrimMinimumSpanningTree()

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

Definition at line 115 of file minimum_spanning_tree.h.

◆ ComputeMinimumWeightMatching()

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

Definition at line 109 of file christofides.h.

◆ ComputeMinimumWeightMatchingWithMIP()

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

Definition at line 145 of file christofides.h.

◆ ComputeOneTree()

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 
)

Definition at line 331 of file one_tree_lower_bound.h.

◆ ComputeOneTreeLowerBound()

double ComputeOneTreeLowerBound ( int  number_of_nodes,
const CostFunction &  cost 
)

Definition at line 480 of file one_tree_lower_bound.h.

◆ ComputeOneTreeLowerBoundWithAlgorithm()

double 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 ComputeOneTreeLowerBoundWithParameters ( int  number_of_nodes,
const CostFunction &  cost,
const TravelingSalesmanLowerBoundParameters &  parameters 
)

Definition at line 452 of file one_tree_lower_bound.h.

◆ CoverArcsByCliques()

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

◆ DijkstraShortestPath()

bool 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 FindCliques ( std::function< bool(int, int)>  graph,
int  node_count,
std::function< bool(const std::vector< int > &)>  callback 
)

◆ GetNodeMinimizingEdgeCostToSource()

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

Definition at line 310 of file one_tree_lower_bound.h.

◆ IsEulerianGraph()

bool IsEulerianGraph ( const Graph &  graph)

Definition at line 40 of file eulerian_path.h.

◆ IsSemiEulerianGraph()

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

Definition at line 55 of file eulerian_path.h.

◆ MakeHamiltonianPathSolver()

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

Definition at line 599 of file hamiltonian_path.h.

◆ NearestNeighbors()

std::set< std::pair< int, int > > 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 StableDijkstraShortestPath ( int  node_count,
int  start_node,
int  end_node,
std::function< int64(int, int)>  graph,
int64  disconnected_distance,
std::vector< int > *  nodes 
)