14 #ifndef OR_TOOLS_GRAPH_EBERT_GRAPH_H_
15 #define OR_TOOLS_GRAPH_EBERT_GRAPH_H_
177 #include "absl/strings/str_cat.h"
187 template <
typename NodeIndexType,
typename ArcIndexType>
189 template <
typename NodeIndexType,
typename ArcIndexType>
190 class ForwardEbertGraph;
191 template <
typename NodeIndexType,
typename ArcIndexType>
192 class ForwardStaticGraph;
212 template <
typename NodeIndexType,
typename ArcIndexType,
typename DerivedGraph>
286 const NodeIndexType
head)
const {
288 arc = ThisAsDerived()->NextOutgoingArc(
tail, arc)) {
297 NodeIndexType
Head(
const ArcIndexType arc)
const {
298 DCHECK(ThisAsDerived()->CheckArcValidity(arc));
306 return absl::StrCat(
static_cast<int64>(node));
314 return absl::StrCat(
static_cast<int64>(arc));
329 void Next() { head_ = graph_.NextNode(head_); }
332 NodeIndexType
Index()
const {
return head_; }
336 const DerivedGraph& graph_;
352 void Next() { arc_ = graph_.NextArc(arc_); }
355 ArcIndexType
Index()
const {
return arc_; }
359 const DerivedGraph& graph_;
387 DCHECK(&iterator.graph_ == &graph_);
388 node_ = iterator.node_;
389 arc_ = iterator.arc_;
397 arc_ = graph_.NextOutgoingArc(node_, arc_);
402 ArcIndexType
Index()
const {
return arc_; }
407 bool CheckInvariant()
const {
411 DCHECK(graph_.IsOutgoing(arc_, node_));
416 const DerivedGraph& graph_;
458 NodeIndexType
NextNode(
const NodeIndexType node)
const {
460 const NodeIndexType next_node = node + 1;
472 ArcIndexType
NextArc(
const ArcIndexType arc)
const {
473 DCHECK(ThisAsDerived()->CheckArcValidity(arc));
474 const ArcIndexType next_arc = arc + 1;
481 return ThisAsDerived()->FindNextOutgoingArc(
482 ThisAsDerived()->FirstOutgoingOrOppositeIncomingArc(node));
507 inline const DerivedGraph* ThisAsDerived()
const {
508 return static_cast<const DerivedGraph*
>(
this);
513 inline DerivedGraph* ThisAsDerived() {
514 return static_cast<DerivedGraph*
>(
this);
518 template <
typename NodeIndexType,
typename ArcIndexType>
526 return head_[
a] < head_[
b];
533 template <
typename NodeIndexType,
typename ArcIndexType>
536 ForwardStaticGraph<NodeIndexType, ArcIndexType> > {
579 annotation_handler_(annotation_handler) {}
587 ArcIndexType destination)
const override {
623 const bool sort_arcs_by_head,
624 std::vector<std::pair<NodeIndexType, NodeIndexType> >* client_input_arcs,
629 client_cycle_handler) {
635 std::vector<std::pair<NodeIndexType, NodeIndexType> >& input_arcs =
652 num_nodes_,
static_cast<NodeIndexType
>(input_arcs[arc].first + 1));
654 num_nodes_,
static_cast<NodeIndexType
>(input_arcs[arc].second + 1));
657 for (NodeIndexType node = 0; node <
num_nodes; ++node) {
664 std::unique_ptr<ArcIndexType[]> arc_permutation;
665 if (client_cycle_handler !=
nullptr) {
667 for (ArcIndexType input_arc = 0; input_arc <
num_arcs; ++input_arc) {
668 NodeIndexType
tail = input_arcs[input_arc].first;
669 NodeIndexType
head = input_arcs[input_arc].second;
674 arc_permutation[
kFirstArc + arc] = input_arc;
682 for (ArcIndexType input_arc = 0; input_arc <
num_arcs; ++input_arc) {
683 NodeIndexType
tail = input_arcs[input_arc].first;
686 input_arcs[input_arc].first =
static_cast<NodeIndexType
>(arc);
688 for (ArcIndexType input_arc = 0; input_arc <
num_arcs; ++input_arc) {
690 static_cast<ArcIndexType
>(input_arcs[input_arc].first);
691 NodeIndexType
head = input_arcs[input_arc].second;
697 for (ArcIndexType input_arc = 0; input_arc <
num_arcs; ++input_arc) {
698 NodeIndexType
tail = input_arcs[input_arc].first;
699 NodeIndexType
head = input_arcs[input_arc].second;
715 if (sort_arcs_by_head) {
717 if (client_cycle_handler !=
nullptr) {
718 for (NodeIndexType node = 0; node <
num_nodes; ++node) {
721 &arc_permutation[begin], &arc_permutation[end],
727 for (NodeIndexType node = 0; node <
num_nodes; ++node) {
733 ArcIndexType begin_index = (begin <
num_arcs ? begin : begin - 1);
734 ArcIndexType begin_offset = (begin <
num_arcs ? 0 : 1);
735 ArcIndexType end_index = (end > 0 ? end - 1 : end);
736 ArcIndexType end_offset = (end > 0 ? 1 : 0);
737 std::sort(&
head_[begin_index] + begin_offset,
738 &
head_[end_index] + end_offset);
743 if (client_cycle_handler !=
nullptr &&
num_arcs > 0) {
756 NodeIndexType
Tail(
const ArcIndexType arc)
const {
759 return (*tail_)[arc];
763 bool IsIncoming(ArcIndexType arc, NodeIndexType node)
const {
764 return Head(arc) == node;
784 return ((tail_ !=
nullptr) && (arc >=
kFirstArc) &&
785 (arc <= tail_->max_index()));
789 ArcIndexType arc)
const {
803 std::string result =
"Arcs:(node) :\n";
808 result +=
"Node:First arc :\n";
820 if (tail_ ==
nullptr) {
821 if (!RepresentationClean()) {
831 typename Base::NodeIterator node_it(*
this);
832 for (; node_it.Ok(); node_it.Next()) {
833 NodeIndexType node = node_it.Index();
834 typename Base::OutgoingArcIterator arc_it(*
this, node);
835 for (; arc_it.Ok(); arc_it.Next()) {
836 (*tail_)[arc_it.Index()] = node;
857 bool IsDirect()
const {
return true; }
858 bool RepresentationClean()
const {
return true; }
859 bool IsOutgoing(
const NodeIndexType node,
860 const ArcIndexType unused_arc)
const {
865 ArcIndexType FirstOutgoingOrOppositeIncomingArc(NodeIndexType node)
const {
866 DCHECK(RepresentationClean());
873 ArcIndexType FindNextOutgoingArc(ArcIndexType arc)
const {
893 std::unique_ptr<ZVector<NodeIndexType> > tail_;
897 template <
typename NodeIndexType,
typename ArcIndexType,
typename DerivedGraph>
902 template <
typename NodeIndexType,
typename ArcIndexType,
typename DerivedGraph>
908 template <
typename NodeIndexType,
typename ArcIndexType,
typename DerivedGraph>
913 template <
typename NodeIndexType,
typename ArcIndexType,
typename DerivedGraph>
918 template <
typename NodeIndexType,
typename ArcIndexType,
typename DerivedGraph>
925 template <
typename NodeIndexType,
typename ArcIndexType,
typename DerivedGraph>
947 template <
typename NodeIndexType,
typename ArcIndexType,
typename DerivedGraph>
949 :
public StarGraphBase<NodeIndexType, ArcIndexType, DerivedGraph> {
951 friend class StarGraphBase<NodeIndexType, ArcIndexType, DerivedGraph>;
978 bool Reserve(NodeIndexType new_max_num_nodes, ArcIndexType new_max_num_arcs) {
979 if (new_max_num_nodes < 0 || new_max_num_nodes >
kMaxNumNodes) {
982 if (new_max_num_arcs < 0 || new_max_num_arcs >
kMaxNumArcs) {
990 ThisAsDerived()->ReserveInternal(new_max_num_nodes, new_max_num_arcs);
1014 ThisAsDerived()->RecordArc(arc,
tail,
head);
1021 template <
typename ArcIndexTypeStrictWeakOrderingFunctor>
1023 const ArcIndexTypeStrictWeakOrderingFunctor& compare,
1025 std::unique_ptr<ArcIndexType[]> arc_permutation(
1031 arc_permutation[i] = i;
1044 ThisAsDerived()->BuildRepresentation();
1052 DerivedGraph* graph)
1053 : annotation_handler_(annotation_handler),
1059 if (annotation_handler_ !=
nullptr) {
1062 head_temp_ = graph_->Head(source);
1063 tail_temp_ = graph_->Tail(source);
1067 ArcIndexType destination)
const override {
1068 if (annotation_handler_ !=
nullptr) {
1071 graph_->SetHead(destination, graph_->Head(source));
1072 graph_->SetTail(destination, graph_->Tail(source));
1076 if (annotation_handler_ !=
nullptr) {
1079 graph_->SetHead(destination, head_temp_);
1080 graph_->SetTail(destination, tail_temp_);
1087 void SetSeen(ArcIndexType* permutation_element)
const override {
1088 *permutation_element =
kNilArc;
1091 bool Unseen(ArcIndexType permutation_element)
const override {
1092 return permutation_element !=
kNilArc;
1099 DerivedGraph* graph_;
1100 NodeIndexType head_temp_;
1101 NodeIndexType tail_temp_;
1114 LOG(DFATAL) <<
"Could not reserve memory for "
1124 const NodeIndexType node)
const {
1133 DCHECK(ThisAsDerived()->CheckArcValidity(arc));
1139 const ArcIndexType arc)
const {
1140 DCHECK(ThisAsDerived()->CheckArcValidity(arc));
1141 DCHECK(ThisAsDerived()->IsDirect(arc));
1157 inline const DerivedGraph* ThisAsDerived()
const {
1158 return static_cast<const DerivedGraph*
>(
this);
1163 inline DerivedGraph* ThisAsDerived() {
1164 return static_cast<DerivedGraph*
>(
this);
1177 void SetHead(
const ArcIndexType arc,
const NodeIndexType
head) {
1185 template <
typename NodeIndexType,
typename ArcIndexType>
1188 EbertGraph<NodeIndexType, ArcIndexType> > {
1245 DCHECK(CheckInvariant());
1251 NodeIndexType node, ArcIndexType arc)
1255 DCHECK(CheckInvariant());
1260 DCHECK(&iterator.graph_ == &graph_);
1261 node_ = iterator.node_;
1262 arc_ = iterator.arc_;
1271 DCHECK(CheckInvariant());
1275 ArcIndexType
Index()
const {
return arc_; }
1280 bool CheckInvariant()
const {
1291 NodeIndexType node_;
1303 arc_(graph_.
StartArc(graph_.FirstIncomingArc(node))) {
1304 DCHECK(CheckInvariant());
1315 DCHECK(CheckInvariant());
1320 DCHECK(&iterator.graph_ == &graph_);
1321 node_ = iterator.node_;
1322 arc_ = iterator.arc_;
1330 arc_ = graph_.NextIncomingArc(arc_);
1331 DCHECK(CheckInvariant());
1342 bool CheckInvariant()
const {
1353 NodeIndexType node_;
1376 NodeIndexType
Tail(
const ArcIndexType arc)
const {
1410 const ArcIndexType opposite = ~arc;
1419 return arc !=
kNilArc && arc >= 0;
1425 return arc !=
kNilArc && arc < 0;
1430 NodeIndexType node)
const {
1431 return Tail(arc) == node;
1460 std::string result =
"Arcs:(node, next arc) :\n";
1465 result +=
"Node:First arc :\n";
1481 void ReserveInternal(NodeIndexType new_max_num_nodes,
1482 ArcIndexType new_max_num_arcs) {
1483 head_.
Reserve(-new_max_num_arcs, new_max_num_arcs - 1);
1485 for (ArcIndexType arc = -new_max_num_arcs; arc < -
max_num_arcs_; ++arc) {
1489 for (ArcIndexType arc =
max_num_arcs_; arc < new_max_num_arcs; ++arc) {
1496 ArcIndexType FirstIncomingArc(
const NodeIndexType node)
const {
1503 ArcIndexType NextIncomingArc(
const ArcIndexType arc)
const {
1511 void RecordArc(ArcIndexType arc, NodeIndexType
tail, NodeIndexType
head) {
1520 void SetTail(
const ArcIndexType arc,
const NodeIndexType
tail) {
1526 void Attach(ArcIndexType arc) {
1539 ArcIndexType FindNextOutgoingArc(ArcIndexType arc)
const {
1549 ArcIndexType FindNextIncomingArc(ArcIndexType arc)
const {
1561 template <
typename NodeIndexType,
typename ArcIndexType>
1564 ForwardEbertGraph<NodeIndexType, ArcIndexType> > {
1626 return (tail_ !=
nullptr) && (arc >=
kFirstArc) &&
1627 (arc <= tail_->max_index());
1631 NodeIndexType
Tail(
const ArcIndexType arc)
const {
1634 return (*tail_)[arc];
1639 return IsDirect(arc) &&
Head(arc) == node;
1651 Attach((*tail_)[arc], arc);
1660 if (tail_ ==
nullptr) {
1671 typename Base::NodeIterator node_it(*
this);
1672 for (; node_it.Ok(); node_it.Next()) {
1673 NodeIndexType node = node_it.Index();
1674 typename Base::OutgoingArcIterator arc_it(*
this, node);
1675 for (; arc_it.Ok(); arc_it.Next()) {
1676 (*tail_)[arc_it.Index()] = node;
1700 std::string result =
"Arcs:(node, next arc) :\n";
1705 result +=
"Node:First arc :\n";
1722 void ReserveTailArray(ArcIndexType new_max_num_arcs) {
1723 if (tail_ !=
nullptr) {
1727 if (tail_->Reserve(
kFirstArc, new_max_num_arcs - 1)) {
1728 for (ArcIndexType arc = tail_->max_index() + 1; arc < new_max_num_arcs;
1759 void ReserveInternal(NodeIndexType new_max_num_nodes,
1760 ArcIndexType new_max_num_arcs) {
1763 for (ArcIndexType arc =
max_num_arcs_; arc < new_max_num_arcs; ++arc) {
1767 ReserveTailArray(new_max_num_arcs);
1772 void RecordArc(ArcIndexType arc, NodeIndexType
tail, NodeIndexType
head) {
1780 void SetTail(
const ArcIndexType arc,
const NodeIndexType
tail) {
1784 tail_->Set(arc,
tail);
1788 void Attach(NodeIndexType
tail, ArcIndexType arc) {
1797 if (tail_ !=
nullptr) {
1799 tail_->Set(arc,
tail);
1804 ArcIndexType FindNextOutgoingArc(ArcIndexType arc)
const {
1813 bool IsOutgoing(
const ArcIndex unused_arc,
1821 bool IsDirect(
const ArcIndex unused_arc)
const {
return true; }
1838 std::unique_ptr<ZVector<NodeIndexType> > tail_;
1847 template <
typename GraphType>
1853 template <
typename NodeIndexType,
typename ArcIndexType>
1859 template <
typename NodeIndexType,
typename ArcIndexType>
1865 namespace or_internal {
1871 template <
typename GraphType,
bool has_reverse_arcs>
1881 template <
typename GraphType>
1894 template <
typename GraphType,
bool has_reverse_arcs>
1904 template <
typename GraphType>
1915 template <
typename GraphType>
1923 tail_array_builder(graph_);
1924 return tail_array_builder.BuildTailArray();
1930 tail_array_releaser(graph_);
1931 tail_array_releaser.ReleaseTailArray();
1938 template <
typename GraphType>
1946 return ((graph_.Tail(
a) < graph_.Tail(
b)) ||
1947 ((graph_.Tail(
a) == graph_.Tail(
b)) &&
1948 (graph_.Head(
a) < graph_.Head(
b))));
1952 const GraphType& graph_;
1955 namespace or_internal {
1962 template <
typename GraphType,
bool is_dynamic>
1968 : num_arcs_(0), sort_arcs_(sort_arcs) {
1969 Reserve(max_num_nodes, max_num_arcs);
1977 if (num_arcs_ < max_num_arcs_ &&
1978 tail < GraphType::kFirstNode + max_num_nodes_ &&
1979 head < GraphType::kFirstNode + max_num_nodes_) {
1981 arcs_.push_back(std::make_pair(
tail,
head));
1986 return GraphType::kNilArc;
1992 client_cycle_handler) {
1993 GraphType* graph =
new GraphType(max_num_nodes_, num_arcs_, sort_arcs_,
1994 &arcs_, client_cycle_handler);
2002 max_num_nodes_ = new_max_num_nodes;
2003 max_num_arcs_ = new_max_num_arcs;
2004 arcs_.reserve(new_max_num_arcs);
2013 std::pair<typename GraphType::NodeIndex, typename GraphType::NodeIndex> >
2016 const bool sort_arcs_;
2022 template <
typename GraphType>
2028 : graph_(new GraphType(max_num_nodes, max_num_arcs)),
2029 sort_arcs_(sort_arcs) {}
2033 return graph_->Reserve(new_max_num_nodes, new_max_num_arcs);
2043 client_cycle_handler) {
2048 graph_->GroupForwardArcsByFunctor(arc_ordering, client_cycle_handler);
2051 GraphType* result = graph_;
2057 GraphType*
const graph_;
2058 const bool sort_arcs_;
2063 template <
typename GraphType>
2066 GraphType, graph_traits<GraphType>::is_dynamic> {
2073 num_nodes, num_arcs, sort_arcs) {}
2087 template <
typename GraphType>
2089 if (line_graph ==
nullptr) {
2090 LOG(DFATAL) <<
"line_graph must not be NULL";
2093 if (line_graph->num_nodes() != 0) {
2094 LOG(DFATAL) <<
"line_graph must be empty";
2097 typedef typename GraphType::ArcIterator ArcIterator;
2098 typedef typename GraphType::OutgoingArcIterator OutgoingArcIterator;
2101 for (ArcIterator arc_iterator(graph); arc_iterator.Ok();
2102 arc_iterator.Next()) {
2105 for (OutgoingArcIterator iterator(graph,
head); iterator.Ok();
2110 line_graph->Reserve(graph.num_arcs(), num_arcs);
2111 for (ArcIterator arc_iterator(graph); arc_iterator.Ok();
2112 arc_iterator.Next()) {
2115 for (OutgoingArcIterator iterator(graph,
head); iterator.Ok();
2117 line_graph->AddArc(arc, iterator.Index());
#define DCHECK_LE(val1, val2)
#define DCHECK_GE(val1, val2)
#define DCHECK_LT(val1, val2)
#define DCHECK(condition)
#define DCHECK_EQ(val1, val2)
AnnotatedGraphBuildManager(typename GraphType::NodeIndex num_nodes, typename GraphType::ArcIndex num_arcs, bool sort_arcs)
bool operator()(typename GraphType::ArcIndex a, typename GraphType::ArcIndex b) const
ArcFunctorOrderingByTailAndHead(const GraphType &graph)
void SetIndexFromIndex(ArcIndexType source, ArcIndexType destination) const override
void SetIndexFromTemp(ArcIndexType destination) const override
void SetTempFromIndex(ArcIndexType source) override
void operator=(const IncomingArcIterator &iterator)
IncomingArcIterator(const EbertGraph &graph, NodeIndexType node, ArcIndexType arc)
IncomingArcIterator(const EbertGraph &graph, NodeIndexType node)
ArcIndexType Index() const
OutgoingOrOppositeIncomingArcIterator(const EbertGraph &graph, NodeIndexType node, ArcIndexType arc)
OutgoingOrOppositeIncomingArcIterator(const EbertGraph &graph, NodeIndexType node)
ArcIndexType Index() const
void operator=(const OutgoingOrOppositeIncomingArcIterator &iterator)
~CycleHandlerForAnnotatedArcs() override
void SetIndexFromIndex(ArcIndexType source, ArcIndexType destination) const override
bool Unseen(ArcIndexType permutation_element) const override
CycleHandlerForAnnotatedArcs(PermutationCycleHandler< ArcIndexType > *annotation_handler, DerivedGraph *graph)
void SetTempFromIndex(ArcIndexType source) override
void SetIndexFromTemp(ArcIndexType destination) const override
void SetSeen(ArcIndexType *permutation_element) const override
static const NodeIndexType kNilNode
ZVector< ArcIndexType > next_adjacent_arc_
bool IsNodeValid(NodeIndexType node) const
ArcIndexType max_num_arcs_
static const ArcIndexType kFirstArc
ArcIndexType NextOutgoingArc(const NodeIndexType unused_node, const ArcIndexType arc) const
ZVector< ArcIndexType > first_incident_arc_
static const ArcIndexType kMaxNumArcs
bool Reserve(NodeIndexType new_max_num_nodes, ArcIndexType new_max_num_arcs)
bool representation_clean_
ArcIndexType AddArc(NodeIndexType tail, NodeIndexType head)
ZVector< NodeIndexType > head_
ArcIndexType end_arc_index() const
void Initialize(NodeIndexType max_num_nodes, ArcIndexType max_num_arcs)
ArcIndexType FirstOutgoingOrOppositeIncomingArc(const NodeIndexType node) const
void GroupForwardArcsByFunctor(const ArcIndexTypeStrictWeakOrderingFunctor &compare, PermutationCycleHandler< ArcIndexType > *annotation_handler)
static const ArcIndexType kNilArc
static const NodeIndexType kMaxNumNodes
NodeIndexType max_num_nodes_
static const NodeIndexType kFirstNode
ArcIndexType NextAdjacentArc(const ArcIndexType arc) const
bool IsOutgoingOrOppositeIncoming(ArcIndexType arc, NodeIndexType node) const
bool IsDirect(const ArcIndexType arc) const
void BuildRepresentation()
bool IsIncoming(ArcIndexType arc, NodeIndexType node) const
NodeIndexType DirectArcHead(const ArcIndexType arc) const
bool CheckArcValidity(const ArcIndexType arc) const
ArcIndexType Opposite(const ArcIndexType arc) const
bool IsOutgoing(ArcIndexType arc, NodeIndexType node) const
std::string DebugString() const
bool IsReverse(const ArcIndexType arc) const
ArcIndexType ReverseArc(const ArcIndexType arc) const
ArcIndexType DirectArc(const ArcIndexType arc) const
NodeIndexType Tail(const ArcIndexType arc) const
EbertGraph(NodeIndexType max_num_nodes, ArcIndexType max_num_arcs)
bool CheckArcBounds(const ArcIndexType arc) const
NodeIndexType DirectArcTail(const ArcIndexType arc) const
ForwardEbertGraph(NodeIndexType max_num_nodes, ArcIndexType max_num_arcs)
void BuildRepresentation()
bool IsIncoming(ArcIndexType arc, NodeIndexType node) const
bool CheckArcValidity(const ArcIndexType arc) const
bool CheckTailIndexValidity(const ArcIndexType arc) const
std::string DebugString() const
NodeIndexType Tail(const ArcIndexType arc) const
bool CheckArcBounds(const ArcIndexType arc) const
bool TailArrayComplete() const
void SetIndexFromIndex(ArcIndexType source, ArcIndexType destination) const override
CycleHandlerForAnnotatedArcs(PermutationCycleHandler< ArcIndexType > *annotation_handler, NodeIndexType *data)
void SetTempFromIndex(ArcIndexType source) override
void SetIndexFromTemp(ArcIndexType destination) const override
bool IsIncoming(ArcIndexType arc, NodeIndexType node) const
bool CheckArcValidity(const ArcIndexType arc) const
bool CheckTailIndexValidity(const ArcIndexType arc) const
ArcIndexType NextOutgoingArc(const NodeIndexType node, ArcIndexType arc) const
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)
std::string DebugString() const
NodeIndexType Tail(const ArcIndexType arc) const
bool CheckArcBounds(const ArcIndexType arc) const
bool TailArrayComplete() const
void Apply(IndexType permutation[], int permutation_start, int permutation_end)
virtual void SetIndexFromTemp(IndexType destination) const =0
virtual void SetTempFromIndex(IndexType source)=0
virtual void SetIndexFromIndex(IndexType source, IndexType destination) const =0
PermutationIndexComparisonByArcHead(const ZVector< NodeIndexType > &head)
bool operator()(ArcIndexType a, ArcIndexType b) const
ArcIterator(const DerivedGraph &graph)
ArcIndexType Index() const
NodeIterator(const DerivedGraph &graph)
NodeIndexType Index() const
void operator=(const OutgoingArcIterator &iterator)
ArcIndexType Index() const
OutgoingArcIterator(const DerivedGraph &graph, NodeIndexType node, ArcIndexType arc)
OutgoingArcIterator(const DerivedGraph &graph, NodeIndexType node)
static const NodeIndexType kNilNode
ArcIndexType NextArc(const ArcIndexType arc) const
NodeIndexType max_num_nodes() const
bool IsNodeValid(NodeIndexType node) const
ArcIndexType max_num_arcs_
static const ArcIndexType kFirstArc
ArcIndexType num_arcs() const
NodeIndexType Head(const ArcIndexType arc) const
ZVector< ArcIndexType > first_incident_arc_
std::string ArcDebugString(const ArcIndexType arc) const
static const ArcIndexType kMaxNumArcs
NodeIndexType num_nodes() const
ArcIndexType max_num_arcs() const
std::string NodeDebugString(const NodeIndexType node) const
ZVector< NodeIndexType > head_
ArcIndexType end_arc_index() const
static const ArcIndexType kNilArc
ArcIndexType max_end_arc_index() const
static const NodeIndexType kMaxNumNodes
NodeIndexType max_num_nodes_
NodeIndexType end_node_index() const
NodeIndexType StartNode(NodeIndexType node) const
ArcIndexType FirstOutgoingArc(const NodeIndexType node) const
static const NodeIndexType kFirstNode
NodeIndexType max_end_node_index() const
NodeIndexType NextNode(const NodeIndexType node) const
ArcIndexType StartArc(ArcIndexType arc) const
ArcIndexType LookUpArc(const NodeIndexType tail, const NodeIndexType head) const
bool BuildTailArrayFromAdjacencyListsIfForwardGraph() const
TailArrayManager(GraphType *g)
void ReleaseTailArrayIfForwardGraph() const
void Set(int64 index, T value)
bool Reserve(int64 new_min_index, int64 new_max_index)
bool Reserve(const typename GraphType::NodeIndex new_max_num_nodes, const typename GraphType::ArcIndex new_max_num_arcs)
GraphType::ArcIndex AddArc(const typename GraphType::NodeIndex tail, const typename GraphType::NodeIndex head)
GraphBuilderFromArcs(typename GraphType::NodeIndex max_num_nodes, typename GraphType::ArcIndex max_num_arcs, bool sort_arcs)
GraphType * Graph(PermutationCycleHandler< typename GraphType::ArcIndex > *client_cycle_handler)
GraphType::ArcIndex AddArc(typename GraphType::NodeIndex tail, typename GraphType::NodeIndex head)
GraphBuilderFromArcs(typename GraphType::NodeIndex max_num_nodes, typename GraphType::ArcIndex max_num_arcs, bool sort_arcs)
GraphType * Graph(PermutationCycleHandler< typename GraphType::ArcIndex > *client_cycle_handler)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
ZVector< FlowQuantity > QuantityArray
ZVector< NodeIndex > NodeIndexArray
ForwardStaticGraph< NodeIndex, ArcIndex > ForwardStarStaticGraph
ForwardEbertGraph< NodeIndex, ArcIndex > ForwardStarGraph
bool BuildLineGraph(const GraphType &graph, GraphType *const line_graph)
ZVector< CostValue > CostArray
ZVector< ArcIndex > ArcIndexArray
EbertGraph< NodeIndex, ArcIndex > StarGraph
static constexpr bool has_reverse_arcs
static constexpr bool is_dynamic
bool BuildTailArray() const
TailArrayBuilder(GraphType *graph)
bool BuildTailArray() const
TailArrayBuilder(GraphType *unused_graph)
void ReleaseTailArray() const
TailArrayReleaser(GraphType *graph)
void ReleaseTailArray() const
TailArrayReleaser(GraphType *unused_graph)