#include <ebert_graph.h>

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

Public Types
typedef NodeIndexType	NodeIndex

typedef ArcIndexType	ArcIndex

Public Member Functions
	ForwardEbertGraph ()

	ForwardEbertGraph (NodeIndexType max_num_nodes, ArcIndexType max_num_arcs)

	~ForwardEbertGraph ()

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.

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.

void	BuildRepresentation ()

bool	BuildTailArray ()

void	ReleaseTailArray ()

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

std::string	DebugString () const

Public Member Functions inherited from operations_research::EbertGraphBase< NodeIndexType, ArcIndexType, ForwardEbertGraph< NodeIndexType, ArcIndexType > >
bool	Reserve (NodeIndexType new_max_num_nodes, ArcIndexType new_max_num_arcs)

ArcIndexType	AddArc (NodeIndexType tail, NodeIndexType head)

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, ForwardEbertGraph< 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	EbertGraphBase< NodeIndexType, ArcIndexType, ForwardEbertGraph< NodeIndexType, ArcIndexType > >

class	StarGraphBase< NodeIndexType, ArcIndexType, ForwardEbertGraph< NodeIndexType, ArcIndexType > >

Additional Inherited Members
Static Public Attributes inherited from operations_research::EbertGraphBase< NodeIndexType, ArcIndexType, ForwardEbertGraph< NodeIndexType, ArcIndexType > >
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, ForwardEbertGraph< 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::EbertGraphBase< NodeIndexType, ArcIndexType, ForwardEbertGraph< NodeIndexType, ArcIndexType > >
	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, ForwardEbertGraph< 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::EbertGraphBase< NodeIndexType, ArcIndexType, ForwardEbertGraph< NodeIndexType, ArcIndexType > >
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, ForwardEbertGraph< 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::ForwardEbertGraph< NodeIndexType, ArcIndexType >

A forward-star-only graph representation for greater efficiency in those algorithms that don't need reverse arcs.

Definition at line 1567 of file ebert_graph.h.

Member Typedef Documentation

◆ ArcIndex

template<typename NodeIndexType , typename ArcIndexType >

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

Definition at line 1604 of file ebert_graph.h.

◆ NodeIndex

template<typename NodeIndexType , typename ArcIndexType >

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

Definition at line 1603 of file ebert_graph.h.

Constructor & Destructor Documentation

◆ ForwardEbertGraph() [1/2]

template<typename NodeIndexType , typename ArcIndexType >

operations_research::ForwardEbertGraph< NodeIndexType, ArcIndexType >::ForwardEbertGraph ( )

inline

Definition at line 1606 of file ebert_graph.h.

◆ ForwardEbertGraph() [2/2]

template<typename NodeIndexType , typename ArcIndexType >

operations_research::ForwardEbertGraph< NodeIndexType, ArcIndexType >::ForwardEbertGraph	(	NodeIndexType	max_num_nodes,
		ArcIndexType	max_num_arcs )

inline

Definition at line 1608 of file ebert_graph.h.

◆ ~ForwardEbertGraph()

template<typename NodeIndexType , typename ArcIndexType >

operations_research::ForwardEbertGraph< NodeIndexType, ArcIndexType >::~ForwardEbertGraph ( )

inline

Definition at line 1612 of file ebert_graph.h.

Member Function Documentation

◆ BuildRepresentation()

template<typename NodeIndexType , typename ArcIndexType >

void operations_research::ForwardEbertGraph< NodeIndexType, ArcIndexType >::BuildRepresentation ( )

inline

Recreates the next_adjacent_arc_ and first_incident_arc_ variables from the arrays head_ and tail_ in O(n + m) time. This is useful if the head_ and tail_ arrays have been sorted according to a given criterion, for example.

Definition at line 1651 of file ebert_graph.h.

◆ BuildTailArray()

template<typename NodeIndexType , typename ArcIndexType >

bool operations_research::ForwardEbertGraph< 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 1661 of file ebert_graph.h.

◆ CheckArcBounds()

template<typename NodeIndexType , typename ArcIndexType >

bool operations_research::ForwardEbertGraph< 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 ForwardEbertGraph class can use it. To be used in a DCHECK.

Definition at line 1617 of file ebert_graph.h.

◆ CheckArcValidity()

template<typename NodeIndexType , typename ArcIndexType >

bool operations_research::ForwardEbertGraph< 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 ForwardEbertGraph class can use it. To be used in a DCHECK.

Definition at line 1625 of file ebert_graph.h.

◆ CheckTailIndexValidity()

template<typename NodeIndexType , typename ArcIndexType >

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

inline

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

Definition at line 1630 of file ebert_graph.h.

◆ DebugString()

template<typename NodeIndexType , typename ArcIndexType >

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

inline

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

Definition at line 1703 of file ebert_graph.h.

◆ IsIncoming()

template<typename NodeIndexType , typename ArcIndexType >

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

inline

Returns true if arc is incoming to node.

Definition at line 1643 of file ebert_graph.h.

◆ ReleaseTailArray()

template<typename NodeIndexType , typename ArcIndexType >

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

inline

Definition at line 1689 of file ebert_graph.h.

◆ Tail()

template<typename NodeIndexType , typename ArcIndexType >

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

inline

Returns the tail or start-node of arc.

Definition at line 1636 of file ebert_graph.h.

◆ TailArrayComplete()

template<typename NodeIndexType , typename ArcIndexType >

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

inline

To be used in a DCHECK().

Definition at line 1692 of file ebert_graph.h.

Friends And Related Symbol Documentation

◆ EbertGraphBase< NodeIndexType, ArcIndexType, ForwardEbertGraph< NodeIndexType, ArcIndexType > >

template<typename NodeIndexType , typename ArcIndexType >

friend class EbertGraphBase< NodeIndexType, ArcIndexType, ForwardEbertGraph< NodeIndexType, ArcIndexType > >

friend

Definition at line 1572 of file ebert_graph.h.

◆ StarGraphBase< NodeIndexType, ArcIndexType, ForwardEbertGraph< NodeIndexType, ArcIndexType > >

template<typename NodeIndexType , typename ArcIndexType >

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

friend

Definition at line 1572 of file ebert_graph.h.

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

ortools/graph/ebert_graph.h

Public Types

Public Member Functions

Friends

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ ArcIndex

◆ NodeIndex

Constructor & Destructor Documentation

◆ ForwardEbertGraph() [1/2]

◆ ForwardEbertGraph() [2/2]

◆ ~ForwardEbertGraph()

Member Function Documentation

◆ BuildRepresentation()

◆ BuildTailArray()

◆ CheckArcBounds()

◆ CheckArcValidity()

◆ CheckTailIndexValidity()

◆ DebugString()

◆ IsIncoming()

◆ ReleaseTailArray()

◆ Tail()

◆ TailArrayComplete()

Friends And Related Symbol Documentation

◆ EbertGraphBase< NodeIndexType, ArcIndexType, ForwardEbertGraph< NodeIndexType, ArcIndexType > >

◆ StarGraphBase< NodeIndexType, ArcIndexType, ForwardEbertGraph< NodeIndexType, ArcIndexType > >