#include <ebert_graph.h>

Inheritance diagram for operations_research::ForwardStaticGraph< NodeIndexType, ArcIndexType >:

Classes
class	CycleHandlerForAnnotatedArcs

Public Types
typedef NodeIndexType	NodeIndex

typedef ArcIndexType	ArcIndex

Public Member Functions
	ForwardStaticGraph (const NodeIndexType num_nodes, const ArcIndexType num_arcs, const bool sort_arcs_by_head, std::vector< std::pair< NodeIndexType, NodeIndexType > > client_input_arcs, operations_research::PermutationCycleHandler< ArcIndexType > const client_cycle_handler)

NodeIndexType	Tail (const ArcIndexType arc) const
	Returns the tail or start-node of arc.

bool	IsIncoming (ArcIndexType arc, NodeIndexType node) const
	Returns true if arc is incoming to node.

bool	CheckArcBounds (const ArcIndexType arc) const

bool	CheckArcValidity (const ArcIndexType arc) const

bool	CheckTailIndexValidity (const ArcIndexType arc) const
	Returns true if arc is a valid index into the (*tail_) array.

ArcIndexType	NextOutgoingArc (const NodeIndexType node, ArcIndexType arc) const

std::string	DebugString () const

bool	BuildTailArray ()

void	ReleaseTailArray ()

bool	TailArrayComplete () const
	To be used in a DCHECK().

Public Member Functions inherited from operations_research::StarGraphBase< NodeIndexType, ArcIndexType, ForwardStaticGraph< NodeIndexType, ArcIndexType > >
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

Friends
class	StarGraphBase< NodeIndexType, ArcIndexType, ForwardStaticGraph< NodeIndexType, ArcIndexType > >

Additional Inherited Members
Static Public Attributes inherited from operations_research::StarGraphBase< NodeIndexType, ArcIndexType, ForwardStaticGraph< NodeIndexType, ArcIndexType > >
static const NodeIndexType	kNilNode
	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
	The index of the first node in the graph.

static const ArcIndexType	kFirstArc
	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 inherited from operations_research::StarGraphBase< NodeIndexType, ArcIndexType, ForwardStaticGraph< NodeIndexType, ArcIndexType > >
	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 inherited from operations_research::StarGraphBase< NodeIndexType, ArcIndexType, ForwardStaticGraph< NodeIndexType, ArcIndexType > >
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>
class operations_research::ForwardStaticGraph< NodeIndexType, ArcIndexType >

Definition at line 533 of file ebert_graph.h.

Member Typedef Documentation

◆ ArcIndex

template<typename NodeIndexType , typename ArcIndexType >

ArcIndexType operations_research::ForwardStaticGraph< NodeIndexType, ArcIndexType >::ArcIndex

Definition at line 564 of file ebert_graph.h.

◆ NodeIndex

template<typename NodeIndexType , typename ArcIndexType >

NodeIndexType operations_research::ForwardStaticGraph< NodeIndexType, ArcIndexType >::NodeIndex

Definition at line 563 of file ebert_graph.h.

Constructor & Destructor Documentation

◆ ForwardStaticGraph()

template<typename NodeIndexType , typename ArcIndexType >

operations_research::ForwardStaticGraph< NodeIndexType, ArcIndexType >::ForwardStaticGraph	(	const NodeIndexType	num_nodes,
		const ArcIndexType	num_arcs,
		const bool	sort_arcs_by_head,
		std::vector< std::pair< NodeIndexType, NodeIndexType > > *	client_input_arcs,
		operations_research::PermutationCycleHandler< ArcIndexType > *const	client_cycle_handler )

inline

Constructor for use by GraphBuilderFromArcs instances and direct clients that want to materialize a graph in one step. Materializing all at once is the only choice available with a static graph.

Args: sort_arcs_by_head: determines whether arcs incident to each tail node are sorted by head node. client_cycle_handler: if non-NULL, mediates the permutation of arbitrary annotation data belonging to the client according to the permutation applied to the arcs in forming the graph. Two permutations may be composed to form the final one that affects the arcs. First, the arcs are always permuted to group them by tail node because ForwardStaticGraph requires this. Second, if each node's outgoing arcs are sorted by head node (according to sort_arcs_by_head), that sorting implies an additional permutation on the arcs.

A more convenient name for a parameter required by style to be a pointer, because we modify its referent.

We coopt the first_incident_arc_ array as a node-indexed vector used for two purposes related to degree before setting up its final values. First, it counts the out-degree of each node. Second, it is reused to count the number of arcs outgoing from each node that have already been put in place from the given input_arcs. We reserve an extra entry as a sentinel at the end.

Take this opportunity to see how many nodes are really mentioned in the arc list.

The head_ entry will get permuted into the right place later.

We reuse the input_arcs[].first entries to hold our mapping to the head_ array. This allows us to spread out cache badness.

We cannot reuse the input_arcs[].first entries so we map to the head_ array in a single loop.

Shift the entries in first_incident_arc_ to compensate for the counting each one has done through its incident arcs. Note that there is a special sentry element at the end of first_incident_arc_.

The second argument in the following has a strange index expression because ZVector claims that no index is valid unless it refers to an element in the vector. In particular an index one past the end is invalid.

Apply the computed permutation if we haven't already.

We use a permutation cycle handler to place the head array indices and permute the client's arc annotation data along with them.

Parameters

client_cycle_handler

Todo: (user): For some reason, SWIG breaks if the operations_research namespace is not explicit in the following argument declaration.

Definition at line 623 of file ebert_graph.h.

Member Function Documentation

◆ BuildTailArray()

template<typename NodeIndexType , typename ArcIndexType >

bool operations_research::ForwardStaticGraph< NodeIndexType, ArcIndexType >::BuildTailArray ( )

inline

If (*tail_) is already allocated, we have the invariant that its contents are canonical, so we do not need to do anything here in that case except return true.

We have been asked to build the (*tail_) array, but we have no valid information from which to build it. The graph is in an unrecoverable, inconsistent state.

Reallocate (*tail_) and rebuild its contents from the adjacency lists.

Definition at line 818 of file ebert_graph.h.

◆ CheckArcBounds()

template<typename NodeIndexType , typename ArcIndexType >

bool operations_research::ForwardStaticGraph< NodeIndexType, ArcIndexType >::CheckArcBounds ( const ArcIndexType arc ) const

inline

Utility function to check that an arc index is within the bounds. It is exported so that users of the ForwardStaticGraph class can use it. To be used in a DCHECK.

Definition at line 772 of file ebert_graph.h.

◆ CheckArcValidity()

template<typename NodeIndexType , typename ArcIndexType >

bool operations_research::ForwardStaticGraph< NodeIndexType, ArcIndexType >::CheckArcValidity ( const ArcIndexType arc ) const

inline

Utility function to check that an arc index is within the bounds AND different from kNilArc. It is exported so that users of the ForwardStaticGraph class can use it. To be used in a DCHECK.

Definition at line 780 of file ebert_graph.h.

◆ CheckTailIndexValidity()

template<typename NodeIndexType , typename ArcIndexType >

bool operations_research::ForwardStaticGraph< NodeIndexType, ArcIndexType >::CheckTailIndexValidity ( const ArcIndexType arc ) const

inline

Returns true if arc is a valid index into the (*tail_) array.

Definition at line 785 of file ebert_graph.h.

◆ DebugString()

template<typename NodeIndexType , typename ArcIndexType >

std::string operations_research::ForwardStaticGraph< NodeIndexType, ArcIndexType >::DebugString ( ) const

inline

Returns a debug string containing all the information contained in the data structure in raw form.

Definition at line 804 of file ebert_graph.h.

◆ IsIncoming()

template<typename NodeIndexType , typename ArcIndexType >

bool operations_research::ForwardStaticGraph< NodeIndexType, ArcIndexType >::IsIncoming	(	ArcIndexType	arc,
		NodeIndexType	node ) const

inline

Returns true if arc is incoming to node.

Definition at line 765 of file ebert_graph.h.

◆ NextOutgoingArc()

template<typename NodeIndexType , typename ArcIndexType >

ArcIndexType operations_research::ForwardStaticGraph< NodeIndexType, ArcIndexType >::NextOutgoingArc	(	const NodeIndexType	node,
		ArcIndexType	arc ) const

inline

Definition at line 790 of file ebert_graph.h.

◆ ReleaseTailArray()

template<typename NodeIndexType , typename ArcIndexType >

void operations_research::ForwardStaticGraph< NodeIndexType, ArcIndexType >::ReleaseTailArray ( )

inline

Definition at line 846 of file ebert_graph.h.

◆ Tail()

template<typename NodeIndexType , typename ArcIndexType >

NodeIndexType operations_research::ForwardStaticGraph< NodeIndexType, ArcIndexType >::Tail ( const ArcIndexType arc ) const

inline

Returns the tail or start-node of arc.

Definition at line 758 of file ebert_graph.h.

◆ TailArrayComplete()

template<typename NodeIndexType , typename ArcIndexType >

bool operations_research::ForwardStaticGraph< NodeIndexType, ArcIndexType >::TailArrayComplete ( ) const

inline

To be used in a DCHECK().

Definition at line 849 of file ebert_graph.h.

Friends And Related Symbol Documentation

◆ StarGraphBase< NodeIndexType, ArcIndexType, ForwardStaticGraph< NodeIndexType, ArcIndexType > >

template<typename NodeIndexType , typename ArcIndexType >

friend class StarGraphBase< NodeIndexType, ArcIndexType, ForwardStaticGraph< NodeIndexType, ArcIndexType > >

friend

Definition at line 538 of file ebert_graph.h.

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

ortools/graph/ebert_graph.h

Classes

Public Types

Public Member Functions

Friends

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ ArcIndex

◆ NodeIndex

Constructor & Destructor Documentation

◆ ForwardStaticGraph()

Member Function Documentation

◆ BuildTailArray()

◆ CheckArcBounds()

◆ CheckArcValidity()

◆ CheckTailIndexValidity()

◆ DebugString()

◆ IsIncoming()

◆ NextOutgoingArc()

◆ ReleaseTailArray()

◆ Tail()

◆ TailArrayComplete()

Friends And Related Symbol Documentation

◆ StarGraphBase< NodeIndexType, ArcIndexType, ForwardStaticGraph< NodeIndexType, ArcIndexType > >