# 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. Commented Feb 11, 2015 at 16:52
• – kglr
Commented Feb 11, 2015 at 17:21
• @kguler From the title and a quick glance that seems like a duplicate. Is it not? Commented Feb 11, 2015 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? Commented Feb 11, 2015 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
Commented Feb 11, 2015 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 ... Commented Feb 11, 2015 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_]. Commented Feb 11, 2015 at 18:52
• @Szabolcs Thanks for the caveat. Commented Feb 11, 2015 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. Commented Feb 11, 2015 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
Commented Feb 11, 2015 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* Commented Feb 11, 2015 at 19:24
• +1 for using Union instead of Sort and Union Commented Feb 11, 2015 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. Commented Feb 11, 2015 at 20:21
• Mr.Wizard You are indeed perceptive. Yes, I was. Commented Feb 11, 2015 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}] &[#,


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. Commented Feb 11, 2015 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 Commented Feb 11, 2015 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. Commented Feb 11, 2015 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. Commented Feb 11, 2015 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. Commented Feb 11, 2015 at 19:15