#include <Graph_d.h>

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. | |
| Graph (const Graph &G) | |
| Constructs a graph that is a copy of G. | |
| virtual | ~Graph () |
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 () const |
| Returns a randomly chosen node. | |
| edge | chooseEdge () const |
| Returns a randomly chosen edge. | |
| template<class NODELIST> | |
| void | allNodes (NODELIST &nodes) const |
| Returns a list with all nodes of the graph. | |
| template<class EDGELIST> | |
| void | allEdges (EDGELIST &edges) const |
| Returns a list with all edges of the graph. | |
| template<class EDGELIST> | |
| void | adjEdges (node v, EDGELIST &edges) const |
| Returns a list with all edges adjacent to node v. | |
| template<class ADJLIST> | |
| void | adjEntries (node v, ADJLIST &entries) const |
| Returns a list with all entries in the adjacency list of node v. | |
| template<class EDGELIST> | |
| void | inEdges (node v, EDGELIST &edges) const |
| Returns a list with all incoming edges of node v. | |
| template<class EDGELIST> | |
| void | outEdges (node v, EDGELIST &edges) const |
| Returns a list with all outgoing edges of node v. | |
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=ogdf::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 | |
| void | delNode (node v) |
| Removes node v and all incident edges from the graph. | |
| void | delEdge (edge e) |
| Removes edge e from the graph. | |
| void | clear () |
| Removes all nodes and all edges from the graph. | |
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. | |
| void | restoreEdge (edge e) |
| Restores a hidden edge e. | |
| void | restoreAllEdges () |
| Restores all hidden edges. | |
Advanced modification methods | |
| 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) |
| Contracts edge e while preserving the order of adjacency entries. | |
| void | move (edge e, adjEntry adjSrc, Direction dirSrc, adjEntry adjTgt, Direction dirTgt) |
| 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 node w. | |
| 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 node w. | |
| edge | searchEdge (node v, node w) const |
| Searches and returns the edge between node v and node 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 | collaps (NODELIST &nodes) |
| Collapses all nodes in the list nodes 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 the adjacency entry adjMove before or after adjPos. | |
| void | moveAdjAfter (adjEntry adjMove, adjEntry adjAfter) |
| Moves the adjacency entry adjMove after adjAfter. | |
| void | moveAdjBefore (adjEntry adjMove, adjEntry adjBefore) |
| Moves the adjacency entry adjMove before adjBefore. | |
| void | reverseAdjEdges () |
| Reverses all adjacency lists. | |
| void | swapAdjEdges (adjEntry adj1, adjEntry adj2) |
| Exchanges two entries in an adjacency list. | |
Input and output | |
| bool | readGML (const char *fileName) |
| Reads a graph in GML format from file fileName. | |
| bool | readGML (istream &is) |
| Reads a graph in GML format from input stream is. | |
| void | writeGML (const char *fileName) const |
| Writes the graph in GML format to file fileName. | |
| void | writeGML (ostream &os) const |
| Writes the graph in GML format to output stream os. | |
| bool | readLEDAGraph (const char *fileName) |
| Reads a graph in LEDA format from file fileName. | |
| bool | readLEDAGraph (istream &is) |
| Read a graph in LEDA format from input stream is. | |
Miscellaneous | |
| int | genus () const |
| Returns the genus of the graph. | |
| bool | representsCombEmbedding () const |
| Returns true iff the graph represents a combinatorial embedding. | |
| bool | consistencyCheck () const |
| Checks the consistency of the data structure. | |
Registering of arrays | |
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 GraphObserver (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 GraphObserver. | |
| void | resetEdgeIdCount (int maxId) |
| Resets the edge id count to maxId. | |
Operators | |
| Graph & | operator= (const Graph &G) |
| Assignment operator. | |
| void * | operator new (size_t nBytes) |
| void * | operator new (size_t, void *p) |
| void | operator delete (void *p, size_t nBytes) |
Static Public Member Functions | |
| static int | nextPower2 (int start, int idCount) |
| Returns the smallest power of 2 which is >= 2^start and > idCount. | |
Protected Member Functions | |
| void | construct (const Graph &G, NodeArray< node > &mapNode, EdgeArray< edge > &mapEdge) |
| void | assign (const Graph &G, NodeArray< node > &mapNode, EdgeArray< edge > &mapEdge) |
| 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. | |
| void | constructInitByActiveNodes (const List< node > &nodes, const NodeArray< bool > &activeNodes, NodeArray< node > &mapNode, EdgeArray< edge > &mapEdge) |
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) |
| node | pureNewNode () |
| void | moveAdj (adjEntry adj, node w) |
| void | reinitArrays () |
| void | reinitStructures () |
| void | resetAdjEntryIndex (int newIndex, int oldIndex) |
| bool | readToEndOfLine (istream &is) |
Private Attributes | |
| GraphList< NodeElement > | m_nodes |
| The list of all nodes. | |
| GraphList< EdgeElement > | m_edges |
| The list of all edges. | |
| int | m_nNodes |
| The number of nodes in the graph. | |
| int | m_nEdges |
| The number of edges in the graph. | |
| int | m_nodeIdCount |
| The Index that will be assigned to the next created node. | |
| int | m_edgeIdCount |
| The Index that will be assigned to the next created edge. | |
| int | m_nodeArrayTableSize |
| The current table size of node arrays associated with this graph. | |
| int | m_edgeArrayTableSize |
| The current table size of edge arrays associated with this graph. | |
| ListPure< NodeArrayBase * > | m_regNodeArrays |
| The registered node arrays. | |
| ListPure< EdgeArrayBase * > | m_regEdgeArrays |
| The registered edge arrays. | |
| ListPure< AdjEntryArrayBase * > | m_regAdjArrays |
| The registered adjEntry arrays. | |
| ListPure< GraphObserver * > | m_regStructures |
| The registered graph structures. | |
| GraphList< EdgeElement > | m_hiddenEdges |
| The list of hidden edges. | |
Besides the usage of iteration macros defined in Graph_d.h, the following code is recommended for further iteration tasks.
forall_adj_edges(e,v) if(e->source() != v) continue;
forall_adj_edges(e,v) if(e->target() != v) continue;
forall_adj_edges(e,v) if ((x = e->target()) == v) continue;
forall_adj_edges(e,v) { if (e->source() != v) continue; x = e->target(); }
forall_adj_edges(e,v) if ((x = e->source()) == v) continue;
forall_adj_edges(e,v) { if (e->target() != v) continue; x = e->source(); }
Definition at line 697 of file Graph_d.h.
The type of nodes.
| vertex | |
| dummy | |
| generalizationMerger | |
| generalizationExpander | |
| highDegreeExpander | |
| lowDegreeExpander | |
| associationClass |
Reimplemented in ogdf::ExtendedNestingGraph.
| 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.
| virtual ogdf::Graph::~Graph | ( | ) | [virtual] |
| bool ogdf::Graph::empty | ( | ) | const [inline] |
| int ogdf::Graph::numberOfNodes | ( | ) | const [inline] |
| int ogdf::Graph::numberOfEdges | ( | ) | const [inline] |
| int ogdf::Graph::maxNodeIndex | ( | ) | const [inline] |
| int ogdf::Graph::maxEdgeIndex | ( | ) | const [inline] |
| int ogdf::Graph::maxAdjEntryIndex | ( | ) | const [inline] |
| int ogdf::Graph::nodeArrayTableSize | ( | ) | const [inline] |
| int ogdf::Graph::edgeArrayTableSize | ( | ) | const [inline] |
| int ogdf::Graph::adjEntryArrayTableSize | ( | ) | const [inline] |
| node ogdf::Graph::firstNode | ( | ) | const [inline] |
| node ogdf::Graph::lastNode | ( | ) | const [inline] |
| edge ogdf::Graph::firstEdge | ( | ) | const [inline] |
| edge ogdf::Graph::lastEdge | ( | ) | const [inline] |
| node ogdf::Graph::chooseNode | ( | ) | const |
Returns a randomly chosen node.
| edge ogdf::Graph::chooseEdge | ( | ) | const |
Returns a randomly chosen edge.
| void ogdf::Graph::allNodes | ( | NODELIST & | nodes | ) | const [inline] |
| void ogdf::Graph::allEdges | ( | EDGELIST & | edges | ) | const [inline] |
| void ogdf::Graph::adjEdges | ( | node | v, | |
| EDGELIST & | edges | |||
| ) | const [inline] |
| void ogdf::Graph::adjEntries | ( | node | v, | |
| ADJLIST & | entries | |||
| ) | const [inline] |
| void ogdf::Graph::inEdges | ( | node | v, | |
| EDGELIST & | edges | |||
| ) | const [inline] |
| void ogdf::Graph::outEdges | ( | node | v, | |
| EDGELIST & | edges | |||
| ) | const [inline] |
| node ogdf::Graph::newNode | ( | ) |
| node ogdf::Graph::newNode | ( | int | index | ) |
Creates a new node with predefined index and returns it.
Creates a new edge (v,w) and returns it.
Reimplemented in ogdf::GraphCopySimple, and ogdf::GraphCopy.
Creates a new edge (v,w) with predefined index and returns it.
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. |
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).
| 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. |
Reimplemented in ogdf::GraphCopy.
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).
| 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. |
Reimplemented in ogdf::GraphCopy.
| void ogdf::Graph::delNode | ( | node | v | ) |
Removes node v and all incident edges from the graph.
| void ogdf::Graph::delEdge | ( | edge | e | ) |
Removes edge e from the graph.
| void ogdf::Graph::clear | ( | ) |
Removes all nodes and all edges from the graph.
| 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).
| void ogdf::Graph::restoreEdge | ( | edge | e | ) |
Restores a hidden edge e.
| void ogdf::Graph::restoreAllEdges | ( | ) |
Restores all hidden edges.
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.
Reimplemented in ogdf::GraphCopy, ogdf::ClusterPlanRep, ogdf::PlanRep, ogdf::PlanRepExpansion, ogdf::PlanRepInc, and ogdf::PlanRepUML.
| 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
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.
Reimplemented in ogdf::GraphCopy, and ogdf::PlanRepExpansion.
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. |
Contracts edge e while preserving the order of adjacency entries.
| void ogdf::Graph::move | ( | edge | e, | |
| adjEntry | adjSrc, | |||
| Direction | dirSrc, | |||
| adjEntry | adjTgt, | |||
| Direction | dirTgt | |||
| ) |
Moves the target node of edge e to node w.
If e=(v,u) before, then e=(v,w) afterwards-
Moves the target node of edge e to node w.
If e=(v,u) before, then e=(v,w) afterwards. Inserts the adjacency entry before or after adjTgt according to dir.
Moves the source node of edge e to node w.
If e=(v,u) before, then e=(w,u) afterwards.
Moves the source node of edge e to node w.
If e=(v,u) before, then e=(w,u) afterwards. Inserts the adjacency entry before or after adjSrc according to dir.
Searches and returns the edge between node v and node w.
| void ogdf::Graph::reverseEdge | ( | edge | e | ) |
Reverses the edge e, i.e., exchanges source and target node.
| void ogdf::Graph::reverseAllEdges | ( | ) |
Reverses all edges in the graph.
| void ogdf::Graph::collaps | ( | NODELIST & | nodes | ) | [inline] |
| void ogdf::Graph::sort | ( | node | v, | |
| const ADJ_ENTRY_LIST & | newOrder | |||
| ) | [inline] |
| void ogdf::Graph::reverseAdjEdges | ( | node | v | ) | [inline] |
Moves the adjacency entry adjMove before or after adjPos.
| 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. |
Moves the adjacency entry adjMove after adjAfter.
| 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. |
Moves the adjacency entry adjMove before adjBefore.
| 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 a