#include <ebert_graph.h>

Inheritance diagram for operations_research::EbertGraphBase< NodeIndexType, ArcIndexType, DerivedGraph >:

Classes
class	CycleHandlerForAnnotatedArcs

Public Member Functions
bool	Reserve (NodeIndexType new_max_num_nodes, ArcIndexType new_max_num_arcs)

ArcIndexType	AddArc (NodeIndexType tail, NodeIndexType head)

template<typename ArcIndexTypeStrictWeakOrderingFunctor >
void	GroupForwardArcsByFunctor (const ArcIndexTypeStrictWeakOrderingFunctor &compare, PermutationCycleHandler< ArcIndexType > *annotation_handler)

ArcIndexType	end_arc_index () const

bool	IsNodeValid (NodeIndexType node) const

Public Member Functions inherited from operations_research::StarGraphBase< NodeIndexType, ArcIndexType, DerivedGraph >
NodeIndexType	num_nodes () const
	Returns the number of nodes in the graph.

ArcIndexType	num_arcs () const

NodeIndexType	end_node_index () const

ArcIndexType	end_arc_index () const

NodeIndexType	max_num_nodes () const
	Returns the maximum possible number of nodes in the graph.

ArcIndexType	max_num_arcs () const

NodeIndexType	max_end_node_index () const

ArcIndexType	max_end_arc_index () const

bool	IsNodeValid (NodeIndexType node) const

ArcIndexType	LookUpArc (const NodeIndexType tail, const NodeIndexType head) const

NodeIndexType	Head (const ArcIndexType arc) const
	Returns the head or end-node of arc.

std::string	NodeDebugString (const NodeIndexType node) const

std::string	ArcDebugString (const ArcIndexType arc) const

Static Public Attributes
static const ArcIndexType	kFirstArc
	The index of the first arc in the graph.

static const NodeIndexType	kFirstNode
	The index of the first node in the graph.

static const ArcIndexType	kMaxNumArcs

static const NodeIndexType	kMaxNumNodes
	The maximum possible node index in the graph.

static const ArcIndexType	kNilArc
	The index of the 'nil' arc in the graph.

static const NodeIndexType	kNilNode
	The index of the 'nil' node in the graph.

Static Public Attributes inherited from operations_research::StarGraphBase< NodeIndexType, ArcIndexType, DerivedGraph >
static const NodeIndexType	kNilNode = -1
	The index of the 'nil' node in the graph.

static const ArcIndexType	kNilArc
	The index of the 'nil' arc in the graph.

static const NodeIndexType	kFirstNode = 0
	The index of the first node in the graph.

static const ArcIndexType	kFirstArc = 0
	The index of the first arc in the graph.

static const NodeIndexType	kMaxNumNodes
	The maximum possible node index in the graph.

static const ArcIndexType	kMaxNumArcs

Protected Member Functions
	EbertGraphBase ()

	~EbertGraphBase ()

void	Initialize (NodeIndexType max_num_nodes, ArcIndexType max_num_arcs)

ArcIndexType	FirstOutgoingOrOppositeIncomingArc (const NodeIndexType node) const
	Returns the first arc in node's incidence list.

ArcIndexType	NextAdjacentArc (const ArcIndexType arc) const
	Returns the next arc following the passed argument in its adjacency list.

ArcIndexType	NextOutgoingArc (const NodeIndexType unused_node, const ArcIndexType arc) const
	Returns the outgoing arc following the argument in the adjacency list.

Protected Member Functions inherited from operations_research::StarGraphBase< NodeIndexType, ArcIndexType, DerivedGraph >
	StarGraphBase ()

	~StarGraphBase ()

NodeIndexType	StartNode (NodeIndexType node) const

ArcIndexType	StartArc (ArcIndexType arc) const

NodeIndexType	NextNode (const NodeIndexType node) const

ArcIndexType	NextArc (const ArcIndexType arc) const

ArcIndexType	FirstOutgoingArc (const NodeIndexType node) const
	Returns the first outgoing arc for node.

Protected Attributes
ZVector< ArcIndexType >	next_adjacent_arc_

bool	representation_clean_

ZVector< ArcIndexType >	first_incident_arc_

ZVector< NodeIndexType >	head_
	Array of node indices. head_[i] contains the head node of arc i.

ArcIndexType	max_num_arcs_
	The maximum number of arcs that the graph can hold.

NodeIndexType	max_num_nodes_
	The maximum number of nodes that the graph can hold.

ArcIndexType	num_arcs_
	The current number of arcs held by the graph.

NodeIndexType	num_nodes_
	The maximum index of the node currently held by the graph.

Protected Attributes inherited from operations_research::StarGraphBase< NodeIndexType, ArcIndexType, DerivedGraph >
NodeIndexType	max_num_nodes_
	The maximum number of nodes that the graph can hold.

ArcIndexType	max_num_arcs_
	The maximum number of arcs that the graph can hold.

NodeIndexType	num_nodes_
	The maximum index of the node currently held by the graph.

ArcIndexType	num_arcs_
	The current number of arcs held by the graph.

ZVector< NodeIndexType >	head_
	Array of node indices. head_[i] contains the head node of arc i.

ZVector< ArcIndexType >	first_incident_arc_

Friends
class	StarGraphBase< NodeIndexType, ArcIndexType, DerivedGraph >

Detailed Description

template<typename NodeIndexType, typename ArcIndexType, typename DerivedGraph>
class operations_research::EbertGraphBase< NodeIndexType, ArcIndexType, DerivedGraph >

A template for the base class that holds the functionality that exists in common between the EbertGraph<> template and the ForwardEbertGraph<> template.

This template is for internal use only, and this is enforced by making all constructors for this class template protected. Clients should use one of the two derived-class templates. Most clients will not even use those directly, but will use the StarGraph and ForwardStarGraph typenames declared above.

The DerivedGraph template argument must be the type of the class (typically itself built from a template) that:

implements the full interface expected for either ForwardEbertGraph or EbertGraph, and
inherits from an instance of this template. The base class needs access to some members of the derived class such as, for example, NextOutgoingArc(), and it gets this access via the DerivedGraph template argument.

Definition at line 950 of file ebert_graph.h.

Constructor & Destructor Documentation

◆ EbertGraphBase()

template<typename NodeIndexType , typename ArcIndexType , typename DerivedGraph >

operations_research::EbertGraphBase< NodeIndexType, ArcIndexType, DerivedGraph >::EbertGraphBase ( )

inlineprotected

Definition at line 1113 of file ebert_graph.h.

◆ ~EbertGraphBase()

template<typename NodeIndexType , typename ArcIndexType , typename DerivedGraph >

operations_research::EbertGraphBase< NodeIndexType, ArcIndexType, DerivedGraph >::~EbertGraphBase ( )

inlineprotected

Definition at line 1115 of file ebert_graph.h.

Member Function Documentation

◆ AddArc()

template<typename NodeIndexType , typename ArcIndexType , typename DerivedGraph >

ArcIndexType operations_research::EbertGraphBase< NodeIndexType, ArcIndexType, DerivedGraph >::AddArc	(	NodeIndexType	tail,
		NodeIndexType	head )

inline

Adds an arc to the graph and returns its index. Returns kNilArc if the arc could not be added.

Note: for a given pair (tail, head) AddArc does not overwrite an already-existing arc between tail and head: Another arc is created instead. This makes it possible to handle multi-graphs.

Definition at line 1003 of file ebert_graph.h.

◆ end_arc_index()

template<typename NodeIndexType , typename ArcIndexType , typename DerivedGraph >

ArcIndexType operations_research::StarGraphBase< NodeIndexType, ArcIndexType, DerivedGraph >::end_arc_index ( ) const

inline

Returns one more than the largest index of an extant direct arc. To be used as a helper when clients need to dimension or iterate over arrays of arc annotation information.

Definition at line 251 of file ebert_graph.h.

◆ FirstOutgoingOrOppositeIncomingArc()

template<typename NodeIndexType , typename ArcIndexType , typename DerivedGraph >

ArcIndexType operations_research::EbertGraphBase< NodeIndexType, ArcIndexType, DerivedGraph >::FirstOutgoingOrOppositeIncomingArc ( const NodeIndexType node ) const

inlineprotected

Returns the first arc in node's incidence list.

Definition at line 1128 of file ebert_graph.h.

◆ GroupForwardArcsByFunctor()

template<typename NodeIndexType , typename ArcIndexType , typename DerivedGraph >

template<typename ArcIndexTypeStrictWeakOrderingFunctor >

void operations_research::EbertGraphBase< NodeIndexType, ArcIndexType, DerivedGraph >::GroupForwardArcsByFunctor	(	const ArcIndexTypeStrictWeakOrderingFunctor &	compare,
		PermutationCycleHandler< ArcIndexType > *	annotation_handler )

inline

Todo: (user): Configure SWIG to handle the GroupForwardArcsByFunctor member template and the CycleHandlerForAnnotatedArcs class.

Determine the permutation that groups arcs by their tail nodes.

Start with the identity permutation.

Now we actually permute the head_ array and the scaled_arc_cost_ array according to the sorting permutation.

Finally, rebuild the graph from its permuted head_ array.

Definition at line 1024 of file ebert_graph.h.

◆ Initialize()

template<typename NodeIndexType , typename ArcIndexType , typename DerivedGraph >

void operations_research::EbertGraphBase< NodeIndexType, ArcIndexType, DerivedGraph >::Initialize	(	NodeIndexType	max_num_nodes,
		ArcIndexType	max_num_arcs )

inlineprotected

Definition at line 1117 of file ebert_graph.h.

◆ IsNodeValid()

template<typename NodeIndexType , typename ArcIndexType , typename DerivedGraph >

bool operations_research::StarGraphBase< NodeIndexType, ArcIndexType, DerivedGraph >::IsNodeValid ( NodeIndexType node ) const

inline

Utility function to check that a node index is within the bounds AND different from kNilNode. Returns true if node is in the range [kFirstNode .. max_num_nodes_). It is exported so that users of the DerivedGraph class can use it. To be used in a DCHECK; also used internally to validate arguments passed to our methods from clients (e.g., AddArc()).

Definition at line 278 of file ebert_graph.h.

◆ NextAdjacentArc()

template<typename NodeIndexType , typename ArcIndexType , typename DerivedGraph >

ArcIndexType operations_research::EbertGraphBase< NodeIndexType, ArcIndexType, DerivedGraph >::NextAdjacentArc ( const ArcIndexType arc ) const

inlineprotected

Returns the next arc following the passed argument in its adjacency list.

Definition at line 1136 of file ebert_graph.h.

◆ NextOutgoingArc()

template<typename NodeIndexType , typename ArcIndexType , typename DerivedGraph >

ArcIndexType operations_research::EbertGraphBase< NodeIndexType, ArcIndexType, DerivedGraph >::NextOutgoingArc	(	const NodeIndexType	unused_node,
		const ArcIndexType	arc ) const

inlineprotected

Returns the outgoing arc following the argument in the adjacency list.

Definition at line 1143 of file ebert_graph.h.

◆ Reserve()

template<typename NodeIndexType , typename ArcIndexType , typename DerivedGraph >

bool operations_research::EbertGraphBase< NodeIndexType, ArcIndexType, DerivedGraph >::Reserve	(	NodeIndexType	new_max_num_nodes,
		ArcIndexType	new_max_num_arcs )

inline

Reserves memory needed for max_num_nodes nodes and max_num_arcs arcs. Returns false if the parameters passed are not OK. It can be used to enlarge the graph, but does not shrink memory if called with smaller values.

Definition at line 980 of file ebert_graph.h.

Friends And Related Symbol Documentation

◆ StarGraphBase< NodeIndexType, ArcIndexType, DerivedGraph >

template<typename NodeIndexType , typename ArcIndexType , typename DerivedGraph >

friend class StarGraphBase< NodeIndexType, ArcIndexType, DerivedGraph >

friend

Definition at line 952 of file ebert_graph.h.

Member Data Documentation

◆ first_incident_arc_

template<typename NodeIndexType , typename ArcIndexType , typename DerivedGraph >

ZVector<ArcIndexType> operations_research::StarGraphBase< NodeIndexType, ArcIndexType, DerivedGraph >::first_incident_arc_

protected

Array of arc indices. first_incident_arc_[i] contains the first arc incident to node i.

Definition at line 501 of file ebert_graph.h.

◆ head_

template<typename NodeIndexType , typename ArcIndexType , typename DerivedGraph >

ZVector<NodeIndexType> operations_research::StarGraphBase< NodeIndexType, ArcIndexType, DerivedGraph >::head_

protected

Array of node indices. head_[i] contains the head node of arc i.

Definition at line 497 of file ebert_graph.h.

◆ kFirstArc

template<typename NodeIndexType , typename ArcIndexType , typename DerivedGraph >

const ArcIndexType operations_research::StarGraphBase< NodeIndexType, ArcIndexType, DerivedGraph >::kFirstArc

static

The index of the first arc in the graph.

Definition at line 224 of file ebert_graph.h.

◆ kFirstNode

template<typename NodeIndexType , typename ArcIndexType , typename DerivedGraph >

const NodeIndexType operations_research::StarGraphBase< NodeIndexType, ArcIndexType, DerivedGraph >::kFirstNode

static

The index of the first node in the graph.

Definition at line 221 of file ebert_graph.h.

◆ kMaxNumArcs

template<typename NodeIndexType , typename ArcIndexType , typename DerivedGraph >

const ArcIndexType operations_research::StarGraphBase< NodeIndexType, ArcIndexType, DerivedGraph >::kMaxNumArcs

static

The maximum possible number of arcs in the graph. (The maximum index is kMaxNumArcs-1, since indices start at 0. Unfortunately we waste a value representing this and the max_num_arcs_ member.)

The maximum possible number of arcs in the graph. (The maximum index is kMaxNumArcs-1, since indices start at 0.)

Definition at line 234 of file ebert_graph.h.

◆ kMaxNumNodes

template<typename NodeIndexType , typename ArcIndexType , typename DerivedGraph >

const NodeIndexType operations_research::StarGraphBase< NodeIndexType, ArcIndexType, DerivedGraph >::kMaxNumNodes

static

The maximum possible node index in the graph.

The maximum possible number of nodes in the graph. (The maximum index is kMaxNumNodes-1, since indices start at 0. Unfortunately we waste a value representing this and the max_num_nodes_ member.)

Definition at line 229 of file ebert_graph.h.

◆ kNilArc

template<typename NodeIndexType , typename ArcIndexType , typename DerivedGraph >

const ArcIndexType operations_research::StarGraphBase< NodeIndexType, ArcIndexType, DerivedGraph >::kNilArc

static

The index of the 'nil' arc in the graph.

Definition at line 218 of file ebert_graph.h.

◆ kNilNode

template<typename NodeIndexType , typename ArcIndexType , typename DerivedGraph >

const NodeIndexType operations_research::StarGraphBase< NodeIndexType, ArcIndexType, DerivedGraph >::kNilNode

static

The index of the 'nil' node in the graph.

Definition at line 215 of file ebert_graph.h.

◆ max_num_arcs_

template<typename NodeIndexType , typename ArcIndexType , typename DerivedGraph >

ArcIndexType operations_research::StarGraphBase< NodeIndexType, ArcIndexType, DerivedGraph >::max_num_arcs_

protected

The maximum number of arcs that the graph can hold.

Definition at line 488 of file ebert_graph.h.

◆ max_num_nodes_

template<typename NodeIndexType , typename ArcIndexType , typename DerivedGraph >

NodeIndexType operations_research::StarGraphBase< NodeIndexType, ArcIndexType, DerivedGraph >::max_num_nodes_

protected

The maximum number of nodes that the graph can hold.

Definition at line 485 of file ebert_graph.h.

◆ next_adjacent_arc_

template<typename NodeIndexType , typename ArcIndexType , typename DerivedGraph >

ZVector<ArcIndexType> operations_research::EbertGraphBase< NodeIndexType, ArcIndexType, DerivedGraph >::next_adjacent_arc_

protected

Array of next indices. next_adjacent_arc_[i] contains the next arc in the adjacency list of arc i.

Definition at line 1152 of file ebert_graph.h.

◆ num_arcs_

template<typename NodeIndexType , typename ArcIndexType , typename DerivedGraph >

ArcIndexType operations_research::StarGraphBase< NodeIndexType, ArcIndexType, DerivedGraph >::num_arcs_

protected

The current number of arcs held by the graph.

Definition at line 494 of file ebert_graph.h.

◆ num_nodes_

template<typename NodeIndexType , typename ArcIndexType , typename DerivedGraph >

NodeIndexType operations_research::StarGraphBase< NodeIndexType, ArcIndexType, DerivedGraph >::num_nodes_

protected

The maximum index of the node currently held by the graph.

Definition at line 491 of file ebert_graph.h.

◆ representation_clean_

template<typename NodeIndexType , typename ArcIndexType , typename DerivedGraph >

bool operations_research::EbertGraphBase< NodeIndexType, ArcIndexType, DerivedGraph >::representation_clean_

protected

Flag to indicate that BuildRepresentation() needs to be called before the adjacency lists are examined. Only for DCHECK in debug builds.

Definition at line 1157 of file ebert_graph.h.

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

ortools/graph/ebert_graph.h

Classes

Public Member Functions

Static Public Attributes

Protected Member Functions

Protected Attributes

Friends

Detailed Description

Constructor & Destructor Documentation

◆ EbertGraphBase()

◆ ~EbertGraphBase()

Member Function Documentation

◆ AddArc()

◆ end_arc_index()

◆ FirstOutgoingOrOppositeIncomingArc()

◆ GroupForwardArcsByFunctor()

◆ Initialize()

◆ IsNodeValid()

◆ NextAdjacentArc()

◆ NextOutgoingArc()

◆ Reserve()

Friends And Related Symbol Documentation

◆ StarGraphBase< NodeIndexType, ArcIndexType, DerivedGraph >

Member Data Documentation

◆ first_incident_arc_

◆ head_

◆ kFirstArc

◆ kFirstNode

◆ kMaxNumArcs

◆ kMaxNumNodes

◆ kNilArc

◆ kNilNode

◆ max_num_arcs_

◆ max_num_nodes_

◆ next_adjacent_arc_

◆ num_arcs_

◆ num_nodes_

◆ representation_clean_