C++ Reference
C++ Reference: Graph
Namespaces | |
| or_internal | |
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 ¶meters) |
| 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
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
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
|
strong |
◆ CliqueResponse
|
strong |
◆ 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()
|
inline |
Definition at line 88 of file flow_problem.pb.h.
◆ FlowModel_ProblemType_Parse()
|
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 |
Definition at line 84 of file flow_problem.pb.h.
◆ FlowModel_ProblemType_ProblemType_MAX
|
constexpr |
Definition at line 83 of file flow_problem.pb.h.
◆ FlowModel_ProblemType_ProblemType_MIN
|
constexpr |
Definition at line 82 of file flow_problem.pb.h.