[ VIGRA Homepage | Function Index | Class Index | Namespaces | File List | Main Page ]

binary_forest.hxx VIGRA

1 /************************************************************************/
2 /* */
3 /* Copyright 2014-2015 by Ullrich Koethe and Philip Schill */
4 /* */
5 /* This file is part of the VIGRA computer vision library. */
6 /* The VIGRA Website is */
7 /* http://hci.iwr.uni-heidelberg.de/vigra/ */
8 /* Please direct questions, bug reports, and contributions to */
9 /* ullrich.koethe@iwr.uni-heidelberg.de or */
10 /* vigra@informatik.uni-hamburg.de */
11 /* */
12 /* Permission is hereby granted, free of charge, to any person */
13 /* obtaining a copy of this software and associated documentation */
14 /* files (the "Software"), to deal in the Software without */
15 /* restriction, including without limitation the rights to use, */
16 /* copy, modify, merge, publish, distribute, sublicense, and/or */
17 /* sell copies of the Software, and to permit persons to whom the */
18 /* Software is furnished to do so, subject to the following */
19 /* conditions: */
20 /* */
21 /* The above copyright notice and this permission notice shall be */
22 /* included in all copies or substantial portions of the */
23 /* Software. */
24 /* */
25 /* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND */
26 /* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES */
27 /* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND */
28 /* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT */
29 /* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, */
30 /* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING */
31 /* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR */
32 /* OTHER DEALINGS IN THE SOFTWARE. */
33 /* */
34 /************************************************************************/
35 #ifndef VIGRA_BINARY_FOREST_HXX
36 #define VIGRA_BINARY_FOREST_HXX
37 
38 #include <vector>
39 #include "graphs.hxx"
40 
41 namespace vigra
42 {
43 
44 /** \addtogroup GraphDataStructures
45 */
46 //@{
47 
48 /********************************************************/
49 /* */
50 /* BinaryForest */
51 /* */
52 /********************************************************/
53 
54 /**
55  * @brief BinaryForest stores a collection of rooted binary trees.
56  *
57  * Each connected component of the BinaryForest is thus a tree, and all edges are
58  * directed away from the root node of the corresponding tree.
59  *
60  * @note If there is an arc from node <tt>u</tt> to node <tt>v</tt>, then the
61  * arc ID is <tt>2*id(u)</tt> when <tt>v</tt> is the left child and <tt>2*id(u)+1</tt>
62  * when <tt>v</tt> is the right child.
63  */
65 {
66 public:
67 
68  typedef Int64 index_type;
69  /// Node descriptor type of the present graph.
70  typedef detail::NodeDescriptor<index_type> Node;
71  /// Arc descriptor type of the present graph.
72  typedef detail::ArcDescriptor<index_type> Arc;
73 
74  /// @brief Create an empty forest.
75  BinaryForest();
76 
77  /// @brief Add a new node (its node ID will be selected automatically).
78  Node addNode();
79  /// @brief Add a new arc from node \a u to node \a v.
80  /// The arc ID is <tt>2*id(u)</tt> if \a v is the left child of \a u, <tt>2*id(u)+1</tt> otherwise.
81  Arc addArc(Node const & u, Node const & v);
82  /// @brief Check if \a node exists.
83  bool valid(Node const & node) const;
84  /// @brief Check if \a arc exists.
85  bool valid(Arc const & arc) const;
86  /// @brief Find start node of \a arc.
87  Node source(Arc const & arc) const;
88  /// @brief Find end node of \a arc.
89  Node target(Arc const & arc) const;
90  /// @brief Get ID for node descriptor \a node.
91  index_type id(Node const & node) const;
92  /// @brief Get ID for arc descriptor \a arc.
93  index_type id(Arc const & arc) const;
94  /// @brief Get node descriptor for \a id.
95  Node nodeFromId(index_type const & id) const;
96  /// @brief Get arc descriptor for \a id.
97  Arc arcFromId(index_type const & id) const;
98  /// @brief Return the highest existing node ID.
99  index_type maxNodeId() const;
100  /// @brief Return the highest possible arc ID (equivalent to <tt>2*maxNodeId() + 1</tt>).
101  index_type maxArcId() const;
102  /// @brief Return the number of nodes (equivalent to <tt>maxNodeId()+1</tt>).
103  size_t numNodes() const;
104  /// @brief Return the number of arcs.
105  /// Always less than <tt>maxArcId()</tt> because not all arcs actually exist.
106  size_t numArcs() const;
107  /// @brief Return the number of incoming edges of \a node.
108  /// <tt>0</tt> for a root node, <tt>1</tt> otherwise.
109  size_t inDegree(Node const & node) const;
110  /// @brief Return the number of outgoing edges of \a node.
111  /// <tt>0</tt> for a leaf node, <tt>1</tt> or <tt>2</tt> otherwise.
112  size_t outDegree(Node const & node) const;
113  /// @brief Return the number of parents of \a node (equivalent to <tt>inDegree()</tt>).
114  size_t numParents(Node const & node) const;
115  /// @brief Return the number of children of \a node (equivalent to <tt>outDegree()</tt>).
116  size_t numChildren(Node const & node) const;
117  /// @brief Return the number of trees in the forest.
118  size_t numRoots() const;
119  /// @brief Create node cescriptor for ID \a i, or <tt>lemon::INVALID</tt> if
120  /// \a i is not a valid ID.
121  Node getNode(size_t i) const;
122  /// @brief Get the parent node descriptor of \a node, or <tt>lemon::INVALID</tt>
123  /// if \a node is a root or \a i is non-zero.
124  Node getParent(Node const & node, size_t i = 0) const;
125  /// @brief Get child number \a i of \a node.
126  /// Returns the left child if <tt>i=0</tt>, the right child if <tt>i=1</tt>,
127  /// and <tt>lemon::INVALID</tt> for other values of \a i or when the respective
128  /// is undefined.
129  Node getChild(Node const & node, size_t i = 0) const;
130  /// @brief Get the root node descriptor of tree \a i in the forest, or
131  /// <tt>lemon::INVALID</tt> if \a i is invalid.
132  Node getRoot(size_t i = 0) const;
133  /// @brief Merge two forests and increase the IDs of \a other to avoid ID clashes.
134  /// The function returns the offset that has been added to these IDs.
135  size_t merge(BinaryForest const & other);
136 
137 private:
138 
139  struct NodeT
140  {
141  NodeT()
142  :
143  parent(-1),
144  left_child(-1),
145  right_child(-1)
146  {}
147  index_type parent, left_child, right_child;
148  };
149 
150  std::vector<NodeT> nodes_;
151 
152  // Sorted vector with the node ids of the roots.
153  std::vector<index_type> root_nodes_;
154 
155  size_t num_arcs_;
156 };
157 
158 
159 
161  :
162  nodes_(),
163  root_nodes_(),
164  num_arcs_(0)
165 {}
166 
168 {
169  Node n = Node(nodes_.size());
170  nodes_.push_back(NodeT());
171  root_nodes_.push_back(n.id());
172  return n;
173 }
174 
176  Node const & u,
177  Node const & v
178 ){
179  NodeT & u_node = nodes_[u.id()];
180  NodeT & v_node = nodes_[v.id()];
181  index_type arc_id = 2*u.id();
182 
183  // Make sure that the arc is not inserted twice.
184  if (u_node.left_child == v.id())
185  return Arc(arc_id);
186  if (u_node.right_child == v.id())
187  return Arc(arc_id+1);
188 
189  // Add v as child of u.
190  if (u_node.left_child == -1)
191  {
192  u_node.left_child = v.id();
193  }
194  else if (u_node.right_child == -1)
195  {
196  u_node.right_child = v.id();
197  ++arc_id;
198  }
199  else
200  {
201  vigra_fail("BinaryForest::addArc(): The node u already has two children.");
202  }
203 
204  // Add u as parent of v.
205  v_node.parent = u.id();
206 
207  // If v was a root node, remove it from the list.
208  auto it = std::lower_bound(root_nodes_.begin(), root_nodes_.end(), v.id());
209  if (it != root_nodes_.end() && !(v.id() < *it))
210  root_nodes_.erase(it);
211 
212  ++num_arcs_;
213  return Arc(arc_id);
214 }
215 
217  Node const & node
218 ) const {
219  // NOTE: The conversion to size_t is valid since we first check for >= 0.
220  return node.id() >= 0 && (size_t)node.id() < nodes_.size();
221 }
222 
224  Arc const & arc
225 ) const {
226  if (arc == lemon::INVALID)
227  return false;
228 
229  index_type const uid = arc.id()/2;
230  if (!valid(Node(uid)))
231  return false;
232 
233  if (arc.id() % 2 == 0)
234  return nodes_[uid].left_child != -1;
235  else
236  return nodes_[uid].right_child != -1;
237 }
238 
240  Arc const & arc
241 ) const {
242  return Node(arc.id()/2);
243 }
244 
246  Arc const & arc
247 ) const {
248  NodeT const & u_node = nodes_[arc.id()/2];
249  if (arc.id() % 2 == 0)
250  return Node(u_node.left_child);
251  else
252  return Node(u_node.right_child);
253 }
254 
255 inline BinaryForest::index_type BinaryForest::id(
256  Node const & node
257 ) const {
258  return node.id();
259 }
260 
261 inline BinaryForest::index_type BinaryForest::id(
262  Arc const & arc
263 ) const {
264  return arc.id();
265 }
266 
268  index_type const & id
269 ) const {
270  return Node(id);
271 }
272 
274  index_type const & id
275 ) const {
276  return Arc(id);
277 }
278 
279 inline BinaryForest::index_type BinaryForest::maxNodeId() const
280 {
281  return nodes_.size()-1;
282 }
283 
284 inline BinaryForest::index_type BinaryForest::maxArcId() const
285 {
286  return 2*maxNodeId() + 1;
287 }
288 
289 inline size_t BinaryForest::numNodes() const
290 {
291  return nodes_.size();
292 }
293 
294 inline size_t BinaryForest::numArcs() const
295 {
296  return num_arcs_;
297 }
298 
300  Node const & node
301 ) const {
302  if (nodes_[node.id()].parent == -1)
303  return 0;
304  else
305  return 1;
306 }
307 
309  Node const & node
310 ) const {
311  NodeT const & n = nodes_[node.id()];
312  if (n.left_child == -1 && n.right_child == -1)
313  return 0;
314  else if (n.left_child == -1 || n.right_child == -1)
315  return 1;
316  else
317  return 2;
318 }
319 
321  Node const & node
322 ) const {
323  return inDegree(node);
324 }
325 
327  Node const & node
328 ) const {
329  return outDegree(node);
330 }
331 
332 inline size_t BinaryForest::numRoots() const
333 {
334  return root_nodes_.size();
335 }
336 
338  size_t i
339 ) const {
340  if (i >= numNodes())
341  return Node(lemon::INVALID);
342  else
343  return Node(i);
344 }
345 
347  Node const & node,
348  size_t i
349 ) const {
350  NodeT const & n = nodes_[node.id()];
351  if (n.parent == -1 || i != 0)
352  return Node(lemon::INVALID);
353  else
354  return Node(n.parent);
355 }
356 
358  Node const & node,
359  size_t i
360 ) const {
361  NodeT const & n = nodes_[node.id()];
362  if (i == 0)
363  return Node(n.left_child);
364  else if (i == 1)
365  return Node(n.right_child);
366  else
367  return Node(lemon::INVALID);
368 }
369 
371  size_t i
372 ) const {
373  if (i >= root_nodes_.size())
374  return Node(lemon::INVALID);
375  else
376  return Node(root_nodes_[i]);
377 }
378 
379 inline size_t BinaryForest::merge(
380  BinaryForest const & other
381 ){
382  num_arcs_ += other.num_arcs_;
383  size_t const offset = nodes_.size();
384  nodes_.insert(nodes_.end(), other.nodes_.begin(), other.nodes_.end());
385  for (size_t i = offset; i < nodes_.size(); ++i)
386  {
387  NodeT & n = nodes_[i];
388  if (n.parent != -1)
389  n.parent += offset;
390  if (n.left_child != -1)
391  n.left_child += offset;
392  if (n.right_child != -1)
393  n.right_child += offset;
394  }
395 
396  size_t const root_offset = root_nodes_.size();
397  root_nodes_.insert(root_nodes_.end(), other.root_nodes_.begin(), other.root_nodes_.end());
398  for (size_t i = root_offset; i < root_nodes_.size(); ++i)
399  {
400  root_nodes_[i] += offset;
401  }
402  return offset;
403 }
404 
405 //@}
406 
407 } // namespace vigra
408 
409 #endif
index_type id(Node const &node) const
Get ID for node descriptor node.
Definition: binary_forest.hxx:255
size_t numChildren(Node const &node) const
Return the number of children of node (equivalent to outDegree()).
Definition: binary_forest.hxx:326
Node getNode(size_t i) const
Create node cescriptor for ID i, or lemon::INVALID if i is not a valid ID.
Definition: binary_forest.hxx:337
Node getRoot(size_t i=0) const
Get the root node descriptor of tree i in the forest, or lemon::INVALID if i is invalid.
Definition: binary_forest.hxx:370
Node getParent(Node const &node, size_t i=0) const
Get the parent node descriptor of node, or lemon::INVALID if node is a root or i is non-zero...
Definition: binary_forest.hxx:346
detail::NodeDescriptor< index_type > Node
Node descriptor type of the present graph.
Definition: binary_forest.hxx:70
Node addNode()
Add a new node (its node ID will be selected automatically).
Definition: binary_forest.hxx:167
size_t numNodes() const
Return the number of nodes (equivalent to maxNodeId()+1).
Definition: binary_forest.hxx:289
detail::ArcDescriptor< index_type > Arc
Arc descriptor type of the present graph.
Definition: binary_forest.hxx:72
Arc addArc(Node const &u, Node const &v)
Add a new arc from node u to node v. The arc ID is 2*id(u) if v is the left child of u...
Definition: binary_forest.hxx:175
Node nodeFromId(index_type const &id) const
Get node descriptor for id.
Definition: binary_forest.hxx:267
size_t inDegree(Node const &node) const
Return the number of incoming edges of node. 0 for a root node, 1 otherwise.
Definition: binary_forest.hxx:299
bool valid(Node const &node) const
Check if node exists.
Definition: binary_forest.hxx:216
detail::SelectIntegerType< 64, detail::SignedIntTypes >::type Int64
64-bit signed int
Definition: sized_int.hxx:177
Node source(Arc const &arc) const
Find start node of arc.
Definition: binary_forest.hxx:239
index_type maxNodeId() const
Return the highest existing node ID.
Definition: binary_forest.hxx:279
Arc arcFromId(index_type const &id) const
Get arc descriptor for id.
Definition: binary_forest.hxx:273
Node target(Arc const &arc) const
Find end node of arc.
Definition: binary_forest.hxx:245
size_t merge(BinaryForest const &other)
Merge two forests and increase the IDs of other to avoid ID clashes. The function returns the offset ...
Definition: binary_forest.hxx:379
index_type maxArcId() const
Return the highest possible arc ID (equivalent to 2*maxNodeId() + 1).
Definition: binary_forest.hxx:284
size_t outDegree(Node const &node) const
Return the number of outgoing edges of node. 0 for a leaf node, 1 or 2 otherwise. ...
Definition: binary_forest.hxx:308
BinaryForest stores a collection of rooted binary trees.
Definition: binary_forest.hxx:64
size_t numArcs() const
Return the number of arcs. Always less than maxArcId() because not all arcs actually exist...
Definition: binary_forest.hxx:294
size_t numRoots() const
Return the number of trees in the forest.
Definition: binary_forest.hxx:332
size_t numParents(Node const &node) const
Return the number of parents of node (equivalent to inDegree()).
Definition: binary_forest.hxx:320
BinaryForest()
Create an empty forest.
Definition: binary_forest.hxx:160
Node getChild(Node const &node, size_t i=0) const
Get child number i of node. Returns the left child if i=0, the right child if i=1, and lemon::INVALID for other values of i or when the respective is undefined.
Definition: binary_forest.hxx:357

© Ullrich Köthe (ullrich.koethe@iwr.uni-heidelberg.de)
Heidelberg Collaboratory for Image Processing, University of Heidelberg, Germany

html generated using doxygen and Python
vigra 1.11.1 (Fri May 19 2017)