|
| | UpwardPlanRep () |
| | standart constructor
|
| |
| | UpwardPlanRep (const CombinatorialEmbedding &Gamma) |
| |
| | UpwardPlanRep (const GraphCopy &GC, adjEntry adj_ext) |
| |
| | UpwardPlanRep (const UpwardPlanRep &UPR) |
| | copy constructor
|
| |
| virtual | ~UpwardPlanRep () |
| |
| void | augment () |
| | convert to a single source single sink graph (result is not necessary a st-graph!).
|
| |
| bool | augmented () const |
| | return true if graph is augmented to a single source single sink graph
|
| |
| adjEntry | getAdjEntry (const CombinatorialEmbedding &Gamma, node v, face f) const |
| | return the adjEntry of v which right face is f.
|
| |
| CombinatorialEmbedding & | getEmbedding () |
| |
| const CombinatorialEmbedding & | getEmbedding () const |
| | return the upward planar embedding
|
| |
| node | getSuperSink () const |
| |
| node | getSuperSource () const |
| |
| void | insertEdgePathEmbedded (edge eOrig, SList< adjEntry > crossedEdges, EdgeArray< int > &cost) |
| | same as insertEdgePath, but assumes that the graph is embedded
|
| |
| bool | isSinkArc (edge e) const |
| |
| bool | isSourceArc (edge e) const |
| |
| adjEntry | leftInEdge (node v) const |
| |
| int | numberOfCrossings () const |
| |
| UpwardPlanRep & | operator= (const UpwardPlanRep ©) |
| | Assignment operator.
|
| |
| void | outputFaces (const CombinatorialEmbedding &embedding) const |
| |
| adjEntry | sinkSwitchOf (node v) |
| | 0 if node v is not a sink switch (not the top sink switch !!) of an internal face. else v is sink-switch of the right face of the adjEntry.
|
| |
| | GraphCopy () |
| | Default constructor (does nothing!).
|
| |
| | GraphCopy (const Graph &G) |
| | Creates a graph copy of G.
|
| |
| | GraphCopy (const GraphCopy &GC) |
| | Copy constructor.
|
| |
| virtual | ~GraphCopy () |
| |
| const Graph & | original () const |
| | Returns a reference to the original graph.
|
| |
| node | original (node v) const |
| | Returns the node in the original graph corresponding to v.
|
| |
| edge | original (edge e) const |
| | Returns the edge in the original graph corresponding to e.
|
| |
| adjEntry | original (adjEntry adj) const |
| | Returns the adjacency entry in the original graph corresponding to adj.
|
| |
| node | copy (node v) const |
| | Returns the node in the graph copy corresponding to v.
|
| |
| const List< edge > & | chain (edge e) const |
| | Returns the list of edges coresponding to edge e.
|
| |
| edge | copy (edge e) const |
| | Returns the first edge in the list of edges coresponding to edge e.
|
| |
| adjEntry | copy (adjEntry adj) const |
| | Returns the adjacency entry in the copy graph corresponding to adj.
|
| |
| bool | isDummy (node v) const |
| | Returns true iff v has no corresponding node in the original graph.
|
| |
| bool | isDummy (edge e) const |
| | Returns true iff e has no corresponding edge in the original graph.
|
| |
| bool | isReversed (edge e) const |
| | Returns true iff edge e has been reversed.
|
| |
| bool | isReversedCopyEdge (edge e) const |
| | Returns true iff e is reversed w.r.t.
|
| |
| node | newNode (node vOrig) |
| | Creates a new node in the graph copy with original node vOrig.
|
| |
| virtual void | delNode (node v) override |
| | Removes node v and all its adjacent edges cleaning-up their corresponding lists of original edges.
|
| |
| virtual void | delEdge (edge e) override |
| | Removes edge e and clears the list of edges corresponding to e's original edge.
|
| |
| virtual void | clear () override |
| | Removes all nodes and all edges from the graph.
|
| |
| virtual edge | split (edge e) override |
| | Splits edge e.
|
| |
| void | unsplit (edge eIn, edge eOut) override |
| | Undoes a previous split operation.
|
| |
| edge | newEdge (edge eOrig) |
| | Creates a new edge (v,w) with original edge eOrig.
|
| |
| void | setEdge (edge eOrig, edge eCopy) |
| | sets eOrig to be the corresponding original edge of eCopy and vice versa
|
| |
| bool | embed () |
| | Embeds the graph copy.
|
| |
| void | removePseudoCrossings () |
| | Removes all crossing nodes which are actually only two "touching" edges.
|
| |
| bool | hasSameEdgesCrossings () const |
| | Returns whether there are two edges in the GraphCopy that cross each other multiple times.
|
| |
| bool | hasAdjacentEdgesCrossings () const |
| | Returns whether the GraphCopy contains at least one crossing of two adjacent edges.
|
| |
| bool | hasNonSimpleCrossings () const |
| | Returns whether the GraphCopy contains crossings that will result in a non-simple drawing.
|
| |
| void | removeNonSimpleCrossings (SListPure< edge > &edgesToCheck, DynamicDualGraph *dualGraph=nullptr) |
| | Removes all non-simple cossings involving edges from edgesToCheck (see hasNonSimpleCrossings() for a definition of non-simple crossings).
|
| |
| void | removeNonSimpleCrossings (DynamicDualGraph *dualGraph=nullptr) |
| | Removes all non-simple cossings (see hasNonSimpleCrossings() for a definition of non-simple crossings).
|
| |
| void | removeNonSimpleCrossings (node origNode, DynamicDualGraph *dualGraph=nullptr) |
| | Removes all non-simple cossings involving edges incident to origNode (see hasNonSimpleCrossings() for a definition of non-simple crossings).
|
| |
| void | insertEdgePath (edge eOrig, const SList< adjEntry > &crossedEdges) |
| | Re-inserts edge eOrig by "crossing" the edges in crossedEdges.
|
| |
| void | insertEdgePath (node srcOrig, node tgtOrig, const SList< adjEntry > &crossedEdges) |
| | Special version (for FixedEmbeddingUpwardEdgeInserter only).
|
| |
| void | removeEdgePath (edge eOrig) |
| | Removes the complete edge path for edge eOrig.
|
| |
| edge | insertCrossing (edge &crossingEdge, edge crossedEdge, bool rightToLeft) |
| | Inserts crossings between two copy 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.
|
| |
| edge | newEdge (node v, adjEntry adj, edge eOrig, CombinatorialEmbedding &E) |
| | Creates a new edge with original edge eOrig in an embedding E.
|
| |
| void | setOriginalEmbedding () |
| | Sets the embedding of the graph copy to the embedding of the original graph.
|
| |
| void | insertEdgePathEmbedded (edge eOrig, CombinatorialEmbedding &E, const SList< adjEntry > &crossedEdges) |
| | Re-inserts edge eOrig by "crossing" the edges in crossedEdges in embedding E.
|
| |
| void | insertEdgePathEmbedded (edge eOrig, CombinatorialEmbedding &E, DynamicDualGraph &dual, const SList< adjEntry > &crossedEdges) |
| |
| void | removeEdgePathEmbedded (CombinatorialEmbedding &E, edge eOrig, FaceSet< false > &newFaces) |
| | Removes the complete edge path for edge eOrig while preserving the embedding.
|
| |
| void | removeEdgePathEmbedded (CombinatorialEmbedding &E, DynamicDualGraph &dual, edge eOrig) |
| |
| void | init (const Graph &G) |
| | Re-initializes the copy using the graph G.
|
| |
| void | createEmpty (const Graph &G) |
| | Associates the graph copy with G, but does not create any nodes or edges.
|
| |
| void | initByCC (const CCsInfo &info, int cc, EdgeArray< edge > &eCopy) |
| | Initializes the graph copy for the nodes in component cc.
|
| |
| void | initByNodes (const List< node > &origNodes, EdgeArray< edge > &eCopy) |
| | Initializes the graph copy for the nodes in a component.
|
| |
| void | initByActiveNodes (const List< node > &nodeList, const NodeArray< bool > &activeNodes, EdgeArray< edge > &eCopy) |
| | Initializes the graph copy for the nodes in nodeList.
|
| |
| GraphCopy & | operator= (const GraphCopy &GC) |
| | Assignment operator.
|
| |
| | 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.
|
| |
| 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.
|
| |
| void | unsplit (node u) |
| | 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.
|
| |
Upward planarized representations (of a connected component) of a graph.
The upward planarization representation is a single source single sink graph. The single source is s_hat and the single sink is t_hat. s_hat is connected with the sources of the original graph. This muss be done before creating of a instance of UpwardPlanRep. The super sink t_hat is contructed in this class. For technical reason we contruct a sink t and connect the sink of the original graph with t. Then we connect t with t_hat. The edge (t,t_hat) is called the external face handle. Because the right face of the adjEntry of this edge should be the external face.
Definition at line 50 of file UpwardPlanRep.h.
Inheritance diagram for ogdf::UpwardPlanRep:
