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

#include <graph.h>

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

Classes

struct  OppositeIncomingArcIteratorTag
struct  OutgoingArcIteratorTag
 Do not use directly. See instead the arc iteration functions below. More...
class  OutgoingOrOppositeIncomingArcIterator

Public Types

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

Public Member Functions

 ReverseArcListGraph ()
 ReverseArcListGraph (NodeIndexType num_nodes, ArcIndexType arc_capacity)
NodeIndexType Head (ArcIndexType arc) const
NodeIndexType Tail (ArcIndexType arc) const
ArcIndexType OppositeArc (ArcIndexType arc) const
ArcIndexType OutDegree (NodeIndexType node) const
 ReverseArcListGraph<>::OutDegree() and InDegree() work in O(degree).
ArcIndexType InDegree (NodeIndexType node) const
BeginEndWrapper< OutgoingArcIteratorOutgoingArcs (NodeIndexType node) const
BeginEndWrapper< OutgoingArcIteratorOutgoingArcsStartingFrom (NodeIndexType node, ArcIndexType from) const
BeginEndWrapper< IncomingArcIteratorIncomingArcs (NodeIndexType node) const
BeginEndWrapper< IncomingArcIteratorIncomingArcsStartingFrom (NodeIndexType node, ArcIndexType from) const
BeginEndWrapper< OutgoingOrOppositeIncomingArcIteratorOutgoingOrOppositeIncomingArcs (NodeIndexType node) const
BeginEndWrapper< OppositeIncomingArcIteratorOppositeIncomingArcs (NodeIndexType node) const
BeginEndWrapper< OppositeIncomingArcIteratorOppositeIncomingArcsStartingFrom (NodeIndexType node, ArcIndexType from) const
BeginEndWrapper< OutgoingOrOppositeIncomingArcIteratorOutgoingOrOppositeIncomingArcsStartingFrom (NodeIndexType node, ArcIndexType from) const
BeginEndWrapper< OutgoingHeadIteratoroperator[] (NodeIndexType node) const
void ReserveNodes (NodeIndexType bound) override
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 ()
BaseGraphoperator= (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< NodeIndexAllNodes () const
 BaseGraph implementation -------------------------------------------------—.
IntegerRange< ArcIndexAllForwardArcs () 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_

Detailed Description

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

Extends the ListGraph by also storing the reverse arcs. This class also documents the Graph interface related to reverse arc.

  • NodeIndexType can be unsigned, but ArcIndexType must be signed.
  • It has most of the same advantanges and disadvantages as ListGraph.
  • It takes 2 * ArcIndexType * node_capacity()

Definition at line 833 of file graph.h.

Member Typedef Documentation

◆ IncomingArcIterator

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

Definition at line 874 of file graph.h.

◆ OppositeIncomingArcIterator

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

◆ OutgoingArcIterator

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

◆ OutgoingHeadIterator

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t>
using util::ReverseArcListGraph< NodeIndexType, ArcIndexType >::OutgoingHeadIterator
Initial value:
ArcPropertyIterator< Graph, ArcIterator, typename Graph::NodeIndex, &Graph::Head > ArcHeadIterator
An iterator that iterates on the heads of the arcs of another iterator.
Definition graph.h:361

Definition at line 872 of file graph.h.

Constructor & Destructor Documentation

◆ ReverseArcListGraph() [1/2]

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

Definition at line 847 of file graph.h.

◆ ReverseArcListGraph() [2/2]

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

Definition at line 848 of file graph.h.

Member Function Documentation

◆ AddArc()

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

Definition at line 1611 of file graph.h.

◆ AddNode()

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

Definition at line 1601 of file graph.h.

◆ Build() [1/2]

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

Definition at line 949 of file graph.h.

◆ Build() [2/2]

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

Definition at line 1625 of file graph.h.

◆ Head()

template<typename NodeIndexType, typename ArcIndexType>
NodeIndexType util::ReverseArcListGraph< NodeIndexType, ArcIndexType >::Head ( ArcIndexType arc) const

Definition at line 1570 of file graph.h.

◆ IncomingArcs()

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

Definition at line 902 of file graph.h.

◆ IncomingArcsStartingFrom()

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

Definition at line 906 of file graph.h.

◆ InDegree()

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

Definition at line 1555 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>
BeginEndWrapper< typename ReverseArcListGraph< NodeIndexType, ArcIndexType >::OutgoingHeadIterator > util::ReverseArcListGraph< 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.

Note
BeginEndWrapper is a borrowed range (std::ranges::borrowed_range) so copying begin/end is safe.

Definition at line 1536 of file graph.h.

◆ OppositeArc()

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

Returns the opposite arc of a given arc. That is the reverse arc of the given forward arc or the forward arc of a given reverse arc.

Definition at line 1563 of file graph.h.

◆ OppositeIncomingArcs()

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t>
BeginEndWrapper< OppositeIncomingArcIterator > util::ReverseArcListGraph< NodeIndexType, ArcIndexType >::OppositeIncomingArcs ( NodeIndexType node) const
inline

Definition at line 919 of file graph.h.

◆ OppositeIncomingArcsStartingFrom()

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t>
BeginEndWrapper< OppositeIncomingArcIterator > util::ReverseArcListGraph< NodeIndexType, ArcIndexType >::OppositeIncomingArcsStartingFrom ( NodeIndexType node,
ArcIndexType from ) const
inline

Definition at line 925 of file graph.h.

◆ OutDegree()

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

ReverseArcListGraph<>::OutDegree() and InDegree() work in O(degree).

Definition at line 1547 of file graph.h.

◆ OutgoingArcs()

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t>
BeginEndWrapper< OutgoingArcIterator > util::ReverseArcListGraph< NodeIndexType, ArcIndexType >::OutgoingArcs ( NodeIndexType node) const
inline

Arc iterations functions over the arcs touching a node (see the top-level comment for the different types). To be used as follows: for (const Graph::ArcIndex arc : IterationFunction(node)) { ... }

The StartingFrom() version are similar, but restart the iteration from a given arc position (which must be valid in the iteration context), or kNilArc, in which case an empty range is returned.

Definition at line 888 of file graph.h.

◆ OutgoingArcsStartingFrom()

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t>
BeginEndWrapper< OutgoingArcIterator > util::ReverseArcListGraph< NodeIndexType, ArcIndexType >::OutgoingArcsStartingFrom ( NodeIndexType node,
ArcIndexType from ) const
inline

Definition at line 893 of file graph.h.

◆ OutgoingOrOppositeIncomingArcs()

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

◆ OutgoingOrOppositeIncomingArcsStartingFrom()

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

◆ ReserveArcs()

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

Definition at line 1592 of file graph.h.

◆ ReserveNodes()

template<typename NodeIndexType, typename ArcIndexType>
void util::ReverseArcListGraph< NodeIndexType, ArcIndexType >::ReserveNodes ( NodeIndexType bound)
override

Definition at line 1583 of file graph.h.

◆ Tail()

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

Definition at line 1577 of file graph.h.


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