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

binary_forest.hxx
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 */
64 class BinaryForest
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
160 inline BinaryForest::BinaryForest()
161 :
162 nodes_(),
163 root_nodes_(),
164 num_arcs_(0)
165{}
166
167 inline BinaryForest::Node BinaryForest::addNode()
168{
169 Node n = Node(nodes_.size());
170 nodes_.push_back(NodeT());
171 root_nodes_.push_back(n.id());
172 return n;
173}
174
175 inline BinaryForest::Arc BinaryForest::addArc(
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
216 inline bool BinaryForest::valid(
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
223 inline bool BinaryForest::valid(
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
239 inline BinaryForest::Node BinaryForest::source(
240 Arc const & arc
241) const {
242 return Node(arc.id()/2);
243}
244
245 inline BinaryForest::Node BinaryForest::target(
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
267 inline BinaryForest::Node BinaryForest::nodeFromId(
268 index_type const & id
269) const {
270 return Node(id);
271}
272
273 inline BinaryForest::Arc BinaryForest::arcFromId(
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
299 inline size_t BinaryForest::inDegree(
300 Node const & node
301) const {
302 if (nodes_[node.id()].parent == -1)
303 return 0;
304 else
305 return 1;
306}
307
308 inline size_t BinaryForest::outDegree(
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
320 inline size_t BinaryForest::numParents(
321 Node const & node
322) const {
323 return inDegree(node);
324}
325
326 inline size_t BinaryForest::numChildren(
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
337 inline BinaryForest::Node BinaryForest::getNode(
338 size_t i
339) const {
340 if (i >= numNodes())
341 return Node(lemon::INVALID);
342 else
343 return Node(i);
344}
345
346 inline BinaryForest::Node BinaryForest::getParent(
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
357 inline BinaryForest::Node BinaryForest::getChild(
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
370 inline BinaryForest::Node BinaryForest::getRoot(
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
vigra::BinaryForest
BinaryForest stores a collection of rooted binary trees.
Definition binary_forest.hxx:65
vigra::BinaryForest::maxNodeId
index_type maxNodeId() const
Return the highest existing node ID.
Definition binary_forest.hxx:279
vigra::BinaryForest::BinaryForest
BinaryForest()
Create an empty forest.
Definition binary_forest.hxx:160
vigra::BinaryForest::addArc
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
vigra::BinaryForest::numParents
size_t numParents(Node const &node) const
Return the number of parents of node (equivalent to inDegree()).
Definition binary_forest.hxx:320
vigra::BinaryForest::numRoots
size_t numRoots() const
Return the number of trees in the forest.
Definition binary_forest.hxx:332
vigra::BinaryForest::maxArcId
index_type maxArcId() const
Return the highest possible arc ID (equivalent to 2*maxNodeId() + 1).
Definition binary_forest.hxx:284
vigra::BinaryForest::numArcs
size_t numArcs() const
Return the number of arcs. Always less than maxArcId() because not all arcs actually exist.
Definition binary_forest.hxx:294
vigra::BinaryForest::arcFromId
Arc arcFromId(index_type const &id) const
Get arc descriptor for id.
Definition binary_forest.hxx:273
vigra::BinaryForest::target
Node target(Arc const &arc) const
Find end node of arc.
Definition binary_forest.hxx:245
vigra::BinaryForest::outDegree
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
vigra::BinaryForest::getRoot
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
vigra::BinaryForest::Node
detail::NodeDescriptor< index_type > Node
Node descriptor type of the present graph.
Definition binary_forest.hxx:70
vigra::BinaryForest::addNode
Node addNode()
Add a new node (its node ID will be selected automatically).
Definition binary_forest.hxx:167
vigra::BinaryForest::getNode
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
vigra::BinaryForest::nodeFromId
Node nodeFromId(index_type const &id) const
Get node descriptor for id.
Definition binary_forest.hxx:267
vigra::BinaryForest::getChild
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,...
Definition binary_forest.hxx:357
vigra::BinaryForest::Arc
detail::ArcDescriptor< index_type > Arc
Arc descriptor type of the present graph.
Definition binary_forest.hxx:72
vigra::BinaryForest::source
Node source(Arc const &arc) const
Find start node of arc.
Definition binary_forest.hxx:239
vigra::BinaryForest::inDegree
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
vigra::BinaryForest::valid
bool valid(Node const &node) const
Check if node exists.
Definition binary_forest.hxx:216
vigra::BinaryForest::id
index_type id(Node const &node) const
Get ID for node descriptor node.
Definition binary_forest.hxx:255
vigra::BinaryForest::numNodes
size_t numNodes() const
Return the number of nodes (equivalent to maxNodeId()+1).
Definition binary_forest.hxx:289
vigra::BinaryForest::getParent
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
vigra::BinaryForest::merge
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
vigra::BinaryForest::numChildren
size_t numChildren(Node const &node) const
Return the number of children of node (equivalent to outDegree()).
Definition binary_forest.hxx:326
vigra::RGBValue
Class for a single RGB value.
Definition rgbvalue.hxx:128
vigra
vigra::Int64
detail::SelectIntegerType< 64, detail::SignedIntTypes >::type Int64
64-bit signed int
Definition sized_int.hxx:177

© 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