Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
util::ReverseArcStaticGraph< NodeIndexType, ArcIndexType > Class Template Reference

Detailed Description

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t>
class util::ReverseArcStaticGraph< NodeIndexType, ArcIndexType >

StaticGraph with reverse arc.

  • NodeIndexType can be unsigned, but ArcIndexType must be signed.
  • It has most of the same advantanges and disadvantages as StaticGraph.
  • It takes 2 * ArcIndexType * node_capacity()
  • If the ArcIndexPermutation is needed, then an extra ArcIndexType * arc_capacity() is needed for it.
  • The reverse arcs from a node are sorted by head (so we could add a log() time lookup function).

Definition at line 973 of file graph.h.

#include <graph.h>

Inheritance diagram for util::ReverseArcStaticGraph< NodeIndexType, ArcIndexType >:
util::BaseGraph< int32_t, int32_t, true >

Classes

class  OutgoingOrOppositeIncomingArcIterator

Public Types

using OppositeIncomingArcIterator = IntegerRangeIterator<ArcIndexType>
using IncomingArcIterator
using OutgoingArcIterator = IntegerRangeIterator<ArcIndexType>
Public Types inherited from util::BaseGraph< int32_t, int32_t, true >
typedef int32_t NodeIndex
typedef int32_t ArcIndex

Public Member Functions

 ReverseArcStaticGraph ()
 ReverseArcStaticGraph (NodeIndexType num_nodes, ArcIndexType arc_capacity)
ArcIndexType OppositeArc (ArcIndexType arc) const
NodeIndexType Head (ArcIndexType arc) const
NodeIndexType Tail (ArcIndexType arc) const
ArcIndexType OutDegree (NodeIndexType node) const
 ReverseArcStaticGraph<>::OutDegree() and InDegree() work in O(1).
ArcIndexType InDegree (NodeIndexType node) const
IntegerRange< ArcIndexType > OutgoingArcs (NodeIndexType node) const
IntegerRange< ArcIndexType > OutgoingArcsStartingFrom (NodeIndexType node, ArcIndexType from) const
IntegerRange< ArcIndexType > OppositeIncomingArcs (NodeIndexType node) const
IntegerRange< ArcIndexType > OppositeIncomingArcsStartingFrom (NodeIndexType node, ArcIndexType from) const
BeginEndWrapper< IncomingArcIterator > IncomingArcs (NodeIndexType node) const
BeginEndWrapper< IncomingArcIterator > IncomingArcsStartingFrom (NodeIndexType node, ArcIndexType from) const
BeginEndWrapper< OutgoingOrOppositeIncomingArcIterator > OutgoingOrOppositeIncomingArcs (NodeIndexType node) const
BeginEndWrapper< OutgoingOrOppositeIncomingArcIterator > OutgoingOrOppositeIncomingArcsStartingFrom (NodeIndexType node, ArcIndexType from) const
absl::Span< const NodeIndexType > operator[] (NodeIndexType node) const
void ReserveArcs (ArcIndexType bound) override
void AddNode (NodeIndexType node)
ArcIndexType AddArc (NodeIndexType tail, NodeIndexType head)
void Build ()
void Build (std::vector< ArcIndexType > *permutation)
bool IsArcValid (ArcIndexType arc) const
Public Member Functions inherited from util::BaseGraph< int32_t, int32_t, true >
 BaseGraph ()
BaseGraph & operator= (const BaseGraph &)=default
virtual ~BaseGraph ()=default
int32_t num_nodes () const
int32_t size () const
int32_t num_arcs () const
 Returns the number of valid arcs in the graph.
IntegerRange< NodeIndex > AllNodes () const
 BaseGraph implementation -------------------------------------------------—.
IntegerRange< ArcIndex > AllForwardArcs () const
bool IsNodeValid (int32_t node) const
 Returns true if the given node is a valid node of the graph.
bool IsArcValid (int32_t arc) const
int32_t node_capacity () const
 Capacity reserved for future nodes, always >= num_nodes_.
int32_t arc_capacity () const
 Capacity reserved for future arcs, always >= num_arcs_.
virtual void ReserveNodes (int32_t bound)
virtual void ReserveArcs (int32_t bound)
void Reserve (int32_t node_capacity, int32_t arc_capacity)
void FreezeCapacities ()

Additional Inherited Members

Static Public Attributes inherited from util::BaseGraph< int32_t, int32_t, true >
static constexpr bool kHasNegativeReverseArcs
static constexpr int32_t kNilNode
static constexpr int32_t kNilArc
Protected Member Functions inherited from util::BaseGraph< int32_t, int32_t, true >
void ComputeCumulativeSum (internal::Vector< int32_t, int32_t > *v)
 Functions commented when defined because they are implementation details.
void BuildStartAndForwardHead (internal::SVector< int32_t, int32_t > *head, internal::Vector< int32_t, int32_t > *start, std::vector< int32_t > *permutation)
Protected Attributes inherited from util::BaseGraph< int32_t, int32_t, true >
int32_t num_nodes_
int32_t node_capacity_
int32_t num_arcs_
int32_t arc_capacity_
bool const_capacities_

Member Typedef Documentation

◆ IncomingArcIterator

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t>
using util::ReverseArcStaticGraph< NodeIndexType, ArcIndexType >::IncomingArcIterator
Initial value:
ArcOppositeArcIterator<ReverseArcStaticGraph,
OppositeIncomingArcIterator>
util::ReverseArcStaticGraph::OppositeIncomingArcIterator
IntegerRangeIterator< ArcIndexType > OppositeIncomingArcIterator
Definition graph.h:1008
util::ArcOppositeArcIterator
ArcPropertyIterator< Graph, ArcIterator, typename Graph::ArcIndex, &Graph::OppositeArc > ArcOppositeArcIterator
An iterator that iterates on the opposite arcs of another iterator.
Definition graph.h:373

Definition at line 1009 of file graph.h.

◆ OppositeIncomingArcIterator

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t>
using util::ReverseArcStaticGraph< NodeIndexType, ArcIndexType >::OppositeIncomingArcIterator = IntegerRangeIterator<ArcIndexType>

Definition at line 1008 of file graph.h.

◆ OutgoingArcIterator

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t>
using util::ReverseArcStaticGraph< NodeIndexType, ArcIndexType >::OutgoingArcIterator = IntegerRangeIterator<ArcIndexType>

Definition at line 1012 of file graph.h.

Constructor & Destructor Documentation

◆ ReverseArcStaticGraph() [1/2]

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t>
util::ReverseArcStaticGraph< NodeIndexType, ArcIndexType >::ReverseArcStaticGraph ( )
inline

Definition at line 987 of file graph.h.

◆ ReverseArcStaticGraph() [2/2]

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t>
util::ReverseArcStaticGraph< NodeIndexType, ArcIndexType >::ReverseArcStaticGraph ( NodeIndexType num_nodes,
ArcIndexType arc_capacity )
inline

Definition at line 988 of file graph.h.

Member Function Documentation

◆ AddArc()

template<typename NodeIndexType, typename ArcIndexType>
ArcIndexType util::ReverseArcStaticGraph< NodeIndexType, ArcIndexType >::AddArc ( NodeIndexType tail,
NodeIndexType head )

We inverse head and tail here because it is more convenient this way during build time, see Build().

Definition at line 1741 of file graph.h.

◆ AddNode()

template<typename NodeIndexType, typename ArcIndexType>
void util::ReverseArcStaticGraph< NodeIndexType, ArcIndexType >::AddNode ( NodeIndexType node)

Definition at line 1733 of file graph.h.

◆ Build() [1/2]

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t>
void util::ReverseArcStaticGraph< NodeIndexType, ArcIndexType >::Build ( )
inline

Definition at line 1068 of file graph.h.

◆ Build() [2/2]

template<typename NodeIndexType, typename ArcIndexType>
void util::ReverseArcStaticGraph< NodeIndexType, ArcIndexType >::Build ( std::vector< ArcIndexType > * permutation)

Computes incoming degree of each nodes.

Computes the reverse arcs of the forward arcs.

Note
this sort the reverse arcs with the same tail by head.
Todo
(user): the 0 is wasted here, but minor optimisation.

Computes in reverse_start_ the start index of the reverse arcs.

Fill reverse arc information.

Definition at line 1755 of file graph.h.

◆ Head()

template<typename NodeIndexType, typename ArcIndexType>
NodeIndexType util::ReverseArcStaticGraph< NodeIndexType, ArcIndexType >::Head ( ArcIndexType arc) const
Todo
(user): support Head() and Tail() before Build(), like StaticGraph<>.

Definition at line 1710 of file graph.h.

◆ IncomingArcs()

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t>
BeginEndWrapper< IncomingArcIterator > util::ReverseArcStaticGraph< NodeIndexType, ArcIndexType >::IncomingArcs ( NodeIndexType node) const
inline

Definition at line 1037 of file graph.h.

◆ IncomingArcsStartingFrom()

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t>
BeginEndWrapper< IncomingArcIterator > util::ReverseArcStaticGraph< NodeIndexType, ArcIndexType >::IncomingArcsStartingFrom ( NodeIndexType node,
ArcIndexType from ) const
inline

Definition at line 1043 of file graph.h.

◆ InDegree()

template<typename NodeIndexType, typename ArcIndexType>
ArcIndexType util::ReverseArcStaticGraph< NodeIndexType, ArcIndexType >::InDegree ( NodeIndexType node) const

Definition at line 1687 of file graph.h.

◆ IsArcValid()

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t>
bool util::BaseGraph< NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::IsArcValid ( ArcIndexType arc) const
inline

Returns true if the given arc is a valid arc of the graph.

Note
the arc validity range changes for graph with reverse arcs.

Definition at line 249 of file graph.h.

◆ operator[]()

template<typename NodeIndexType, typename ArcIndexType>
absl::Span< const NodeIndexType > util::ReverseArcStaticGraph< NodeIndexType, ArcIndexType >::operator[] ( NodeIndexType node) const

This loops over the heads of the OutgoingArcs(node). It is just a more convenient way to achieve this. Moreover this interface is used by some graph algorithms.

Definition at line 1694 of file graph.h.

◆ OppositeArc()

template<typename NodeIndexType, typename ArcIndexType>
ArcIndexType util::ReverseArcStaticGraph< NodeIndexType, ArcIndexType >::OppositeArc ( ArcIndexType arc) const

Definition at line 1702 of file graph.h.

◆ OppositeIncomingArcs()

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t>
IntegerRange< ArcIndexType > util::ReverseArcStaticGraph< NodeIndexType, ArcIndexType >::OppositeIncomingArcs ( NodeIndexType node) const
inline

Definition at line 1025 of file graph.h.

◆ OppositeIncomingArcsStartingFrom()

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t>
IntegerRange< ArcIndexType > util::ReverseArcStaticGraph< NodeIndexType, ArcIndexType >::OppositeIncomingArcsStartingFrom ( NodeIndexType node,
ArcIndexType from ) const
inline

Definition at line 1029 of file graph.h.

◆ OutDegree()

template<typename NodeIndexType, typename ArcIndexType>
ArcIndexType util::ReverseArcStaticGraph< NodeIndexType, ArcIndexType >::OutDegree ( NodeIndexType node) const

ReverseArcStaticGraph<>::OutDegree() and InDegree() work in O(1).

Definition at line 1681 of file graph.h.

◆ OutgoingArcs()

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t>
IntegerRange< ArcIndexType > util::ReverseArcStaticGraph< NodeIndexType, ArcIndexType >::OutgoingArcs ( NodeIndexType node) const
inline

Definition at line 1014 of file graph.h.

◆ OutgoingArcsStartingFrom()

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t>
IntegerRange< ArcIndexType > util::ReverseArcStaticGraph< NodeIndexType, ArcIndexType >::OutgoingArcsStartingFrom ( NodeIndexType node,
ArcIndexType from ) const
inline

Definition at line 1017 of file graph.h.

◆ OutgoingOrOppositeIncomingArcs()

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t>
BeginEndWrapper< OutgoingOrOppositeIncomingArcIterator > util::ReverseArcStaticGraph< NodeIndexType, ArcIndexType >::OutgoingOrOppositeIncomingArcs ( NodeIndexType node) const

◆ OutgoingOrOppositeIncomingArcsStartingFrom()

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t>
BeginEndWrapper< OutgoingOrOppositeIncomingArcIterator > util::ReverseArcStaticGraph< NodeIndexType, ArcIndexType >::OutgoingOrOppositeIncomingArcsStartingFrom ( NodeIndexType node,
ArcIndexType from ) const

◆ ReserveArcs()

template<typename NodeIndexType, typename ArcIndexType>
void util::ReverseArcStaticGraph< NodeIndexType, ArcIndexType >::ReserveArcs ( ArcIndexType bound)
override

Definition at line 1725 of file graph.h.

◆ Tail()

template<typename NodeIndexType, typename ArcIndexType>
NodeIndexType util::ReverseArcStaticGraph< NodeIndexType, ArcIndexType >::Tail ( ArcIndexType arc) const

Definition at line 1718 of file graph.h.

The documentation for this class was generated from the following file: