C++ Reference
C++ Reference: Graph
ebert_graph.h
Go to the documentation of this file.
AnnotatedGraphBuildManager(typename GraphType::NodeIndex num_nodes, typename GraphType::ArcIndex num_arcs, bool sort_arcs)
Definition: ebert_graph.h:2068
bool operator()(typename GraphType::ArcIndex a, typename GraphType::ArcIndex b) const
Definition: ebert_graph.h:1944
ArcFunctorOrderingByTailAndHead(const GraphType &graph)
Definition: ebert_graph.h:1941
void operator=(const IncomingArcIterator &iterator)
Definition: ebert_graph.h:1319
IncomingArcIterator(const EbertGraph &graph, NodeIndexType node, ArcIndexType arc)
Definition: ebert_graph.h:1309
bool Ok() const
Definition: ebert_graph.h:1326
IncomingArcIterator(const EbertGraph &graph, NodeIndexType node)
Definition: ebert_graph.h:1300
ArcIndexType Index() const
Definition: ebert_graph.h:1335
Definition: ebert_graph.h:1237
OutgoingOrOppositeIncomingArcIterator(const EbertGraph &graph, NodeIndexType node, ArcIndexType arc)
Definition: ebert_graph.h:1250
void Next()
Definition: ebert_graph.h:1269
bool Ok() const
Definition: ebert_graph.h:1266
OutgoingOrOppositeIncomingArcIterator(const EbertGraph &graph, NodeIndexType node)
Definition: ebert_graph.h:1239
ArcIndexType Index() const
Definition: ebert_graph.h:1275
void operator=(const OutgoingOrOppositeIncomingArcIterator &iterator)
Definition: ebert_graph.h:1259
~CycleHandlerForAnnotatedArcs() override
Definition: ebert_graph.h:1095
void SetIndexFromIndex(ArcIndexType source, ArcIndexType destination) const override
Definition: ebert_graph.h:1066
bool Unseen(ArcIndexType permutation_element) const override
Definition: ebert_graph.h:1091
CycleHandlerForAnnotatedArcs(PermutationCycleHandler< ArcIndexType > *annotation_handler, DerivedGraph *graph)
Definition: ebert_graph.h:1050
void SetTempFromIndex(ArcIndexType source) override
Definition: ebert_graph.h:1058
void SetIndexFromTemp(ArcIndexType destination) const override
Definition: ebert_graph.h:1075
void SetSeen(ArcIndexType *permutation_element) const override
Definition: ebert_graph.h:1087
static const NodeIndexType kNilNode
Definition: ebert_graph.h:216
ZVector< ArcIndexType > next_adjacent_arc_
Definition: ebert_graph.h:1147
bool IsNodeValid(NodeIndexType node) const
Definition: ebert_graph.h:279
ArcIndexType max_num_arcs_
Definition: ebert_graph.h:489
static const ArcIndexType kFirstArc
Definition: ebert_graph.h:225
ArcIndexType NextOutgoingArc(const NodeIndexType unused_node, const ArcIndexType arc) const
Definition: ebert_graph.h:1138
ZVector< ArcIndexType > first_incident_arc_
Definition: ebert_graph.h:502
static const ArcIndexType kMaxNumArcs
Definition: ebert_graph.h:235
bool Reserve(NodeIndexType new_max_num_nodes, ArcIndexType new_max_num_arcs)
Definition: ebert_graph.h:978
bool representation_clean_
Definition: ebert_graph.h:1152
ArcIndexType AddArc(NodeIndexType tail, NodeIndexType head)
Definition: ebert_graph.h:1001
ZVector< NodeIndexType > head_
Definition: ebert_graph.h:498
ArcIndexType end_arc_index() const
Definition: ebert_graph.h:252
void Initialize(NodeIndexType max_num_nodes, ArcIndexType max_num_arcs)
Definition: ebert_graph.h:1112
NodeIndexType num_nodes_
Definition: ebert_graph.h:492
ArcIndexType FirstOutgoingOrOppositeIncomingArc(const NodeIndexType node) const
Definition: ebert_graph.h:1123
void GroupForwardArcsByFunctor(const ArcIndexTypeStrictWeakOrderingFunctor &compare, PermutationCycleHandler< ArcIndexType > *annotation_handler)
Definition: ebert_graph.h:1022
static const ArcIndexType kNilArc
Definition: ebert_graph.h:219
static const NodeIndexType kMaxNumNodes
Definition: ebert_graph.h:230
NodeIndexType max_num_nodes_
Definition: ebert_graph.h:486
static const NodeIndexType kFirstNode
Definition: ebert_graph.h:222
ArcIndexType NextAdjacentArc(const ArcIndexType arc) const
Definition: ebert_graph.h:1131
bool IsOutgoingOrOppositeIncoming(ArcIndexType arc, NodeIndexType node) const
Definition: ebert_graph.h:1429
bool IsDirect(const ArcIndexType arc) const
Definition: ebert_graph.h:1417
void BuildRepresentation()
Definition: ebert_graph.h:1448
bool IsIncoming(ArcIndexType arc, NodeIndexType node) const
Definition: ebert_graph.h:1435
NodeIndexType DirectArcHead(const ArcIndexType arc) const
Definition: ebert_graph.h:1391
bool CheckArcValidity(const ArcIndexType arc) const
Definition: ebert_graph.h:1371
ArcIndexType Opposite(const ArcIndexType arc) const
Definition: ebert_graph.h:1409
bool IsOutgoing(ArcIndexType arc, NodeIndexType node) const
Definition: ebert_graph.h:1440
std::string DebugString() const
Definition: ebert_graph.h:1458
bool IsReverse(const ArcIndexType arc) const
Definition: ebert_graph.h:1423
ArcIndexType ReverseArc(const ArcIndexType arc) const
Definition: ebert_graph.h:1402
ArcIndexType DirectArc(const ArcIndexType arc) const
Definition: ebert_graph.h:1396
NodeIndexType Tail(const ArcIndexType arc) const
Definition: ebert_graph.h:1376
EbertGraph(NodeIndexType max_num_nodes, ArcIndexType max_num_arcs)
Definition: ebert_graph.h:1228
bool CheckArcBounds(const ArcIndexType arc) const
Definition: ebert_graph.h:1363
NodeIndexType DirectArcTail(const ArcIndexType arc) const
Definition: ebert_graph.h:1384
ForwardEbertGraph(NodeIndexType max_num_nodes, ArcIndexType max_num_arcs)
Definition: ebert_graph.h:1603
void BuildRepresentation()
Definition: ebert_graph.h:1646
ForwardEbertGraph()
Definition: ebert_graph.h:1601
bool IsIncoming(ArcIndexType arc, NodeIndexType node) const
Definition: ebert_graph.h:1638
bool BuildTailArray()
Definition: ebert_graph.h:1656
bool CheckArcValidity(const ArcIndexType arc) const
Definition: ebert_graph.h:1620
void ReleaseTailArray()
Definition: ebert_graph.h:1684
bool CheckTailIndexValidity(const ArcIndexType arc) const
Definition: ebert_graph.h:1625
std::string DebugString() const
Definition: ebert_graph.h:1698
NodeIndexType Tail(const ArcIndexType arc) const
Definition: ebert_graph.h:1631
bool CheckArcBounds(const ArcIndexType arc) const
Definition: ebert_graph.h:1612
~ForwardEbertGraph()
Definition: ebert_graph.h:1607
bool TailArrayComplete() const
Definition: ebert_graph.h:1687
NodeIndexType NodeIndex
Definition: ebert_graph.h:1598
void SetIndexFromIndex(ArcIndexType source, ArcIndexType destination) const override
Definition: ebert_graph.h:586
CycleHandlerForAnnotatedArcs(PermutationCycleHandler< ArcIndexType > *annotation_handler, NodeIndexType *data)
Definition: ebert_graph.h:575
void SetTempFromIndex(ArcIndexType source) override
Definition: ebert_graph.h:581
void SetIndexFromTemp(ArcIndexType destination) const override
Definition: ebert_graph.h:592
bool IsIncoming(ArcIndexType arc, NodeIndexType node) const
Definition: ebert_graph.h:763
bool BuildTailArray()
Definition: ebert_graph.h:816
bool CheckArcValidity(const ArcIndexType arc) const
Definition: ebert_graph.h:778
void ReleaseTailArray()
Definition: ebert_graph.h:844
bool CheckTailIndexValidity(const ArcIndexType arc) const
Definition: ebert_graph.h:783
ArcIndexType NextOutgoingArc(const NodeIndexType node, ArcIndexType arc) const
Definition: ebert_graph.h:788
ForwardStaticGraph(const NodeIndexType num_nodes, const ArcIndexType num_arcs, const bool sort_arcs_by_head, std::vector< std::pair< NodeIndexType, NodeIndexType > > *client_input_arcs, operations_research::PermutationCycleHandler< ArcIndexType > *const client_cycle_handler)
Definition: ebert_graph.h:621
std::string DebugString() const
Definition: ebert_graph.h:802
NodeIndexType Tail(const ArcIndexType arc) const
Definition: ebert_graph.h:756
bool CheckArcBounds(const ArcIndexType arc) const
Definition: ebert_graph.h:770
bool TailArrayComplete() const
Definition: ebert_graph.h:847
NodeIndexType NodeIndex
Definition: ebert_graph.h:564
PermutationIndexComparisonByArcHead(const ZVector< NodeIndexType > &head)
Definition: ebert_graph.h:521
bool operator()(ArcIndexType a, ArcIndexType b) const
Definition: ebert_graph.h:525
ArcIterator(const DerivedGraph &graph)
Definition: ebert_graph.h:345
ArcIndexType Index() const
Definition: ebert_graph.h:355
NodeIterator(const DerivedGraph &graph)
Definition: ebert_graph.h:322
NodeIndexType Index() const
Definition: ebert_graph.h:332
void Next()
Definition: ebert_graph.h:396
void operator=(const OutgoingArcIterator &iterator)
Definition: ebert_graph.h:386
bool Ok() const
Definition: ebert_graph.h:393
ArcIndexType Index() const
Definition: ebert_graph.h:402
OutgoingArcIterator(const DerivedGraph &graph, NodeIndexType node, ArcIndexType arc)
Definition: ebert_graph.h:377
OutgoingArcIterator(const DerivedGraph &graph, NodeIndexType node)
Definition: ebert_graph.h:368
static const NodeIndexType kNilNode
Definition: ebert_graph.h:216
ArcIndexType NextArc(const ArcIndexType arc) const
Definition: ebert_graph.h:472
NodeIndexType max_num_nodes() const
Definition: ebert_graph.h:255
bool IsNodeValid(NodeIndexType node) const
Definition: ebert_graph.h:279
ArcIndexType max_num_arcs_
Definition: ebert_graph.h:489
static const ArcIndexType kFirstArc
Definition: ebert_graph.h:225
ArcIndexType num_arcs() const
Definition: ebert_graph.h:241
NodeIndexType Head(const ArcIndexType arc) const
Definition: ebert_graph.h:297
ZVector< ArcIndexType > first_incident_arc_
Definition: ebert_graph.h:502
std::string ArcDebugString(const ArcIndexType arc) const
Definition: ebert_graph.h:310
static const ArcIndexType kMaxNumArcs
Definition: ebert_graph.h:235
NodeIndexType num_nodes() const
Definition: ebert_graph.h:237
ArcIndexType max_num_arcs() const
Definition: ebert_graph.h:259
std::string NodeDebugString(const NodeIndexType node) const
Definition: ebert_graph.h:302
ZVector< NodeIndexType > head_
Definition: ebert_graph.h:498
ArcIndexType end_arc_index() const
Definition: ebert_graph.h:252
static const ArcIndexType kNilArc
Definition: ebert_graph.h:219
ArcIndexType max_end_arc_index() const
Definition: ebert_graph.h:271
static const NodeIndexType kMaxNumNodes
Definition: ebert_graph.h:230
NodeIndexType max_num_nodes_
Definition: ebert_graph.h:486
NodeIndexType end_node_index() const
Definition: ebert_graph.h:247
NodeIndexType StartNode(NodeIndexType node) const
Definition: ebert_graph.h:439
ArcIndexType FirstOutgoingArc(const NodeIndexType node) const
Definition: ebert_graph.h:479
static const NodeIndexType kFirstNode
Definition: ebert_graph.h:222
NodeIndexType max_end_node_index() const
Definition: ebert_graph.h:264
NodeIndexType NextNode(const NodeIndexType node) const
Definition: ebert_graph.h:458
ArcIndexType StartArc(ArcIndexType arc) const
Definition: ebert_graph.h:445
ArcIndexType LookUpArc(const NodeIndexType tail, const NodeIndexType head) const
Definition: ebert_graph.h:285
bool BuildTailArrayFromAdjacencyListsIfForwardGraph() const
Definition: ebert_graph.h:1920
TailArrayManager(GraphType *g)
Definition: ebert_graph.h:1918
void ReleaseTailArrayIfForwardGraph() const
Definition: ebert_graph.h:1927
GraphType * Graph(PermutationCycleHandler< typename GraphType::ArcIndex > *client_cycle_handler)
Definition: ebert_graph.h:2042
bool Reserve(const typename GraphType::NodeIndex new_max_num_nodes, const typename GraphType::ArcIndex new_max_num_arcs)
Definition: ebert_graph.h:2031
GraphType::ArcIndex AddArc(const typename GraphType::NodeIndex tail, const typename GraphType::NodeIndex head)
Definition: ebert_graph.h:2036
GraphBuilderFromArcs(typename GraphType::NodeIndex max_num_nodes, typename GraphType::ArcIndex max_num_arcs, bool sort_arcs)
Definition: ebert_graph.h:2025
GraphType::ArcIndex AddArc(typename GraphType::NodeIndex tail, typename GraphType::NodeIndex head)
Definition: ebert_graph.h:1972
GraphType * Graph(PermutationCycleHandler< typename GraphType::ArcIndex > *client_cycle_handler)
Definition: ebert_graph.h:1991
GraphBuilderFromArcs(typename GraphType::NodeIndex max_num_nodes, typename GraphType::ArcIndex max_num_arcs, bool sort_arcs)
Definition: ebert_graph.h:1965
Definition: christofides.h:35
ZVector< FlowQuantity > QuantityArray
Definition: ebert_graph.h:209
bool BuildLineGraph(const GraphType &graph, GraphType *const line_graph)
Definition: ebert_graph.h:2088
ForwardStaticGraph< NodeIndex, ArcIndex > ForwardStarStaticGraph
Definition: ebert_graph.h:206
ForwardEbertGraph< NodeIndex, ArcIndex > ForwardStarGraph
Definition: ebert_graph.h:205
EbertGraph< NodeIndex, ArcIndex > StarGraph
Definition: ebert_graph.h:204
static constexpr bool has_reverse_arcs
Definition: ebert_graph.h:1849
static constexpr bool is_dynamic
Definition: ebert_graph.h:1850
bool BuildTailArray() const
Definition: ebert_graph.h:1885
GraphType *const graph_
Definition: ebert_graph.h:1887
TailArrayBuilder(GraphType *graph)
Definition: ebert_graph.h:1883
bool BuildTailArray() const
Definition: ebert_graph.h:1875
TailArrayBuilder(GraphType *unused_graph)
Definition: ebert_graph.h:1873
GraphType *const graph_
Definition: ebert_graph.h:1910
void ReleaseTailArray() const
Definition: ebert_graph.h:1908
TailArrayReleaser(GraphType *graph)
Definition: ebert_graph.h:1906
void ReleaseTailArray() const
Definition: ebert_graph.h:1898
TailArrayReleaser(GraphType *unused_graph)
Definition: ebert_graph.h:1896