#include <graph.h>

Inheritance diagram for util::StaticGraph< NodeIndexType, ArcIndexType >::OutgoingArcIterator:

Public Member Functions
	OutgoingArcIterator (const OutgoingArcIterator &)=default

OutgoingArcIterator &	operator= (const OutgoingArcIterator &)=default

	OutgoingArcIterator (const StaticGraph &graph, NodeIndexType node)

	OutgoingArcIterator (const StaticGraph &graph, NodeIndexType node, ArcIndexType arc)

bool	Ok () const

ArcIndexType	Index () const

void	Next ()

	DEFINE_STL_ITERATOR_FUNCTIONS (OutgoingArcIterator)

StaticGraph< NodeIndexType, ArcIndexType >	FromArcs (NodeIndexType num_nodes, const ArcContainer &arcs)
	StaticGraph implementation -----------------------------------------------—.

bool	IsArcValid (ArcIndexType arc) const

	StaticGraph ()

	StaticGraph (NodeIndexType num_nodes, ArcIndexType arc_capacity)

StaticGraph< NodeIndexType, ArcIndexType >	FromArcs (NodeIndexType num_nodes, const ArcContainer &arcs)
	StaticGraph implementation -----------------------------------------------—.

NodeIndexType	Head (ArcIndexType arc) const

NodeIndexType	Tail (ArcIndexType arc) const

ArcIndexType	OutDegree (NodeIndexType node) const

BeginEndWrapper< OutgoingArcIterator >	OutgoingArcs (NodeIndexType node) const

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

absl::Span< const NodeIndexType >	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< 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 ()

Static Public Member Functions
static StaticGraph	FromArcs (NodeIndexType num_nodes, const ArcContainer &arcs)
	Shortcut to directly create a finalized graph, i.e. Build() is called.

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

typedef ArcIndexType	ArcIndex

typedef NodeIndexType	NodeIndex

typedef ArcIndexType	ArcIndex

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::StaticGraph< NodeIndexType, ArcIndexType >::OutgoingArcIterator

Definition at line 1448 of file graph.h.

Constructor & Destructor Documentation

◆ OutgoingArcIterator() [1/3]

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

util::StaticGraph< NodeIndexType, ArcIndexType >::OutgoingArcIterator::OutgoingArcIterator ( const OutgoingArcIterator & )

default

◆ OutgoingArcIterator() [2/3]

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

util::StaticGraph< NodeIndexType, ArcIndexType >::OutgoingArcIterator::OutgoingArcIterator	(	const StaticGraph &	graph,
		NodeIndexType	node )

inline

Definition at line 1452 of file graph.h.

◆ OutgoingArcIterator() [3/3]

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

util::StaticGraph< NodeIndexType, ArcIndexType >::OutgoingArcIterator::OutgoingArcIterator	(	const StaticGraph &	graph,
		NodeIndexType	node,
		ArcIndexType	arc )

inline

Definition at line 1454 of file graph.h.

Member Function Documentation

◆ AddArc()

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

Definition at line 446 of file graph.h.

◆ AddNode()

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

Definition at line 445 of file graph.h.

◆ Build() [1/2]

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

inline

Definition at line 448 of file graph.h.

◆ Build() [2/2]

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

Implementation details: A reader may be surprised that we do many passes into the data where things could be done in one pass. For instance, during construction, we store the edges first, and then do a second pass at the end to compute the degree distribution.

This is because it is a lot more efficient cache-wise to do it this way. This was determined by various experiments, but can also be understood:

during repetitive call to AddArc() a client usually accesses various areas of memory, and there is no reason to pollute the cache with possibly random access to degree[i].
When the degrees are needed, we compute them in one go, maximizing the chance of cache hit during the computation.

If Arc are in order, start_ already contains the degree distribution.

Computes outgoing degree of each nodes. We have to clear start_, since at least the first arc was processed with arc_in_order_ == true.

Computes the forward arc permutation.

Note: this temporarily alters the start_ vector.

We use "tail_" (which now contains rubbish) to permute "head_" faster.

Restore in start_[i] the index of the first arc with tail >= i.

Recompute the correct tail_ vector

Definition at line 449 of file graph.h.

◆ DEFINE_STL_ITERATOR_FUNCTIONS()

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

util::StaticGraph< NodeIndexType, ArcIndexType >::OutgoingArcIterator::DEFINE_STL_ITERATOR_FUNCTIONS ( OutgoingArcIterator )

Note(user): we lose a bit by returning a BeginEndWrapper<> on top of this iterator rather than a simple IntegerRange<> on the arc indices. On my computer: around 420M arcs/sec instead of 440M arcs/sec.

However, it is slightly more consistent to do it this way, and we don't have two different codes depending on the way a client iterates on the arcs.

◆ FromArcs() [1/3]

static StaticGraph util::StaticGraph< NodeIndexType, ArcIndexType >::FromArcs	(	NodeIndexType	num_nodes,
		const ArcContainer &	arcs )

static

Shortcut to directly create a finalized graph, i.e. Build() is called.

◆ FromArcs() [2/3]

StaticGraph< NodeIndexType, ArcIndexType > util::StaticGraph< NodeIndexType, ArcIndexType >::FromArcs	(	NodeIndexType	num_nodes,
		const ArcContainer &	arcs )

StaticGraph implementation -----------------------------------------------—.

Definition at line 1294 of file graph.h.

◆ FromArcs() [3/3]

StaticGraph< NodeIndexType, ArcIndexType > util::StaticGraph< NodeIndexType, ArcIndexType >::FromArcs	(	NodeIndexType	num_nodes,
		const ArcContainer &	arcs )

StaticGraph implementation -----------------------------------------------—.

Definition at line 1294 of file graph.h.

◆ Head()

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

Definition at line 431 of file graph.h.

◆ Index()

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

ArcIndexType util::StaticGraph< NodeIndexType, ArcIndexType >::OutgoingArcIterator::Index ( ) const

inline

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

◆ Next()

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

void util::StaticGraph< NodeIndexType, ArcIndexType >::OutgoingArcIterator::Next ( )

inline

Definition at line 1463 of file graph.h.

◆ Ok()

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

bool util::StaticGraph< NodeIndexType, ArcIndexType >::OutgoingArcIterator::Ok ( ) const

inline

Definition at line 1461 of file graph.h.

◆ operator=()

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

OutgoingArcIterator & util::StaticGraph< NodeIndexType, ArcIndexType >::OutgoingArcIterator::operator= ( const OutgoingArcIterator & )

default

◆ operator[]()

absl::Span< const NodeIndexType > util::StaticGraph< 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 441 of file graph.h.

◆ OutDegree()

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

Definition at line 433 of file graph.h.

◆ OutgoingArcs()

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

◆ OutgoingArcsStartingFrom()

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

◆ ReserveArcs()

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

overridevirtual

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

Definition at line 444 of file graph.h.

◆ ReserveNodes()

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

overridevirtual

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

Definition at line 443 of file graph.h.

◆ StaticGraph() [1/2]

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

inline

Definition at line 415 of file graph.h.

◆ StaticGraph() [2/2]

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

inline

Definition at line 416 of file graph.h.

◆ Tail()

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

Definition at line 432 of file graph.h.

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

ortools/graph/graph.h

Public Member Functions

Static Public Member Functions

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ OutgoingArcIterator() [1/3]

◆ OutgoingArcIterator() [2/3]

◆ OutgoingArcIterator() [3/3]

Member Function Documentation

◆ AddArc()

◆ AddNode()

◆ Build() [1/2]

◆ Build() [2/2]

◆ DEFINE_STL_ITERATOR_FUNCTIONS()

◆ FromArcs() [1/3]

◆ FromArcs() [2/3]

◆ FromArcs() [3/3]

◆ Head()

◆ Index()

◆ IsArcValid() [1/2]

◆ IsArcValid() [2/2]

◆ Next()

◆ Ok()

◆ operator=()

◆ operator[]()

◆ OutDegree()

◆ OutgoingArcs()

◆ OutgoingArcsStartingFrom()

◆ ReserveArcs()

◆ ReserveNodes()

◆ StaticGraph() [1/2]

◆ StaticGraph() [2/2]

◆ Tail()