7
$\begingroup$

I programmatically generate many large undirected graphs. Sometimes these graphs are multigraphs, that is, they contain more than one edge between a pair of nodes. I've tried to delete the "extra" edges, to keep only one per node pair, with no success. It should be trivial, but I can't find a simple solution.

Take for instance, the following simple graph:

G0 = Graph[{a <-> b, b <-> c, c <-> a, b <-> a, b <-> c, b <-> a}, 
VertexLabels -> All]

enter image description here

How to keep only one edge between a and b, and one edge between c and b?

I've tried some very inefficient ways, but no success. I'd like to know if there's a simple solution (since the problem seems trivial at glance).

Note: If there are self-loops, I'd still like to keep them, therefore SimpleGraph[] is not a solution for this particular problem.

Thank you,

Pedro

$\endgroup$
6
$\begingroup$
Graph[
  DeleteDuplicates[
  Sort /@ {a <-> b, b <-> c, c <-> a, b <-> a, b <-> c, b <-> a}], 
  VertexLabels -> All]

or

Graph[
 DeleteDuplicates[
 Map[Sort, {a <-> b, b <-> c, c <-> a, b <-> a, b <-> c, b <-> a}]],
 VertexLabels -> All]
$\endgroup$
  • $\begingroup$ Wow, this is very simple and works with my large networks, thanks! $\endgroup$ – PedroSapichu Jul 12 '18 at 23:31
6
$\begingroup$

if self-loops are not needed

  • SimpleGraph[g]
    removes all self-loops and multiple edges between the same vertices.

So

SimpleGraph[G0, Options @ G0]

enter image description here

But ...

in my case, I'd still need them if they exist.

So it is not as simple any more:

simpleGraph = Graph[First /@ Gather[Sort /@ EdgeList @ #], Options @ #] &

G1 = Graph[{a <-> b, a <-> a, a <-> a,a <-> a, b <-> c, c <-> a,
     b <-> a, b <-> c, b <-> a},  VertexLabels -> All, ImageSize -> 200];

Row[{G1, SimpleGraph[G1, Options @ G1], simpleGraph @ G1}]

enter image description here

Alternatively, you can also use

simpleGraph2 = EdgeDelete[#, Flatten[Rest /@ Gather[Sort /@ EdgeList @ #]]]&;
simpleGraph3 = AdjacencyGraph[VertexList @#, Unitize @ AdjacencyMatrix @ #, Options@#]&;
$\endgroup$
  • $\begingroup$ This is a great option if self-loops are not needed (in my case, I'd still need them if they exist). Thank you! @kglr $\endgroup$ – PedroSapichu Jul 13 '18 at 0:13
5
$\begingroup$

As others said, SimpleGraph will do this. But it will also remove self-loops.

g = Graph[{1 <-> 1, 1 <-> 2, 2 <-> 3, 2 <-> 3, 3 <-> 1}]

enter image description here

SimpleGraph[g]

enter image description here

IGraph/M has functions to deal precisely with this problem.

IGSimpleGraph has options which control the removal of self-loops and multi-edges separately. We can just turn off self-loops removal.

IGSimpleGraph[g, SelfLoops -> True]

enter image description here

There is also a function that merges multi-edges and combines their weights. The default combiner adds up the weights—for unweighted graphs this means counting how many edges were merged.

IGWeightedSimpleGraph[g, EdgeLabels -> "EdgeWeight"]

enter image description here


A final note: I know that you are already familiar with IGraph/M. When there is an issue like this, it is always worth checking if IGraph/M has a solution—it often does, especially when the problem is this common. IGraph/M development is driven by practical issues that come up during real-world network analysis tasks, not by mere guesses about what users might or might not need.

$\endgroup$
  • $\begingroup$ that's actually a great solution. I've explored IGraph/M, but most of the time I try to use simple built-in MMA functions. Next time I'll check IGraph before trying to solve something that might be already implemented there. Thanks! $\endgroup$ – PedroSapichu Jul 13 '18 at 15:00
  • $\begingroup$ @PedroSapichu BTW all feedback about IGraph/M (especially constructive criticism) is welcome! $\endgroup$ – Szabolcs Jul 13 '18 at 17:49
1
$\begingroup$

Maybe this is you after

SimpleGraph[G0]

$\endgroup$

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.