|
|||
|
|
|
|||
|
|
A data structure to store full components with additional "loss" functionality. More...
#include <ogdf/graphalg/steiner_tree/FullComponentStore.h>
Inheritance diagram for ogdf::steiner_tree::FullComponentWithLossStore< T >:Public Member Functions | |
| void | computeAllLosses () |
| Compute the loss, both edge set and value, of all full components. | |
| T | loss (int id) const |
| Returns the loss value of full component with given id. | |
| const List< edge > & | lossBridges (int id) const |
| Returns a list of non-loss edges (that are bridges between the Loss components) of full component with given id. | |
| node | lossTerminal (node v) const |
| Returns the terminal (in the original graph) that belongs to a given node v (in the store) according to the Loss of the component. | |
| Public Member Functions inherited from ogdf::steiner_tree::FullComponentWithExtraStore< T, LossMetadata< T > > | |
| LossMetadata< T > & | extra (int i) |
| Returns a reference to the extra data of this full component. | |
| const LossMetadata< T > & | extra (int i) const |
| Returns a const reference to the extra data of this full component. | |
| Public Member Functions inherited from ogdf::steiner_tree::FullComponentStore< T, ExtraDataType > | |
| FullComponentStore (const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal) | |
| T | cost (int i) const |
| Returns the sum of edge costs of this full component. | |
| template<typename Fun > | |
| void | foreachAdjEntry (int i, Fun f) const |
| template<typename Fun > | |
| void | foreachEdge (int id, const NodeArray< NodeArray< edge > > &pred, Fun f) const |
| template<typename Fun > | |
| void | foreachNode (int id, const NodeArray< NodeArray< edge > > &pred, Fun f) const |
| template<typename Fun > | |
| void | foreachNode (int id, Fun f) const |
| const EdgeWeightedGraph< T > & | graph () const |
| void | insert (const EdgeWeightedGraphCopy< T > &comp) |
Inserts a component. Note that comp is copied and degree-2 nodes are removed. | |
| bool | isEmpty () const |
| Checks if the store does not contain any full components. | |
| bool | isTerminal (int id, node t) const |
| checks if a given node t is a terminal in the full component with given id | |
| bool | isTerminal (node v) const |
| node | original (node v) const |
| void | remove (int id) |
Removes a component by its id. | |
| int | size () const |
| Returns the number of full components in the store. | |
| adjEntry | start (int i) const |
| const Array< node > & | terminals (int id) const |
| Returns the list of terminals in the full component with given id. | |
Protected Member Functions | |
| node | findLossTerminal (const node u, const NodeArray< edge > &pred) |
| Starting from a Steiner node find the nearest terminal along a shortest path. | |
| Protected Member Functions inherited from ogdf::steiner_tree::FullComponentStore< T, ExtraDataType > | |
| void | copyEdges (Metadata< ExtraDataType > &data, const EdgeWeightedGraphCopy< T > &comp) |
Copy edges from comp into our representation. | |
| void | copyEdgesWithSimplifiedPaths (Metadata< ExtraDataType > &data, const EdgeWeightedGraphCopy< T > &comp, const ArrayBuffer< node > &nonterminals) |
Copy edges from comp into our representation, traversing variant to ignore degree-2 nodes. | |
| void | traverseOverDegree2Nonterminals (node &uO, T &weight, EdgeArray< bool > &marked, adjEntry adj, const EdgeWeightedGraphCopy< T > &comp) const |
| Traverse over degree-2 nonterminals. | |
Protected Attributes | |
| NodeArray< node > | m_lossTerminal |
| Indicates which Steiner node is connected to which terminal through the loss edges, indexed by the Steiner node. | |
| Protected Attributes inherited from ogdf::steiner_tree::FullComponentStore< T, ExtraDataType > | |
| ArrayBuffer< Metadata< ExtraDataType > > | m_components |
| List of full components (based on metadata) | |
| EdgeWeightedGraph< T > | m_graph |
| Our graph representation for the full component store. | |
| const NodeArray< bool > & | m_isTerminal |
| Incidence vector for terminal nodes. | |
| NodeArray< node > | m_nodeCopy |
| Mapping of original terminals to m_graph nodes. | |
| NodeArray< node > | m_nodeOrig |
| Mapping of m_graph nodes to original nodes. | |
| const EdgeWeightedGraph< T > & | m_originalGraph |
| The original Steiner instance. | |
| const List< node > & | m_terminals |
| The terminal list of the original Steiner instance. | |
A data structure to store full components with additional "loss" functionality.
Definition at line 381 of file FullComponentStore.h.
|
inline |
Compute the loss, both edge set and value, of all full components.
Definition at line 405 of file FullComponentStore.h.
|
inlineprotected |
Starting from a Steiner node find the nearest terminal along a shortest path.
| u | Steiner node to start from |
| pred | The shortest path predecessor data structure |
Definition at line 393 of file FullComponentStore.h.
|
inline |
Returns the loss value of full component with given id.
Definition at line 447 of file FullComponentStore.h.
|
inline |
Returns a list of non-loss edges (that are bridges between the Loss components) of full component with given id.
Definition at line 450 of file FullComponentStore.h.
|
inline |
Returns the terminal (in the original graph) that belongs to a given node v (in the store) according to the Loss of the component.
A terminal and a Steiner node are linked if the terminal is the first one on the shortest loss path starting from the Steiner node.
Definition at line 458 of file FullComponentStore.h.
|
protected |
Indicates which Steiner node is connected to which terminal through the loss edges, indexed by the Steiner node.
Definition at line 385 of file FullComponentStore.h.
