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

Improve this question
11
  • 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, 2017 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, 2017 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, 2017 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, 2017 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.
    – Stop harming Monica
    Oct 2, 2017 at 16:39

2 Answers 2

Reset to default
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.

Improve this answer
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).

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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