3

I've read this post Name of data structure that's tree-like with multiple root nodes. What I'm asking for is not a forest.

I would give you a simple example that easily depicts my case.

You have a usual power source from EB and an inverter (alternate power source) in your house. Consider these as the root nodes. And the next level are the monitoring meters at every room. And at the next level you have your equipment like Fan, AC, Fridge etc.

In this tree the first level are the list of power sources and the second-to-nth level will have the energy flow till the consumption equipment.

Is there any suitable data structure to depict this tree which has multiple root nodes?

Edit:

Image of the Required Structure

enter image description here

  • 1
    In your problem, In What your roots of trees are related to each others ? If they're independant they you just have independant logical trees that are associated with the same physical material through their leaves. – Walfrat Sep 26 '17 at 11:51
  • Hi Walfrat, roots nodes are independent. Considering them as independent logical trees will result in performance issue as i'm very sure that from the second level its a common tree and seperating them would simply cause redundancy of all nodes from the second level. – Vivek Sep 26 '17 at 11:57
  • 5
    No. The defining point of a tree is that it has a single root node. If you have multiple roots, it's just a plain old directed graph. – Kilian Foth Sep 26 '17 at 12:09
  • 1
    In graph theory, a tree is a very general structure that can have multiple roots. There is a directed, rooted tree that has only one root, which, I think, is what most of us programmers think of when we say tree data structure. We can have a directed tree without requiring a single root. – Erik Eidt Sep 26 '17 at 15:32
  • 2
    @Vivek I am sorry you took it personally, it was not intended to be. Your contradictory description made the question unclear, I already stated that. Now that mistake is fixed but I do not think the question is clear enough to answer it without too much guessing. Your description suggest your graph might be a multitree. It might have more interesting properties and some subset of those properties might have a name too, if a name is what you are after --is it? The fact that you did neither accept any answer nor commented to explain why they do not solve your problem does not help either. – Goyo Oct 2 '17 at 16:39
17

You are looking for a kind of Directed Acyclic Graph (DAG). These graphs do not have a root node. However, the nodes have a partial order. I.e. when we look at two nodes we can sometimes tell which node is “higher”. In your example, we could say that power sources are higher than meters which are higher than consumers.

Trees are a special kind of DAG where each node has exactly one parent node (except for the root which has no parents).

A Multitree is a DAG where there is only one unambiguous path between two nodes. I.e. all nodes that are reachable from any (root) node form a tree.

2

There are datastructures called multitree or polytree, direcected acyclic graphs with multiple root nodes.

From your example regarding energy flow, you may what to check the max-flow min-cut theorem as well (a.k.a. s-t flow theorem).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.