Algorithm to convert many paths into a graph?

Question

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.

Answer 1

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

Answer 2

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.