Given a directed graph $(V,E)$ with $E\subseteq V\times V$, a source vertex $v_0\in V$ from which all other vertices are reachable, and a set $I$ of unique identifiers for the edges in $E$ (i.e., there is a bijection $I \rightarrow E$), we can construct a set $M\subseteq V \times \mathcal{P}(I)$ containing exactly those $(v,S)$ such that there is a path from $v_0$ to $v$ using exactly the edges represented by $S$ (in any order and repetition). For example, the graph $(\{A,B\},\{(A,B),(B,A)\})$ with $v_0=A$ and $I(a)=(A,B), I(b)=(B,A)$ would be represented as $\{(A,\emptyset),(B,\{a\}),(A,\{a,b\}),(B,\{a,b\})\}$.
I wonder under which conditions the inverse construction is possible: assuming $M$ is "consistent" (there is at least one graph satisfying it), what conditions are needed for $M$ to represent a unique graph? Certainly $M$ has to satisfy some kind of "closure" property, like: for every $(v,S)\in M$ (with $S\neq\emptyset$), there exists $(u,P)\in M$ such that $|S|=|P|+1$. Then a (hopefully deterministic) algorithm would construct $G$ by picking elements from $M$ in order of increasing cardinality.
Edit: of course the closure property should be that for every $(v,S)\in M$ (with $S\neq\emptyset$), there exists $(u,P)\in M$ such that $S= P\uplus\{x\}$. But this is not strong enough if self-loops are allowed: $\{(A,\emptyset),(B,\{a\}),(B,\{a,b\})\}$ represents two non-isomorphic graphs (one with $b=(B,A)$, the other with $b=(B,B)$).
Edit: I just noticed that there are counter-examples even without self-loops: $M=\{(A,\emptyset),(B,\{a\}),(C,\{a,b\}),(C,\{a,b,c\})\}$ may imply $c=(C,B)$ or $c=(C,A)$ (or $c=(C,C)$).
Has somebody worked on this kind of problem?