#include <ebert_graph.h>

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

Classes
class	ArcIterator
	Iterator class for traversing the arcs in the graph. More...

class	NodeIterator
	Iterator class for traversing all the nodes in the graph. More...

class	OutgoingArcIterator
	Iterator class for traversing the outgoing arcs associated to a given node. More...

Public Member Functions
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 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
	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
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_

Detailed Description

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

Definition at line 212 of file ebert_graph.h.

Constructor & Destructor Documentation

◆ StarGraphBase()

template<typename NodeIndexType , typename ArcIndexType , typename DerivedGraph >

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

inlineprotected

Definition at line 426 of file ebert_graph.h.

◆ ~StarGraphBase()

template<typename NodeIndexType , typename ArcIndexType , typename DerivedGraph >

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

inlineprotected

Definition at line 433 of file ebert_graph.h.

Member Function Documentation

◆ ArcDebugString()

template<typename NodeIndexType , typename ArcIndexType , typename DerivedGraph >

std::string operations_research::StarGraphBase< NodeIndexType, ArcIndexType, DerivedGraph >::ArcDebugString ( const ArcIndexType arc ) const

inline

Definition at line 309 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.

◆ end_node_index()

template<typename NodeIndexType , typename ArcIndexType , typename DerivedGraph >

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

inline

Returns one more than the largest index of an extant node, meaning a node that is mentioned as the head or tail of some arc in the graph. To be used as a helper when clients need to dimension or iterate over arrays of node annotation information.

Definition at line 246 of file ebert_graph.h.

◆ FirstOutgoingArc()

template<typename NodeIndexType , typename ArcIndexType , typename DerivedGraph >

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

inlineprotected

Returns the first outgoing arc for node.

Definition at line 478 of file ebert_graph.h.

◆ Head()

template<typename NodeIndexType , typename ArcIndexType , typename DerivedGraph >

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

inline

Returns the head or end-node of arc.

Definition at line 296 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.

◆ LookUpArc()

template<typename NodeIndexType , typename ArcIndexType , typename DerivedGraph >

ArcIndexType operations_research::StarGraphBase< NodeIndexType, ArcIndexType, DerivedGraph >::LookUpArc	(	const NodeIndexType	tail,
		const NodeIndexType	head ) const

inline

Returns the first arc going from tail to head, if it exists, or kNilArc if such an arc does not exist.

Definition at line 284 of file ebert_graph.h.

◆ max_end_arc_index()

template<typename NodeIndexType , typename ArcIndexType , typename DerivedGraph >

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

inline

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

Definition at line 270 of file ebert_graph.h.

◆ max_end_node_index()

template<typename NodeIndexType , typename ArcIndexType , typename DerivedGraph >

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

inline

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

Definition at line 263 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 ( ) const

inline

Returns the maximum possible number of original arcs in the graph. (The ones with positive indices.)

Definition at line 258 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 ( ) const

inline

Returns the maximum possible number of nodes in the graph.

Definition at line 254 of file ebert_graph.h.

◆ NextArc()

template<typename NodeIndexType , typename ArcIndexType , typename DerivedGraph >

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

inlineprotected

Returns the arc following the argument in the graph. Returns kNilArc (= end) if the range of arcs has been exhausted. It is called by ArcIterator::Next() and as such does not expect to be passed an argument equal to kNilArc. This is why the return line is simplified from return ( arc == kNilArc || next_arc >= num_arcs_) ? kNilArc : next_arc; to return next_arc < num_arcs_ ? next_arc : kNilArc;

Definition at line 471 of file ebert_graph.h.

◆ NextNode()

template<typename NodeIndexType , typename ArcIndexType , typename DerivedGraph >

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

inlineprotected

Returns the node following the argument in the graph. Returns kNilNode (= end) if the range of nodes has been exhausted. It is called by NodeIterator::Next() and as such does not expect to be passed an argument equal to kNilNode. This is why the return line is simplified from return (node == kNilNode || next_node >= num_nodes_) ? kNilNode : next_node; to return next_node < num_nodes_ ? next_node : kNilNode;

Definition at line 457 of file ebert_graph.h.

◆ NodeDebugString()

template<typename NodeIndexType , typename ArcIndexType , typename DerivedGraph >

std::string operations_research::StarGraphBase< NodeIndexType, ArcIndexType, DerivedGraph >::NodeDebugString ( const NodeIndexType node ) const

inline

Definition at line 301 of file ebert_graph.h.

◆ num_arcs()

template<typename NodeIndexType , typename ArcIndexType , typename DerivedGraph >

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

inline

Returns the number of original arcs in the graph (The ones with positive indices.)

Definition at line 240 of file ebert_graph.h.

◆ num_nodes()

template<typename NodeIndexType , typename ArcIndexType , typename DerivedGraph >

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

inline

Returns the number of nodes in the graph.

Definition at line 236 of file ebert_graph.h.

◆ StartArc()

template<typename NodeIndexType , typename ArcIndexType , typename DerivedGraph >

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

inlineprotected

Returns kNilArc if the graph has no arcs arc if it has at least one arc. Useful for initializing iterators correctly in the case of empty graphs.

Definition at line 444 of file ebert_graph.h.

◆ StartNode()

template<typename NodeIndexType , typename ArcIndexType , typename DerivedGraph >

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

inlineprotected

Returns kNilNode if the graph has no nodes or node if it has at least one node. Useful for initializing iterators correctly in the case of empty graphs.

Definition at line 438 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 = 0

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 = 0

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

Initial value:

=

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

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

Initial value:

=

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

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

Initial value:

=

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

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 = -1

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.

◆ 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.

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

Detailed Description

Constructor & Destructor Documentation

◆ StarGraphBase()

◆ ~StarGraphBase()

Member Function Documentation

◆ ArcDebugString()

◆ end_arc_index()

◆ end_node_index()

◆ FirstOutgoingArc()

◆ Head()

◆ IsNodeValid()

◆ LookUpArc()

◆ max_end_arc_index()

◆ max_end_node_index()

◆ max_num_arcs()

◆ max_num_nodes()

◆ NextArc()

◆ NextNode()

◆ NodeDebugString()

◆ num_arcs()

◆ num_nodes()

◆ StartArc()

◆ StartNode()

Member Data Documentation

◆ first_incident_arc_

◆ head_

◆ kFirstArc

◆ kFirstNode

◆ kMaxNumArcs

◆ kMaxNumNodes

◆ kNilArc

◆ kNilNode

◆ max_num_arcs_

◆ max_num_nodes_

◆ num_arcs_

◆ num_nodes_