7

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

Vivek
  • 189
  • 1
  • 1
  • 6
  • 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
  • 6
    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](https://en.wikipedia.org/wiki/Tree_(graph_theory)) is a very general structure that can have multiple roots. There is a [directed, rooted tree](https://en.wikipedia.org/wiki/Tree_(graph_theory)#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
  • In the title you say "multiple root nodes" but in your example there is only one root node. What are you actually asking? – Stop harming Monica Sep 26 '17 at 18:40
  • @ErikEidt From your link about tree (graph theory): "A rooted tree is a tree in which one vertex has been designated the root." Note the "one vertex" bit. – Stop harming Monica Sep 26 '17 at 18:43
  • Goyo, In my example i depicted two nodes on the root. 1. usual power source 2. Inverter Power Source. – Vivek Sep 27 '17 at 04:05
  • @Vivek You wrote "the root node" (singular). You didn't show how your graph looks like so I don't really know. It is probably a multitree and several other things too, but what would be a suitable data structure depends on your intent. – Stop harming Monica Sep 27 '17 at 10:01
  • @Goyo, sorry it was a mistake. But were you the one down voting just for that? – Vivek Oct 02 '17 at 13:48
  • 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. – Stop harming Monica Oct 02 '17 at 16:39
  • @Goyo, Thanks a lot. That makes a lot more sense. And seriously i didn't took it personal. I was confused few years back in stack overflow and the same now with stack exchange. And regarding other answers i'm still investigating if DSA is the right solution. I'll update my question as per your suggestions. Thanks again. – Vivek Oct 03 '17 at 06:25

2 Answers2

23

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.

amon
  • 132,749
  • 27
  • 279
  • 375
4

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).

Philip Kendall
  • 22,899
  • 9
  • 58
  • 61
Bruno Ranieri
  • 149
  • 3