12
$\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$
4
  • 1
    $\begingroup$ I think this question is too broad. What are your constraints? $\endgroup$
    – adrianN
    Jan 15, 2014 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, 2014 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, 2014 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, 2014 at 19:45

5 Answers 5

7
$\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$
0
10
$\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$
5
  • 2
    $\begingroup$ The graphical representation is a huge improvement over the original answer. Thank you for posting it as an answer not a comment. $\endgroup$
    – JoseOrtiz3
    Jun 15, 2019 at 22:42
  • 2
    $\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, 2019 at 17:05
  • $\begingroup$ @William don't worry, it's not specific to you whatsoever. Choosing to encode a graph meant solely for humans to understand as a set of unnamed and non-semantically numbered vertices is basically the least efficient way you could possibly communicate that information. Even without a visual graph, which is obviously the only remotely sane choice for sighted people, you could have phrased it like this: 'Replace each directed link with a chain of two nodes, named "source-adjacent" and "target-adjacent". From "source-adjacent", add a new leaf. From "target-adjacent", add a chain of two nodes.' $\endgroup$
    – iono
    Jun 29, 2023 at 4:42
  • $\begingroup$ @William 'Because we added this structure to every node, the original nodes, regardless of their original relationships, will now all have neighbours with exactly 3 links. Now, any leaf whose neighbour has only 2 links must be the end of the 2-node chain we added to "source-adjacent". From there, move to "source-adjacent". Now we can distinguish between our 2 neighbours (the original source node and "target-adjacent") the same way: checking which one doesn't only have neighbours with 3 links: that's "target-adjacent" (because it neighbours a leaf). Now we know the original link's direction.' $\endgroup$
    – iono
    Jun 29, 2023 at 5:03
  • $\begingroup$ I flipped "source" and "target" according to the original scheme but you get the point. It's an elegant solution but identifying all nodes by an arbitary integer and then listing their connections is the way to explain to computers, not humans, and even then makes for unreadable code. The leaf and the 2-node chain we add to "source-adjacent" and "target-adjacent", respectively, exist purely to give meaning so we should name them as such: "source-indicator" and "target-indicator". It's inexcusable how badly many programmers and mathematicians name things - a necessary and teachable skill. $\endgroup$
    – iono
    Jun 29, 2023 at 5:17
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$
2
  • $\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, 2014 at 13:26
  • $\begingroup$ I added a picture to make it clearer. $\endgroup$
    – adrianN
    Jan 15, 2014 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$
1
  • $\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$ Jan 15, 2014 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$
5
  • $\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$ Jan 16, 2014 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, 2014 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, 2014 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$ Jan 16, 2014 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, 2014 at 21:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.