Given an adjacency matrix, what is an algorithm/pseudo-code to convert a directed graph to an undirected graph without adding additional vertices (does not have to be reversable)?

similar question here

  • 2
    $\begingroup$ Convert in what way, with what properties? It's not at all clear what you're looking for in the resulting undirected graph. $\endgroup$ – David Richerby Apr 20 '16 at 6:13
  • $\begingroup$ @DavidRicherby Any way is fine and just use the general properties of an adjacency matrix... Resulting undirected graph should be an adjacency matrix; I'm not sure what you mean really? $\endgroup$ – Ibrahim Apr 23 '16 at 22:59
  • 1
    $\begingroup$ OK, fine. Convert any directed graph to the undirected graph with three vertices and no edges. Not acceptable? So it turns out that "any way" is not fine. So what are you looking for? You want to convert a digraph X into an undirected graph Y but you've not said anything at all about how Y should related to X. $\endgroup$ – David Richerby Apr 24 '16 at 16:38
  • $\begingroup$ @DavidRicherby lets say each edge in a directed graph has 1 arrow pointing to some vertex, so the edges are 1way; so what I was asking is basically how to make the edges 2way. $\endgroup$ – Ibrahim Apr 28 '16 at 7:48
  • 1
    $\begingroup$ What do you mean by "how to make the edges 2-way"? If you're asking how to write a program to do that, the question is off-topic because we don't do programming here. If you're not asking about programming, I can't see what you are asking. Just make every edge 2-way by adding the edge $(y,x)$ for every edge $(x,y)$, if it's not already there. $\endgroup$ – David Richerby Apr 28 '16 at 14:59

Note that for an undirected graph, the adjacency matrix is symmetric, i.e. A[i,j] == A[j,i].

From this, we can see that we can simply compute the new value of A[i,j] = A[j,i] depending if A[i,j] or A[j,i] is set. Assuming the graph is unweighted, we can do:

for i from 0 to n-1
    for j from 0 to i
        if A[i,j] == 1 OR A[j,i] == 1
            A[i,j] = A[j,i] = 1
            A[i,j] = A[j,i] = 0

Note that we only have to consider 1 + 2 + 3 + ... + n-1 entries since the resultant adjacency matrix is symmetric.

If we have a weighted graph, we now have the problem of which edge weight to take as the new undirected graph edge weight. For example, if w(2,5) = 5 but w(5,2) = 10, the resultant edge weight is ambiguous. However, this is enough for you to figure out what else you need from here.

  • $\begingroup$ So for a weighted graph it would just be if A[i,j] !=0 { A[j,i] == A[i,j] } and vice versa? (given there is a maximum of 1 edge between any pair of vertices) $\endgroup$ – Ibrahim Apr 23 '16 at 23:07
  • $\begingroup$ @Ibrahim Yes that's correct, in this case, you can just set A[i, j] = A[j, i] = max(A[i, j], A[j, i]), assuming you have no negative weight edges/you use 0 to represent the absence of an edge in the adjacency matrix. $\endgroup$ – Irvin Lim Apr 24 '16 at 3:56

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