#include <graph.h>

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

Classes
class	OutgoingArcIterator

Public Member Functions
	StaticGraph ()

	StaticGraph (NodeIndexType num_nodes, ArcIndexType arc_capacity)

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)

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

bool	IsArcValid (ArcIndexType arc) const

Public Member Functions inherited from util::BaseGraph< int32_t, int32_t, false >
	BaseGraph ()

	BaseGraph (const BaseGraph &)=default

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

void	GroupForwardArcsByFunctor (const A &a, B *b)

int32_t	max_end_arc_index () const

Static Public Member Functions
template<class ArcContainer >
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< int32_t, int32_t, false >
typedef int32_t	NodeIndex

typedef int32_t	ArcIndex

Static Public Attributes inherited from util::BaseGraph< int32_t, int32_t, false >
static const int32_t	kNilNode

static const int32_t	kNilArc

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

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

Protected Attributes inherited from util::BaseGraph< int32_t, int32_t, false >
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::StaticGraph< NodeIndexType, ArcIndexType >

Most efficient implementation of a graph without reverse arcs:

Build() needs to be called after the arc and node have been added.
The graph is really compact memory wise: ArcIndexType * node_capacity() + 2 * NodeIndexType * arc_capacity(), but when Build() is called it uses a temporary extra space of ArcIndexType * arc_capacity().
The construction is really fast.

NOTE(user): if the need arises for very-well compressed graphs, we could shave NodeIndexType * arc_capacity() off the permanent memory requirement with a similar class that doesn't support Tail(), i.e. StaticGraphWithoutTail<>. This almost corresponds to a past implementation of StaticGraph<> @CL 116144340.

Definition at line 408 of file graph.h.

Constructor & Destructor Documentation

◆ StaticGraph() [1/2]

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

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

inline

Definition at line 418 of file graph.h.

◆ StaticGraph() [2/2]

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

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

inline

Definition at line 419 of file graph.h.

Member Function Documentation

◆ AddArc()

template<typename NodeIndexType , typename ArcIndexType >

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

Definition at line 1332 of file graph.h.

◆ AddNode()

template<typename NodeIndexType , typename ArcIndexType >

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

Definition at line 1324 of file graph.h.

◆ Build() [1/2]

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

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

inline

Definition at line 451 of file graph.h.

◆ Build() [2/2]

template<typename NodeIndexType , typename ArcIndexType >

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

◆ FromArcs() [1/2]

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

template<class ArcContainer >

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/2]

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

template<class ArcContainer >

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

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

Definition at line 1284 of file graph.h.

◆ Head()

template<typename NodeIndexType , typename ArcIndexType >

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

Definition at line 1360 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 >

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

◆ OutDegree()

template<typename NodeIndexType , typename ArcIndexType >

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

Definition at line 1302 of file graph.h.

◆ OutgoingArcs()

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

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

◆ OutgoingArcsStartingFrom()

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

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

◆ ReserveArcs()

template<typename NodeIndexType , typename ArcIndexType >

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

override

Definition at line 1316 of file graph.h.

◆ ReserveNodes()

template<typename NodeIndexType , typename ArcIndexType >

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

override

Definition at line 1308 of file graph.h.

◆ Tail()

template<typename NodeIndexType , typename ArcIndexType >

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

Definition at line 1353 of file graph.h.

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

ortools/graph/graph.h

Classes

Public Member Functions

Static Public Member Functions

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ StaticGraph() [1/2]

◆ StaticGraph() [2/2]

Member Function Documentation

◆ AddArc()

◆ AddNode()

◆ Build() [1/2]

◆ Build() [2/2]

◆ FromArcs() [1/2]

◆ FromArcs() [2/2]

◆ Head()

◆ IsArcValid()

◆ operator[]()

◆ OutDegree()

◆ OutgoingArcs()

◆ OutgoingArcsStartingFrom()

◆ ReserveArcs()

◆ ReserveNodes()

◆ Tail()