Data type for general directed graphs (adjacency list representation). More...

#include <ogdf/basic/Graph_d.h>

Inheritance diagram for ogdf::Graph:

Classes
class	CCsInfo
	Info structure for maintaining connected components. More...

class	HiddenEdgeSet
	Functionality for temporarily hiding edges in constant time. More...

Public Types
Enumerations
These enumerations are mainly meant for advanced or internal usage scenarios.
enum class	EdgeType { association = 0 , generalization = 1 , dependency = 2 }
	The type of edges (only used in derived classes). More...

enum class	NodeType { vertex = 0 , dummy = 1 , generalizationMerger = 2 , generalizationExpander = 3 , highDegreeExpander = 4 , lowDegreeExpander = 5 , associationClass = 6 }
	The type of nodes. More...

Iterators
These types are used for graph object iterators, which are returned by graph object containers like nodes and edges.
using	node_iterator = internal::GraphIterator< node >
	Provides a bidirectional iterator to a node in a graph.

using	edge_iterator = internal::GraphIterator< edge >
	Provides a bidirectional iterator to an edge in a graph.

using	adjEntry_iterator = internal::GraphIterator< adjEntry >
	Provides a bidirectional iterator to an entry in an adjacency list.

Public Member Functions
	Graph ()
	Constructs an empty graph.

	Graph (const Graph &G)
	Constructs a graph that is a copy of `G`.

virtual	~Graph ()
	Destructor.

Access methods
bool	empty () const
	Returns true iff the graph is empty, i.e., contains no nodes.

int	numberOfNodes () const
	Returns the number of nodes in the graph.

int	numberOfEdges () const
	Returns the number of edges in the graph.

int	maxNodeIndex () const
	Returns the largest used node index.

int	maxEdgeIndex () const
	Returns the largest used edge index.

int	maxAdjEntryIndex () const
	Returns the largest used adjEntry index.

int	nodeArrayTableSize () const
	Returns the table size of node arrays associated with this graph.

int	edgeArrayTableSize () const
	Returns the table size of edge arrays associated with this graph.

int	adjEntryArrayTableSize () const
	Returns the table size of adjEntry arrays associated with this graph.

node	firstNode () const
	Returns the first node in the list of all nodes.

node	lastNode () const
	Returns the last node in the list of all nodes.

edge	firstEdge () const
	Returns the first edge in the list of all edges.

edge	lastEdge () const
	Returns the last edge in the list of all edges.

node	chooseNode (std::function< bool(node)> includeNode=[](node) { return true;}, bool isFastTest=true) const
	Returns a random node.

edge	chooseEdge (std::function< bool(edge)> includeEdge=[](edge) { return true;}, bool isFastTest=true) const
	Returns a random edge.

template<class CONTAINER >
void	allNodes (CONTAINER &nodeContainer) const
	Returns a container with all nodes of the graph.

template<class CONTAINER >
void	allEdges (CONTAINER &edgeContainer) const
	Returns a container with all edges of the graph.

Creation of new nodes and edges
node	newNode ()
	Creates a new node and returns it.

node	newNode (int index)
	Creates a new node with predefined index and returns it.

edge	newEdge (node v, node w)
	Creates a new edge (`v`,`w`) and returns it.

edge	newEdge (node v, node w, int index)
	Creates a new edge (`v`,`w`) with predefined index and returns it.

edge	newEdge (adjEntry adjSrc, adjEntry adjTgt, Direction dir=Direction::after)
	Creates a new edge at predefined positions in the adjacency lists.

edge	newEdge (node v, adjEntry adjTgt)
	Creates a new edge at predefined positions in the adjacency lists.

edge	newEdge (adjEntry adjSrc, node w)
	Creates a new edge at predefined positions in the adjacency lists.

Removing nodes and edges
virtual void	delNode (node v)
	Removes node `v` and all incident edges from the graph.

virtual void	delEdge (edge e)
	Removes edge `e` from the graph.

virtual void	clear ()
	Removes all nodes and all edges from the graph.

Advanced modification methods
void	insert (const Graph &G, NodeArray< node > &nodeMap)
	Inserts Graph `G` as a subgraph into this Graph.

void	insert (const Graph &G)
	Inserts Graph `G` as a subgraph into this Graph.

virtual edge	split (edge e)
	Splits edge `e` into two edges introducing a new node.

void	unsplit (node u)
	Undoes a split operation.

virtual void	unsplit (edge eIn, edge eOut)
	Undoes a split operation.

node	splitNode (adjEntry adjStartLeft, adjEntry adjStartRight)
	Splits a node while preserving the order of adjacency entries.

node	contract (edge e, bool keepSelfLoops=false)
	Contracts edge `e` while preserving the order of adjacency entries.

void	move (edge e, adjEntry adjSrc, Direction dirSrc, adjEntry adjTgt, Direction dirTgt)
	Moves edge `e` to a different adjacency list.

void	moveTarget (edge e, node w)
	Moves the target node of edge `e` to node `w`.

void	moveTarget (edge e, adjEntry adjTgt, Direction dir)
	Moves the target node of edge `e` to a specific position in an adjacency list.

void	moveSource (edge e, node w)
	Moves the source node of edge `e` to node `w`.

void	moveSource (edge e, adjEntry adjSrc, Direction dir)
	Moves the source node of edge `e` to a specific position in an adjacency list.

edge	searchEdge (node v, node w, bool directed=false) const
	Searches and returns an edge connecting nodes `v` and `w` in time O( min(deg(`v` ), deg(`w` ))).

void	reverseEdge (edge e)
	Reverses the edge `e`, i.e., exchanges source and target node.

void	reverseAllEdges ()
	Reverses all edges in the graph.

template<class NODELIST >
void	collapse (NODELIST &nodesToCollapse)
	Collapses all nodes in the list `nodesToCollapse` to the first node in the list.

template<class ADJ_ENTRY_LIST >
void	sort (node v, const ADJ_ENTRY_LIST &newOrder)
	Sorts the adjacency list of node `v` according to `newOrder`.

void	reverseAdjEdges (node v)
	Reverses the adjacency list of `v`.

void	moveAdj (adjEntry adjMove, Direction dir, adjEntry adjPos)
	Moves adjacency entry `adjMove` before or after `adjPos`.

void	moveAdjAfter (adjEntry adjMove, adjEntry adjAfter)
	Moves adjacency entry `adjMove` after `adjAfter`.

void	moveAdjBefore (adjEntry adjMove, adjEntry adjBefore)
	Moves adjacency entry `adjMove` before `adjBefore`.

void	reverseAdjEdges ()
	Reverses all adjacency lists.

void	swapAdjEdges (adjEntry adj1, adjEntry adj2)
	Exchanges two entries in an adjacency list.

Miscellaneous
int	genus () const
	Returns the genus of the graph's embedding.

bool	representsCombEmbedding () const
	Returns true iff the graph represents a combinatorial embedding.

Registering arrays and observers
These methods are used by various graph array types like NodeArray or EdgeArray. There should be no need to use them directly in user code.
ListIterator< NodeArrayBase * >	registerArray (NodeArrayBase *pNodeArray) const
	Registers a node array.

ListIterator< EdgeArrayBase * >	registerArray (EdgeArrayBase *pEdgeArray) const
	Registers an edge array.

ListIterator< AdjEntryArrayBase * >	registerArray (AdjEntryArrayBase *pAdjArray) const
	Registers an adjEntry array.

ListIterator< GraphObserver * >	registerStructure (GraphObserver *pStructure) const
	Registers a graph observer (e.g. a ClusterGraph).

void	unregisterArray (ListIterator< NodeArrayBase * > it) const
	Unregisters a node array.

void	unregisterArray (ListIterator< EdgeArrayBase * > it) const
	Unregisters an edge array.

void	unregisterArray (ListIterator< AdjEntryArrayBase * > it) const
	Unregisters an adjEntry array.

void	unregisterStructure (ListIterator< GraphObserver * > it) const
	Unregisters a graph observer.

template<class ArrayBase >
void	moveRegisterArray (ListIterator< ArrayBase * > it, ArrayBase *pArray) const
	Move the registration `it` of an graph element array to `pArray` (used with move semantics for graph element arrays).

void	resetEdgeIdCount (int maxId)
	Resets the edge id count to `maxId`.

Operators
Graph &	operator= (const Graph &G)
	Assignment operator.

Public Attributes
Graph object containers
These containers maintain the nodes and edges of the graph, and provide node and edge iterators.
internal::GraphObjectContainer< NodeElement >	nodes
	The container containing all node objects.

internal::GraphObjectContainer< EdgeElement >	edges
	The container containing all edge objects.

Protected Member Functions
void	assign (const Graph &G, NodeArray< node > &mapNode, EdgeArray< edge > &mapEdge)

void	construct (const Graph &G, NodeArray< node > &mapNode, EdgeArray< edge > &mapEdge)

void	constructInitByActiveNodes (const List< node > &nodeList, const NodeArray< bool > &activeNodes, NodeArray< node > &mapNode, EdgeArray< edge > &mapEdge)

void	constructInitByCC (const CCsInfo &info, int cc, NodeArray< node > &mapNode, EdgeArray< edge > &mapEdge)
	Constructs a copy of connected component `cc` in `info`.

void	constructInitByNodes (const Graph &G, const List< node > &nodeList, NodeArray< node > &mapNode, EdgeArray< edge > &mapEdge)
	Constructs a copy of the subgraph of `G` induced by `nodeList`.

Private Member Functions
void	copy (const Graph &G)

void	copy (const Graph &G, NodeArray< node > &mapNode, EdgeArray< edge > &mapEdge)

edge	createEdgeElement (node v, node w, adjEntry adjSrc, adjEntry adjTgt)

void	moveAdj (adjEntry adj, node w)

node	pureNewNode ()

void	reinitArrays (bool doResetTableSizes=true)
	Re-initializes registed arrays with respect to the current sizes. Calls resetTableSizes() if `doResetTableSizes` is `true` (default).

void	resetAdjEntryIndex (int newIndex, int oldIndex)

void	resetTableSizes ()
	Sets the sizes of registered node and edge arrays to the next power of two that is no less than the current id counts. Respects the minimum table size constants.

void	restoreAllEdges ()
	Used to restore all hidden edges upon deleting the graph.

Private Attributes
int	m_edgeArrayTableSize
	The current table size of edge arrays associated with this graph.

int	m_edgeIdCount
	The Index that will be assigned to the next created edge.

List< HiddenEdgeSet * >	m_hiddenEdgeSets
	The list of hidden edges.

std::mutex	m_mutexRegArrays
	The critical section for protecting shared acces to register/unregister methods.

int	m_nodeArrayTableSize
	The current table size of node arrays associated with this graph.

int	m_nodeIdCount
	The Index that will be assigned to the next created node.

ListPure< AdjEntryArrayBase * >	m_regAdjArrays
	The registered adjEntry arrays.

ListPure< EdgeArrayBase * >	m_regEdgeArrays
	The registered edge arrays.

ListPure< NodeArrayBase * >	m_regNodeArrays
	The registered node arrays.

ListPure< GraphObserver * >	m_regStructures
	The registered graph structures.

Detailed Description

Data type for general directed graphs (adjacency list representation).

Thread Safety

The class Graph allows shared access of threads to const methods only. If one thread executes a non-const method, shared access is no longer thread-safe.

Iteration

You may iterate over the nodes and edges of a graph using C++11 range-based for loops. Find some examples below.

Iterate over all nodes v of graph G using c++11 syntax :
for(node v : G.nodes) {

// do stuff with node v

}

ogdf::Graph::nodes
internal::GraphObjectContainer< NodeElement > nodes
The container containing all node objects.
Definition Graph_d.h:589

ogdf::NodeElement
Class for the representation of nodes.
Definition Graph_d.h:177
Iterate over all nodes v of graph G :
for(node v = G.firstNode(); v != nullptr; v = v->succ()) {

// do stuff with node v

}
Iterate over all edges e of graph G using c++11 syntax :
for(edge e : G.edges) {

// do stuff with node v

}

ogdf::EdgeElement
Class for the representation of edges.
Definition Graph_d.h:300

ogdf::Graph::edges
internal::GraphObjectContainer< EdgeElement > edges
The container containing all edge objects.
Definition Graph_d.h:592
Iterate over all incident edges of node v using c++11 syntax:
for(adjEntry adj : v->adjEntries) {

edge e = adj->theEdge();

// do stuff with edge e

}

ogdf::AdjElement
Class for adjacency list elements.
Definition Graph_d.h:79

Definition at line 521 of file Graph_d.h.

Member Typedef Documentation

◆ adjEntry_iterator

using ogdf::Graph::adjEntry_iterator = internal::GraphIterator<adjEntry>

Provides a bidirectional iterator to an entry in an adjacency list.

Definition at line 556 of file Graph_d.h.

◆ edge_iterator

using ogdf::Graph::edge_iterator = internal::GraphIterator<edge>

Provides a bidirectional iterator to an edge in a graph.

Definition at line 554 of file Graph_d.h.

◆ node_iterator

using ogdf::Graph::node_iterator = internal::GraphIterator<node>

Provides a bidirectional iterator to a node in a graph.

Definition at line 552 of file Graph_d.h.

Member Enumeration Documentation

◆ EdgeType

enum class ogdf::Graph::EdgeType

strong

The type of edges (only used in derived classes).

Enumerator
association
generalization
dependency

Definition at line 566 of file Graph_d.h.

◆ NodeType

enum class ogdf::Graph::NodeType

strong

The type of nodes.

Enumerator
vertex
dummy
generalizationMerger
generalizationExpander
highDegreeExpander
lowDegreeExpander
associationClass

Definition at line 569 of file Graph_d.h.

Constructor & Destructor Documentation

◆ Graph() [1/2]

ogdf::Graph::Graph ( )

Constructs an empty graph.

◆ Graph() [2/2]

ogdf::Graph::Graph ( const Graph & G )

Constructs a graph that is a copy of G.

The constructor assures that the adjacency lists of nodes in the constructed graph are in the same order as the adjacency lists in G. This is in particular important when dealing with embedded graphs.

Parameters

G	is the graph that will be copied.

◆ ~Graph()

virtual ogdf::Graph::~Graph ( )

virtual

Destructor.

Member Function Documentation

◆ adjEntryArrayTableSize()

int ogdf::Graph::adjEntryArrayTableSize ( ) const

inline

Returns the table size of adjEntry arrays associated with this graph.

Definition at line 643 of file Graph_d.h.

◆ allEdges()

template<class CONTAINER >

void ogdf::Graph::allEdges ( CONTAINER & edgeContainer ) const

inline

Returns a container with all edges of the graph.

Template Parameters

CONTAINER is the type of the edge container which is returned.

Parameters

edgeContainer is assigned the list of all edges.

Definition at line 695 of file Graph_d.h.

◆ allNodes()

template<class CONTAINER >

void ogdf::Graph::allNodes ( CONTAINER & nodeContainer ) const

inline

Returns a container with all nodes of the graph.

Template Parameters

CONTAINER is the type of node container which is returned.

Parameters

nodeContainer is assigned the container of all nodes.

Definition at line 685 of file Graph_d.h.

◆ assign()

void ogdf::Graph::assign	(	const Graph &	G,
		NodeArray< node > &	mapNode,
		EdgeArray< edge > &	mapEdge
	)

protected

◆ chooseEdge()

edge ogdf::Graph::chooseEdge	(	std::function< bool(edge)>	includeEdge = `[](edge) { return true;}`,
		bool	isFastTest = `true`
	)		const

Returns a random edge.

nullptr is returned if no feasible edge exists.

See also: chooseIteratorFrom

◆ chooseNode()

node ogdf::Graph::chooseNode	(	std::function< bool(node)>	includeNode = `[](node) { return true;}`,
		bool	isFastTest = `true`
	)		const

Returns a random node.

nullptr is returned if no feasible node exists.

See also: chooseIteratorFrom

◆ clear()

virtual void ogdf::Graph::clear ( )

virtual

Removes all nodes and all edges from the graph.

Reimplemented in ogdf::GraphCopy.

◆ collapse()

template<class NODELIST >

void ogdf::Graph::collapse ( NODELIST & nodesToCollapse )

inline

Collapses all nodes in the list nodesToCollapse to the first node in the list.

Parallel edges are removed.

Template Parameters

NODELIST is the type of input node list.

Parameters

nodesToCollapse is the list of nodes that will be collapsed. This list will be empty after the call.

Definition at line 1056 of file Graph_d.h.

◆ construct()

void ogdf::Graph::construct	(	const Graph &	G,
		NodeArray< node > &	mapNode,
		EdgeArray< edge > &	mapEdge
	)

protected

◆ constructInitByActiveNodes()

void ogdf::Graph::constructInitByActiveNodes	(	const List< node > &	nodeList,
		const NodeArray< bool > &	activeNodes,
		NodeArray< node > &	mapNode,
		EdgeArray< edge > &	mapEdge
	)

protected

◆ constructInitByCC()

void ogdf::Graph::constructInitByCC	(	const CCsInfo &	info,
		int	cc,
		NodeArray< node > &	mapNode,
		EdgeArray< edge > &	mapEdge
	)

protected

Constructs a copy of connected component cc in info.

◆ constructInitByNodes()

void ogdf::Graph::constructInitByNodes	(	const Graph &	G,
		const List< node > &	nodeList,
		NodeArray< node > &	mapNode,
		EdgeArray< edge > &	mapEdge
	)

protected

Constructs a copy of the subgraph of G induced by nodeList.

This method preserves the order in the adjacency lists, i.e., if G is embedded, its embedding induces the embedding of the copy.

◆ contract()

node ogdf::Graph::contract	(	edge	e,
		bool	keepSelfLoops = `false`
	)

Contracts edge e while preserving the order of adjacency entries.

Parameters

e	is the edge to be contracted.
keepSelfLoops	determines whether edges parallel to `e` will result in self-loops or not (in the latter case, they will also be contracted).

Returns: The endpoint of e to which all edges have been moved. The implementation ensures this to be the source of the former edge e.

◆ copy() [1/2]

void ogdf::Graph::copy ( const Graph & G )

private

◆ copy() [2/2]

void ogdf::Graph::copy	(	const Graph &	G,
		NodeArray< node > &	mapNode,
		EdgeArray< edge > &	mapEdge
	)

private

◆ createEdgeElement()

edge ogdf::Graph::createEdgeElement	(	node	v,
		node	w,
		adjEntry	adjSrc,
		adjEntry	adjTgt
	)

private

◆ delEdge()

virtual void ogdf::Graph::delEdge ( edge e )

virtual

Removes edge e from the graph.

Reimplemented in ogdf::GraphCopySimple, ogdf::GraphCopy, and ogdf::PlanRepExpansion.

◆ delNode()

virtual void ogdf::Graph::delNode ( node v )

virtual

Removes node v and all incident edges from the graph.

Reimplemented in ogdf::GraphCopySimple, and ogdf::GraphCopy.

◆ edgeArrayTableSize()

int ogdf::Graph::edgeArrayTableSize ( ) const

inline

Returns the table size of edge arrays associated with this graph.

Definition at line 640 of file Graph_d.h.

◆ empty()

bool ogdf::Graph::empty ( ) const

inline

Returns true iff the graph is empty, i.e., contains no nodes.

Definition at line 619 of file Graph_d.h.

◆ firstEdge()

edge ogdf::Graph::firstEdge ( ) const

inline

Returns the first edge in the list of all edges.

Definition at line 652 of file Graph_d.h.

◆ firstNode()

node ogdf::Graph::firstNode ( ) const

inline

Returns the first node in the list of all nodes.

Definition at line 646 of file Graph_d.h.

◆ genus()

int ogdf::Graph::genus ( ) const

Returns the genus of the graph's embedding.

The genus of a graph is defined as follows. Let G be a graph with m edges, n nodes, nz isolated vertices, fc face cycles, and c connected components. Then,

\[ genus(G) = (m - n - nz - fc + 2c)/2 \]

Returns: the genus of the graph's current embedding; if this is 0, then the graph is planarly embedded.

◆ insert() [1/2]

void ogdf::Graph::insert ( const Graph & G )

Inserts Graph G as a subgraph into this Graph.

Parameters

G	is the Graph to be inserted into this Graph.

◆ insert() [2/2]

void ogdf::Graph::insert	(	const Graph &	G,
		NodeArray< node > &	nodeMap
	)

Inserts Graph G as a subgraph into this Graph.

Parameters

G	is the Graph to be inserted into this Graph.
nodeMap	is assigned a mapping from nodes in `G` to nodes in this Graph.

◆ lastEdge()

edge ogdf::Graph::lastEdge ( ) const

inline

Returns the last edge in the list of all edges.

Definition at line 655 of file Graph_d.h.

◆ lastNode()

node ogdf::Graph::lastNode ( ) const

inline

Returns the last node in the list of all nodes.

Definition at line 649 of file Graph_d.h.

◆ maxAdjEntryIndex()

int ogdf::Graph::maxAdjEntryIndex ( ) const

inline

Returns the largest used adjEntry index.

Definition at line 634 of file Graph_d.h.

◆ maxEdgeIndex()

int ogdf::Graph::maxEdgeIndex ( ) const

inline

Returns the largest used edge index.

Definition at line 631 of file Graph_d.h.

◆ maxNodeIndex()

int ogdf::Graph::maxNodeIndex ( ) const

inline

Returns the largest used node index.

Definition at line 628 of file Graph_d.h.

◆ move()

void ogdf::Graph::move	(	edge	e,
		adjEntry	adjSrc,
		Direction	dirSrc,
		adjEntry	adjTgt,
		Direction	dirTgt
	)

Moves edge e to a different adjacency list.

The source adjacency entry of e is moved to the adjacency list containing adjSrc and is inserted before or after adjSrc, and its target adjacency entry to the adjacency list containing adjTgt and is inserted before or after adjTgt; e is afterwards an edge from owner(adjSrc) to owner(adjTgt).

Parameters

e	is the edge to be moved.
adjSrc	is the adjaceny entry before or after which the source adjacency entry of `e` will be inserted.
dirSrc	specifies if the source adjacency entry of `e` will be inserted before or after `adjSrc`.
adjTgt	is the adjaceny entry before or after which the target adjacency entry of `e` will be inserted.
dirTgt	specifies if the target adjacency entry of `e` will be inserted before or after `adjTgt`.

◆ moveAdj() [1/2]

void ogdf::Graph::moveAdj	(	adjEntry	adj,
		node	w
	)

private

◆ moveAdj() [2/2]

void ogdf::Graph::moveAdj	(	adjEntry	adjMove,
		Direction	dir,
		adjEntry	adjPos
	)

inline

Moves adjacency entry adjMove before or after adjPos.

Precondition: adjMove and adjAfter are distinct entries in the same adjacency list.

Parameters

adjMove	is an entry in the adjacency list of a node in this graph.
adjPos	is an entry in the same adjacency list as `adjMove`.
dir	specifies if `adjMove` is moved before or after `adjPos`.

Definition at line 1117 of file Graph_d.h.

◆ moveAdjAfter()

void ogdf::Graph::moveAdjAfter	(	adjEntry	adjMove,
		adjEntry	adjAfter
	)

inline

Moves adjacency entry adjMove after adjAfter.

Precondition: adjMove and adjAfter are distinct entries in the same adjacency list.

Parameters

adjMove	is an entry in the adjacency list of a node in this graph.
adjAfter	is an entry in the same adjacency list as `adjMove`.

Definition at line 1133 of file Graph_d.h.

◆ moveAdjBefore()

void ogdf::Graph::moveAdjBefore	(	adjEntry	adjMove,
		adjEntry	adjBefore
	)

inline

Moves adjacency entry adjMove before adjBefore.

Precondition: adjMove and adjBefore are distinct entries in the same adjacency list.

Parameters

adjMove	is an entry in the adjacency list of a node in this graph.
adjBefore	is an entry in the same adjacency list as `adjMove`.

Definition at line 1148 of file Graph_d.h.

◆ moveRegisterArray()

template<class ArrayBase >

void ogdf::Graph::moveRegisterArray	(	ListIterator< ArrayBase * >	it,
		ArrayBase *	pArray
	)		const

inline

Move the registration it of an graph element array to pArray (used with move semantics for graph element arrays).

Definition at line 1281 of file Graph_d.h.

◆ moveSource() [1/2]

void ogdf::Graph::moveSource	(	edge	e,
		adjEntry	adjSrc,
		Direction	dir
	)

Moves the source node of edge e to a specific position in an adjacency list.

Let w be the node containing adjSrc. If e=(v,u) before, then e=(w,u) afterwards. Inserts the adjacency entry before or after adjSrc according to dir.

Parameters

e	is the edge whose source node is moved.
adjSrc	is the adjacency entry before or after which the source adjacency entry of `e` is inserted.
dir	specifies if the source adjacency entry of `e` is inserted before or after `adjSrc`.

◆ moveSource() [2/2]

void ogdf::Graph::moveSource	(	edge	e,
		node	w
	)

Moves the source node of edge e to node w.

If e=(v,u) before, then e=(w,u) afterwards.

Parameters

e	is the edge whose source node is moved.
w	is the new source node of `e`.

◆ moveTarget() [1/2]

void ogdf::Graph::moveTarget	(	edge	e,
		adjEntry	adjTgt,
		Direction	dir
	)

Moves the target node of edge e to a specific position in an adjacency list.

Let w be the node containing adjTgt. If e=(v,u) before, then e=(v,w) afterwards. Inserts the adjacency entry before or after adjTgt according to dir.

Parameters

e	is the edge whose target node is moved.
adjTgt	is the adjacency entry before or after which the target adjacency entry of `e` is inserted.
dir	specifies if the target adjacency entry of `e` is inserted before or after `adjTgt`.

◆ moveTarget() [2/2]

void ogdf::Graph::moveTarget	(	edge	e,
		node	w
	)

Moves the target node of edge e to node w.

If e=(v,u) before, then e=(v,w) afterwards.

Parameters

e	is the edge whose target node is moved.
w	is the new target node of `e`.

◆ newEdge() [1/5]

edge ogdf::Graph::newEdge	(	adjEntry	adjSrc,
		adjEntry	adjTgt,
		Direction	dir = `Direction::after`
	)

Creates a new edge at predefined positions in the adjacency lists.

Let v be the node whose adjacency list contains adjSrc, and w the node whose adjacency list contains adjTgt. Then, the created edge is (v,w).

Parameters

adjSrc	is the adjacency entry after which the new edge is inserted in the adjacency list of v.
adjTgt	is the adjacency entry after which the new edge is inserted in the adjacency list of w.
dir	specifies if the edge is inserted before or after the given adjacency entries.

Returns: the newly created edge.

◆ newEdge() [2/5]

edge ogdf::Graph::newEdge	(	adjEntry	adjSrc,
		node	w
	)

Creates a new edge at predefined positions in the adjacency lists.

Let v be the node whose adjacency list contains adjSrc. Then, the created edge is (v,w).

Parameters

adjSrc	is the adjacency entry after which the new edge is inserted in the adjacency list of v.
w	is the source node of the new edge; the edge is added at the end of the adjacency list of `w`.

Returns: the newly created edge.

◆ newEdge() [3/5]

edge ogdf::Graph::newEdge	(	node	v,
		adjEntry	adjTgt
	)

Creates a new edge at predefined positions in the adjacency lists.

Let w be the node whose adjacency list contains adjTgt. Then, the created edge is (v,w).

Parameters

v	is the source node of the new edge; the edge is added at the end of the adjacency list of `v`.
adjTgt	is the adjacency entry after which the new edge is inserted in the adjacency list of w.

Returns: the newly created edge.

◆ newEdge() [4/5]

edge ogdf::Graph::newEdge	(	node	v,
		node	w
	)

Creates a new edge (v,w) and returns it.

Parameters

v	is the source node of the newly created edge.
w	is the target node of the newly created edge.

Returns: the newly created edge.

◆ newEdge() [5/5]

edge ogdf::Graph::newEdge	(	node	v,
		node	w,
		int	index
	)

Creates a new edge (v,w) with predefined index and returns it.

Precondition: index is currently not the index of any other edge in the graph.

Attention: Passing an edge index that is already in use results in an inconsistent data structure. Only use this method if you know what you're doing!

Parameters

v	is the source node of the newly created edge.
w	is the target node of the newly created edge.
index	is the index that will be assigned to the newly created edge.

Returns: the newly created edge.

◆ newNode() [1/2]

node ogdf::Graph::newNode ( )

Creates a new node and returns it.

◆ newNode() [2/2]

node ogdf::Graph::newNode ( int index )

Creates a new node with predefined index and returns it.

Precondition: index is currently not the index of any other node in the graph.

Attention: Passing a node index that is already in use results in an inconsistent data structure. Only use this method if you know what you're doing!

Parameters

index is the index that will be assigned to the newly created node.

Returns: the newly created node.

◆ nodeArrayTableSize()

int ogdf::Graph::nodeArrayTableSize ( ) const

inline

Returns the table size of node arrays associated with this graph.

Definition at line 637 of file Graph_d.h.

◆ numberOfEdges()

int ogdf::Graph::numberOfEdges ( ) const

inline

Returns the number of edges in the graph.

Definition at line 625 of file Graph_d.h.

◆ numberOfNodes()

int ogdf::Graph::numberOfNodes ( ) const

inline

Returns the number of nodes in the graph.

Definition at line 622 of file Graph_d.h.

◆ operator=()

Graph & ogdf::Graph::operator= ( const Graph & G )

Assignment operator.

The assignment operature assures that the adjacency lists of nodes in the constructed graph are in the same order as the adjacency lists in G. This is in particular important when dealing with embedded graphs.

Parameters

G	is the graph to be copied.

Returns: this graph.

◆ pureNewNode()

node ogdf::Graph::pureNewNode ( )

private

◆ registerArray() [1/3]

ListIterator< AdjEntryArrayBase * > ogdf::Graph::registerArray ( AdjEntryArrayBase * pAdjArray ) const

Registers an adjEntry array.

Remarks: This method is automatically called by adjacency entry arrays; it should not be called manually.

Parameters

pAdjArray is a pointer to the adjacency entry array's base; this adjacency entry array must be associated with this graph.

Returns: an iterator pointing to the entry for the registered adjacency entry array in the list of registered adjacency entry arrays. This iterator is required for unregistering the adjacency entry array again.

◆ registerArray() [2/3]

ListIterator< EdgeArrayBase * > ogdf::Graph::registerArray ( EdgeArrayBase * pEdgeArray ) const

Registers an edge array.

Remarks: This method is automatically called by edge arrays; it should not be called manually.

Parameters

pEdgeArray is a pointer to the edge array's base; this edge array must be associated with this graph.

Returns: an iterator pointing to the entry for the registered edge array in the list of registered edge arrays. This iterator is required for unregistering the edge array again.

◆ registerArray() [3/3]

ListIterator< NodeArrayBase * > ogdf::Graph::registerArray ( NodeArrayBase * pNodeArray ) const

Registers a node array.

Remarks: This method is automatically called by node arrays; it should not be called manually.

Parameters

pNodeArray is a pointer to the node array's base; this node array must be associated with this graph.

Returns: an iterator pointing to the entry for the registered node array in the list of registered node arrays. This iterator is required for unregistering the node array again.

◆ registerStructure()

ListIterator< GraphObserver * > ogdf::Graph::registerStructure ( GraphObserver * pStructure ) const

Registers a graph observer (e.g. a ClusterGraph).

Parameters

pStructure is a pointer to the graph observer that shall be registered; this graph observer must be associated with this graph.

Returns: an iterator pointing to the entry for the registered graph observer in the list of registered graph observers. This iterator is required for unregistering the graph observer again.

◆ reinitArrays()

void ogdf::Graph::reinitArrays ( bool doResetTableSizes = true )

private

Re-initializes registed arrays with respect to the current sizes. Calls resetTableSizes() if doResetTableSizes is true (default).

◆ representsCombEmbedding()

bool ogdf::Graph::representsCombEmbedding ( ) const

inline

Returns true iff the graph represents a combinatorial embedding.

Returns: true if the current embedding (given by the adjacency lists) represents a combinatorial embedding, false otherwise.

Definition at line 1196 of file Graph_d.h.

◆ resetAdjEntryIndex()

void ogdf::Graph::resetAdjEntryIndex	(	int	newIndex,
		int	oldIndex
	)

private

◆ resetEdgeIdCount()

void ogdf::Graph::resetEdgeIdCount ( int maxId )

Resets the edge id count to maxId.

The next edge will get edge id maxId +1. Use this function with caution! It is provided as an efficient way to reduce the edge id count. The Graph class increments the edge id count whenever an edge is created; free edge ids resulting from removing edges are not reused (there is not something like a freelist).

This function is , e.g., useful, when a lot of edges has been added and all these edges are removed again (without creating other new edges meanwile). Then, it is safe to reduce the edge id count to the value it had before, cf. the following code snippet:

int oldIdCount = G.maxEdgeIndex();
Create some edges
...
Remove all these edges again
G.resetEdgeIdCount(oldIdCount);

Reducing the edge id count will reduce the memory consumption of edge arrays associated with the graph.

Precondition: -1 <= maxId <= maximal edge id in the graph.

Parameters

maxId is an upper bound of the edge ids in the graph.

◆ resetTableSizes()

void ogdf::Graph::resetTableSizes ( )

private

Sets the sizes of registered node and edge arrays to the next power of two that is no less than the current id counts. Respects the minimum table size constants.

◆ restoreAllEdges()

void ogdf::Graph::restoreAllEdges ( )

private

Used to restore all hidden edges upon deleting the graph.

◆ reverseAdjEdges() [1/2]

void ogdf::Graph::reverseAdjEdges ( )

Reverses all adjacency lists.

◆ reverseAdjEdges() [2/2]

void ogdf::Graph::reverseAdjEdges ( node v )

inline

Reverses the adjacency list of v.

Parameters

v	is the node whose adjacency list will be reveresed.

Definition at line 1107 of file Graph_d.h.

◆ reverseAllEdges()

void ogdf::Graph::reverseAllEdges ( )

Reverses all edges in the graph.

◆ reverseEdge()

void ogdf::Graph::reverseEdge ( edge e )

Reverses the edge e, i.e., exchanges source and target node.

◆ searchEdge()

edge ogdf::Graph::searchEdge	(	node	v,
		node	w,
		bool	directed = `false`
	)		const

Searches and returns an edge connecting nodes v and w in time O( min(deg(v ), deg(w ))).

Parameters

v	is the first endpoint of the edge to be searched.
w	is the second endpoint of the edge to be searched.
directed	iff set to true, enforces that `v` must be the source node and `w` the target node of the edge.

Returns: an edge (v,w) (or (w,v) for !directed) if such an edge exists, nullptr otherwise.

◆ sort()

template<class ADJ_ENTRY_LIST >

void ogdf::Graph::sort	(	node	v,
		const ADJ_ENTRY_LIST &	newOrder
	)

inline

Sorts the adjacency list of node v according to newOrder.

Precondition: newOrder contains exactly the adjacency entries of v!

Template Parameters

ADJ_ENTRY_LIST is the type of the input adjacency entry list.

Parameters

v	is the node whose adjacency list will be sorted.
newOrder	is the list of adjacency entries of `v` in the new order.

Definition at line 1086 of file Graph_d.h.

◆ split()

virtual edge ogdf::Graph::split ( edge e )

virtual

Splits edge e into two edges introducing a new node.

Let e=(v,w). Then, the resulting two edges are e=(v,u) and e'=(u,w), where u is a new node.

Note: The edge e is modified by this operation.

Parameters

e	is the edge to be split.

Returns: The edge e'.

Reimplemented in ogdf::GraphCopy, ogdf::ClusterPlanRep, ogdf::PlanRep, ogdf::PlanRepExpansion, ogdf::PlanRepInc, and ogdf::PlanRepUML.

◆ splitNode()

node ogdf::Graph::splitNode	(	adjEntry	adjStartLeft,
		adjEntry	adjStartRight
	)

Splits a node while preserving the order of adjacency entries.

This method splits a node v into two nodes vl and vr. Node vl receives all adjacent edges of v from adjStartLeft until the edge preceding adjStartRight, and vr the remaining nodes (thus adjStartRight is the first edge that goes to vr). The order of adjacency entries is preserved. Additionally, a new edge (vl,vr) is created, such that this edge is inserted before adjStartLeft and adjStartRight in the adjacency lists of vl and vr.

When adjStartLeft and adjStartRight are the same, vl receives all edges and the edge (vl, vr) is inserted before adjStartLeft in the adjacency list of vl.

Node v is modified to become node vl, and node vr is returned. This method is useful when modifying combinatorial embeddings.

Parameters

adjStartLeft	is the first entry that goes to the left node.
adjStartRight	is the first entry that goes to the right node.

Returns: the newly created node.

◆ swapAdjEdges()

void ogdf::Graph::swapAdjEdges	(	adjEntry	adj1,
		adjEntry	adj2
	)

inline

Exchanges two entries in an adjacency list.

Precondition: adj1 and adj2 must be belong to the same adjacency list.

Parameters

adj1	the first adjacency entry to be swapped.
adj2	the secomd adjacency entry to be swapped.

Definition at line 1166 of file Graph_d.h.

◆ unregisterArray() [1/3]

void ogdf::Graph::unregisterArray ( ListIterator< AdjEntryArrayBase * > it ) const

Unregisters an adjEntry array.

Parameters

it	is an iterator pointing to the entry in the list of registered adjacency entry arrays for the adjacency entry array to be unregistered.

◆ unregisterArray() [2/3]

void ogdf::Graph::unregisterArray ( ListIterator< EdgeArrayBase * > it ) const

Unregisters an edge array.

Parameters

it	is an iterator pointing to the entry in the list of registered edge arrays for the edge array to be unregistered.

◆ unregisterArray() [3/3]

void ogdf::Graph::unregisterArray ( ListIterator< NodeArrayBase * > it ) const

Unregisters a node array.

Parameters

it	is an iterator pointing to the entry in the list of registered node arrays for the node array to be unregistered.

◆ unregisterStructure()

void ogdf::Graph::unregisterStructure ( ListIterator< GraphObserver * > it ) const

Unregisters a graph observer.

Parameters

it	is an iterator pointing to the entry in the list of registered graph observers for the graph observer to be unregistered.

◆ unsplit() [1/2]

virtual void ogdf::Graph::unsplit	(	edge	eIn,
		edge	eOut
	)

virtual

Undoes a split operation.

For two edges eIn = (x,u) and eOut = (u,y), removes node u by joining eIn and eOut. Edge eOut is removed and eIn is reused.

Precondition: eIn and eOut are the only edges incident with u and none of them is a self-loop.

Parameters

eIn	is the (only) incoming edge of u.
eOut	is the (only) outgoing edge of u.

Reimplemented in ogdf::GraphCopy, and ogdf::PlanRepExpansion.

◆ unsplit() [2/2]

void ogdf::Graph::unsplit ( node u )

Undoes a split operation.

Removes node u by joining the two edges adjacent to u. The outgoing edge of u is removed and the incoming edge is reused

Precondition: u has exactly one incoming and one outgoing edge, and none of them is a self-loop.

Parameters

u	is the node to be unsplit.

Member Data Documentation

◆ edges

internal::GraphObjectContainer<EdgeElement> ogdf::Graph::edges

The container containing all edge objects.

Definition at line 592 of file Graph_d.h.

◆ m_edgeArrayTableSize

int ogdf::Graph::m_edgeArrayTableSize

private

The current table size of edge arrays associated with this graph.

Definition at line 530 of file Graph_d.h.

◆ m_edgeIdCount

int ogdf::Graph::m_edgeIdCount

private

The Index that will be assigned to the next created edge.

Definition at line 527 of file Graph_d.h.

◆ m_hiddenEdgeSets

List<HiddenEdgeSet*> ogdf::Graph::m_hiddenEdgeSets

private

The list of hidden edges.

Definition at line 541 of file Graph_d.h.

◆ m_mutexRegArrays

std::mutex ogdf::Graph::m_mutexRegArrays

mutableprivate

The critical section for protecting shared acces to register/unregister methods.

Definition at line 538 of file Graph_d.h.

◆ m_nodeArrayTableSize

int ogdf::Graph::m_nodeArrayTableSize

private

The current table size of node arrays associated with this graph.

Definition at line 529 of file Graph_d.h.

◆ m_nodeIdCount

int ogdf::Graph::m_nodeIdCount

private

The Index that will be assigned to the next created node.

Definition at line 526 of file Graph_d.h.

◆ m_regAdjArrays

ListPure<AdjEntryArrayBase*> ogdf::Graph::m_regAdjArrays

mutableprivate

The registered adjEntry arrays.

Definition at line 534 of file Graph_d.h.

◆ m_regEdgeArrays

ListPure<EdgeArrayBase*> ogdf::Graph::m_regEdgeArrays

mutableprivate

The registered edge arrays.

Definition at line 533 of file Graph_d.h.

◆ m_regNodeArrays

ListPure<NodeArrayBase*> ogdf::Graph::m_regNodeArrays

mutableprivate

The registered node arrays.

Definition at line 532 of file Graph_d.h.

◆ m_regStructures

ListPure<GraphObserver*> ogdf::Graph::m_regStructures

mutableprivate

The registered graph structures.

Definition at line 535 of file Graph_d.h.

◆ nodes

internal::GraphObjectContainer<NodeElement> ogdf::Graph::nodes

The container containing all node objects.

Definition at line 589 of file Graph_d.h.

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

include/ogdf/basic/Graph_d.h

OpenGraph DrawingFramework

Classes

Public Types

Public Member Functions

Public Attributes

Protected Member Functions

Private Member Functions

Private Attributes

Detailed Description

Thread Safety

Iteration

Member Typedef Documentation

◆ adjEntry_iterator

◆ edge_iterator

◆ node_iterator

Member Enumeration Documentation

◆ EdgeType

◆ NodeType

Constructor & Destructor Documentation

◆ Graph() [1/2]

◆ Graph() [2/2]

◆ ~Graph()

Member Function Documentation

◆ adjEntryArrayTableSize()

◆ allEdges()

◆ allNodes()

◆ assign()

◆ chooseEdge()

◆ chooseNode()

◆ clear()

◆ collapse()

◆ construct()

◆ constructInitByActiveNodes()

◆ constructInitByCC()

◆ constructInitByNodes()

◆ contract()

◆ copy() [1/2]

◆ copy() [2/2]

◆ createEdgeElement()

◆ delEdge()

◆ delNode()

◆ edgeArrayTableSize()

◆ empty()

◆ firstEdge()

◆ firstNode()

◆ genus()

◆ insert() [1/2]

◆ insert() [2/2]

◆ lastEdge()

◆ lastNode()

◆ maxAdjEntryIndex()

◆ maxEdgeIndex()

◆ maxNodeIndex()

◆ move()

◆ moveAdj() [1/2]

◆ moveAdj() [2/2]

◆ moveAdjAfter()

◆ moveAdjBefore()

◆ moveRegisterArray()

◆ moveSource() [1/2]

◆ moveSource() [2/2]

◆ moveTarget() [1/2]

◆ moveTarget() [2/2]

◆ newEdge() [1/5]

◆ newEdge() [2/5]

◆ newEdge() [3/5]

◆ newEdge() [4/5]

◆ newEdge() [5/5]

◆ newNode() [1/2]

◆ newNode() [2/2]

◆ nodeArrayTableSize()

◆ numberOfEdges()

◆ numberOfNodes()

◆ operator=()

◆ pureNewNode()

◆ registerArray() [1/3]

◆ registerArray() [2/3]

◆ registerArray() [3/3]

◆ registerStructure()

◆ reinitArrays()

Open
Graph Drawing
Framework