HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Reconstruct directed graph from list of ancestors for each node

Submitted by: @import:stackexchange-cs··
0
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

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 7


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.

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.