35 #ifndef VIGRA_BINARY_FOREST_HXX
36 #define VIGRA_BINARY_FOREST_HXX
68 typedef Int64 index_type;
70 typedef detail::NodeDescriptor<index_type>
Node;
72 typedef detail::ArcDescriptor<index_type>
Arc;
91 index_type
id(
Node const & node)
const;
93 index_type
id(
Arc const & arc)
const;
147 index_type parent, left_child, right_child;
150 std::vector<NodeT> nodes_;
153 std::vector<index_type> root_nodes_;
170 nodes_.push_back(NodeT());
171 root_nodes_.push_back(n.id());
179 NodeT & u_node = nodes_[u.id()];
180 NodeT & v_node = nodes_[v.id()];
181 index_type arc_id = 2*u.id();
184 if (u_node.left_child == v.id())
186 if (u_node.right_child == v.id())
187 return Arc(arc_id+1);
190 if (u_node.left_child == -1)
192 u_node.left_child = v.id();
194 else if (u_node.right_child == -1)
196 u_node.right_child = v.id();
201 vigra_fail(
"BinaryForest::addArc(): The node u already has two children.");
205 v_node.parent = u.id();
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);
220 return node.id() >= 0 && (size_t)node.id() < nodes_.size();
226 if (arc == lemon::INVALID)
229 index_type
const uid = arc.id()/2;
233 if (arc.id() % 2 == 0)
234 return nodes_[uid].left_child != -1;
236 return nodes_[uid].right_child != -1;
242 return Node(arc.id()/2);
248 NodeT
const & u_node = nodes_[arc.id()/2];
249 if (arc.id() % 2 == 0)
250 return Node(u_node.left_child);
252 return Node(u_node.right_child);
268 index_type
const &
id
274 index_type
const &
id
281 return nodes_.size()-1;
291 return nodes_.size();
302 if (nodes_[node.id()].parent == -1)
311 NodeT
const & n = nodes_[node.id()];
312 if (n.left_child == -1 && n.right_child == -1)
314 else if (n.left_child == -1 || n.right_child == -1)
334 return root_nodes_.size();
341 return Node(lemon::INVALID);
350 NodeT
const & n = nodes_[node.id()];
351 if (n.parent == -1 || i != 0)
352 return Node(lemon::INVALID);
354 return Node(n.parent);
361 NodeT
const & n = nodes_[node.id()];
363 return Node(n.left_child);
365 return Node(n.right_child);
367 return Node(lemon::INVALID);
373 if (i >= root_nodes_.size())
374 return Node(lemon::INVALID);
376 return Node(root_nodes_[i]);
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)
387 NodeT & n = nodes_[i];
390 if (n.left_child != -1)
391 n.left_child += offset;
392 if (n.right_child != -1)
393 n.right_child += offset;
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)
400 root_nodes_[i] += offset;
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