Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

FullComponentStore.h
Go to the documentation of this file.
1 
32 #pragma once
33 
34 #include <ogdf/basic/NodeArray.h>
36 
37 namespace ogdf {
38 namespace steiner_tree {
39 
40 #define OGDF_FULLCOMPONENTSTORE_REMOVE_IN_GRAPH_REPRESENTATION_ALSO // unnecessary but may save memory
41 
43 template<typename T, typename ExtraDataType = void>
45 {
46 protected:
54 
55  template<class Y, class Enable = void> // Metadata without extra data
56  struct Metadata {
59  T cost;
61  : start(nullptr)
62  , terminals(0)
63  , cost(0)
64  {
65  }
66  };
67  template<class Y> // Metadata with extra data
68  struct Metadata<Y, typename std::enable_if<!std::is_void<Y>::value>::type> {
71  T cost;
72  Y extra;
74  : start(nullptr)
75  , terminals(0)
76  , cost(0)
77  {
78  }
79  };
81 
83  void traverseOverDegree2Nonterminals(node& uO, T& weight, EdgeArray<bool>& marked, adjEntry adj, const EdgeWeightedGraphCopy<T>& comp) const {
84  while (m_nodeCopy[uO] == nullptr && !m_isTerminal[uO]) {
85  OGDF_ASSERT(comp.copy(uO)->degree() == 2);
86  adj = adj->twin()->cyclicSucc();
87  OGDF_ASSERT(comp.original(adj->theNode()) == uO);
88  edge e2 = adj->theEdge();
89  marked[e2] = true;
90  weight += comp.weight(e2);
91  uO = comp.original(adj->twinNode());
92  }
93  }
94 
96  void copyEdgesWithSimplifiedPaths(Metadata<ExtraDataType>& data, const EdgeWeightedGraphCopy<T>& comp, const ArrayBuffer<node>& nonterminals) {
97  EdgeArray<bool> marked(comp, false);
98  for (node v : nonterminals) {
99  for (adjEntry adj : comp.copy(m_nodeOrig[v])->adjEntries) {
100  edge e = adj->theEdge();
101  if (!marked[e]) {
102  marked[e] = true;
103  node vO = comp.original(adj->theNode());
104  OGDF_ASSERT(m_nodeCopy[vO] != nullptr);
105  node uO = comp.original(adj->twinNode());
106  T weight(comp.weight(e));
107 
108  traverseOverDegree2Nonterminals(uO, weight, marked, adj, comp);
109 
110  edge eC = m_graph.newEdge(m_nodeCopy[uO], m_nodeCopy[vO], weight);
111  data.cost += weight;
112  if (m_isTerminal[uO]) {
113  data.start = eC->adjSource();
114  }
115  }
116  }
117  }
118 #ifdef OGDF_DEBUG
119  for (edge e : comp.edges) {
120  OGDF_ASSERT(marked[e] == true);
121  }
122 #endif
123  }
124 
126  void copyEdges(Metadata<ExtraDataType>& data, const EdgeWeightedGraphCopy<T>& comp) {
127  for (edge e : comp.edges) {
128  node uO = comp.original(e->source());
129  node vO = comp.original(e->target());
130  T weight = comp.weight(e);
131  edge eC = m_graph.newEdge(m_nodeCopy[uO], m_nodeCopy[vO], weight);
132  data.cost += weight;
133  if (m_isTerminal[uO]) {
134  data.start = eC->adjSource();
135  } else
136  if (m_isTerminal[vO]) {
137  data.start = eC->adjTarget();
138  }
139  }
140  }
141 
142 public:
144  : m_originalGraph(G)
147  , m_nodeCopy(G, nullptr)
149  {
150  for (node v : m_terminals) {
151  node u = m_graph.newNode();
152  m_nodeCopy[v] = u;
153  m_nodeOrig[u] = v;
154  }
155  }
156 
159  {
160  OGDF_ASSERT(!comp.empty());
161  OGDF_ASSERT(isTree(comp));
162 
163  // we temporarily use m_nodeCopy for nonterminals (with degree > 2) also
164  ArrayBuffer<node> nonterminals(comp.numberOfNodes() / 2);
165 
166  // add all nonterminals with degree > 2 of comp to m_graph
167  // and find terminals
168  Metadata<ExtraDataType> data;
169  bool existNoncritical = false;
170  for (node v : comp.nodes) {
171  node vO = comp.original(v);
172  if (m_nodeCopy[vO] == nullptr) {
173  OGDF_ASSERT(v->degree() >= 2);
174  if (v->degree() > 2) {
175  node vC = m_graph.newNode();
176  m_nodeCopy[vO] = vC;
177  m_nodeOrig[vC] = vO;
178  nonterminals.push(vC);
179  } else {
180  existNoncritical = true;
181  }
182  } else {
183  data.terminals.grow(1, vO);
184  }
185  }
186  data.terminals.quicksort(GenericComparer<node, int>([](node v) { return v->index(); }));
187 
188  // add all edges of comp to m_graph
189  // and find start adjEntry
190  if (existNoncritical) {
191  if (nonterminals.empty()) {
192  OGDF_ASSERT(data.terminals.size() == 2);
193  OGDF_ASSERT(data.cost == 0);
194  for (edge e : comp.edges) {
195  data.cost += comp.weight(e);
196  }
197  edge eC = m_graph.newEdge(m_nodeCopy[data.terminals[0]], m_nodeCopy[data.terminals[1]], data.cost);
198  data.start = eC->adjSource();
199  } else {
200  copyEdgesWithSimplifiedPaths(data, comp, nonterminals);
201  }
202  } else {
203  copyEdges(data, comp);
204  }
205  OGDF_ASSERT(data.start != nullptr);
206 
207  // cleanup m_nodeCopy (only terminals should be set)
208  for (node vC : nonterminals) {
209  m_nodeCopy[m_nodeOrig[vC]] = nullptr;
210  }
211 
212  m_components.push(data);
213  }
214 
216  void remove(int id)
217  {
218 #ifdef OGDF_FULLCOMPONENTSTORE_REMOVE_IN_GRAPH_REPRESENTATION_ALSO
219  auto &comp = m_components[id];
220  if (comp.terminals.size() == 2) {
221  m_graph.delEdge(comp.start->theEdge());
222  } else {
223  ArrayBuffer<node> stack(2 * comp.terminals.size() - 3);
224  stack.push(comp.start->twinNode());
225  m_graph.delEdge(comp.start->theEdge());
226  while (!stack.empty()) {
227  const node v = stack.popRet();
228  if (!isTerminal(v)) {
229  for (adjEntry adj : v->adjEntries) {
230  stack.push(adj->twinNode());
231  }
232  m_graph.delNode(v);
233  }
234  }
235  }
236 #endif
237  if (m_components.size() == id + 1) {
238  m_components.pop();
239  } else {
240  m_components[id] = m_components.popRet();
241  }
242  }
243 
245  int size() const
246  {
247  return m_components.size();
248  }
249 
251  bool isEmpty() const
252  {
253  return m_components.empty();
254  }
255 
257  const Array<node> &terminals(int id) const
258  {
259  OGDF_ASSERT(id >= 0);
260  OGDF_ASSERT(id < m_components.size());
261  return m_components[id].terminals;
262  }
263 
265  bool isTerminal(int id, node t) const
266  {
267  OGDF_ASSERT(id >= 0);
268  OGDF_ASSERT(id < m_components.size());
269  return m_components[id].terminals.linearSearch(t) != -1;
270  }
271 
272  bool isTerminal(node v) const
273  {
274  return m_isTerminal[m_nodeOrig[v]];
275  }
276 
278  T cost(int i) const
279  {
280  OGDF_ASSERT(i >= 0);
281  OGDF_ASSERT(i < m_components.size());
282  return m_components[i].cost;
283  }
284 
285  adjEntry start(int i) const
286  {
287  OGDF_ASSERT(i >= 0);
288  OGDF_ASSERT(i < m_components.size());
289  return m_components[i].start;
290  }
291 
293  {
294  return m_graph;
295  }
296 
297  node original(node v) const
298  {
299  OGDF_ASSERT(m_nodeOrig[v] != nullptr);
300  return m_nodeOrig[v];
301  }
302 
303  template<typename Fun>
304  void foreachAdjEntry(int i, Fun f) const
305  {
306  adjEntry start = m_components[i].start;
307  int size = m_components[i].terminals.size();
308  if (size == 2) {
309  f(start->twin());
310  return;
311  }
312  // size >= 3: do DFS over nonterminals (terminals are only leaves)
313  ArrayBuffer<adjEntry> stack(2*size - 2);
314  stack.push(start);
315  while (!stack.empty()) {
316  const adjEntry back = stack.popRet()->twin();
317  f(back);
318  if (!this->isTerminal(back->theNode())) {
319  for (adjEntry adj = back->cyclicSucc(); adj != back; adj = adj->cyclicSucc()) {
320  stack.push(adj);
321  }
322  }
323  }
324  }
325 
326  // \brief Do f(v) for each (original) node v of degree at least 3 in component with given id
327  template<typename Fun>
328  void foreachNode(int id, Fun f) const
329  {
330  f(original(start(id)->theNode()));
331  foreachAdjEntry(id, [&](adjEntry back) {
332  f(original(back->theNode()));
333  });
334  }
335 
336  // \brief Do f(e) for each (original) edge e in component with given id
337  template<typename Fun>
338  void foreachEdge(int id, const NodeArray<NodeArray<edge>> &pred, Fun f) const
339  {
340  foreachAdjEntry(id, [&](adjEntry back) {
341  const node u = original(back->twinNode());
342  for (node v = original(back->theNode()); pred[u][v]; v = pred[u][v]->opposite(v)) {
343  f(pred[u][v]);
344  }
345  });
346  }
347 
348  // \brief Do f(v) for each node v (also of degree 2) in component with given id
349  template<typename Fun>
350  void foreachNode(int id, const NodeArray<NodeArray<edge>> &pred, Fun f) const
351  {
352  if (m_components[id].terminals.size() == 3) {
353  // use a variant that works when only pred[t] has been filled for all terminals t
354  adjEntry start = m_components[id].start;
355  const node c = start->twinNode();
356  f(original(c));
357  for (adjEntry adj : c->adjEntries) {
358  const node u = original(adj->twinNode());
359  node v = original(c);
360  while (v != u) {
361  v = pred[u][v]->opposite(v);
362  f(v);
363  }
364  }
365  return;
366  }
367  f(original(start(id)->theNode()));
368  foreachAdjEntry(id, [&](adjEntry back) {
369  const node u = original(back->twinNode());
370  for (node v = original(back->theNode()); pred[u][v]; v = pred[u][v]->opposite(v)) {
371  f(v);
372  }
373  });
374  }
375 };
376 
380 template<typename T, typename ExtraDataType>
381 class FullComponentWithExtraStore : public FullComponentStore<T, ExtraDataType>
382 {
383 public:
385 
387  ExtraDataType &extra(int i)
388  {
389  OGDF_ASSERT(i >= 0);
390  OGDF_ASSERT(i < this->m_components.size());
391  return this->m_components[i].extra;
392  }
393 
395  const ExtraDataType &extra(int i) const
396  {
397  OGDF_ASSERT(i >= 0);
398  OGDF_ASSERT(i < this->m_components.size());
399  return this->m_components[i].extra;
400  }
401 };
402 
403 template<typename T>
404 struct LossMetadata {
405  T loss;
408  : loss(0)
409  , bridges()
410  {
411  }
412 };
413 
417 template<typename T>
418 class FullComponentWithLossStore : public FullComponentWithExtraStore<T, LossMetadata<T>>
419 {
420 protected:
422 
430  {
431  if (!m_lossTerminal[u]
432  && pred[u]) {
433  m_lossTerminal[u] = findLossTerminal(pred[u]->opposite(u), pred);
434  }
435 
436  return m_lossTerminal[u];
437  }
438 
439 public:
441 
444  {
445  m_lossTerminal.init(this->m_graph, nullptr);
446 
447  // add zero-cost edges between all terminals (to be removed later),
448  // and set m_lossTerminal mapping for terminals
449  List<edge> zeroEdges;
450  const node s = this->m_terminals.front();
451  const node sC = this->m_nodeCopy[s];
452  m_lossTerminal[sC] = s;
453  for (ListConstIterator<node> it = this->m_terminals.begin().succ(); it.valid(); ++it) {
454  const node v = *it;
455  const node vC = this->m_nodeCopy[v];
456  m_lossTerminal[vC] = v;
457  zeroEdges.pushBack(this->m_graph.newEdge(sC, vC, 0));
458  }
459 
460  // compute minimum spanning tree
461  NodeArray<edge> pred(this->m_graph);
462  EdgeArray<bool> isLossEdge(this->m_graph, false);
463  computeMinST(sC, this->m_graph, this->m_graph.edgeWeights(), pred, isLossEdge);
464 
465  // remove zero-cost edges again
466  for (edge e : zeroEdges) {
467  this->m_graph.delEdge(e);
468  }
469 
470  // find loss bridges and compute loss value
471  for (int id = 0; id < this->size(); ++id) {
472  this->foreachAdjEntry(id, [&](adjEntry adj) {
473  edge e = adj->theEdge();
474  if (!isLossEdge[e]) {
475  this->extra(id).bridges.pushBack(e);
476  findLossTerminal(e->source(), pred);
477  findLossTerminal(e->target(), pred);
478  } else {
479  this->extra(id).loss += this->m_graph.weight(e);
480  }
481  });
482  }
483  }
484 
486  T loss(int id) const
487  {
488  return this->extra(id).loss;
489  }
490 
492  const List<edge> &lossBridges(int id) const
493  {
494  return this->extra(id).bridges;
495  }
496 
504  {
505  OGDF_ASSERT(m_lossTerminal.valid());
506  return m_lossTerminal[v];
507  }
508 };
509 
510 }
511 }
ogdf::ArrayBuffer
An array that keeps track of the number of inserted elements; also usable as an efficient stack.
Definition: Array.h:45
ogdf
The namespace for all OGDF objects.
Definition: AugmentationModule.h:36
ogdf::steiner_tree::FullComponentWithLossStore::m_lossTerminal
NodeArray< node > m_lossTerminal
Indicates which Steiner node is connected to which terminal through the loss edges,...
Definition: FullComponentStore.h:421
ogdf::Graph::empty
bool empty() const
Returns true iff the graph is empty, i.e., contains no nodes.
Definition: Graph_d.h:598
ogdf::steiner_tree::FullComponentStore::Metadata< Y, typename std::enable_if<!std::is_void< Y >::value >::type >::extra
Y extra
Definition: FullComponentStore.h:72
OGDF_ASSERT
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition: basic.h:41
ogdf::GraphCopy::original
const Graph & original() const
Returns a reference to the original graph.
Definition: GraphCopy.h:292
ogdf::ArrayBuffer::empty
bool empty() const
Returns true if the buffer is empty, false otherwise.
Definition: ArrayBuffer.h:116
ogdf::steiner_tree::FullComponentStore::original
node original(node v) const
Definition: FullComponentStore.h:297
ogdf::AdjElement::theNode
node theNode() const
Returns the node whose adjacency list contains this element.
Definition: Graph_d.h:100
ogdf::steiner_tree::FullComponentStore::terminals
const Array< node > & terminals(int id) const
Returns the list of terminals in the full component with given id.
Definition: FullComponentStore.h:257
ogdf::NodeElement::index
int index() const
Returns the (unique) node index.
Definition: Graph_d.h:203
ogdf::computeMinST
T computeMinST(const Graph &G, const EdgeArray< T > &weight, EdgeArray< bool > &isInTree)
Computes a minimum spanning tree using Prim's algorithm.
Definition: extended_graph_alg.h:273
ogdf::steiner_tree::FullComponentStore::Metadata< Y, typename std::enable_if<!std::is_void< Y >::value >::type >::start
adjEntry start
Adjacency entry on a terminal where a non-terminal BFS yields the component.
Definition: FullComponentStore.h:69
ogdf::steiner_tree::FullComponentStore::insert
void insert(const EdgeWeightedGraphCopy< T > &comp)
Inserts a component. Note that comp is copied and degree-2 nodes are removed.
Definition: FullComponentStore.h:158
ogdf::steiner_tree::FullComponentStore::size
int size() const
Returns the number of full components in the store.
Definition: FullComponentStore.h:245
ogdf::steiner_tree::FullComponentStore::m_terminals
const List< node > & m_terminals
The terminal list of the original Steiner instance.
Definition: FullComponentStore.h:48
ogdf::steiner_tree::FullComponentWithLossStore::lossTerminal
node lossTerminal(node v) const
Returns the terminal (in the original graph) that belongs to a given node v (in the store) according ...
Definition: FullComponentStore.h:503
ogdf::steiner_tree::FullComponentStore::Metadata< Y, typename std::enable_if<!std::is_void< Y >::value >::type >::terminals
Array< node > terminals
Terminals, sorted by node index.
Definition: FullComponentStore.h:70
ogdf::steiner_tree::FullComponentWithLossStore::loss
T loss(int id) const
Returns the loss value of full component with given id.
Definition: FullComponentStore.h:486
ogdf::ArrayBuffer::popRet
E popRet()
Removes the newest element from the buffer and returns it.
Definition: ArrayBuffer.h:113
ogdf::steiner_tree::FullComponentStore::isTerminal
bool isTerminal(node v) const
Definition: FullComponentStore.h:272
ogdf::NodeArray< bool >
ogdf::steiner_tree::FullComponentStore::Metadata< Y, typename std::enable_if<!std::is_void< Y >::value >::type >::cost
T cost
Cost.
Definition: FullComponentStore.h:71
ogdf::AdjElement::twin
adjEntry twin() const
Returns the corresponding adjacency element associated with the same edge.
Definition: Graph_d.h:105
ogdf::steiner_tree::FullComponentStore::m_originalGraph
const EdgeWeightedGraph< T > & m_originalGraph
The original Steiner instance.
Definition: FullComponentStore.h:47
ogdf::steiner_tree::FullComponentStore::Metadata< Y, typename std::enable_if<!std::is_void< Y >::value >::type >::Metadata
Metadata()
Definition: FullComponentStore.h:73
ogdf::EdgeArray< bool >
ogdf::GraphCopy::copy
node copy(node v) const
Returns the node in the graph copy corresponding to v.
Definition: GraphCopy.h:341
ogdf::steiner_tree::FullComponentStore::foreachNode
void foreachNode(int id, Fun f) const
Definition: FullComponentStore.h:328
ogdf::steiner_tree::LossMetadata::bridges
List< edge > bridges
List of non-loss edges.
Definition: FullComponentStore.h:406
ogdf::AdjElement
Class for adjacency list elements.
Definition: Graph_d.h:79
ogdf::steiner_tree::LossMetadata::loss
T loss
The loss of a component.
Definition: FullComponentStore.h:405
ogdf::steiner_tree::FullComponentStore::m_graph
EdgeWeightedGraph< T > m_graph
Our graph representation for the full component store.
Definition: FullComponentStore.h:50
EdgeWeightedGraphCopy.h
Extends the GraphCopy concept to weighted graphs.
ogdf::steiner_tree::FullComponentStore::FullComponentStore
FullComponentStore(const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal)
Definition: FullComponentStore.h:143
ogdf::steiner_tree::LossMetadata::LossMetadata
LossMetadata()
Definition: FullComponentStore.h:407
ogdf::AdjElement::theEdge
edge theEdge() const
Returns the edge associated with this adjacency entry.
Definition: Graph_d.h:96
ogdf::Graph::nodes
internal::GraphObjectContainer< NodeElement > nodes
The container containing all node objects.
Definition: Graph_d.h:568
ogdf::NodeElement::degree
int degree() const
Returns the degree of the node (indegree + outdegree).
Definition: Graph_d.h:210
ogdf::Graph::numberOfNodes
int numberOfNodes() const
Returns the number of nodes in the graph.
Definition: Graph_d.h:601
backward::Color::type
type
Definition: backward.hpp:1716
ogdf::steiner_tree::FullComponentStore::m_nodeCopy
NodeArray< node > m_nodeCopy
Mapping of original terminals to m_graph nodes.
Definition: FullComponentStore.h:52
ogdf::EdgeWeightedGraph
Definition: EdgeWeightedGraph.h:39
ogdf::Array< node >
ogdf::NodeElement::adjEntries
internal::GraphObjectContainer< AdjElement > adjEntries
The container containing all entries in the adjacency list of this node.
Definition: Graph_d.h:200
ogdf::ArrayBuffer::push
void push(E e)
Puts a new element in the buffer.
Definition: ArrayBuffer.h:102
ogdf::steiner_tree::FullComponentStore::cost
T cost(int i) const
Returns the sum of edge costs of this full component.
Definition: FullComponentStore.h:278
ogdf::steiner_tree::FullComponentWithLossStore::lossBridges
const List< edge > & lossBridges(int id) const
Returns a list of non-loss edges (that are bridges between the Loss components) of full component wit...
Definition: FullComponentStore.h:492
ogdf::EdgeElement::source
node source() const
Returns the source node of the edge.
Definition: Graph_d.h:326
ogdf::steiner_tree::FullComponentStore::Metadata::cost
T cost
Cost.
Definition: FullComponentStore.h:59
ogdf::List
Doubly linked lists (maintaining the length of the list).
Definition: List.h:40
ogdf::EdgeElement::adjSource
adjEntry adjSource() const
Returns the corresponding adjacancy entry at source node.
Definition: Graph_d.h:333
ogdf::steiner_tree::FullComponentStore::Metadata::start
adjEntry start
Adjacency entry on a terminal where a non-terminal BFS yields the component.
Definition: FullComponentStore.h:57
ogdf::steiner_tree::FullComponentStore::copyEdges
void copyEdges(Metadata< ExtraDataType > &data, const EdgeWeightedGraphCopy< T > &comp)
Copy edges from comp into our representation.
Definition: FullComponentStore.h:126
ogdf::steiner_tree::FullComponentStore::m_components
ArrayBuffer< Metadata< ExtraDataType > > m_components
List of full components (based on metadata)
Definition: FullComponentStore.h:80
ogdf::steiner_tree::FullComponentStore::traverseOverDegree2Nonterminals
void traverseOverDegree2Nonterminals(node &uO, T &weight, EdgeArray< bool > &marked, adjEntry adj, const EdgeWeightedGraphCopy< T > &comp) const
Traverse over degree-2 nonterminals.
Definition: FullComponentStore.h:83
ogdf::steiner_tree::LossMetadata
Definition: FullComponentStore.h:404
ogdf::steiner_tree::FullComponentStore::start
adjEntry start(int i) const
Definition: FullComponentStore.h:285
ogdf::steiner_tree::FullComponentWithExtraStore::extra
ExtraDataType & extra(int i)
Returns a reference to the extra data of this full component.
Definition: FullComponentStore.h:387
ogdf::steiner_tree::FullComponentWithLossStore::findLossTerminal
node findLossTerminal(const node u, const NodeArray< edge > &pred)
Starting from a Steiner node find the nearest terminal along a shortest path.
Definition: FullComponentStore.h:429
ogdf::steiner_tree::FullComponentStore::isTerminal
bool isTerminal(int id, node t) const
checks if a given node t is a terminal in the full component with given id
Definition: FullComponentStore.h:265
ogdf::steiner_tree::FullComponentStore::graph
const EdgeWeightedGraph< T > & graph() const
Definition: FullComponentStore.h:292
ogdf::AdjElement::twinNode
node twinNode() const
Returns the associated node of the corresponding adjacency entry (shorthand for twin()->theNode()).
Definition: Graph_d.h:108
NodeArray.h
Declaration and implementation of NodeArray class.
ogdf::steiner_tree::FullComponentStore
A data structure to store full components.
Definition: FullComponentStore.h:44
ogdf::AdjElement::cyclicSucc
adjEntry cyclicSucc() const
Returns the cyclic successor in the adjacency list.
Definition: Graph_d.h:279
ogdf::steiner_tree::FullComponentStore::Metadata::terminals
Array< node > terminals
Terminals, sorted by node index.
Definition: FullComponentStore.h:58
ogdf::steiner_tree::FullComponentStore::foreachNode
void foreachNode(int id, const NodeArray< NodeArray< edge >> &pred, Fun f) const
Definition: FullComponentStore.h:350
ogdf::steiner_tree::FullComponentStore::copyEdgesWithSimplifiedPaths
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.
Definition: FullComponentStore.h:96
ogdf::EdgeElement::adjTarget
adjEntry adjTarget() const
Returns the corresponding adjacancy entry at target node.
Definition: Graph_d.h:335
ogdf::steiner_tree::FullComponentWithExtraStore::extra
const ExtraDataType & extra(int i) const
Returns a const reference to the extra data of this full component.
Definition: FullComponentStore.h:395
ogdf::steiner_tree::FullComponentStore::isEmpty
bool isEmpty() const
Checks if the store does not contain any full components.
Definition: FullComponentStore.h:251
ogdf::Graph::edges
internal::GraphObjectContainer< EdgeElement > edges
The container containing all edge objects.
Definition: Graph_d.h:571
ogdf::steiner_tree::FullComponentWithLossStore
A data structure to store full components with additional "loss" functionality.
Definition: FullComponentStore.h:418
std
Definition: GML.h:110
ogdf::steiner_tree::FullComponentStore::Metadata::Metadata
Metadata()
Definition: FullComponentStore.h:60
ogdf::steiner_tree::FullComponentStore::m_isTerminal
const NodeArray< bool > & m_isTerminal
Incidence vector for terminal nodes.
Definition: FullComponentStore.h:49
ogdf::EdgeWeightedGraphCopy::weight
T weight(const edge e) const
Definition: EdgeWeightedGraphCopy.h:51
ogdf::EdgeWeightedGraphCopy
Definition: EdgeWeightedGraphCopy.h:40
ogdf::EdgeElement
Class for the representation of edges.
Definition: Graph_d.h:292
ogdf::steiner_tree::FullComponentStore::foreachAdjEntry
void foreachAdjEntry(int i, Fun f) const
Definition: FullComponentStore.h:304
ogdf::Array::size
INDEX size() const
Returns the size (number of elements) of the array.
Definition: Array.h:286
ogdf::steiner_tree::FullComponentStore::m_nodeOrig
NodeArray< node > m_nodeOrig
Mapping of m_graph nodes to original nodes.
Definition: FullComponentStore.h:53
ogdf::ListIteratorBase
Encapsulates a pointer to a list element.
Definition: List.h:42
ogdf::steiner_tree::FullComponentStore::remove
void remove(int id)
Removes a component by its id.
Definition: FullComponentStore.h:216
ogdf::EdgeElement::target
node target() const
Returns the target node of the edge.
Definition: Graph_d.h:328
ogdf::steiner_tree::FullComponentWithLossStore::computeAllLosses
void computeAllLosses()
Compute the loss, both edge set and value, of all full components.
Definition: FullComponentStore.h:443
ogdf::steiner_tree::FullComponentStore::Metadata
Definition: FullComponentStore.h:56
ogdf::NodeElement
Class for the representation of nodes.
Definition: Graph_d.h:169
ogdf::steiner_tree::FullComponentWithExtraStore
A data structure to store full components with extra data for each component.
Definition: FullComponentStore.h:381
ogdf::steiner_tree::FullComponentStore::foreachEdge
void foreachEdge(int id, const NodeArray< NodeArray< edge >> &pred, Fun f) const
Definition: FullComponentStore.h:338
ogdf::GenericComparer
Compare elements based on a single comparable attribute.
Definition: comparer.h:377
ogdf::isTree
bool isTree(const Graph &G)
Returns true iff G is a tree, i.e. contains no undirected cycle and is connected.
Definition: simple_graph_alg.h:956
ogdf::List::pushBack
iterator pushBack(const E &x)
Adds element x at the end of the list.
Definition: List.h:1374