2
$\begingroup$

I have a problem that I encountered that boils down to the following:

Considered this directed graph I found on Google: enter image description here

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.

$\endgroup$
  • $\begingroup$ At the very least, you need the graph to be acyclic. If it isn't, you can't tell the difference between, e.g., a directed cycle and a bidirectional complete graph. $\endgroup$ – David Richerby Apr 4 '14 at 7:15
  • $\begingroup$ Graph should be acyclic. $\endgroup$ – workalldayallnight Apr 4 '14 at 12:14
2
$\begingroup$

Such a list can yield more than one graph. Consider 4: 1 2 3, 3: 1, 2: 1. One graph is $1\to 2, 2 \to 3, 3 \to 4$. A second graph is $1\to2, 1\to3, 2\to 4, 3\to 4$.

$\endgroup$
  • $\begingroup$ No, it's still wrong. In your first graph, 2 is an ancestor of 3 but the ancestor relation says that only 1 should be. $\endgroup$ – David Richerby Apr 4 '14 at 13:35
0
$\begingroup$

A naive but simple solution that only works for a complete ancestor relation:

Preliminaries

  • Model:

    • A directed graph $G=(V,E)$ is isomorphic to a relation $R(G)=(V,<_{E}), u <_{E} v \equiv (u,v) \in E$.
    • The ancestor relation is the transitive closure of the relation $R(G)$ corresponding to your target graph $G$ (there are several candidates for $G$ which you have no informatio to distinguish between, see further notes in this section). In particular, for each pair $(u,w) \in R^{q+1}$, the closure relation contains $(v,w) \in R^{q}$ for each $(u,v) \in R$.
  • Your graph must be directed (cf. comment by DavidRicherby), otherwise there is no unique solution. This shouldn't be a problem, as a graphical representation of timed branch and merge operations is cycle-free by nature.

  • The graph to be reconstructed must not contain any forward (='shortcutting') edges . To see this, assume it does contain one such edge $e$. The ancestor relations of this graph ad the same graph with $e$ deleted are the same.
  • The ancestor relation must be complete. Otherwise you wouldn't catch all forward (='shortcutting') edges in the ancestor relation's graph. You can compute the transitive closure of the ancestor relation beforehand, however, with Floyd-Warshall (sloppily phrased, the inversion of hte thinning operation). Thus you are guaranteed the correct result if your (incomplete) ancestor relation contains each predecessor relationship.

Algorithm 1

Reconstruct $R$ by iterative thinning.

Setup a $n \,x\, n$-matrix $A=(a_{ij})_{i,j=1\dots }$ to represent the ancestor relation: $a_{ij} = 1$ if $i$ is an ancestor of $j$, 0 otherwise. Copy $A$ into a new $n \,x\, n$-matrix $B$ and iterate over each tuple $(k,l,m) \in \{1,\ldots,n\}^3$. if $a_{kl}=1, a_{lm}=1$ and $a_{km}=1$, set $b_{km} := 0$. You'll end up with the adjacency matrix of your graph.

Efficiency 1

This naive approach requires $O(n^3)$ due to the iteration over all tuples.

Algorithm 2

This algorithm pursues the same idea more efficently at the cost of simplicity.

  • Create the topologically sorted graph $G=(V,E)$ from the ancestor relation. In a nutshell this means assigning numbers from $\{1,\dots k\}, k \leq n$ as 'levels' to the nodes in the graph. the closer a node is to one of the graph's minimal elements, the smaller its level.
  • Observation: if the absolute level difference (call that 'level distance', formally a mapping $d: E \to \mathbb N, d((u,v)) = |level(u)-level(v)|$ ) of the endpoints of an edge is 1, then this edge belongs to the target graph.
  • Order the edges of the graph in a descending way according to the level distance of their respective endpoints.
  • Iterate over this list. Let $e=(u,v) \in E$ be the currently inspected edge. iterate over all $w \in V: (u,w) \in E, d(u,w) = 1$ and $z \in V: (z,v) \in E, d(z,v) = 1$. if $(w,v) \in E$ or $(u,z) \in E$, delete $e$.
  • You'll end up with the desired graph.

Efficiency 2

  • Topological sorting takes $O(|V|+|E|)$
  • Edge sorting takes $O(|E| \log |E|)$.
  • The iteration is bound by $(O(|V|\cdot |E|)$ (check $O(|E|)$ edges, at each check compute up to $O(|V|)$ immediate level predecessors/successors. The structure to access precisely these edges incident to a given vertex can be added during edge sorting at no extra cost).
$\endgroup$
  • $\begingroup$ The directed graph isn't isomorphic to that relation: the relation is guaranteed to be transitive and the directed graph might not be. The graph can be mapped to its transitive closure but, as you observe in your following three points this mapping isn't injective for general (directed) graphs or even DAGs. As such, you can't even say that the graph corresponds to the transitive closure (though you probably can say that if the other three conditions are met, assuming that list is exhaustive). $\endgroup$ – David Richerby Apr 4 '14 at 10:36
  • $\begingroup$ @DavidRicherby The isomorphism remark was meant to refer to the general correspondence between the tuple notation of a finite relation and a representation as a directed graph, for the OP stated his problem in terms of the ancestor relation while the algorithm comes in terms of graphs. I've adjusted the wording. $\endgroup$ – collapsar Apr 4 '14 at 11:00
  • $\begingroup$ I realise I misread what you'd written; the new phrasing is clearer. My confusing came about because the symbol "$<$" is very nearly always used to denote a linear total order or, at the very least, some kind of partial order. The reader is very likely to see "$<$" and imagine something transitive, which is exactly what I did -- I interpreted it as the transitive closure of the edge relation. To be honest, though, I'm not sure why you're writing that the graph is isomorphic to exactly the same structure where the edge relation has been renamed from "$E$" to "$<_E$". Why not just work with "E"? $\endgroup$ – David Richerby Apr 4 '14 at 11:08
  • 1
    $\begingroup$ @DavidRicherby I introduced the new symbol just for expositional clarity - Thank you for making me see that this overformalizing is countereffective. $\endgroup$ – collapsar Apr 4 '14 at 14:23

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.