#include <graph.h>

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

Classes
class	IncomingArcIterator

class	OppositeIncomingArcIterator

class	OutgoingArcIterator

class	OutgoingHeadIterator

class	OutgoingOrOppositeIncomingArcIterator

Public Member Functions
	ReverseArcListGraph ()

	ReverseArcListGraph (NodeIndexType num_nodes, ArcIndexType arc_capacity)

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< IncomingArcIterator >	IncomingArcs (NodeIndexType node) const

BeginEndWrapper< OutgoingOrOppositeIncomingArcIterator >	OutgoingOrOppositeIncomingArcs (NodeIndexType node) const

BeginEndWrapper< OppositeIncomingArcIterator >	OppositeIncomingArcs (NodeIndexType node) const

BeginEndWrapper< OutgoingArcIterator >	OutgoingArcsStartingFrom (NodeIndexType node, ArcIndexType from) const

BeginEndWrapper< IncomingArcIterator >	IncomingArcsStartingFrom (NodeIndexType node, ArcIndexType from) const

BeginEndWrapper< OutgoingOrOppositeIncomingArcIterator >	OutgoingOrOppositeIncomingArcsStartingFrom (NodeIndexType node, ArcIndexType from) const

BeginEndWrapper< OppositeIncomingArcIterator >	OppositeIncomingArcsStartingFrom (NodeIndexType node, ArcIndexType from) const

BeginEndWrapper< OutgoingHeadIterator >	operator[] (NodeIndexType node) const

NodeIndexType	Head (ArcIndexType arc) const

NodeIndexType	Tail (ArcIndexType arc) 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< NodeIndexType, ArcIndexType, HasReverseArcs >
	BaseGraph ()

	BaseGraph (const BaseGraph &)=default

BaseGraph &	operator= (const BaseGraph &)=default

virtual	~BaseGraph ()=default

NodeIndexType	num_nodes () const

NodeIndexType	size () const

ArcIndexType	num_arcs () const
	Returns the number of valid arcs in the graph.

IntegerRange< NodeIndex >	AllNodes () const
	BaseGraph implementation -------------------------------------------------—.

IntegerRange< ArcIndex >	AllForwardArcs () const

bool	IsNodeValid (NodeIndexType node) const
	Returns true if the given node is a valid node of the graph.

bool	IsArcValid (ArcIndexType arc) const

NodeIndexType	node_capacity () const
	Capacity reserved for future nodes, always >= num_nodes_.

ArcIndexType	arc_capacity () const
	Capacity reserved for future arcs, always >= num_arcs_.

void	Reserve (NodeIndexType node_capacity, ArcIndexType arc_capacity)

void	FreezeCapacities ()

template<typename A , typename B >
void	GroupForwardArcsByFunctor (const A &a, B *b)

ArcIndexType	max_end_arc_index () const

Additional Inherited Members
Public Types inherited from util::BaseGraph< NodeIndexType, ArcIndexType, HasReverseArcs >
typedef NodeIndexType	NodeIndex

typedef ArcIndexType	ArcIndex

Static Public Attributes inherited from util::BaseGraph< NodeIndexType, ArcIndexType, HasReverseArcs >
static const NodeIndexType	kNilNode

static const ArcIndexType	kNilArc

Protected Member Functions inherited from util::BaseGraph< NodeIndexType, ArcIndexType, HasReverseArcs >
void	ComputeCumulativeSum (std::vector< ArcIndexType > *v)
	Functions commented when defined because they are implementation details.

void	BuildStartAndForwardHead (SVector< NodeIndexType > head, std::vector< ArcIndexType > start, std::vector< ArcIndexType > *permutation)

Protected Attributes inherited from util::BaseGraph< NodeIndexType, ArcIndexType, HasReverseArcs >
NodeIndexType	num_nodes_

NodeIndexType	node_capacity_

ArcIndexType	num_arcs_

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

Definition at line 476 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 489 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 490 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 1553 of file graph.h.

◆ AddNode()

template<typename NodeIndexType , typename ArcIndexType >

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

Definition at line 1543 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 546 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 1567 of file graph.h.

◆ Head()

template<typename NodeIndexType , typename ArcIndexType >

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

Definition at line 1512 of file graph.h.

◆ IncomingArcs()

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

BeginEndWrapper< IncomingArcIterator > util::ReverseArcListGraph< NodeIndexType, ArcIndexType >::IncomingArcs ( NodeIndexType node ) const

◆ IncomingArcsStartingFrom()

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

BeginEndWrapper< IncomingArcIterator > util::ReverseArcListGraph< NodeIndexType, ArcIndexType >::IncomingArcsStartingFrom	(	NodeIndexType	node,
		ArcIndexType	from ) const

◆ InDegree()

template<typename NodeIndexType , typename ArcIndexType >

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

Definition at line 1497 of file graph.h.

◆ IsArcValid()

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

bool util::BaseGraph< NodeIndexType, ArcIndexType, HasReverseArcs >::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 230 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.

Definition at line 1481 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 1505 of file graph.h.

◆ OppositeIncomingArcs()

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

BeginEndWrapper< OppositeIncomingArcIterator > util::ReverseArcListGraph< NodeIndexType, ArcIndexType >::OppositeIncomingArcs ( NodeIndexType node ) const

◆ OppositeIncomingArcsStartingFrom()

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

BeginEndWrapper< OppositeIncomingArcIterator > util::ReverseArcListGraph< NodeIndexType, ArcIndexType >::OppositeIncomingArcsStartingFrom	(	NodeIndexType	node,
		ArcIndexType	from ) const

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

◆ OutgoingArcs()

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

BeginEndWrapper< OutgoingArcIterator > util::ReverseArcListGraph< NodeIndexType, ArcIndexType >::OutgoingArcs ( NodeIndexType node ) const

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).

◆ OutgoingArcsStartingFrom()

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

BeginEndWrapper< OutgoingArcIterator > util::ReverseArcListGraph< NodeIndexType, ArcIndexType >::OutgoingArcsStartingFrom	(	NodeIndexType	node,
		ArcIndexType	from ) const

◆ 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 )

overridevirtual

Reimplemented from util::BaseGraph< NodeIndexType, ArcIndexType, HasReverseArcs >.

Definition at line 1534 of file graph.h.

◆ ReserveNodes()

template<typename NodeIndexType , typename ArcIndexType >

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

overridevirtual

Changes the graph capacities. The functions will fail in debug mode if:

const_capacities_ is true.
A valid node does not fall into the new node range.
A valid arc does not fall into the new arc range. In non-debug mode, const_capacities_ is ignored and nothing will happen if the new capacity value for the arcs or the nodes is too small.

Reimplemented from util::BaseGraph< NodeIndexType, ArcIndexType, HasReverseArcs >.

Definition at line 1525 of file graph.h.

◆ Tail()

template<typename NodeIndexType , typename ArcIndexType >

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

Definition at line 1519 of file graph.h.

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

ortools/graph/graph.h

Classes

Public Member Functions

Additional Inherited Members

Detailed Description

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()