#include <graph.h>

Inheritance diagram for util::ListGraph< NodeIndexType, ArcIndexType >::OutgoingHeadIterator:

Public Types
using	iterator_category = std::input_iterator_tag

using	difference_type = ptrdiff_t

using	pointer = const NodeIndexType*

using	reference = const NodeIndexType&

using	value_type = NodeIndexType

Public Types inherited from util::BaseGraph< NodeIndexType, ArcIndexType, false >
typedef NodeIndexType	NodeIndex

typedef ArcIndexType	ArcIndex

typedef NodeIndexType	NodeIndex

typedef ArcIndexType	ArcIndex

Public Member Functions
	OutgoingHeadIterator (const ListGraph &graph, NodeIndexType node)

	OutgoingHeadIterator (const ListGraph &graph, NodeIndexType node, ArcIndexType arc)

bool	Ok () const

NodeIndexType	Index () const

void	Next ()

bool	operator!= (const typename ListGraph< NodeIndexType, ArcIndexType >::OutgoingHeadIterator &other) const

NodeIndexType	operator* () const

void	operator++ ()

bool	IsArcValid (ArcIndexType arc) const

	ListGraph ()

	ListGraph (NodeIndexType num_nodes, ArcIndexType arc_capacity)

void	AddNode (NodeIndexType node)

ArcIndexType	AddArc (NodeIndexType tail, NodeIndexType head)

void	Build ()

void	Build (std::vector< ArcIndexType > *permutation)

ArcIndexType	OutDegree (NodeIndexType node) const

BeginEndWrapper< OutgoingArcIterator >	OutgoingArcs (NodeIndexType node) const

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

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

NodeIndexType	Tail (ArcIndexType arc) const
	Returns the tail/head of a valid arc.

NodeIndexType	Head (ArcIndexType arc) const

void	ReserveNodes (NodeIndexType bound) override

void	ReserveArcs (ArcIndexType bound) override

bool	IsArcValid (ArcIndexType arc) const

Public Member Functions inherited from util::BaseGraph< NodeIndexType, ArcIndexType, false >
	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 ()

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

Additional Inherited Members
Static Public Attributes inherited from util::BaseGraph< NodeIndexType, ArcIndexType, false >
static constexpr bool	kHasNegativeReverseArcs

static const NodeIndexType	kNilNode

static const ArcIndexType	kNilArc

static constexpr bool	kHasNegativeReverseArcs

static const NodeIndexType	kNilNode

static const ArcIndexType	kNilArc

Protected Member Functions inherited from util::BaseGraph< NodeIndexType, ArcIndexType, false >
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)

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, false >
NodeIndexType	num_nodes_

NodeIndexType	node_capacity_

ArcIndexType	num_arcs_

ArcIndexType	arc_capacity_

bool	const_capacities_

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::ListGraph< NodeIndexType, ArcIndexType >::OutgoingHeadIterator

Definition at line 1251 of file graph.h.

Member Typedef Documentation

◆ difference_type

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

using util::ListGraph< NodeIndexType, ArcIndexType >::OutgoingHeadIterator::difference_type = ptrdiff_t

Definition at line 1254 of file graph.h.

◆ iterator_category

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

using util::ListGraph< NodeIndexType, ArcIndexType >::OutgoingHeadIterator::iterator_category = std::input_iterator_tag

Definition at line 1253 of file graph.h.

◆ pointer

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

using util::ListGraph< NodeIndexType, ArcIndexType >::OutgoingHeadIterator::pointer = const NodeIndexType*

Definition at line 1255 of file graph.h.

◆ reference

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

using util::ListGraph< NodeIndexType, ArcIndexType >::OutgoingHeadIterator::reference = const NodeIndexType&

Definition at line 1256 of file graph.h.

◆ value_type

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

using util::ListGraph< NodeIndexType, ArcIndexType >::OutgoingHeadIterator::value_type = NodeIndexType

Definition at line 1257 of file graph.h.

Constructor & Destructor Documentation

◆ OutgoingHeadIterator() [1/2]

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

util::ListGraph< NodeIndexType, ArcIndexType >::OutgoingHeadIterator::OutgoingHeadIterator	(	const ListGraph &	graph,
		NodeIndexType	node )

inline

Definition at line 1259 of file graph.h.

◆ OutgoingHeadIterator() [2/2]

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

util::ListGraph< NodeIndexType, ArcIndexType >::OutgoingHeadIterator::OutgoingHeadIterator	(	const ListGraph &	graph,
		NodeIndexType	node,
		ArcIndexType	arc )

inline

Definition at line 1263 of file graph.h.

Member Function Documentation

◆ AddArc()

ArcIndexType util::ListGraph< NodeIndexType, ArcIndexType >::AddArc	(	NodeIndexType	tail,
		NodeIndexType	head )

Adds an arc to the graph and returns its current index which will always be num_arcs() - 1. It will also automatically call AddNode(tail) and AddNode(head). It will fail in DEBUG mode if the capacities are fixed and this cause the graph to grow beyond them.

Note: Self referencing arcs and duplicate arcs are supported.

Definition at line 338 of file graph.h.

◆ AddNode()

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

If node is not a valid node, sets num_nodes_ to node + 1 so that the given node becomes valid. It will fail in DEBUG mode if the capacities are fixed and the new node is out of range.

Definition at line 330 of file graph.h.

◆ Build() [1/2]

void util::ListGraph< NodeIndexType, ArcIndexType >::Build ( )

inline

Some graph implementations need to be finalized with Build() before they can be used. After Build() is called, the arc indices (which had been the return values of previous AddArc() calls) may change: the new index of former arc #i will be stored in permutation[i] if #i is smaller than permutation.size() or will be unchanged otherwise. If you don't care about these, just call the simple no-output version Build().

Note: some implementations become immutable after calling Build().

Definition at line 348 of file graph.h.

◆ Build() [2/2]

void util::ListGraph< NodeIndexType, ArcIndexType >::Build ( std::vector< ArcIndexType > * permutation )

Definition at line 349 of file graph.h.

◆ Head()

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

Definition at line 379 of file graph.h.

◆ Index()

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

NodeIndexType util::ListGraph< NodeIndexType, ArcIndexType >::OutgoingHeadIterator::Index ( ) const

inline

Definition at line 1270 of file graph.h.

◆ IsArcValid() [1/2]

( ArcIndexType arc ) const

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

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

◆ IsArcValid() [2/2]

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

◆ ListGraph() [1/2]

util::ListGraph< NodeIndexType, ArcIndexType >::ListGraph ( )

inline

Definition at line 316 of file graph.h.

◆ ListGraph() [2/2]

util::ListGraph< NodeIndexType, ArcIndexType >::ListGraph	(	NodeIndexType	num_nodes,
		ArcIndexType	arc_capacity )

inline

Reserve space for the graph at construction and do not allow it to grow beyond that, see FreezeCapacities(). This constructor also makes any nodes in [0, num_nodes) valid.

Definition at line 321 of file graph.h.

◆ Next()

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

void util::ListGraph< NodeIndexType, ArcIndexType >::OutgoingHeadIterator::Next ( )

inline

Definition at line 1271 of file graph.h.

◆ Ok()

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

bool util::ListGraph< NodeIndexType, ArcIndexType >::OutgoingHeadIterator::Ok ( ) const

inline

Definition at line 1269 of file graph.h.

◆ operator!=()

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

bool util::ListGraph< NodeIndexType, ArcIndexType >::OutgoingHeadIterator::operator!= ( const typename ListGraph< NodeIndexType, ArcIndexType >::OutgoingHeadIterator & other ) const

inline

Definition at line 1276 of file graph.h.

◆ operator*()

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

NodeIndexType util::ListGraph< NodeIndexType, ArcIndexType >::OutgoingHeadIterator::operator* ( ) const

inline

Definition at line 1281 of file graph.h.

◆ operator++()

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

void util::ListGraph< NodeIndexType, ArcIndexType >::OutgoingHeadIterator::operator++ ( )

inline

Definition at line 1282 of file graph.h.

◆ operator[]()

BeginEndWrapper< typename ListGraph< NodeIndexType, ArcIndexType >::OutgoingHeadIterator > util::ListGraph< 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 375 of file graph.h.

◆ OutDegree()

ArcIndexType util::ListGraph< NodeIndexType, ArcIndexType >::OutDegree ( NodeIndexType node ) const

Graph jargon: the "degree" of a node is its number of arcs. The out-degree is the number of outgoing arcs. The in-degree is the number of incoming arcs, and is only available for some graph implementations, below.

ListGraph<>::OutDegree() works in O(degree).

Definition at line 360 of file graph.h.

◆ OutgoingArcs()

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

Allows to iterate over the forward arcs that verify Tail(arc) == node. This is meant to be used as: for (const ArcIndex arc : graph.OutgoingArcs(node)) { ... }

◆ OutgoingArcsStartingFrom()

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

Advanced usage. Same as OutgoingArcs(), but allows to restart the iteration from an already known outgoing arc of the given node.

◆ ReserveArcs()

void util::ListGraph< NodeIndexType, ArcIndexType >::ReserveArcs ( ArcIndexType bound )

overridevirtual

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

Definition at line 382 of file graph.h.

◆ ReserveNodes()

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

overridevirtual

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

Definition at line 381 of file graph.h.

◆ Tail()

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

Returns the tail/head of a valid arc.

Definition at line 378 of file graph.h.

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

ortools/graph/graph.h

Public Types

Public Member Functions

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ difference_type

◆ iterator_category

◆ pointer

◆ reference

◆ value_type

Constructor & Destructor Documentation

◆ OutgoingHeadIterator() [1/2]

◆ OutgoingHeadIterator() [2/2]

Member Function Documentation

◆ AddArc()

◆ AddNode()

◆ Build() [1/2]

◆ Build() [2/2]

◆ Head()

◆ Index()

◆ IsArcValid() [1/2]

◆ IsArcValid() [2/2]

◆ ListGraph() [1/2]

◆ ListGraph() [2/2]

◆ Next()

◆ Ok()

◆ operator!=()

◆ operator*()

◆ operator++()

◆ operator[]()

◆ OutDegree()

◆ OutgoingArcs()

◆ OutgoingArcsStartingFrom()

◆ ReserveArcs()

◆ ReserveNodes()

◆ Tail()