# Automatically convert pairs of directed edges to an undirected edge?

I have a directed graph, which for some pairs of vertices, has a directed edge between them in each direction. I would like to replace such pairs of directed edges between the same vertices but in opposite directions, by a single undirected edge. What's a simple way to do this?

• Including a sample graph would increase the speed and likelihood of answers. Feb 11 '15 at 16:52
• – kglr
Feb 11 '15 at 17:21
• @kguler From the title and a quick glance that seems like a duplicate. Is it not? Feb 11 '15 at 17:23
• @kguler I see that the Accepted answer using EdgeShapeFunction so it is more formatting that actual replacement. I guess not a duplicate after all? Feb 11 '15 at 17:25
• Mr.Wizard, the two questions are "almost" the same. However, because version 10 allows mixed graphs and version 9 did not, making explicit the requirement that the output is a mixed graph will make the current question truly different from the linked one.
– kglr
Feb 11 '15 at 17:58

A brute-force method using Gather.

Starting graph:

SeedRandom[0]
edges = Rule @@@ RandomInteger[{1, 5}, {12, 2}]

Graph[edges]


Processing and new graph (this will work with both Rule and DirectedEdge:

new =
Gather[edges, #[[1]] == #2[[2]] && #[[2]] == #2[[1]] &] /.
{{_[a_, b_], __} :> a <-> b, {x_} :> x};

Graph[new]


## Update

Seeking a more efficient implementation, if:

• All edges in the original graph are either Rule or UndirectedEdge at the outset

• You do not mind losing multiple (directed) edges between vertices

I believe we can use the much more efficient GatherBy as follows:

new2 =
Union /@ GatherBy[edges, Sort] /.
{{_[a_, b_], __} :> a <-> b, {x_} :> x};

Graph[new2]


• One mistake everyone has made in all the answers is that Graph[EdgeList[g]] will lose unconnected vertices. Graph[VertexList[g], EdgeList[g]] will keep them. This is not nitpicking. I've been bitten hard by this mistake. I know that you are constructing the example graph based purely on an edge list, but this is something that's still worth paying attention to ... Feb 11 '15 at 18:28
• Would you clarify how /. {{_[a_, b_], __} :> a <-> b, {x_} :> x} works? I don't fully understand _[a_, b_] but it seems to be an opaque variation of belisarius' Rule[a_,b_]. Feb 11 '15 at 18:52
• @Szabolcs Thanks for the caveat. Feb 11 '15 at 18:58
• @David _[a_, b_] is a pattern for an expression with any head and two arguments, therefore it will match Rule, DirectedEdge, UndirectedEdge, etc. This lets me collapse any of the sublists from Gather into a single UndirectedEdge without worrying about type. {x_} :> x strips the List from any singlets. Feb 11 '15 at 19:00

An alternative way to use GatherBy

bidirectedToUndirected=Join@@(GatherBy[EdgeList@#,Union] /. {x_, y_} :> {UndirectedEdge @@ x}) &;


Example (from here):

words = DictionaryLookup["wol*"];
edges = Flatten[Map[(Thread[# ->  DeleteCases[Nearest[words, #, 3], #]]) &, words]];
opts = {VertexLabels -> "Name", ImagePadding -> 60, ImageSize -> 500};
g = Graph[edges, opts];

Row[{g, Graph[VertexList[g], bidirectedToUndirected@g, opts]}]  (* thanks: @Szabolcs  *)


• @Mr.Wizard, right. I missed the mixed graph requirement (which version 9 does not support except through using different EdgeShapeFunction properties for different edge types as in the linked Q/A).
– kglr
Feb 11 '15 at 17:47
• Bloody hell, where did that come from? ;-p (I didn't see GatherBy until after posting my version.) +1 of course. *sigh* Feb 11 '15 at 19:24
• +1 for using Union instead of Sort and Union Feb 11 '15 at 20:16
• @David Out of curiosity are you comparing that to my answer? I have reason for what I wrote, or at least I think I do. Feb 11 '15 at 20:21
• Mr.Wizard You are indeed perceptive. Yes, I was. Feb 11 '15 at 22:20

One can do it quite fast with AdjacencyMatrix

graphSum[graphs__, opts___?OptionQ] /; VectorQ[{graphs}, GraphQ] :=
Graph[Union @@ VertexList /@ {graphs}, Join @@ EdgeList /@ {graphs}, opts];

pairwiseMin[a_, b_, dom_: Reals] :=
If[dom === Integers, Quotient, Divide][a + b - Abs[a - b], 2];

mixedGraph[g_Graph] := graphSum @@ Map[AdjacencyGraph[VertexList@g, #] &, {# - #2, #2}] &[#,
pairwiseMin[#, Transpose@#, Integers]] &@AdjacencyMatrix@g


Here graphSum is analog of GraphSum which was in old Combinatorica package. There is built-in GraphComputationGraphSum in V10, but it doesn't work for mixed graphs (one can fix it, see the previous revision of this answer).

SeedRandom[0]
edges = Rule @@@ RandomInteger[{1, 5}, {12, 2}];
g = Graph[Range@7, edges]


mixedGraph@g


It also converts directed loops to undirected loops, but they have the same meaning.

Timing for a big graph:

SeedRandom[0]
edges = Rule @@@ RandomInteger[{1, 10000}, {20000, 2}];
g = Graph[edges];
mixedGraph@g; // AbsoluteTiming
(* {0.213162, Null} *)


It is comparable with Mr.Wizards new2 but it takes into account multiple edges.

Also one can do it purely with graph functions

mixedGraph[g_Graph] :=
GraphUnion[GraphDifference@##, UndirectedGraph@GraphIntersection@##] &[g, ReverseGraph@g]


However, it is slow and simplifies multiple edges.

• +1 for use of some interesting functions, but at least in my testing this is several times slower than my naive brute-force method. I don't know if your output should be considered better or worse than mine; I purposely wanted to change the graph as little as possible but that may not be important to the OP. Feb 11 '15 at 19:08
• @Mr.Wizard It is not fine, I change the wording a bit. Also I add another approach with graph functions which works fine with multigraphs Feb 11 '15 at 19:40

Another not-efficient alternative:

edges //. {a___, Rule[x_, y_], b___, Rule[y_, x_], c___} :> {a, b, c, UndirectedEdge[x, y]}

• I'm afraid that's going to be significantly worse than Gather, based on earlier experimentation with multiple ___` patterns. I'll be happy to be proven wrong but until then I'm holding my vote as an edge list may be quite long. Feb 11 '15 at 19:02
• Seems I was wrong. The speed of this function depends greatly on the nature of the edge list. With little duplication it can be slightly faster than mine, but with more duplication it can be an order of magnitude slower. +1 for a pretty implementation. Feb 11 '15 at 19:13
• @Mr.Wizard As almost always, a repeated replacement rule can't beat a clever implementation in the general case. Thanks for your comments/experimentation. Feb 11 '15 at 19:15