patternMinor
Reconstruct directed graph from list of ancestors for each node
Viewed 0 times
graphancestorseachnodedirectedforreconstructlistfrom
Problem
I have a problem that I encountered that boils down to the following:
Considered this directed graph I found on Google:
I have the following information available to me
How can I re-construct the original graph in a reasonably efficient manner? I basically have large sets of data that I would like to have visualized as branches and merges(similar to a code repository, but not quite).
Note: While I believe my data shouldn't be disjoint, I'm somewhat certain my data is incomplete and will produce disjoint graphs, or at the very least have many separate "roots". There is no ordering to the data, everything must be considered random, the lists can also be thought of as sets.
Considered this directed graph I found on Google:
I have the following information available to me
Node: Ancestors
1 : 3
2 : 1 3 5 7
3 : Null
4 : 3 5
5 : 3
6 : 1 2 3 4 5 7
7 : 1 3
8 : 1 2 3 4 5 6 7How can I re-construct the original graph in a reasonably efficient manner? I basically have large sets of data that I would like to have visualized as branches and merges(similar to a code repository, but not quite).
Note: While I believe my data shouldn't be disjoint, I'm somewhat certain my data is incomplete and will produce disjoint graphs, or at the very least have many separate "roots". There is no ordering to the data, everything must be considered random, the lists can also be thought of as sets.
Solution
Such a list can yield more than one graph. Consider
4: 1 2 3, 3: 2 1, 2: 1. One graph is $1\to 2, 2\to3, 3\to4$. A second graph is $1\to 2, 2\to3, 3\to4 , 2\to4$.Context
StackExchange Computer Science Q#23408, answer score: 4
Revisions (0)
No revisions yet.