|
|||
|
|
|
|||
|
|
#include <ogdf/upward/FaceSinkGraph.h>
Inheritance diagram for ogdf::FaceSinkGraph:Public Member Functions | |
| FaceSinkGraph () | |
| default constructor (dummy) | |
| FaceSinkGraph (const ConstCombinatorialEmbedding &E, node s) | |
| constructor (we assume that the original graph is connected!) | |
| bool | containsSource (node v) const |
| node | faceNodeOf (edge e) |
| node | faceNodeOf (face f) |
| void | init (const ConstCombinatorialEmbedding &E, node s) |
| const ConstCombinatorialEmbedding & | originalEmbedding () const |
| returns a reference to the embedding E of the original graph G | |
| face | originalFace (node v) const |
| returns the face in E corresponding to node v in the face-sink graph, 0 if v corresponds to a sink-switch | |
| const Graph & | originalGraph () const |
| return a reference to the original graph G | |
| node | originalNode (node v) const |
| returns the sink-switch in G corresponding to node v in the face-sink graph, 0 if v corresponds to a face | |
| node | possibleExternalFaces (SList< face > &externalFaces) |
| returns the list of faces f in E such that there exists an upward-planar drawing realizing E with f as external face a node v_T in tree T is returned as representative. v_T is 0 if no possible external face exists. | |
| void | sinkSwitches (FaceArray< List< adjEntry > > &faceSwitches) |
| compute the sink switches of all faces. | |
| void | stAugmentation (node h, Graph &G, node &superSink, SList< edge > &augmentedEdges) |
| augments G to an st-planar graph | |
| void | stAugmentation (node h, Graph &G, SList< node > &augmentedNodes, SList< edge > &augmentedEdges) |
| augments G to an st-planar graph (original implementation) | |
| Public Member Functions inherited from ogdf::Graph | |
| Graph () | |
| Constructs an empty graph. | |
| Graph (const Graph &G) | |
Constructs a graph that is a copy of G. | |
| virtual | ~Graph () |
| Destructor. | |
| 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. | |
| 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. | |
| 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. | |
| 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. | |
| int | genus () const |
| Returns the genus of the graph's embedding. | |
| bool | representsCombEmbedding () const |
| Returns true iff the graph represents a combinatorial embedding. | |
| 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. | |
| Graph & | operator= (const Graph &G) |
| Assignment operator. | |
Private Member Functions | |
| node | checkForest () |
| checks if the face-sink graph is a forest with 1) there is exactly one tree T containing no internal vertex of G 2) all other trees contain exactly one internal vertex of G a node in tree T is returned as representative | |
| bool | dfsCheckForest (node v, node parent, NodeArray< bool > &visited, int &nInternalVertices) |
| performs dfs-traversal and checks for backwards edges | |
| node | dfsFaceNodeOf (node v, node parent, face f1, face f2) |
| node | dfsStAugmentation (node v, node parent, Graph &G, SList< edge > &augmentedEdges) |
| node | dfsStAugmentation (node v, node parent, Graph &G, SList< node > &augmentedNodes, SList< edge > &augmentedEdges) |
| void | doInit () |
| constructs face-sink graph | |
| void | gatherExternalFaces (node v, node parent, SList< face > &externalFaces) |
| builds list of possible external faces | |
Private Attributes | |
| NodeArray< bool > | m_containsSource |
| contains face node the source ? | |
| NodeArray< face > | m_originalFace |
| original face in E | |
| NodeArray< node > | m_originalNode |
| original node in G | |
| const ConstCombinatorialEmbedding * | m_pE |
| associated embedding of graph G | |
| node | m_source |
| the single source | |
| node | m_T |
| representative of unique tree T | |
Additional Inherited Members | |
| Public Types inherited from ogdf::Graph | |
| 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... | |
| 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 Attributes inherited from ogdf::Graph | |
| internal::GraphObjectContainer< NodeElement > | nodes |
| The container containing all node objects. | |
| internal::GraphObjectContainer< EdgeElement > | edges |
| The container containing all edge objects. | |
| Protected Member Functions inherited from ogdf::Graph | |
| 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. | |
Definition at line 42 of file FaceSinkGraph.h.
| ogdf::FaceSinkGraph::FaceSinkGraph | ( | const ConstCombinatorialEmbedding & | E, |
| node | s | ||
| ) |
constructor (we assume that the original graph is connected!)
|
inline |
default constructor (dummy)
Definition at line 48 of file FaceSinkGraph.h.
|
private |
checks if the face-sink graph is a forest with 1) there is exactly one tree T containing no internal vertex of G 2) all other trees contain exactly one internal vertex of G a node in tree T is returned as representative
Definition at line 68 of file FaceSinkGraph.h.
|
private |
performs dfs-traversal and checks for backwards edges
|
private |
|
private |
|
private |
constructs face-sink graph
Definition at line 81 of file FaceSinkGraph.h.
Definition at line 86 of file FaceSinkGraph.h.
|
private |
builds list of possible external faces
all faces in tree T containing the single source s) by a dfs traversal of T
| void ogdf::FaceSinkGraph::init | ( | const ConstCombinatorialEmbedding & | E, |
| node | s | ||
| ) |
|
inline |
returns a reference to the embedding E of the original graph G
Definition at line 56 of file FaceSinkGraph.h.
returns the face in E corresponding to node v in the face-sink graph, 0 if v corresponds to a sink-switch
Definition at line 64 of file FaceSinkGraph.h.
return a reference to the original graph G
Definition at line 53 of file FaceSinkGraph.h.
returns the sink-switch in G corresponding to node v in the face-sink graph, 0 if v corresponds to a face
Definition at line 60 of file FaceSinkGraph.h.
returns the list of faces f in E such that there exists an upward-planar drawing realizing E with f as external face a node v_T in tree T is returned as representative. v_T is 0 if no possible external face exists.
Definition at line 73 of file FaceSinkGraph.h.
compute the sink switches of all faces.
| void ogdf::FaceSinkGraph::stAugmentation | ( | node | h, |
| Graph & | G, | ||
| node & | superSink, | ||
| SList< edge > & | augmentedEdges | ||
| ) |
augments G to an st-planar graph
(introduces only one new node as super sink into G)
| void ogdf::FaceSinkGraph::stAugmentation | ( | node | h, |
| Graph & | G, | ||
| SList< node > & | augmentedNodes, | ||
| SList< edge > & | augmentedEdges | ||
| ) |
augments G to an st-planar graph (original implementation)
introduces also new nodes into G corresponding to face-nodes in face sink graph)
contains face node the source ?
Definition at line 148 of file FaceSinkGraph.h.
original face in E
Definition at line 147 of file FaceSinkGraph.h.
original node in G
Definition at line 146 of file FaceSinkGraph.h.
|
private |
associated embedding of graph G
Definition at line 142 of file FaceSinkGraph.h.
|
private |
the single source
Definition at line 143 of file FaceSinkGraph.h.
|
private |
representative of unique tree T
Definition at line 144 of file FaceSinkGraph.h.
