10
$\begingroup$

I am looking for an algorithm to convert a digraph (directed graph) to an undirected graph in a reversible way, ie the digraph should be reconstructable if we are given the undirected graph. I understand that this will come in expense of the undirected graph having more vertices but I do not mind.

Does one know how to do this or can suggest any references? Thanks in advance.


Update: Regarding the answer of AdrianN below. It might be a good starting point but I don't think it works in its current form. Here is an image of why I think it doesn't: enter image description here


Update after D.W.'s comment: I consider the vertices of the graphs to be unlabeled. If a solution involves labeling the vertices (like AdrianN's does), then it should give the same (isomorphic) undirected graph no matter how the labeling is done. My definition of "isomorphic" for graphs with labeled vertices is that there is a permutation of the labeling that relates the two graphs, but I am not sure of the exact definition for unlabeled graphs...

$\endgroup$
  • 1
    $\begingroup$ I think this question is too broad. What are your constraints? $\endgroup$ – adrianN Jan 15 '14 at 11:47
  • $\begingroup$ I can't really think of any constrains for now. I guess any way to encode the information of a directed graph into an undirected one would do, as long as it is reversible. I guess what I have in mind is the simplest type of undirected graphs, so I am looking for a solution that doesn't use colors either for the vertices or the edges. $\endgroup$ – Heterotic Jan 15 '14 at 12:36
  • $\begingroup$ I think you should specify in the question what you mean by "the same graph". Do you mean that the vertices are labelled, or that the vertices are unlabelled? Do you mean that $(V,E)$ is the same for both, or that the two graphs are isomorphic? It sounds like you mean the latter. Are you sure that's a requirement in your application? If you're allowed to retain labels, the problem gets easier and AdrianN's answer works (because the edge $(3,4)$ is not the same as the edge $(1',2')$). $\endgroup$ – D.W. Jan 15 '14 at 18:51
  • 2
    $\begingroup$ Please incorporate your updates into the question. At any point in time, SE posts should be readable top to bottom without wondering about history; that's archived separately. $\endgroup$ – Raphael Jan 15 '14 at 19:45
6
$\begingroup$

For each directed edge $e=(x,y)$, add new vertices $v^e_1, \dots, v^e_5$ and replace $e$ with the edges $xv^e_1$, $v^e_1v^e_2$, $v^e_1v^e_3$, $v^e_3v^e_4$, $v^e_4v^e_5$, $v^e_3y$.

To decode, every leaf (degree-1 vertex) whose neighbour has degree 2 must be $v^e_5$ for some edge $e=(x,y)$; its neighbour is $v^e_4$ and the other neighbour of $v^e_4$ is $v^e_3$. $v^e_3$ has a unique neighbour that has both degree 3 and is adjacent to a leaf: the neighbour is $v^e_1$ and its leaf is $v^e_2$ (if $v^e_1$ has two leaf neighbours, pick one arbitrarily to be $v^e_2$). The other neighbour of $v^e_1$ is $x$ and the other neighbour of $v^e_3$ is $y$. Restore the directed edge $(x,y)$ and delete the vertices $v^e_1, \dots, v^e_5$.

$\endgroup$
7
$\begingroup$

David Richerby's answer (which was accepted) is good.

I followed his instructions on a simple example digraph, and hope it helps someone.

digraph a <-> b, c -> a, b -> c

(I would have posted this as a comment on David's answer, but I do not have the reputation points required.)

$\endgroup$
  • 1
    $\begingroup$ The graphical representation is a huge improvement over the original answer. Thank you for posting it as an answer not a comment. $\endgroup$ – OrangeSherbet Jun 15 at 22:42
  • 1
    $\begingroup$ I always feel overwhelmed when I look at a formal explanation or formula in a math paper. I just have to get over that anxiety, and look at each sentence slowly -- looking things up I am unfamiliar with as I go along. Then I scribble an example like this to be sure I understand. By the end I am always dumbfounded at how simple it was all a long, and sort of horrified of how much effort it took me to understand it. Feels like I'm from a different planet sometimes. Glad that I could help you understand it quicker. Once you see it, it is easy. $\endgroup$ – William Jun 20 at 17:05
2
$\begingroup$

To convert a directed graph $D$ to an undirected graph $G$ one do the following:

  1. Number the nodes of $D$
  2. Create two undirected graphs $G'$, $G''$ on the same vertex set as $D$
  3. For every edge $u$,$v$ in $D$ add the edge to $G'$ if $u<v$, else add the edge to $G''$
  4. G is the disjoint union of $G'$ and $G''$

When doing the disjoint union one must take care to make it reversible.

Example

$\endgroup$
  • $\begingroup$ This is a good attempt and it's along the lines I had in mind for an answer but it doesn't work because the inverse is not unique. For example, the graph O<->O O O will be converted to the graph O-O O O O-O O O but then this latter could have also come from the directed graph O->O O->O O O, so the process is not reversible. $\endgroup$ – Heterotic Jan 15 '14 at 13:26
  • $\begingroup$ I added a picture to make it clearer. $\endgroup$ – adrianN Jan 15 '14 at 14:54
-1
$\begingroup$

What about the identity function ? I.e. every digraph can be seen as a undirected, bipartite graph with equal sized partitions and vice versa.

$\endgroup$
  • $\begingroup$ I assume you mean to code the digraph $G=(V,E)$ with the graph $(V\times\{0,1\}, \{(\langle u,0\rangle, \langle v,1\rangle)\mid (u,v)\in E\})$. That doesn't work because, it can't cope with bidirectional edges and, if $G'$ is the result of reversing all edges in $G$, then $G$ and $G'$ have isomorphic encodings but aren't necessarily isomorphic themselves. $\endgroup$ – David Richerby Jan 15 '14 at 23:06
-1
$\begingroup$

Here's a stab at this:

Replace the direction information with additional vertices in the undirected graph. In other words, use the additional vertices in the undirected graph to "encode" the direction information. For example, for each directed vertex with at least one edge, add a number of undirected vertices equal to 1 + the number of "incoming" edges. Vertices with zero edges remain unchanged.

To perform the reverse direction, create a directed vertex for each vertex that has 0 or more than 1 edge. (Vertices with exactly one edge are the "direction encoding" vertices). Each edge that connects another multi-edged vertex is a connection in the directed graph. Now is the tricky part that I can't explain an algorithm for (but I think one exists): You must deduce the direction of the arrows given only the number of incoming arrows for each vertex.

I think the tricky part is sort of like playing minesweeper :-) Figure out where the bombs (incoming edges) are given the number of adjacent bombs for each square (vertex).

$\endgroup$
  • $\begingroup$ What is a "directed vertex"? In any case, this isn't uniquely decodable. Suppose a vertex $x$ has a bunch of degree-1 vertices attached to it, along with a bunch of vertices of other degrees. How would you tell how many of them represent incoming edges from vertices of degree 1 and how many are coding the in-degree of $x$? In any case, solving Minesweeper is NP-hard, the solution isn't always unique and it's not obvious that it can be solved at all when the squares aren't necessarily arranged in a nice grid. $\endgroup$ – David Richerby Jan 16 '14 at 19:58
  • $\begingroup$ By "directed vertex", I mean a vertex in the directed graph (as opposed to the equivalent non-directed graph). You can distinguish "real" edges from "degree encoding" edges because only "degree encoding" vertices have a single edge. That was the reason for the "1 +" in my description. I'll take your word about the minesweeperesque "tricky part". I don't know that it is exactly equivalent to minesweeper, but I can believe that I maybe only kicked the bucket down the road :-) $\endgroup$ – Aaron Jan 16 '14 at 20:13
  • $\begingroup$ Also, I didn't quite understand your solution when I first read it, but I see how it works now. Clever! $\endgroup$ – Aaron Jan 16 '14 at 20:26
  • $\begingroup$ Let $x$ be a vertex in the original graph that has no incoming edges and exactly one outgoing edge. In the coded graph, $x$ appears as a vertex with exactly one edge coming out of it. How do you distinguish that sort of degree-1 vertex from the sort of degree-1 vertex that codes in-degree? $\endgroup$ – David Richerby Jan 16 '14 at 20:46
  • $\begingroup$ I think it's "minesweeper-moot" now, but my idea was to take the directed edge $(x,y)$ and convert it to $(x_0,x), (x,y), (y,y_0)$ and $(y,y_1)$. So $x$ will have two edges, not 1. Any vertex which has only 1 edge is degree-coding. $y$ has two degree-coding vertices, indicating a degree of 1. In this simply example, decoding is easy because we know there are only two vertices, and they have degree of 0 and 1, respectively, thus $(x,y)$ $\endgroup$ – Aaron Jan 16 '14 at 21:19

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.