|
|||
|
|
|
|||
|
|
Creates a reduced graph by removing leaves, self-loops, and reducing chains. More...
#include <ogdf/graphalg/GraphReduction.h>
Inheritance diagram for ogdf::GraphReduction:Public Member Functions | |
| GraphReduction (const Graph &G) | |
| virtual | ~GraphReduction () |
| const Graph & | original () const |
| const List< edge > & | original (edge e) const |
| node | original (node v) const |
| edge | reduction (edge e) const |
| node | reduction (node v) const |
| 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. | |
Protected Member Functions | |
| GraphReduction () | |
| 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. | |
Protected Attributes | |
| EdgeArray< List< edge > > | m_eOrig |
| EdgeArray< edge > | m_eReduction |
| const Graph * | m_pGraph |
| NodeArray< node > | m_vOrig |
| NodeArray< node > | m_vReduction |
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. | |
Creates a reduced graph by removing leaves, self-loops, and reducing chains.
GraphReduction is read-only !!!
Definition at line 49 of file GraphReduction.h.
|
inlineprotected |
Definition at line 58 of file GraphReduction.h.
|
inlinevirtual |
Definition at line 64 of file GraphReduction.h.
Definition at line 67 of file GraphReduction.h.
Definition at line 73 of file GraphReduction.h.
Definition at line 70 of file GraphReduction.h.
Definition at line 79 of file GraphReduction.h.
Definition at line 76 of file GraphReduction.h.
Definition at line 53 of file GraphReduction.h.
Definition at line 56 of file GraphReduction.h.
Definition at line 51 of file GraphReduction.h.
Definition at line 52 of file GraphReduction.h.
Definition at line 55 of file GraphReduction.h.
