Detailed Description

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t, bool HasNegativeReverseArcs = false>
class util::BaseGraph< NodeIndexType, ArcIndexType, HasNegativeReverseArcs >

Base class of all Graphs implemented here. The default value for the graph index types is int32_t since almost all graphs that fit into memory do not need bigger indices.

Note: The type can be unsigned, except for the graphs with reverse arcs where the ArcIndexType must be signed, but not necessarily the NodeIndexType.

NodeIndexType and ArcIndexType can be any integer type, but can also be strong integer types (e.g. StrongInt). Strong integer types are types that behave like integers (comparison, arithmetic, etc.), and are (explicitly) constructible/convertible from/to integers.

Definition at line 208 of file graph.h.

#include <graph.h>

Inheritance diagram for util::BaseGraph< NodeIndexType, ArcIndexType, HasNegativeReverseArcs >:

Public Types
typedef NodeIndexType	NodeIndex
typedef ArcIndexType	ArcIndex

Public Member Functions
	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_.
virtual void	ReserveNodes (NodeIndexType bound)
virtual void	ReserveArcs (ArcIndexType bound)
void	Reserve (NodeIndexType node_capacity, ArcIndexType arc_capacity)
void	FreezeCapacities ()

Static Public Attributes
static constexpr bool	kHasNegativeReverseArcs = HasNegativeReverseArcs
static constexpr NodeIndexType	kNilNode
static constexpr ArcIndexType	kNilArc

Protected Member Functions
void	ComputeCumulativeSum (internal::Vector< NodeIndexType, ArcIndexType > *v)
	Functions commented when defined because they are implementation details.
void	BuildStartAndForwardHead (internal::SVector< ArcIndexType, NodeIndexType > head, internal::Vector< NodeIndexType, ArcIndexType > start, std::vector< ArcIndexType > *permutation)

Protected Attributes
NodeIndexType	num_nodes_
NodeIndexType	node_capacity_
ArcIndexType	num_arcs_
ArcIndexType	arc_capacity_
bool	const_capacities_

Member Typedef Documentation

◆ ArcIndex

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t, bool HasNegativeReverseArcs = false>

typedef ArcIndexType util::BaseGraph< NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::ArcIndex

Definition at line 214 of file graph.h.

◆ NodeIndex

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t, bool HasNegativeReverseArcs = false>

typedef NodeIndexType util::BaseGraph< NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::NodeIndex

Typedef so you can use Graph::NodeIndex and Graph::ArcIndex to be generic but also to improve the readability of your code. We also recommend that you define a typedef ... Graph; for readability.

Definition at line 213 of file graph.h.

Constructor & Destructor Documentation

◆ BaseGraph() [1/2]

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t, bool HasNegativeReverseArcs = false>

util::BaseGraph< NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::BaseGraph ( )

inline

Definition at line 217 of file graph.h.

◆ BaseGraph() [2/2]

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t, bool HasNegativeReverseArcs = false>

util::BaseGraph< NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::BaseGraph ( const BaseGraph< NodeIndexType, ArcIndexType, HasNegativeReverseArcs > & )

default

◆ ~BaseGraph()

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t, bool HasNegativeReverseArcs = false>

virtual util::BaseGraph< NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::~BaseGraph ( )

virtualdefault

Member Function Documentation

◆ AllForwardArcs()

template<typename NodeIndexType, typename ArcIndexType, bool HasNegativeReverseArcs>

IntegerRange< ArcIndexType > util::BaseGraph< NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::AllForwardArcs ( ) const

Definition at line 1133 of file graph.h.

◆ AllNodes()

template<typename NodeIndexType, typename ArcIndexType, bool HasNegativeReverseArcs>

IntegerRange< NodeIndexType > util::BaseGraph< NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::AllNodes ( ) const

BaseGraph implementation -------------------------------------------------—.

Allows nice range-based for loop: for (const NodeIndex node : graph.AllNodes()) { ... } for (const ArcIndex arc : graph.AllForwardArcs()) { ... }

Definition at line 1126 of file graph.h.

◆ arc_capacity()

template<typename NodeIndexType, typename ArcIndexType, bool HasNegativeReverseArcs>

ArcIndexType util::BaseGraph< NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::arc_capacity ( ) const

Capacity reserved for future arcs, always >= num_arcs_.

Todo: (user): Same questions as the ones in node_capacity().

Definition at line 1150 of file graph.h.

◆ BuildStartAndForwardHead()

template<typename NodeIndexType, typename ArcIndexType, bool HasNegativeReverseArcs>

void util::BaseGraph< NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::BuildStartAndForwardHead	(	internal::SVector< ArcIndexType, NodeIndexType > *	head,
		internal::Vector< NodeIndexType, ArcIndexType > *	start,
		std::vector< ArcIndexType > *	permutation )

protected

Given the tail of arc #i in (*head)[i] and the head of arc #i in (*head)[~i]

Reorder the arc by increasing tail.
Put the head of the new arc #i in (*head)[i].
Put in start[i] the index of the first arc with tail >= i.
Update "permutation" to reflect the change, unless it is NULL.

Computes the outgoing degree of each nodes and check if we need to permute something or not. Note that the tails are currently stored in the positive range of the SVector head.

Abort early if we do not need the permutation: we only need to put the heads in the positive range.

Computes the forward arc permutation.

Note: this temporarily alters the start vector.

Restore in (*start)[i] the index of the first arc with tail >= i.

Permutes the head into their final position in head. We do not need the tails anymore at this point.

Definition at line 1190 of file graph.h.

◆ ComputeCumulativeSum()

template<typename NodeIndexType, typename ArcIndexType, bool HasNegativeReverseArcs>

void util::BaseGraph< NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::ComputeCumulativeSum ( internal::Vector< NodeIndexType, ArcIndexType > * v )

protected

Functions commented when defined because they are implementation details.

Computes the cumulative sum of the entry in v. We only use it with in/out degree distribution, hence the Check() at the end.

Definition at line 1170 of file graph.h.

◆ FreezeCapacities()

template<typename NodeIndexType, typename ArcIndexType, bool HasNegativeReverseArcs>

void util::BaseGraph< NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::FreezeCapacities ( )

FreezeCapacities() makes any future attempt to change the graph capacities crash in DEBUG mode.

Todo: (user): Only define this in debug mode at the cost of having a lot of ifndef NDEBUG all over the place? remove the function completely ?

Definition at line 1158 of file graph.h.

◆ IsArcValid()

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t, bool HasNegativeReverseArcs = false>

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.

◆ IsNodeValid()

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t, bool HasNegativeReverseArcs = false>

bool util::BaseGraph< NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::IsNodeValid ( NodeIndexType node ) const

inline

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

Definition at line 243 of file graph.h.

◆ node_capacity()

template<typename NodeIndexType, typename ArcIndexType, bool HasNegativeReverseArcs>

NodeIndexType util::BaseGraph< NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::node_capacity ( ) const

Capacity reserved for future nodes, always >= num_nodes_.

Todo: (user): Is it needed? remove completely? return the real capacities at the cost of having a different implementation for each graphs?

Definition at line 1141 of file graph.h.

◆ num_arcs()

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t, bool HasNegativeReverseArcs = false>

ArcIndexType util::BaseGraph< NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::num_arcs ( ) const

inline

Returns the number of valid arcs in the graph.

Definition at line 234 of file graph.h.

◆ num_nodes()

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t, bool HasNegativeReverseArcs = false>

NodeIndexType util::BaseGraph< NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::num_nodes ( ) const

inline

Returns the number of valid nodes in the graph. Prefer using num_nodes(): the size() API is here to make Graph and vector<vector<int>> more alike.

Definition at line 230 of file graph.h.

◆ operator=()

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t, bool HasNegativeReverseArcs = false>

BaseGraph & util::BaseGraph< NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::operator= ( const BaseGraph< NodeIndexType, ArcIndexType, HasNegativeReverseArcs > & )

default

◆ Reserve()

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t, bool HasNegativeReverseArcs = false>

void util::BaseGraph< NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::Reserve	(	NodeIndexType	node_capacity,
		ArcIndexType	arc_capacity )

inline

Definition at line 278 of file graph.h.

◆ ReserveArcs()

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t, bool HasNegativeReverseArcs = false>

virtual void util::BaseGraph< NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::ReserveArcs ( ArcIndexType bound )

inlinevirtual

Reimplemented in util::ReverseArcStaticGraph< NodeIndex, ArcIndex >.

Definition at line 272 of file graph.h.

◆ ReserveNodes()

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t, bool HasNegativeReverseArcs = false>

virtual void util::BaseGraph< NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::ReserveNodes ( NodeIndexType bound )

inlinevirtual

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.

Definition at line 266 of file graph.h.

◆ size()

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t, bool HasNegativeReverseArcs = false>

NodeIndexType util::BaseGraph< NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::size ( ) const

inline

Definition at line 231 of file graph.h.

Member Data Documentation

◆ arc_capacity_

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t, bool HasNegativeReverseArcs = false>

ArcIndexType util::BaseGraph< NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::arc_capacity_

protected

Definition at line 307 of file graph.h.

◆ const_capacities_

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t, bool HasNegativeReverseArcs = false>

bool util::BaseGraph< NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::const_capacities_

protected

Definition at line 308 of file graph.h.

◆ kHasNegativeReverseArcs

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t, bool HasNegativeReverseArcs = false>

bool util::BaseGraph< NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::kHasNegativeReverseArcs = HasNegativeReverseArcs

staticconstexpr

Definition at line 215 of file graph.h.

◆ kNilArc

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t, bool HasNegativeReverseArcs = false>

ArcIndexType util::BaseGraph< NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::kNilArc

staticconstexpr

Initial value:

=

std::numeric_limits<ArcIndexType>::max()

Definition at line 293 of file graph.h.

◆ kNilNode

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t, bool HasNegativeReverseArcs = false>

NodeIndexType util::BaseGraph< NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::kNilNode

staticconstexpr

Initial value:

=

std::numeric_limits<NodeIndexType>::max()

Constants that will never be a valid node or arc. They are the maximum possible node and arc capacity.

Definition at line 290 of file graph.h.

◆ node_capacity_

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t, bool HasNegativeReverseArcs = false>

NodeIndexType util::BaseGraph< NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::node_capacity_

protected

Definition at line 305 of file graph.h.

◆ num_arcs_

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t, bool HasNegativeReverseArcs = false>

ArcIndexType util::BaseGraph< NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::num_arcs_

protected

Definition at line 306 of file graph.h.

◆ num_nodes_

template<typename NodeIndexType = int32_t, typename ArcIndexType = int32_t, bool HasNegativeReverseArcs = false>

NodeIndexType util::BaseGraph< NodeIndexType, ArcIndexType, HasNegativeReverseArcs >::num_nodes_

protected

Definition at line 304 of file graph.h.

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

ortools/graph/graph.h

Detailed Description

Public Types

Public Member Functions

Static Public Attributes

Protected Member Functions

Protected Attributes

Member Typedef Documentation

◆ ArcIndex

◆ NodeIndex

Constructor & Destructor Documentation

◆ BaseGraph() [1/2]

◆ BaseGraph() [2/2]

◆ ~BaseGraph()

Member Function Documentation

◆ AllForwardArcs()

◆ AllNodes()

◆ arc_capacity()

◆ BuildStartAndForwardHead()

◆ ComputeCumulativeSum()

◆ FreezeCapacities()

◆ IsArcValid()

◆ IsNodeValid()

◆ node_capacity()

◆ num_arcs()

◆ num_nodes()

◆ operator=()

◆ Reserve()

◆ ReserveArcs()

◆ ReserveNodes()

◆ size()

Member Data Documentation

◆ arc_capacity_

◆ const_capacities_

◆ kHasNegativeReverseArcs

◆ kNilArc

◆ kNilNode

◆ node_capacity_

◆ num_arcs_

◆ num_nodes_