14#ifndef OR_TOOLS_GRAPH_EBERT_GRAPH_H_
15#define OR_TOOLS_GRAPH_EBERT_GRAPH_H_
178#include "absl/strings/str_cat.h"
187template <
typename NodeIndexType,
typename ArcIndexType>
189template <
typename NodeIndexType,
typename ArcIndexType>
190class ForwardEbertGraph;
191template <
typename NodeIndexType,
typename ArcIndexType>
192class ForwardStaticGraph;
212template <
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_t
>(node));
314 return absl::StrCat(
static_cast<int64_t
>(
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_;
372 DCHECK(CheckInvariant());
382 DCHECK(CheckInvariant());
387 DCHECK(&iterator.graph_ == &graph_);
388 node_ = iterator.node_;
389 arc_ = iterator.arc_;
397 arc_ = graph_.NextOutgoingArc(node_, arc_);
398 DCHECK(CheckInvariant());
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;
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);
518template <
typename NodeIndexType,
typename ArcIndexType>
526 return head_[
a] < head_[
b];
533template <
typename NodeIndexType,
typename ArcIndexType>
536 ForwardStaticGraph<NodeIndexType, ArcIndexType> > {
579 annotation_handler_(annotation_handler) {}
592 ArcIndexType destination)
const override {
626 const bool sort_arcs_by_head,
627 std::vector<std::pair<NodeIndexType, NodeIndexType> >* client_input_arcs,
632 client_cycle_handler) {
638 std::vector<std::pair<NodeIndexType, NodeIndexType> >& input_arcs =
655 num_nodes_,
static_cast<NodeIndexType
>(input_arcs[
arc].first + 1));
657 num_nodes_,
static_cast<NodeIndexType
>(input_arcs[
arc].second + 1));
660 for (NodeIndexType node = 0; node <
num_nodes; ++node) {
667 std::unique_ptr<ArcIndexType[]> arc_permutation;
668 if (client_cycle_handler !=
nullptr) {
670 for (ArcIndexType input_arc = 0; input_arc <
num_arcs; ++input_arc) {
671 NodeIndexType
tail = input_arcs[input_arc].first;
672 NodeIndexType
head = input_arcs[input_arc].second;
685 for (ArcIndexType input_arc = 0; input_arc <
num_arcs; ++input_arc) {
686 NodeIndexType
tail = input_arcs[input_arc].first;
689 input_arcs[input_arc].first =
static_cast<NodeIndexType
>(
arc);
691 for (ArcIndexType input_arc = 0; input_arc <
num_arcs; ++input_arc) {
693 static_cast<ArcIndexType
>(input_arcs[input_arc].first);
694 NodeIndexType
head = input_arcs[input_arc].second;
700 for (ArcIndexType input_arc = 0; input_arc <
num_arcs; ++input_arc) {
701 NodeIndexType
tail = input_arcs[input_arc].first;
702 NodeIndexType
head = input_arcs[input_arc].second;
718 if (sort_arcs_by_head) {
720 if (client_cycle_handler !=
nullptr) {
721 for (NodeIndexType node = 0; node <
num_nodes; ++node) {
724 &arc_permutation[
begin], &arc_permutation[
end],
730 for (NodeIndexType node = 0; node <
num_nodes; ++node) {
738 ArcIndexType end_index = (
end > 0 ?
end - 1 :
end);
739 ArcIndexType end_offset = (
end > 0 ? 1 : 0);
740 std::sort(&
head_[begin_index] + begin_offset,
741 &
head_[end_index] + end_offset);
746 if (client_cycle_handler !=
nullptr &&
num_arcs > 0) {
759 NodeIndexType
Tail(
const ArcIndexType
arc)
const {
762 return (*tail_)[
arc];
788 (arc <= tail_->max_index()));
792 ArcIndexType
arc)
const {
806 std::string result =
"Arcs:(node) :\n";
811 result +=
"Node:First arc :\n";
823 if (tail_ ==
nullptr) {
824 if (!RepresentationClean()) {
834 typename Base::NodeIterator node_it(*
this);
835 for (; node_it.Ok(); node_it.Next()) {
836 NodeIndexType node = node_it.Index();
837 typename Base::OutgoingArcIterator arc_it(*
this, node);
838 for (; arc_it.Ok(); arc_it.Next()) {
839 (*tail_)[arc_it.Index()] = node;
860 bool IsDirect()
const {
return true; }
861 bool RepresentationClean()
const {
return true; }
862 bool IsOutgoing(
const NodeIndexType node,
863 const ArcIndexType unused_arc)
const {
868 ArcIndexType FirstOutgoingOrOppositeIncomingArc(NodeIndexType node)
const {
869 DCHECK(RepresentationClean());
876 ArcIndexType FindNextOutgoingArc(ArcIndexType
arc)
const {
896 std::unique_ptr<ZVector<NodeIndexType> > tail_;
900template <
typename NodeIndexType,
typename ArcIndexType,
typename DerivedGraph>
905template <
typename NodeIndexType,
typename ArcIndexType,
typename DerivedGraph>
908 std::numeric_limits<ArcIndexType>::min();
911template <
typename NodeIndexType,
typename ArcIndexType,
typename DerivedGraph>
916template <
typename NodeIndexType,
typename ArcIndexType,
typename DerivedGraph>
921template <
typename NodeIndexType,
typename ArcIndexType,
typename DerivedGraph>
924 std::numeric_limits<NodeIndexType>::max();
928template <
typename NodeIndexType,
typename ArcIndexType,
typename DerivedGraph>
931 std::numeric_limits<ArcIndexType>::max();
950template <
typename NodeIndexType,
typename ArcIndexType,
typename DerivedGraph>
952 :
public StarGraphBase<NodeIndexType, ArcIndexType, DerivedGraph> {
954 friend class StarGraphBase<NodeIndexType, ArcIndexType, DerivedGraph>;
981 bool Reserve(NodeIndexType new_max_num_nodes, ArcIndexType new_max_num_arcs) {
982 if (new_max_num_nodes < 0 || new_max_num_nodes >
kMaxNumNodes) {
985 if (new_max_num_arcs < 0 || new_max_num_arcs >
kMaxNumArcs) {
993 ThisAsDerived()->ReserveInternal(new_max_num_nodes, new_max_num_arcs);
1024 template <
typename ArcIndexTypeStrictWeakOrderingFunctor>
1026 const ArcIndexTypeStrictWeakOrderingFunctor& compare,
1028 std::unique_ptr<ArcIndexType[]> arc_permutation(
1034 arc_permutation[i] = i;
1047 ThisAsDerived()->BuildRepresentation();
1055 DerivedGraph* graph)
1056 : annotation_handler_(annotation_handler),
1067 if (annotation_handler_ !=
nullptr) {
1070 head_temp_ = graph_->Head(source);
1071 tail_temp_ = graph_->Tail(source);
1075 ArcIndexType destination)
const override {
1076 if (annotation_handler_ !=
nullptr) {
1079 graph_->SetHead(destination, graph_->Head(source));
1080 graph_->SetTail(destination, graph_->Tail(source));
1084 if (annotation_handler_ !=
nullptr) {
1087 graph_->SetHead(destination, head_temp_);
1088 graph_->SetTail(destination, tail_temp_);
1095 void SetSeen(ArcIndexType* permutation_element)
const override {
1096 *permutation_element =
kNilArc;
1099 bool Unseen(ArcIndexType permutation_element)
const override {
1100 return permutation_element !=
kNilArc;
1107 DerivedGraph* graph_;
1108 NodeIndexType head_temp_;
1109 NodeIndexType tail_temp_;
1120 LOG(DFATAL) <<
"Could not reserve memory for "
1130 const NodeIndexType node)
const {
1139 DCHECK(ThisAsDerived()->CheckArcValidity(
arc));
1145 const ArcIndexType
arc)
const {
1146 DCHECK(ThisAsDerived()->CheckArcValidity(
arc));
1147 DCHECK(ThisAsDerived()->IsDirect(
arc));
1163 inline const DerivedGraph* ThisAsDerived()
const {
1164 return static_cast<const DerivedGraph*
>(
this);
1169 inline DerivedGraph* ThisAsDerived() {
1170 return static_cast<DerivedGraph*
>(
this);
1183 void SetHead(
const ArcIndexType
arc,
const NodeIndexType
head) {
1191template <
typename NodeIndexType,
typename ArcIndexType>
1194 EbertGraph<NodeIndexType, ArcIndexType> > {
1251 DCHECK(CheckInvariant());
1257 NodeIndexType node, ArcIndexType
arc)
1261 DCHECK(CheckInvariant());
1266 DCHECK(&iterator.graph_ == &graph_);
1267 node_ = iterator.node_;
1268 arc_ = iterator.arc_;
1277 DCHECK(CheckInvariant());
1281 ArcIndexType
Index()
const {
return arc_; }
1286 bool CheckInvariant()
const {
1297 NodeIndexType node_;
1309 arc_(graph_.
StartArc(graph_.FirstIncomingArc(node))) {
1310 DCHECK(CheckInvariant());
1321 DCHECK(CheckInvariant());
1326 DCHECK(&iterator.graph_ == &graph_);
1327 node_ = iterator.node_;
1328 arc_ = iterator.arc_;
1336 arc_ = graph_.NextIncomingArc(arc_);
1337 DCHECK(CheckInvariant());
1348 bool CheckInvariant()
const {
1359 NodeIndexType node_;
1382 NodeIndexType
Tail(
const ArcIndexType
arc)
const {
1416 const ArcIndexType opposite = ~arc;
1436 NodeIndexType node)
const {
1466 std::string result =
"Arcs:(node, next arc) :\n";
1471 result +=
"Node:First arc :\n";
1487 void ReserveInternal(NodeIndexType new_max_num_nodes,
1488 ArcIndexType new_max_num_arcs) {
1489 head_.
Reserve(-new_max_num_arcs, new_max_num_arcs - 1);
1502 ArcIndexType FirstIncomingArc(
const NodeIndexType node)
const {
1509 ArcIndexType NextIncomingArc(
const ArcIndexType
arc)
const {
1517 void RecordArc(ArcIndexType
arc, NodeIndexType
tail, NodeIndexType
head) {
1526 void SetTail(
const ArcIndexType
arc,
const NodeIndexType
tail) {
1532 void Attach(ArcIndexType
arc) {
1545 ArcIndexType FindNextOutgoingArc(ArcIndexType
arc)
const {
1555 ArcIndexType FindNextIncomingArc(ArcIndexType
arc)
const {
1567template <
typename NodeIndexType,
typename ArcIndexType>
1570 ForwardEbertGraph<NodeIndexType, ArcIndexType> > {
1633 (arc <= tail_->max_index());
1637 NodeIndexType
Tail(
const ArcIndexType
arc)
const {
1640 return (*tail_)[
arc];
1657 Attach((*tail_)[
arc],
arc);
1666 if (tail_ ==
nullptr) {
1678 for (; node_it.
Ok(); node_it.
Next()) {
1679 NodeIndexType node = node_it.
Index();
1681 for (; arc_it.
Ok(); arc_it.
Next()) {
1682 (*tail_)[arc_it.
Index()] = node;
1706 std::string result =
"Arcs:(node, next arc) :\n";
1711 result +=
"Node:First arc :\n";
1728 void ReserveTailArray(ArcIndexType new_max_num_arcs) {
1729 if (tail_ !=
nullptr) {
1733 if (tail_->Reserve(
kFirstArc, new_max_num_arcs - 1)) {
1734 for (ArcIndexType
arc = tail_->max_index() + 1;
arc < new_max_num_arcs;
1765 void ReserveInternal(NodeIndexType new_max_num_nodes,
1766 ArcIndexType new_max_num_arcs) {
1773 ReserveTailArray(new_max_num_arcs);
1778 void RecordArc(ArcIndexType
arc, NodeIndexType
tail, NodeIndexType
head) {
1786 void SetTail(
const ArcIndexType
arc,
const NodeIndexType
tail) {
1794 void Attach(NodeIndexType
tail, ArcIndexType
arc) {
1803 if (tail_ !=
nullptr) {
1810 ArcIndexType FindNextOutgoingArc(ArcIndexType
arc)
const {
1819 bool IsOutgoing(
const ArcIndex unused_arc,
1827 bool IsDirect(
const ArcIndex unused_arc)
const {
return true; }
1844 std::unique_ptr<ZVector<NodeIndexType> > tail_;
1853template <
typename GraphType>
1859template <
typename NodeIndexType,
typename ArcIndexType>
1865template <
typename NodeIndexType,
typename ArcIndexType>
1871namespace or_internal {
1877template <
typename GraphType,
bool has_reverse_arcs>
1887template <
typename GraphType>
1900template <
typename GraphType,
bool has_reverse_arcs>
1910template <
typename GraphType>
1921template <
typename GraphType>
1929 tail_array_builder(graph_);
1930 return tail_array_builder.BuildTailArray();
1936 tail_array_releaser(graph_);
1937 tail_array_releaser.ReleaseTailArray();
1944template <
typename GraphType>
1951 typename GraphType::ArcIndex
b)
const {
1952 return ((graph_.Tail(
a) < graph_.Tail(
b)) ||
1953 ((graph_.Tail(
a) == graph_.Tail(
b)) &&
1954 (graph_.Head(
a) < graph_.Head(
b))));
1958 const GraphType& graph_;
1961namespace or_internal {
1968template <
typename GraphType,
bool is_dynamic>
1972 typename GraphType::ArcIndex max_num_arcs,
1974 : num_arcs_(0), sort_arcs_(sort_arcs) {
1975 Reserve(max_num_nodes, max_num_arcs);
1978 typename GraphType::ArcIndex
AddArc(
typename GraphType::NodeIndex
tail,
1979 typename GraphType::NodeIndex
head) {
1980 DCHECK_LT(num_arcs_, max_num_arcs_);
1981 DCHECK_LT(
tail, GraphType::kFirstNode + max_num_nodes_);
1982 DCHECK_LT(
head, GraphType::kFirstNode + max_num_nodes_);
1983 if (num_arcs_ < max_num_arcs_ &&
1984 tail < GraphType::kFirstNode + max_num_nodes_ &&
1985 head < GraphType::kFirstNode + max_num_nodes_) {
1986 typename GraphType::ArcIndex result = GraphType::kFirstArc + num_arcs_;
1987 arcs_.push_back(std::make_pair(
tail,
head));
1992 return GraphType::kNilArc;
1998 client_cycle_handler) {
1999 GraphType* graph =
new GraphType(max_num_nodes_, num_arcs_, sort_arcs_,
2000 &arcs_, client_cycle_handler);
2006 bool Reserve(
typename GraphType::NodeIndex new_max_num_nodes,
2007 typename GraphType::ArcIndex new_max_num_arcs) {
2008 max_num_nodes_ = new_max_num_nodes;
2009 max_num_arcs_ = new_max_num_arcs;
2010 arcs_.reserve(new_max_num_arcs);
2014 typename GraphType::NodeIndex max_num_nodes_;
2015 typename GraphType::ArcIndex max_num_arcs_;
2016 typename GraphType::ArcIndex num_arcs_;
2019 std::pair<typename GraphType::NodeIndex, typename GraphType::NodeIndex> >
2022 const bool sort_arcs_;
2028template <
typename GraphType>
2032 typename GraphType::ArcIndex max_num_arcs,
2034 : graph_(new GraphType(max_num_nodes, max_num_arcs)),
2035 sort_arcs_(sort_arcs) {}
2037 bool Reserve(
const typename GraphType::NodeIndex new_max_num_nodes,
2038 const typename GraphType::ArcIndex new_max_num_arcs) {
2039 return graph_->Reserve(new_max_num_nodes, new_max_num_arcs);
2043 const typename GraphType::NodeIndex
tail,
2044 const typename GraphType::NodeIndex
head) {
2049 client_cycle_handler) {
2054 graph_->GroupForwardArcsByFunctor(arc_ordering, client_cycle_handler);
2057 GraphType* result = graph_;
2063 GraphType*
const graph_;
2064 const bool sort_arcs_;
2069template <
typename GraphType>
2072 GraphType, graph_traits<GraphType>::is_dynamic> {
2075 typename GraphType::ArcIndex num_arcs,
2079 num_nodes, num_arcs, sort_arcs) {}
2093template <
typename GraphType>
2095 if (line_graph ==
nullptr) {
2096 LOG(DFATAL) <<
"line_graph must not be NULL";
2099 if (line_graph->num_nodes() != 0) {
2100 LOG(DFATAL) <<
"line_graph must be empty";
2103 typedef typename GraphType::ArcIterator ArcIterator;
2104 typedef typename GraphType::OutgoingArcIterator OutgoingArcIterator;
2106 typename GraphType::ArcIndex num_arcs = 0;
2107 for (ArcIterator arc_iterator(graph); arc_iterator.Ok();
2108 arc_iterator.Next()) {
2109 const typename GraphType::ArcIndex
arc = arc_iterator.Index();
2110 const typename GraphType::NodeIndex
head = graph.Head(
arc);
2111 for (OutgoingArcIterator iterator(graph,
head); iterator.Ok();
2116 line_graph->Reserve(graph.num_arcs(), num_arcs);
2117 for (ArcIterator arc_iterator(graph); arc_iterator.Ok();
2118 arc_iterator.Next()) {
2119 const typename GraphType::ArcIndex
arc = arc_iterator.Index();
2120 const typename GraphType::NodeIndex
head = graph.Head(
arc);
2121 for (OutgoingArcIterator iterator(graph,
head); iterator.Ok();
2123 line_graph->AddArc(
arc, iterator.Index());
AnnotatedGraphBuildManager(typename GraphType::NodeIndex num_nodes, typename GraphType::ArcIndex num_arcs, bool sort_arcs)
ArcFunctorOrderingByTailAndHead(const GraphType &graph)
bool operator()(typename GraphType::ArcIndex a, typename GraphType::ArcIndex b) const
void SetTempFromIndex(ArcIndexType source) override
void SetIndexFromTemp(ArcIndexType destination) const override
void SetIndexFromIndex(ArcIndexType source, ArcIndexType destination) const override
CycleHandlerForAnnotatedArcs & operator=(const CycleHandlerForAnnotatedArcs &)=delete
CycleHandlerForAnnotatedArcs(PermutationCycleHandler< ArcIndexType > *annotation_handler, DerivedGraph *graph)
void SetSeen(ArcIndexType *permutation_element) const override
CycleHandlerForAnnotatedArcs(const CycleHandlerForAnnotatedArcs &)=delete
This type is neither copyable nor movable.
void SetTempFromIndex(ArcIndexType source) override
void SetIndexFromTemp(ArcIndexType destination) const override
Sets a data element from the temporary.
void SetIndexFromIndex(ArcIndexType source, ArcIndexType destination) const override
Moves a data element one step along its cycle.
bool Unseen(ArcIndexType permutation_element) const override
~CycleHandlerForAnnotatedArcs() override
static const ArcIndexType kMaxNumArcs
ZVector< NodeIndexType > head_
Array of node indices. head_[i] contains the head node of arc i.
ZVector< ArcIndexType > next_adjacent_arc_
bool Reserve(NodeIndexType new_max_num_nodes, ArcIndexType new_max_num_arcs)
static const NodeIndexType kFirstNode
The index of the first node in the graph.
static const NodeIndexType kNilNode
The index of the 'nil' node in the graph.
static const ArcIndexType kFirstArc
The index of the first arc in the graph.
ArcIndexType NextOutgoingArc(const NodeIndexType unused_node, const ArcIndexType arc) const
Returns the outgoing arc following the argument in the adjacency list.
NodeIndexType max_num_nodes_
The maximum number of nodes that the graph can hold.
ArcIndexType end_arc_index() const
ArcIndexType FirstOutgoingOrOppositeIncomingArc(const NodeIndexType node) const
Returns the first arc in node's incidence list.
static const ArcIndexType kNilArc
The index of the 'nil' arc in the graph.
ArcIndexType num_arcs_
The current number of arcs held by the graph.
void GroupForwardArcsByFunctor(const ArcIndexTypeStrictWeakOrderingFunctor &compare, PermutationCycleHandler< ArcIndexType > *annotation_handler)
bool representation_clean_
ArcIndexType NextAdjacentArc(const ArcIndexType arc) const
Returns the next arc following the passed argument in its adjacency list.
ArcIndexType AddArc(NodeIndexType tail, NodeIndexType head)
ArcIndexType max_num_arcs_
The maximum number of arcs that the graph can hold.
bool IsNodeValid(NodeIndexType node) const
NodeIndexType num_nodes_
The maximum index of the node currently held by the graph.
static const NodeIndexType kMaxNumNodes
The maximum possible node index in the graph.
void Initialize(NodeIndexType max_num_nodes, ArcIndexType max_num_arcs)
ZVector< ArcIndexType > first_incident_arc_
Iterator class for traversing the incoming arcs associated to a given node.
void operator=(const IncomingArcIterator &iterator)
Can only assign from an iterator on the same graph.
IncomingArcIterator(const EbertGraph &graph, NodeIndexType node, ArcIndexType arc)
bool Ok() const
Returns true unless all the incoming arcs have been traversed.
ArcIndexType Index() const
Returns the index of the arc currently pointed to by the iterator.
IncomingArcIterator(const EbertGraph &graph, NodeIndexType node)
void Next()
Advances the current incoming arc index.
OutgoingOrOppositeIncomingArcIterator(const EbertGraph &graph, NodeIndexType node)
ArcIndexType Index() const
Returns the index of the arc currently pointed to by the iterator.
bool Ok() const
Returns true unless all the adjancent arcs have been traversed.
OutgoingOrOppositeIncomingArcIterator(const EbertGraph &graph, NodeIndexType node, ArcIndexType arc)
void Next()
Advances the current adjacent arc index.
void operator=(const OutgoingOrOppositeIncomingArcIterator &iterator)
Can only assign from an iterator on the same graph.
ArcIndexType Opposite(const ArcIndexType arc) const
NodeIndexType DirectArcHead(const ArcIndexType arc) const
bool IsOutgoingOrOppositeIncoming(ArcIndexType arc, NodeIndexType node) const
Returns true if arc is incident to node.
EbertGraph(NodeIndexType max_num_nodes, ArcIndexType max_num_arcs)
bool IsReverse(const ArcIndexType arc) const
Returns true if the arc is in the reverse direction.
bool CheckArcBounds(const ArcIndexType arc) const
NodeIndexType Tail(const ArcIndexType arc) const
Returns the tail or start-node of arc.
bool CheckArcValidity(const ArcIndexType arc) const
void BuildRepresentation()
ArcIndexType DirectArc(const ArcIndexType arc) const
Returns the arc in normal/direct direction.
NodeIndexType DirectArcTail(const ArcIndexType arc) const
bool IsDirect(const ArcIndexType arc) const
Returns true if the arc is direct.
bool IsIncoming(ArcIndexType arc, NodeIndexType node) const
Returns true if arc is incoming to node.
ArcIndexType ReverseArc(const ArcIndexType arc) const
Returns the arc in reverse direction.
bool IsOutgoing(ArcIndexType arc, NodeIndexType node) const
Returns true if arc is outgoing from node.
std::string DebugString() const
std::string DebugString() const
void BuildRepresentation()
bool IsIncoming(ArcIndexType arc, NodeIndexType node) const
Returns true if arc is incoming to node.
bool CheckArcValidity(const ArcIndexType arc) const
ForwardEbertGraph(NodeIndexType max_num_nodes, ArcIndexType max_num_arcs)
NodeIndexType Tail(const ArcIndexType arc) const
Returns the tail or start-node of arc.
bool CheckTailIndexValidity(const ArcIndexType arc) const
Returns true if arc is a valid index into the (*tail_) array.
bool TailArrayComplete() const
To be used in a DCHECK().
bool CheckArcBounds(const ArcIndexType arc) const
void SetTempFromIndex(ArcIndexType source) override
CycleHandlerForAnnotatedArcs(PermutationCycleHandler< ArcIndexType > *annotation_handler, NodeIndexType *data)
CycleHandlerForAnnotatedArcs & operator=(const CycleHandlerForAnnotatedArcs &)=delete
CycleHandlerForAnnotatedArcs(const CycleHandlerForAnnotatedArcs &)=delete
This type is neither copyable nor movable.
void SetIndexFromTemp(ArcIndexType destination) const override
void SetIndexFromIndex(ArcIndexType source, ArcIndexType destination) const override
bool CheckArcValidity(const 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)
bool CheckArcBounds(const ArcIndexType arc) const
bool CheckTailIndexValidity(const ArcIndexType arc) const
Returns true if arc is a valid index into the (*tail_) array.
bool TailArrayComplete() const
To be used in a DCHECK().
std::string DebugString() const
ArcIndexType NextOutgoingArc(const NodeIndexType node, ArcIndexType arc) const
NodeIndexType Tail(const ArcIndexType arc) const
Returns the tail or start-node of arc.
bool IsIncoming(ArcIndexType arc, NodeIndexType node) const
Returns true if arc is incoming to node.
void Apply(IndexType permutation[], int permutation_start, int permutation_end)
virtual void SetIndexFromTemp(IndexType destination) const =0
Sets a data element from the temporary.
virtual void SetTempFromIndex(IndexType source)=0
virtual void SetIndexFromIndex(IndexType source, IndexType destination) const =0
Moves a data element one step along its cycle.
bool operator()(ArcIndexType a, ArcIndexType b) const
PermutationIndexComparisonByArcHead(const ZVector< NodeIndexType > &head)
Iterator class for traversing the arcs in the graph.
void Next()
Advances the current arc index.
ArcIterator(const DerivedGraph &graph)
ArcIndexType Index() const
Returns the index of the arc currently pointed to by the iterator.
bool Ok() const
Returns true unless all the arcs have been traversed.
Iterator class for traversing all the nodes in the graph.
bool Ok() const
Returns true unless all the nodes have been traversed.
NodeIndexType Index() const
Returns the index of the node currently pointed to by the iterator.
void Next()
Advances the current node index.
NodeIterator(const DerivedGraph &graph)
Iterator class for traversing the outgoing arcs associated to a given node.
OutgoingArcIterator(const DerivedGraph &graph, NodeIndexType node)
void operator=(const OutgoingArcIterator &iterator)
Can only assign from an iterator on the same graph.
void Next()
Advances the current outgoing arc index.
OutgoingArcIterator(const DerivedGraph &graph, NodeIndexType node, ArcIndexType arc)
ArcIndexType Index() const
Returns the index of the arc currently pointed to by the iterator.
bool Ok() const
Returns true unless all the outgoing arcs have been traversed.
NodeIndexType end_node_index() const
static const ArcIndexType kMaxNumArcs
ZVector< NodeIndexType > head_
Array of node indices. head_[i] contains the head node of arc i.
static const NodeIndexType kFirstNode
The index of the first node in the graph.
static const NodeIndexType kNilNode
The index of the 'nil' node in the graph.
ArcIndexType NextArc(const ArcIndexType arc) const
std::string ArcDebugString(const ArcIndexType arc) const
static const ArcIndexType kFirstArc
The index of the first arc in the graph.
NodeIndexType max_num_nodes() const
Returns the maximum possible number of nodes in the graph.
NodeIndexType max_num_nodes_
The maximum number of nodes that the graph can hold.
std::string NodeDebugString(const NodeIndexType node) const
ArcIndexType end_arc_index() const
NodeIndexType max_end_node_index() const
static const ArcIndexType kNilArc
The index of the 'nil' arc in the graph.
ArcIndexType num_arcs_
The current number of arcs held by the graph.
NodeIndexType StartNode(NodeIndexType node) const
ArcIndexType max_end_arc_index() const
NodeIndexType NextNode(const NodeIndexType node) const
ArcIndexType max_num_arcs() const
ArcIndexType max_num_arcs_
The maximum number of arcs that the graph can hold.
ArcIndexType StartArc(ArcIndexType arc) const
NodeIndexType num_nodes() const
Returns the number of nodes in the graph.
NodeIndexType Head(const ArcIndexType arc) const
Returns the head or end-node of arc.
ArcIndexType num_arcs() const
ArcIndexType LookUpArc(const NodeIndexType tail, const NodeIndexType head) const
bool IsNodeValid(NodeIndexType node) const
NodeIndexType num_nodes_
The maximum index of the node currently held by the graph.
ArcIndexType FirstOutgoingArc(const NodeIndexType node) const
Returns the first outgoing arc for node.
static const NodeIndexType kMaxNumNodes
The maximum possible node index in the graph.
ZVector< ArcIndexType > first_incident_arc_
bool BuildTailArrayFromAdjacencyListsIfForwardGraph() const
void ReleaseTailArrayIfForwardGraph() const
TailArrayManager(GraphType *g)
bool Reserve(int64_t new_min_index, int64_t new_max_index)
void Set(int64_t index, T value)
Sets to value the content of the array at index.
int64_t max_index() const
void SetAll(T value)
Sets all the elements in the array to value.
GraphType * Graph(PermutationCycleHandler< typename GraphType::ArcIndex > *client_cycle_handler)
bool Reserve(const typename GraphType::NodeIndex new_max_num_nodes, const typename GraphType::ArcIndex new_max_num_arcs)
GraphBuilderFromArcs(typename GraphType::NodeIndex max_num_nodes, typename GraphType::ArcIndex max_num_arcs, bool sort_arcs)
GraphType::ArcIndex AddArc(const typename GraphType::NodeIndex tail, const typename GraphType::NodeIndex head)
GraphType * Graph(PermutationCycleHandler< typename GraphType::ArcIndex > *client_cycle_handler)
Builds the graph from the given arcs.
GraphBuilderFromArcs(typename GraphType::NodeIndex max_num_nodes, typename GraphType::ArcIndex max_num_arcs, bool sort_arcs)
GraphType::ArcIndex AddArc(typename GraphType::NodeIndex tail, typename GraphType::NodeIndex head)
In SWIG mode, we don't want anything besides these top-level includes.
ZVector< NodeIndex > NodeIndexArray
ForwardEbertGraph< NodeIndex, ArcIndex > ForwardStarGraph
ZVector< FlowQuantity > QuantityArray
ZVector< ArcIndex > ArcIndexArray
ForwardStaticGraph< NodeIndex, ArcIndex > ForwardStarStaticGraph
bool BuildLineGraph(const GraphType &graph, GraphType *const line_graph)
EbertGraph< NodeIndex, ArcIndex > StarGraph
ZVector< CostValue > CostArray
std::optional< int64_t > end
static constexpr bool has_reverse_arcs
static constexpr bool is_dynamic
TailArrayBuilder(GraphType *graph)
bool BuildTailArray() const
TailArrayBuilder(GraphType *unused_graph)
bool BuildTailArray() const
TailArrayReleaser(GraphType *graph)
void ReleaseTailArray() const
void ReleaseTailArray() const
TailArrayReleaser(GraphType *unused_graph)