# Algorithm to convert many paths into a graph?

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.

• 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$?
– orlp
Dec 30, 2020 at 21:37
• Yes. Thanks for adding that technical specificity 🙏 Dec 30, 2020 at 22:41
• 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?
– D.W.
Dec 31, 2020 at 7:47

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