Source: http://www.ogdf.net/doc-ogdf/classogdf_1_1_graph.html
Timestamp: 2019-04-20 19:14:02+00:00

Document:
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().
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.
Data type for general directed graphs (adjacency list representation).
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.
Besides the usage of iteration macros defined in Graph_d.h, the following code is recommended for further iteration tasks.
Definition at line 412 of file Graph_d.h.
The type of edges (only used in derived classes).
Definition at line 442 of file Graph_d.h.
Definition at line 449 of file Graph_d.h.
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.
G is the graph that will be copied.
Returns a list with all edges adjacent to node v.
EDGELIST is the type of edge list, which is returned.
v is the node whose incident edges are queried.
edges is assigned the list of all edges incident to v (including incoming and outcoming edges).
Definition at line 552 of file Graph_d.h.
Returns a list with all entries in the adjacency list of node v.
ADJLIST is the type of adjacency entry list, which is returned.
v is the node whose adjacency entries are queried.
entries is assigned the list of all adjacency entries in the adjacency list of v.
Definition at line 566 of file Graph_d.h.
Returns the table size of adjEntry arrays associated with this graph.
Definition at line 503 of file Graph_d.h.
Returns a list with all edges of the graph.
edges is assigned the list of all edges.
Definition at line 538 of file Graph_d.h.
Returns a list with all nodes of the graph.
NODELIST is the type of node list, which is returned.
nodes is assigned the list of all nodes.
Definition at line 526 of file Graph_d.h.
Returns a randomly chosen edge.
Returns a randomly chosen node.
Removes all nodes and all edges from the graph.
Collapses all nodes in the list nodes to the first node in the list.
NODELIST is the type of input node list.
nodes is 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.
Checks the consistency of the data structure.
This method is meant for debugging purposes only.
true if everything is ok, false if the data structure is inconsistent.
Constructs a copy of connected component cc in info.
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.
Contracts edge e while preserving the order of adjacency entries.
e is the edge to be contracted.
the endpoint of e to which all edges have been moved.
Removes edge e from the graph.
e is the egde that will be deleted.
Reimplemented in ogdf::GraphCopy, and ogdf::PlanRepExpansion.
Removes node v and all incident edges from the graph.
v is the node that will be deleted.
Returns the table size of edge arrays associated with this graph.
Definition at line 501 of file Graph_d.h.
Returns true iff the graph is empty, i.e., contains no nodes.
Definition at line 483 of file Graph_d.h.
Enter critical section for (un-)registering arrays.
Definition at line 1267 of file Graph_d.h.
Returns the first edge in the list of all edges.
Definition at line 511 of file Graph_d.h.
Returns the first node in the list of all nodes.
Definition at line 506 of file Graph_d.h.
Returns the genus of the graph's embedding.
the genus of the graph's current embedding; if this is 0, then the graph is planarly embedded.
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).
If an edge is hidden, its source and target node may not be deleted!
e is the edge that will be hidden.
Returns a list with all incoming edges of node v.
edges is assigned the list of all incoming edges incident to v.
Definition at line 580 of file Graph_d.h.
Returns the last edge in the list of all edges.
Definition at line 513 of file Graph_d.h.
Returns the last node in the list of all nodes.
Definition at line 508 of file Graph_d.h.
Leave critical section for (un-)registering arrays.
Definition at line 1274 of file Graph_d.h.
Returns the largest used adjEntry index.
Definition at line 496 of file Graph_d.h.
Returns the largest used edge index.
Definition at line 494 of file Graph_d.h.
Returns the largest used node index.
Definition at line 492 of file Graph_d.h.
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).
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.
Moves adjacency entry adjMove before or after adjPos.
adjMove and adjAfter are distinct entries in the same adjacency list.
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 954 of file Graph_d.h.
Moves adjacency entry adjMove after adjAfter.
adjAfter is an entry in the same adjacency list as adjMove.
Definition at line 968 of file Graph_d.h.
Moves adjacency entry adjMove before adjBefore.
adjMove and adjBefore are distinct entries in the same adjacency list.
adjBefore is an entry in the same adjacency list as adjMove.
Definition at line 981 of file Graph_d.h.
Moves the source node of edge e to node w.
If e=(v,u) before, then e=(w,u) afterwards.
e is the edge whose source node is moved.
w is the new source node of e.
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.
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.
Moves the target node of edge e to node w.
If e=(v,u) before, then e=(v,w) afterwards.
e is the edge whose target node is moved.
w is the new target node of e.
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.
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.
Creates a new edge (v,w) and returns it.
v is the source node of the newly created edge.
w is the target node of the newly created edge.
Creates a new edge (v,w) with predefined index and returns it.
index is currently not the index of any other edge in the graph.
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!
index is the index that will be assigned to the newly created edge.
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).
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.
Let w be the node whose adjacency list contains adjTgt. Then, the created edge is (v,w).
v is the source node of the new edge; the edge is added at the end of the adjacency list of v.
Let v be the node whose adjacency list contains adjSrc. Then, the created edge is (v,w).
w is the source node of the new edge; the edge is added at the end of the adjacency list of w.
Creates a new node and returns it.
Creates a new node with predefined index and returns it.
index is currently not the index of any other node in the graph.
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!
index is the index that will be assigned to the newly created node.
Returns the smallest power of 2 which is >= 2^start and > idCount.
Returns the table size of node arrays associated with this graph.
Definition at line 499 of file Graph_d.h.
Returns the number of edges in the graph.
Definition at line 489 of file Graph_d.h.
Returns the number of nodes in the graph.
Definition at line 486 of file Graph_d.h.
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.
G is the graph to be copied.
Returns a list with all outgoing edges of node v.
edges is assigned the list of all outgoing edges incident to v.
Definition at line 594 of file Graph_d.h.
This method is automatically called by node arrays; it should not be called manually.
pNodeArray is a pointer to the node array's base; this node array must be associated with this graph.
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.
This method is automatically called by edge arrays; it should not be called manually.
pEdgeArray is a pointer to the edge array's base; this edge array must be associated with this graph.
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.
This method is automatically called by adjacency entry arrays; it should not be called manually.
pAdjArray is a pointer to the adjacency entry array's base; this adjacency entry array must be associated with this graph.
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.
Registers a graph observer (e.g. a ClusterGraph).
pStructure is a pointer to the graph observer that shall be registered; this graph observer must be associated with this graph.
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.
Returns true iff the graph represents a combinatorial embedding.
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.
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).
Reducing the edge id count will reduce the memory consumption of edge arrays associated with the graph.
-1 \(\leq\) maxId \(\leq\) maximal edge id in the graph.
maxId is an upper bound of the edge ids in the graph.
Restores a hidden edge e.
e is currently hidden and its source and target have not been removed!
e is the hidden edge that will be restored.
Reverses the adjacency list of v.
v is the node whose adjacency list will be reveresed.
Definition at line 942 of file Graph_d.h.
Reverses all edges in the graph.
Reverses the edge e, i.e., exchanges source and target node.
e is the edge to be reveresed.
Searches and returns an edge connecting nodes v and w in time O(min(deg(v), deg(w))).
v is the source node of the edge to be searched.
w is the target node of the edge to be searched.
an edge (\ v,w) if such an edge exists, 0 otherwise.
Sorts the adjacency list of node v according to newOrder.
newOrder contains exactly the adjacency entries of v!
ADJ_ENTRY_LIST is the type of the input adjacency entry list.
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 928 of file Graph_d.h.
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.
The edge e is modified by this operation.
e is the edge to be split.
Reimplemented in ogdf::PlanRep, ogdf::GraphCopy, ogdf::PlanRepExpansion, ogdf::PlanRepUML, ogdf::PlanRepInc, and ogdf::ClusterPlanRep.
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.
adjStartLeft is the first entry that goes to the left node.
adjStartRight is the first entry that goes to the right node.
Exchanges two entries in an adjacency list.
adj1 and adj2 must be belong to the same adjacency list.
adj1 the first adjacency entry to be swapped.
adj2 the secomd adjacency entry to be swapped.
Definition at line 997 of file Graph_d.h.
it is an iterator pointing to the entry in the list of registered node arrays for the node array to be unregistered.
it is an iterator pointing to the entry in the list of registered edge arrays for the edge array to be unregistered.
it is an iterator pointing to the entry in the list of registered adjacency entry arrays for the adjacency entry array to be unregistered.
it is an iterator pointing to the entry in the list of registered graph observers for the graph observer to be unregistered.
u has exactly one incoming and one outgoing edge, and none of them is a self-loop.
u is the node to be unsplit.
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.
eIn and eOut are the only edges incident with u and none of them is a self-loop.
eIn is the (only) incoming edge of u.
eOut is the (only) outgoing edge of u.
The critical section for protecting shared acces to register/unregister methods.
Definition at line 431 of file Graph_d.h.
The current table size of edge arrays associated with this graph.
Definition at line 423 of file Graph_d.h.
The Index that will be assigned to the next created edge.
Definition at line 420 of file Graph_d.h.
The list of all edges.
Definition at line 415 of file Graph_d.h.
The list of hidden edges.
Definition at line 434 of file Graph_d.h.
The number of edges in the graph.
Definition at line 417 of file Graph_d.h.
The number of nodes in the graph.
Definition at line 416 of file Graph_d.h.
The current table size of node arrays associated with this graph.
Definition at line 422 of file Graph_d.h.
The Index that will be assigned to the next created node.
Definition at line 419 of file Graph_d.h.
The list of all nodes.
Definition at line 414 of file Graph_d.h.
Definition at line 427 of file Graph_d.h.
Definition at line 426 of file Graph_d.h.
Definition at line 425 of file Graph_d.h.
Definition at line 428 of file Graph_d.h.

References: v.

 v.

 v.

 v.

 v.

 v.

 v.

 v.

 v.

 v.