Open
Graph Drawing
Framework

 v.2015.05
 

ogdf::Graph Class Reference

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

Public Types

enum  EdgeType { association = 0, generalization = 1, dependency = 2 }
 The type of edges (only used in derived classes). More...
 
enum  NodeType { vertex, dummy, generalizationMerger, generalizationExpander, highDegreeExpander, lowDegreeExpander, associationClass }
 The type of nodes. More...
 

Public Member Functions

 Graph ()
 Constructs an empty graph. More...
 
 Graph (const Graph &G)
 Constructs a graph that is a copy of G. More...
 
virtual ~Graph ()
 Destructor. More...
 
Access methods
bool empty () const
 Returns true iff the graph is empty, i.e., contains no nodes. More...
 
int numberOfNodes () const
 Returns the number of nodes in the graph. More...
 
int numberOfEdges () const
 Returns the number of edges in the graph. More...
 
int maxNodeIndex () const
 Returns the largest used node index. More...
 
int maxEdgeIndex () const
 Returns the largest used edge index. More...
 
int maxAdjEntryIndex () const
 Returns the largest used adjEntry index. More...
 
int nodeArrayTableSize () const
 Returns the table size of node arrays associated with this graph. More...
 
int edgeArrayTableSize () const
 Returns the table size of edge arrays associated with this graph. More...
 
int adjEntryArrayTableSize () const
 Returns the table size of adjEntry arrays associated with this graph. More...
 
node firstNode () const
 Returns the first node in the list of all nodes. More...
 
node lastNode () const
 Returns the last node in the list of all nodes. More...
 
edge firstEdge () const
 Returns the first edge in the list of all edges. More...
 
edge lastEdge () const
 Returns the last edge in the list of all edges. More...
 
node chooseNode () const
 Returns a randomly chosen node. More...
 
edge chooseEdge () const
 Returns a randomly chosen edge. More...
 
template<class NODELIST >
void allNodes (NODELIST &nodes) const
 Returns a list with all nodes of the graph. More...
 
template<class EDGELIST >
void allEdges (EDGELIST &edges) const
 Returns a list with all edges of the graph. More...
 
template<class EDGELIST >
void adjEdges (node v, EDGELIST &edges) const
 Returns a list with all edges adjacent to node v. More...
 
template<class ADJLIST >
void adjEntries (node v, ADJLIST &entries) const
 Returns a list with all entries in the adjacency list of node v. More...
 
template<class EDGELIST >
void inEdges (node v, EDGELIST &edges) const
 Returns a list with all incoming edges of node v. More...
 
template<class EDGELIST >
void outEdges (node v, EDGELIST &edges) const
 Returns a list with all outgoing edges of node v. More...
 
Creation of new nodes and edges
node newNode ()
 Creates a new node and returns it. More...
 
node newNode (int index)
 Creates a new node with predefined index and returns it. More...
 
edge newEdge (node v, node w)
 Creates a new edge (v,w) and returns it. More...
 
edge newEdge (node v, node w, int index)
 Creates a new edge (v,w) with predefined index and returns it. More...
 
edge newEdge (adjEntry adjSrc, adjEntry adjTgt, Direction dir=ogdf::after)
 Creates a new edge at predefined positions in the adjacency lists. More...
 
edge newEdge (node v, adjEntry adjTgt)
 Creates a new edge at predefined positions in the adjacency lists. More...
 
edge newEdge (adjEntry adjSrc, node w)
 Creates a new edge at predefined positions in the adjacency lists. More...
 
Removing nodes and edges
virtual void delNode (node v)
 Removes node v and all incident edges from the graph. More...
 
virtual void delEdge (edge e)
 Removes edge e from the graph. More...
 
void clear ()
 Removes all nodes and all edges from the graph. More...
 
Hiding edges

These methods are used for temporarily hiding edges. Edges are removed from the list of all edges and their corresponding adfjacency entries from the repsective adjacency lists, but the edge objects themselves are not destroyed; hiddenedges can later be reactivated with restoreEdge().

void hideEdge (edge e)
 Hides the edge e. More...
 
void restoreEdge (edge e)
 Restores a hidden edge e. More...
 
void restoreAllEdges ()
 Restores all hidden edges. More...
 
Advanced modification methods
virtual edge split (edge e)
 Splits edge e into two edges introducing a new node. More...
 
void unsplit (node u)
 Undoes a split operation. More...
 
virtual void unsplit (edge eIn, edge eOut)
 Undoes a split operation. More...
 
node splitNode (adjEntry adjStartLeft, adjEntry adjStartRight)
 Splits a node while preserving the order of adjacency entries. More...
 
node contract (edge e)
 Contracts edge e while preserving the order of adjacency entries. More...
 
void move (edge e, adjEntry adjSrc, Direction dirSrc, adjEntry adjTgt, Direction dirTgt)
 Moves edge e to a different adjacency list. More...
 
void moveTarget (edge e, node w)
 Moves the target node of edge e to node w. More...
 
void moveTarget (edge e, adjEntry adjTgt, Direction dir)
 Moves the target node of edge e to a specific position in an adjacency list. More...
 
void moveSource (edge e, node w)
 Moves the source node of edge e to node w. More...
 
void moveSource (edge e, adjEntry adjSrc, Direction dir)
 Moves the source node of edge e to a specific position in an adjacency list. More...
 
edge searchEdge (node v, node w) const
 Searches and returns an edge connecting nodes v and w in time O(min(deg(v), deg(w))). More...
 
void reverseEdge (edge e)
 Reverses the edge e, i.e., exchanges source and target node. More...
 
void reverseAllEdges ()
 Reverses all edges in the graph. More...
 
template<class NODELIST >
void collaps (NODELIST &nodes)
 Collapses all nodes in the list nodes to the first node in the list. More...
 
template<class ADJ_ENTRY_LIST >
void sort (node v, const ADJ_ENTRY_LIST &newOrder)
 Sorts the adjacency list of node v according to newOrder. More...
 
void reverseAdjEdges (node v)
 Reverses the adjacency list of v. More...
 
void moveAdj (adjEntry adjMove, Direction dir, adjEntry adjPos)
 Moves adjacency entry adjMove before or after adjPos. More...
 
void moveAdjAfter (adjEntry adjMove, adjEntry adjAfter)
 Moves adjacency entry adjMove after adjAfter. More...
 
void moveAdjBefore (adjEntry adjMove, adjEntry adjBefore)
 Moves adjacency entry adjMove before adjBefore. More...
 
void reverseAdjEdges ()
 Reverses all adjacency lists. More...
 
void swapAdjEdges (adjEntry adj1, adjEntry adj2)
 Exchanges two entries in an adjacency list. More...
 
Miscellaneous
int genus () const
 Returns the genus of the graph's embedding. More...
 
bool representsCombEmbedding () const
 Returns true iff the graph represents a combinatorial embedding. More...
 
bool consistencyCheck () const
 Checks the consistency of the data structure. More...
 
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. More...
 
ListIterator< EdgeArrayBase * > registerArray (EdgeArrayBase *pEdgeArray) const
 Registers an edge array. More...
 
ListIterator< AdjEntryArrayBase * > registerArray (AdjEntryArrayBase *pAdjArray) const
 Registers an adjEntry array. More...
 
ListIterator< GraphObserver * > registerStructure (GraphObserver *pStructure) const
 Registers a graph observer (e.g. a ClusterGraph). More...
 
void unregisterArray (ListIterator< NodeArrayBase * > it) const
 Unregisters a node array. More...
 
void unregisterArray (ListIterator< EdgeArrayBase * > it) const
 Unregisters an edge array. More...
 
void unregisterArray (ListIterator< AdjEntryArrayBase * > it) const
 unregisters an adjEntry array. More...
 
void unregisterStructure (ListIterator< GraphObserver * > it) const
 Unregisters a graph observer. More...
 
void resetEdgeIdCount (int maxId)
 Resets the edge id count to maxId. More...
 
Operators
Graphoperator= (const Graph &G)
 Assignment operator. More...
 

Static Public Member Functions

static int nextPower2 (int start, int idCount)
 Returns the smallest power of 2 which is >= 2^start and > idCount. More...
 

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 > &nodes, 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. More...
 
void constructInitByNodes (const Graph &G, const List< node > &nodes, NodeArray< node > &mapNode, EdgeArray< edge > &mapEdge)
 Constructs a copy of the subgraph of G induced by nodes. More...
 

Private Member Functions

void copy (const Graph &G, NodeArray< node > &mapNode, EdgeArray< edge > &mapEdge)
 
void copy (const Graph &G)
 
edge createEdgeElement (node v, node w, adjEntry adjSrc, adjEntry adjTgt)
 
void enterCSRegArrays () const
 Enter critical section for (un-)registering arrays. More...
 
void leaveCSRegArrays () const
 Leave critical section for (un-)registering arrays. More...
 
void moveAdj (adjEntry adj, node w)
 
node pureNewNode ()
 
void reinitArrays ()
 
void reinitStructures ()
 
void resetAdjEntryIndex (int newIndex, int oldIndex)
 

Private Attributes

CriticalSection m_csRegArrays
 The critical section for protecting shared acces to register/unregister methods. More...
 
int m_edgeArrayTableSize
 The current table size of edge arrays associated with this graph. More...
 
int m_edgeIdCount
 The Index that will be assigned to the next created edge. More...
 
GraphList< EdgeElementm_edges
 The list of all edges. More...
 
GraphList< EdgeElementm_hiddenEdges
 The list of hidden edges. More...
 
int m_nEdges
 The number of edges in the graph. More...
 
int m_nNodes
 The number of nodes in the graph. More...
 
int m_nodeArrayTableSize
 The current table size of node arrays associated with this graph. More...
 
int m_nodeIdCount
 The Index that will be assigned to the next created node. More...
 
GraphList< NodeElementm_nodes
 The list of all nodes. More...
 
ListPure< AdjEntryArrayBase * > m_regAdjArrays
 The registered adjEntry arrays. More...
 
ListPure< EdgeArrayBase * > m_regEdgeArrays
 The registered edge arrays. More...
 
ListPure< NodeArrayBase * > m_regNodeArrays
 The registered node arrays. More...
 
ListPure< GraphObserver * > m_regStructures
 The registered graph structures. More...
 

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

Besides the usage of iteration macros defined in Graph_d.h, the following code is recommended for further iteration tasks.

  • Iteration over all outgoing edges e of node v:

    if(e->source() != v) continue;

  • Iteration over all ingoing edges e of node v:

    if(e->target() != v) continue;

  • Iteration over all nodes x reachable by an outgoing edge e of node v (without self-loops):

    if ((x = e->target()) == v) continue;

  • Iteration over all nodes x reachable by an outgoing edge e of node v (with self-loops):

    if (e->source() != v) continue;
    x = e->target();
    }

  • Iteration over all nodes x reachable by an ingoing edge e of node v (without self-loops):

    if ((x = e->source()) == v) continue;

  • Iteration over all nodes x reachable by an ingoing edge e of node v (with self-loops):
    if (e->target() != v) continue;
    x = e->source();
    }

Definition at line 412 of file Graph_d.h.

Member Enumeration Documentation

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

Enumerator
association 
generalization 
dependency 

Definition at line 442 of file Graph_d.h.

The type of nodes.

Enumerator
vertex 
dummy 
generalizationMerger 
generalizationExpander 
highDegreeExpander 
lowDegreeExpander 
associationClass 

Definition at line 449 of file Graph_d.h.

Constructor & Destructor Documentation

ogdf::Graph::Graph ( )

Constructs an empty graph.

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
Gis the graph that will be copied.
virtual ogdf::Graph::~Graph ( )
virtual

Destructor.

Member Function Documentation

template<class EDGELIST >
void ogdf::Graph::adjEdges ( node  v,
EDGELIST &  edges 
) const
inline

Returns a list with all edges adjacent to node v.

Template Parameters
EDGELISTis the type of edge list, which is returned.
Parameters
vis the node whose incident edges are queried.
edgesis assigned the list of all edges incident to v (including incoming and outcoming edges).

Definition at line 552 of file Graph_d.h.

template<class ADJLIST >
void ogdf::Graph::adjEntries ( node  v,
ADJLIST &  entries 
) const
inline

Returns a list with all entries in the adjacency list of node v.

Template Parameters
ADJLISTis the type of adjacency entry list, which is returned.
Parameters
vis the node whose adjacency entries are queried.
entriesis assigned the list of all adjacency entries in the adjacency list of v.

Definition at line 566 of file Graph_d.h.

int ogdf::Graph::adjEntryArrayTableSize ( ) const
inline

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

Definition at line 503 of file Graph_d.h.

template<class EDGELIST >
void ogdf::Graph::allEdges ( EDGELIST &  edges) const
inline

Returns a list with all edges of the graph.

Template Parameters
EDGELISTis the type of edge list, which is returned.
Parameters
edgesis assigned the list of all edges.

Definition at line 538 of file Graph_d.h.

template<class NODELIST >
void ogdf::Graph::allNodes ( NODELIST &  nodes) const
inline

Returns a list with all nodes of the graph.

Template Parameters
NODELISTis the type of node list, which is returned.
Parameters
nodesis assigned the list of all nodes.

Definition at line 526 of file Graph_d.h.

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

Returns a randomly chosen edge.

node ogdf::Graph::chooseNode ( ) const

Returns a randomly chosen node.

void ogdf::Graph::clear ( )

Removes all nodes and all edges from the graph.

template<class NODELIST >
void ogdf::Graph::collaps ( NODELIST &  nodes)
inline

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

Parallel edges are removed.

Template Parameters
NODELISTis the type of input node list.
Parameters
nodesis the list of nodes that will be collapsed. This list will be empty after the call.

Definition at line 897 of file Graph_d.h.

bool ogdf::Graph::consistencyCheck ( ) const

Checks the consistency of the data structure.

Remarks
This method is meant for debugging purposes only.
Returns
true if everything is ok, false if the data structure is inconsistent.
void ogdf::Graph::construct ( const Graph G,
NodeArray< node > &  mapNode,
EdgeArray< edge > &  mapEdge 
)
protected
void ogdf::Graph::constructInitByActiveNodes ( const List< node > &  nodes,
const NodeArray< bool > &  activeNodes,
NodeArray< node > &  mapNode,
EdgeArray< edge > &  mapEdge 
)
protected
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.

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

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

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

node ogdf::Graph::contract ( edge  e)

Contracts edge e while preserving the order of adjacency entries.

Parameters
eis the edge to be contracted.
Returns
the endpoint of e to which all edges have been moved.
void ogdf::Graph::copy ( const Graph G,
NodeArray< node > &  mapNode,
EdgeArray< edge > &  mapEdge 
)
private
void ogdf::Graph::copy ( const Graph G)
private
edge ogdf::Graph::createEdgeElement ( node  v,
node  w,
adjEntry  adjSrc,
adjEntry  adjTgt 
)
private
virtual void ogdf::Graph::delEdge ( edge  e)
virtual

Removes edge e from the graph.

Parameters
eis the egde that will be deleted.

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

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

Removes node v and all incident edges from the graph.

Parameters
vis the node that will be deleted.

Reimplemented in ogdf::GraphCopy.

int ogdf::Graph::edgeArrayTableSize ( ) const
inline

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

Definition at line 501 of file Graph_d.h.

bool ogdf::Graph::empty ( ) const
inline

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

Definition at line 483 of file Graph_d.h.

void ogdf::Graph::enterCSRegArrays ( ) const
inlineprivate

Enter critical section for (un-)registering arrays.

Definition at line 1267 of file Graph_d.h.

edge ogdf::Graph::firstEdge ( ) const
inline

Returns the first edge in the list of all edges.

Definition at line 511 of file Graph_d.h.

node ogdf::Graph::firstNode ( ) const
inline

Returns the first node in the list of all nodes.

Definition at line 506 of file Graph_d.h.

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, \(c\) connected components, \(nz\) isolated vertices, and \(fc\) face cycles. Then,

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

Returns
the genus of the graph's current embedding; if this is 0, then the graph is planarly embedded.
void ogdf::Graph::hideEdge ( edge  e)

Hides the edge e.

The edge e is removed from the list of all edges and adjacency lists of nodes, but not deleted; e can be restored by calling restoreEdge(e).

Attention
If an edge is hidden, its source and target node may not be deleted!
Parameters
eis the edge that will be hidden.
template<class EDGELIST >
void ogdf::Graph::inEdges ( node  v,
EDGELIST &  edges 
) const
inline

Returns a list with all incoming edges of node v.

Template Parameters
EDGELISTis the type of edge list, which is returned.
Parameters
vis the node whose incident edges are queried.
edgesis assigned the list of all incoming edges incident to v.

Definition at line 580 of file Graph_d.h.

edge ogdf::Graph::lastEdge ( ) const
inline

Returns the last edge in the list of all edges.

Definition at line 513 of file Graph_d.h.

node ogdf::Graph::lastNode ( ) const
inline

Returns the last node in the list of all nodes.

Definition at line 508 of file Graph_d.h.

void ogdf::Graph::leaveCSRegArrays ( ) const
inlineprivate

Leave critical section for (un-)registering arrays.

Definition at line 1274 of file Graph_d.h.

int ogdf::Graph::maxAdjEntryIndex ( ) const
inline

Returns the largest used adjEntry index.

Definition at line 496 of file Graph_d.h.

int ogdf::Graph::maxEdgeIndex ( ) const
inline

Returns the largest used edge index.

Definition at line 494 of file Graph_d.h.

int ogdf::Graph::maxNodeIndex ( ) const
inline

Returns the largest used node index.

Definition at line 492 of file Graph_d.h.

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
eis the edge to be moved.
adjSrcis the adjaceny entry before or after which the source adjacency entry of e will be inserted.
dirSrcspecifies if the source adjacency entry of e will be inserted before or after adjSrc.
adjTgtis the adjaceny entry before or after which the target adjacency entry of e will be inserted.
dirTgtspecifies if the target adjacency entry of e will be inserted before or after adjTgt.
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
adjMoveis an entry in the adjacency list of a node in this graph.
adjPosis an entry in the same adjacency list as adjMove.
dirspecifies if adjMove is moved before or after adjPos.

Definition at line 954 of file Graph_d.h.

void ogdf::Graph::moveAdj ( adjEntry  adj,
node  w 
)
private
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
adjMoveis an entry in the adjacency list of a node in this graph.
adjAfteris an entry in the same adjacency list as adjMove.

Definition at line 968 of file Graph_d.h.

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
adjMoveis an entry in the adjacency list of a node in this graph.
adjBeforeis an entry in the same adjacency list as adjMove.

Definition at line 981 of file Graph_d.h.

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
eis the edge whose source node is moved.
wis the new source node of e.
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
eis the edge whose source node is moved.
adjSrcis the adjacency entry before or after which the source adjacency entry of e is inserted.
dirspecifies if the source adjacency entry of e is inserted before or after adjSrc.
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
eis the edge whose target node is moved.
wis the new target node of e.
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
eis the edge whose target node is moved.
adjTgtis the adjacency entry before or after which the target adjacency entry of e is inserted.
dirspecifies if the target adjacency entry of e is inserted before or after adjTgt.
edge ogdf::Graph::newEdge ( node  v,
node  w 
)

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

Parameters
vis the source node of the newly created edge.
wis the target node of the newly created edge.
Returns
the newly created edge.
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
vis the source node of the newly created edge.
wis the target node of the newly created edge.
indexis the index that will be assigned to the newly created edge.
Returns
the newly created edge.
edge ogdf::Graph::newEdge ( adjEntry  adjSrc,
adjEntry  adjTgt,
Direction  dir = ogdf::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
adjSrcis the adjacency entry after which the new edge is inserted in the adjacency list of v.
adjTgtis the adjacency entry after which the new edge is inserted in the adjacency list of w.
dirspecifies if the edge is inserted before or after the given adjacency entries.
Returns
the newly created edge.
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
vis the source node of the new edge; the edge is added at the end of the adjacency list of v.
adjTgtis the adjacency entry after which the new edge is inserted in the adjacency list of w.
Returns
the newly created edge.
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
adjSrcis the adjacency entry after which the new edge is inserted in the adjacency list of v.
wis 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.
node ogdf::Graph::newNode ( )

Creates a new node and returns it.

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
indexis the index that will be assigned to the newly created node.
Returns
the newly created node.
static int ogdf::Graph::nextPower2 ( int  start,
int  idCount 
)
static

Returns the smallest power of 2 which is >= 2^start and > idCount.

int ogdf::Graph::nodeArrayTableSize ( ) const
inline

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

Definition at line 499 of file Graph_d.h.

int ogdf::Graph::numberOfEdges ( ) const
inline

Returns the number of edges in the graph.

Definition at line 489 of file Graph_d.h.

int ogdf::Graph::numberOfNodes ( ) const
inline

Returns the number of nodes in the graph.

Definition at line 486 of file Graph_d.h.

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
Gis the graph to be copied.
Returns
this graph.
template<class EDGELIST >
void ogdf::Graph::outEdges ( node  v,
EDGELIST &  edges 
) const
inline

Returns a list with all outgoing edges of node v.

Template Parameters
EDGELISTis the type of edge list, which is returned.
Parameters
vis the node whose incident edges are queried.
edgesis assigned the list of all outgoing edges incident to v.

Definition at line 594 of file Graph_d.h.

node ogdf::Graph::pureNewNode ( )
private
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
pNodeArrayis 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.
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
pEdgeArrayis 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.
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
pAdjArrayis 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.
ListIterator<GraphObserver*> ogdf::Graph::registerStructure ( GraphObserver pStructure) const

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

Parameters
pStructureis 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.
void ogdf::Graph::reinitArrays ( )
private
void ogdf::Graph::reinitStructures ( )
private
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 1028 of file Graph_d.h.

void ogdf::Graph::resetAdjEntryIndex ( int  newIndex,
int  oldIndex 
)
private
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 \(\leq\) maxId \(\leq\) maximal edge id in the graph.
Parameters
maxIdis an upper bound of the edge ids in the graph.
void ogdf::Graph::restoreAllEdges ( )

Restores all hidden edges.

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

Restores a hidden edge e.

Precondition
e is currently hidden and its source and target have not been removed!
Parameters
eis the hidden edge that will be restored.
void ogdf::Graph::reverseAdjEdges ( node  v)
inline

Reverses the adjacency list of v.

Parameters
vis the node whose adjacency list will be reveresed.

Definition at line 942 of file Graph_d.h.

void ogdf::Graph::reverseAdjEdges ( )

Reverses all adjacency lists.

void ogdf::Graph::reverseAllEdges ( )

Reverses all edges in the graph.

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

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

Parameters
eis the edge to be reveresed.
edge ogdf::Graph::searchEdge ( node  v,
node  w 
) const

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

Parameters
vis the source node of the edge to be searched.
wis the target node of the edge to be searched.
Returns
an edge (\ v,w) if such an edge exists, 0 otherwise.
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_LISTis the type of the input adjacency entry list.
Parameters
vis the node whose adjacency list will be sorted.
newOrderis the list of adjacency entries of v in the new order.

Definition at line 928 of file Graph_d.h.

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
eis the edge to be split.
Returns
The edge e'.

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

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 the adjacency lists of vl and vr.

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

Parameters
adjStartLeftis the first entry that goes to the left node.
adjStartRightis the first entry that goes to the right node.
Returns
the newly created node.
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
adj1the first adjacency entry to be swapped.
adj2the secomd adjacency entry to be swapped.

Definition at line 997 of file Graph_d.h.

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

Unregisters a node array.

Parameters
itis an iterator pointing to the entry in the list of registered node arrays for the node array to be unregistered.
void ogdf::Graph::unregisterArray ( ListIterator< EdgeArrayBase * >  it) const

Unregisters an edge array.

Parameters
itis an iterator pointing to the entry in the list of registered edge arrays for the edge array to be unregistered.
void ogdf::Graph::unregisterArray ( ListIterator< AdjEntryArrayBase * >  it) const

unregisters an adjEntry array.

Parameters
itis an iterator pointing to the entry in the list of registered adjacency entry arrays for the adjacency entry array to be unregistered.
void ogdf::Graph::unregisterStructure ( ListIterator< GraphObserver * >  it) const

Unregisters a graph observer.

Parameters
itis an iterator pointing to the entry in the list of registered graph observers for the graph observer to be unregistered.
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 e is reused

Precondition
u has exactly one incoming and one outgoing edge, and none of them is a self-loop.
Parameters
uis the node to be unsplit.
Returns
The edge e.
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
eInis the (only) incoming edge of u.
eOutis the (only) outgoing edge of u.

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

Member Data Documentation

CriticalSection ogdf::Graph::m_csRegArrays
mutableprivate

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

Definition at line 431 of file Graph_d.h.

int ogdf::Graph::m_edgeArrayTableSize
private

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

Definition at line 423 of file Graph_d.h.

int ogdf::Graph::m_edgeIdCount
private

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

Definition at line 420 of file Graph_d.h.

GraphList<EdgeElement> ogdf::Graph::m_edges
private

The list of all edges.

Definition at line 415 of file Graph_d.h.

GraphList<EdgeElement> ogdf::Graph::m_hiddenEdges
private

The list of hidden edges.

Definition at line 434 of file Graph_d.h.

int ogdf::Graph::m_nEdges
private

The number of edges in the graph.

Definition at line 417 of file Graph_d.h.

int ogdf::Graph::m_nNodes
private

The number of nodes in the graph.

Definition at line 416 of file Graph_d.h.

int ogdf::Graph::m_nodeArrayTableSize
private

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

Definition at line 422 of file Graph_d.h.

int ogdf::Graph::m_nodeIdCount
private

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

Definition at line 419 of file Graph_d.h.

GraphList<NodeElement> ogdf::Graph::m_nodes
private

The list of all nodes.

Definition at line 414 of file Graph_d.h.

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

The registered adjEntry arrays.

Definition at line 427 of file Graph_d.h.

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

The registered edge arrays.

Definition at line 426 of file Graph_d.h.

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

The registered node arrays.

Definition at line 425 of file Graph_d.h.

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

The registered graph structures.

Definition at line 428 of file Graph_d.h.


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