Forward declarations. More...

#include <ebert_graph.h>

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

Classes
class	IncomingArcIterator
	Iterator class for traversing the incoming arcs associated to a given node. More...

class	OutgoingOrOppositeIncomingArcIterator

Public Types
typedef NodeIndexType	NodeIndex

typedef ArcIndexType	ArcIndex

Public Member Functions
	EbertGraph ()

	EbertGraph (NodeIndexType max_num_nodes, ArcIndexType max_num_arcs)

	~EbertGraph ()

bool	CheckArcBounds (const ArcIndexType arc) const

bool	CheckArcValidity (const ArcIndexType arc) const

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

NodeIndexType	DirectArcTail (const ArcIndexType arc) const

NodeIndexType	DirectArcHead (const ArcIndexType arc) const

ArcIndexType	DirectArc (const ArcIndexType arc) const
	Returns the arc in normal/direct direction.

ArcIndexType	ReverseArc (const ArcIndexType arc) const
	Returns the arc in reverse direction.

ArcIndexType	Opposite (const ArcIndexType arc) const

bool	IsDirect (const ArcIndexType arc) const
	Returns true if the arc is direct.

bool	IsReverse (const ArcIndexType arc) const
	Returns true if the arc is in the reverse direction.

bool	IsOutgoingOrOppositeIncoming (ArcIndexType arc, NodeIndexType node) const
	Returns true if arc is incident to node.

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

bool	IsOutgoing (ArcIndexType arc, NodeIndexType node) const
	Returns true if arc is outgoing from node.

void	BuildRepresentation ()

std::string	DebugString () const

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

class	StarGraphBase< NodeIndexType, ArcIndexType, EbertGraph< NodeIndexType, ArcIndexType > >

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

Forward declarations.

Most users should only use StarGraph, which is EbertGraph<int32_t, int32_t>, and other type shortcuts; see the bottom of this file.

Definition at line 1191 of file ebert_graph.h.

Member Typedef Documentation

◆ ArcIndex

template<typename NodeIndexType , typename ArcIndexType >

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

Definition at line 1229 of file ebert_graph.h.

◆ NodeIndex

template<typename NodeIndexType , typename ArcIndexType >

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

Definition at line 1228 of file ebert_graph.h.

Constructor & Destructor Documentation

◆ EbertGraph() [1/2]

template<typename NodeIndexType , typename ArcIndexType >

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

inline

Definition at line 1231 of file ebert_graph.h.

◆ EbertGraph() [2/2]

template<typename NodeIndexType , typename ArcIndexType >

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

inline

Definition at line 1233 of file ebert_graph.h.

◆ ~EbertGraph()

template<typename NodeIndexType , typename ArcIndexType >

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

inline

Definition at line 1237 of file ebert_graph.h.

Member Function Documentation

◆ BuildRepresentation()

template<typename NodeIndexType , typename ArcIndexType >

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

inline

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

Definition at line 1453 of file ebert_graph.h.

◆ CheckArcBounds()

template<typename NodeIndexType , typename ArcIndexType >

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

Definition at line 1368 of file ebert_graph.h.

◆ CheckArcValidity()

template<typename NodeIndexType , typename ArcIndexType >

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

Definition at line 1376 of file ebert_graph.h.

◆ DebugString()

template<typename NodeIndexType , typename ArcIndexType >

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

inline

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

Definition at line 1463 of file ebert_graph.h.

◆ DirectArc()

template<typename NodeIndexType , typename ArcIndexType >

ArcIndexType operations_research::EbertGraph< NodeIndexType, ArcIndexType >::DirectArc ( const ArcIndexType arc ) const

inline

Returns the arc in normal/direct direction.

Definition at line 1401 of file ebert_graph.h.

◆ DirectArcHead()

template<typename NodeIndexType , typename ArcIndexType >

NodeIndexType operations_research::EbertGraph< NodeIndexType, ArcIndexType >::DirectArcHead ( const ArcIndexType arc ) const

inline

Returns the head or end-node of arc if it is positive (i.e. it is taken in the direction it was entered in the graph), and the tail or start-node otherwise. 'That' in Ebert's paper.

Definition at line 1396 of file ebert_graph.h.

◆ DirectArcTail()

template<typename NodeIndexType , typename ArcIndexType >

NodeIndexType operations_research::EbertGraph< NodeIndexType, ArcIndexType >::DirectArcTail ( const ArcIndexType arc ) const

inline

Returns the tail or start-node of arc if it is positive (i.e. it is taken in the direction it was entered in the graph), and the head or end-node otherwise. 'This' in Ebert's paper.

Definition at line 1389 of file ebert_graph.h.

◆ IsDirect()

template<typename NodeIndexType , typename ArcIndexType >

bool operations_research::EbertGraph< NodeIndexType, ArcIndexType >::IsDirect ( const ArcIndexType arc ) const

inline

Returns true if the arc is direct.

Definition at line 1422 of file ebert_graph.h.

◆ IsIncoming()

template<typename NodeIndexType , typename ArcIndexType >

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

inline

Returns true if arc is incoming to node.

Definition at line 1440 of file ebert_graph.h.

◆ IsOutgoing()

template<typename NodeIndexType , typename ArcIndexType >

bool operations_research::EbertGraph< NodeIndexType, ArcIndexType >::IsOutgoing	(	ArcIndexType	arc,
		NodeIndexType	node ) const

inline

Returns true if arc is outgoing from node.

Definition at line 1445 of file ebert_graph.h.

◆ IsOutgoingOrOppositeIncoming()

template<typename NodeIndexType , typename ArcIndexType >

bool operations_research::EbertGraph< NodeIndexType, ArcIndexType >::IsOutgoingOrOppositeIncoming	(	ArcIndexType	arc,
		NodeIndexType	node ) const

inline

Returns true if arc is incident to node.

Definition at line 1434 of file ebert_graph.h.

◆ IsReverse()

template<typename NodeIndexType , typename ArcIndexType >

bool operations_research::EbertGraph< NodeIndexType, ArcIndexType >::IsReverse ( const ArcIndexType arc ) const

inline

Returns true if the arc is in the reverse direction.

Definition at line 1428 of file ebert_graph.h.

◆ Opposite()

template<typename NodeIndexType , typename ArcIndexType >

ArcIndexType operations_research::EbertGraph< NodeIndexType, ArcIndexType >::Opposite ( const ArcIndexType arc ) const

inline

Returns the opposite arc, i.e. the direct arc is the arc is in reverse direction, and the reverse arc if the arc is direct.

Definition at line 1414 of file ebert_graph.h.

◆ ReverseArc()

template<typename NodeIndexType , typename ArcIndexType >

ArcIndexType operations_research::EbertGraph< NodeIndexType, ArcIndexType >::ReverseArc ( const ArcIndexType arc ) const

inline

Returns the arc in reverse direction.

Definition at line 1407 of file ebert_graph.h.

◆ Tail()

template<typename NodeIndexType , typename ArcIndexType >

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

inline

Returns the tail or start-node of arc.

Definition at line 1381 of file ebert_graph.h.

Friends And Related Symbol Documentation

◆ EbertGraphBase< NodeIndexType, ArcIndexType, EbertGraph< NodeIndexType, ArcIndexType > >

template<typename NodeIndexType , typename ArcIndexType >

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

friend

Definition at line 1196 of file ebert_graph.h.

◆ StarGraphBase< NodeIndexType, ArcIndexType, EbertGraph< NodeIndexType, ArcIndexType > >

template<typename NodeIndexType , typename ArcIndexType >

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

friend

Definition at line 1196 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

◆ EbertGraph() [1/2]

◆ EbertGraph() [2/2]

◆ ~EbertGraph()

Member Function Documentation

◆ BuildRepresentation()

◆ CheckArcBounds()

◆ CheckArcValidity()

◆ DebugString()

◆ DirectArc()

◆ DirectArcHead()

◆ DirectArcTail()

◆ IsDirect()

◆ IsIncoming()

◆ IsOutgoing()

◆ IsOutgoingOrOppositeIncoming()

◆ IsReverse()

◆ Opposite()

◆ ReverseArc()

◆ Tail()

Friends And Related Symbol Documentation

◆ EbertGraphBase< NodeIndexType, ArcIndexType, EbertGraph< NodeIndexType, ArcIndexType > >

◆ StarGraphBase< NodeIndexType, ArcIndexType, EbertGraph< NodeIndexType, ArcIndexType > >