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()
- 2 * (ArcIndexType + NodeIndexType) * arc_capacity() memory.

Definition at line 837 of file graph.h.

#include <graph.h>

Inheritance diagram for util::ReverseArcListGraph< NodeIndexType, ArcIndexType >:

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< OutgoingArcIterator >	OutgoingArcs (NodeIndexType node) const
BeginEndWrapper< OutgoingArcIterator >	OutgoingArcsStartingFrom (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< OppositeIncomingArcIterator >	OppositeIncomingArcs (NodeIndexType node) const
BeginEndWrapper< OppositeIncomingArcIterator >	OppositeIncomingArcsStartingFrom (NodeIndexType node, ArcIndexType from) const
BeginEndWrapper< OutgoingOrOppositeIncomingArcIterator >	OutgoingOrOppositeIncomingArcsStartingFrom (NodeIndexType node, ArcIndexType from) const
BeginEndWrapper< OutgoingHeadIterator >	operator[] (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 ()
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::ReverseArcListGraph< NodeIndexType, ArcIndexType >::IncomingArcIterator

Initial value:

ArcOppositeArcIterator<ReverseArcListGraph, OppositeIncomingArcIterator>

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 878 of file graph.h.

◆ OppositeIncomingArcIterator

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t>

using util::ReverseArcListGraph< NodeIndexType, ArcIndexType >::OppositeIncomingArcIterator

Initial value:

 
      ChasingIterator<ArcIndexType, Base::kNilArc,
                      OppositeIncomingArcIteratorTag>

Definition at line 872 of file graph.h.

◆ OutgoingArcIterator

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t>

using util::ReverseArcListGraph< NodeIndexType, ArcIndexType >::OutgoingArcIterator

Initial value:

ChasingIterator<ArcIndexType, Base::kNilArc, OutgoingArcIteratorTag>

Definition at line 869 of file graph.h.

◆ OutgoingHeadIterator

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t>

using util::ReverseArcListGraph< NodeIndexType, ArcIndexType >::OutgoingHeadIterator

Initial value:

ArcHeadIterator<ReverseArcListGraph, OutgoingArcIterator>

util::ArcHeadIterator

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:367

Definition at line 876 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 851 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 852 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 1615 of file graph.h.

◆ AddNode()

template<typename NodeIndexType, typename ArcIndexType>

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

Definition at line 1605 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 953 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 1629 of file graph.h.

◆ Head()

template<typename NodeIndexType, typename ArcIndexType>

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

Definition at line 1574 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 906 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 910 of file graph.h.

◆ InDegree()

template<typename NodeIndexType, typename ArcIndexType>

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

Definition at line 1559 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 1540 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 1567 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 923 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 929 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 1551 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 892 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 897 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 1596 of file graph.h.

◆ ReserveNodes()

template<typename NodeIndexType, typename ArcIndexType>

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

override

Definition at line 1587 of file graph.h.

◆ Tail()

template<typename NodeIndexType, typename ArcIndexType>

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

Definition at line 1581 of file graph.h.

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

ortools/graph/graph.h

Detailed Description

Classes

Public Types

Public Member Functions

Additional Inherited Members

Member Typedef Documentation

◆ IncomingArcIterator

◆ OppositeIncomingArcIterator

◆ OutgoingArcIterator

◆ OutgoingHeadIterator

Constructor & Destructor Documentation

◆ ReverseArcListGraph() [1/2]

◆ ReverseArcListGraph() [2/2]

Member Function Documentation

◆ AddArc()

◆ AddNode()

◆ Build() [1/2]

◆ Build() [2/2]

◆ Head()

◆ IncomingArcs()

◆ IncomingArcsStartingFrom()

◆ InDegree()

◆ IsArcValid()

◆ operator[]()

◆ OppositeArc()

◆ OppositeIncomingArcs()

◆ OppositeIncomingArcsStartingFrom()

◆ OutDegree()

◆ OutgoingArcs()

◆ OutgoingArcsStartingFrom()

◆ OutgoingOrOppositeIncomingArcs()

◆ OutgoingOrOppositeIncomingArcsStartingFrom()

◆ ReserveArcs()

◆ ReserveNodes()

◆ Tail()