3
$\begingroup$

I have a list of billions of paths in an unknown graph, e.g.:

A -> B -> D -> E
A -> F -> K
A -> B -> K -> B -> D -> E

and I want to obtain the edge list, e.g.:

A -> B
A -> F
B -> D
B -> K
D -> E
F -> K
K -> B

This feels like a classical problem, and I would like to know if there is a classical solution.

$\endgroup$
3
  • $\begingroup$ Allow me to rephrase; correct me if I'm wrong. You have a lot of walks of some unknown graph $G$ and wish to reconstruct graph $G$? $\endgroup$
    – orlp
    Dec 30, 2020 at 21:37
  • $\begingroup$ Yes. Thanks for adding that technical specificity 🙏 $\endgroup$ Dec 30, 2020 at 22:41
  • $\begingroup$ It can't be uniquely solved in the worst case: there could be some vertex in the graph that just never happened to be visited. Do you have some probability model (e.g., these walks are random walks from the graph, by some notion of "random")? Or something else? Is there more context? $\endgroup$
    – D.W.
    Dec 31, 2020 at 7:47

2 Answers 2

1
$\begingroup$

There are very different solutions, and which one is best depends much on your specific instance:

  • if $G$ is small, then just parse the input list and add each encountered edge to a set stored in central memory (if the number $n$ of vertices is small then the best solution for this is a boolean $n \times n$ matrix, otherwise a hash table makes a good job);
  • if $G$ is huge, then the approach above needs too much memory; I would then just list all edges, sort them, and remove duplicates (while sorting). Something like zcat list.gz | awk -F ' -> ' '{for (i=2;i<=NF;i++) print $(i-1),"->",$i;}' | sort -u | gzip -c > edges.gz should make the job (maybe use the -S sort option).
$\endgroup$
0
$\begingroup$

You can find the smallest graph that is consistent with those walks from the graph as follows: start with an empty graph; for each pair of vertices that are adjacent in a list, e.g., $A \to B$, add the corresponding edge $A \to B$ to the graph. The resulting graph is one that could have led to those walks, and is the smallest such.

You can't guarantee to uniquely and correctly reconstruct the original graph. If you are unlucky, there could be some vertex in the graph that was just never visited by any walk, and then it won't appear in the reconstruction. If walks are chosen randomly and you have enough of them, the probability of this happening might be low enough that you are willing to accept this risk.

$\endgroup$

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.