Message Boards Message Boards

[✓] How to import multigraphs that have edge properties?

GROUPS:

Cross posted on StackExchange.


Mathematica cannot represent edge properties in multigraphs (except for EdgeWeight, EdgeCapacity and EdgeCost). This is a very severe limitation when using Mathematica for network analysis because there are many datasets out there which have both parallel edges and edge properties (e.g. here).

I am looking for a practical method to import such datasets from GraphML or Graphlet (GML) formats. Since Mathematica cannot handle properties in multigraphs, I need to have parallel edges merged into a single edge, and their properties combined in some way, e.g. as a list. Loop edges should be kept.

Example

This is a graphlet file:

file = "
  graph
  [
   directed 1
   node [
    id 1
    label \"one\"
   ]
   node [
    id 2
    label \"two\"
   ]
   node [
    id 3
    label \"three\"
   ]
   edge [
    source 1
    target 2
    value 123
   ]
   edge [
    source 1
    target 2
    value 321
   ]
   edge [
    source 2
    target 3
    value 42
   ]
   edge [
    source 3
    target 3
    value 137
   ]
  ]";

If we import it normally, there will be only one property value present for the 1->2 edges, even though there are two such edges with different values. It's a pity that Import doesn't even show a warning that something is wrong.

g = ImportString[file, "Graphlet"]
Options[g, Properties]
(* {Properties -> {1 \[DirectedEdge] 2 -> {"value" -> 321}, 
   3 \[DirectedEdge] 3 -> {"value" -> 137}, 
   2 \[DirectedEdge] 3 -> {"value" -> 42}, 
   "GraphProperties" -> {"directed" -> 1}}} *)

Instead, I need this graph:

Graph[{
  Property[1 -> 2, "value" -> {123, 321}],  (* two edges were merged and their property values collected into a list *)
  Property[2 -> 3, "value" -> {42}], 
  Property[3 -> 3, "value" -> {137}]}, 
 VertexLabels -> {1 -> "one", 2 -> "two", 3 -> "three"}]

I am looking for import methods which are:

  • robust
  • not too much hassle
  • using external tools is okay, but I prefer something automatable directly from within Mathematica
POSTED BY: Szabolcs Horvát
Answer
5 months ago

I found a solution and posted it over at StackExchange. A copy is below.


Graphlet (GML)

With the Graphlet format, we can do this:

{edgeRules, edgeAttr, vertexList, vertexAttr, directed} = 
   ImportString[
      file, 
      {"Graphlet", {"EdgeRules", "EdgeAttributes", "VertexList", "VertexAttributes", "DirectedEdges"}}
   ]

(*
{{1 -> 2, 1 -> 2, 2 -> 3, 3 -> 3}, 
 {{"value" -> 123}, {"value" -> 321}, {"value" -> 42}, {"value" -> 137}}, 
 {1, 2, 3}, 
 {{"label" -> "one"}, {"label" -> "two"}, {"label" -> "three"}}, 
 True}
*)

Of these, the "DirectedEdges" element is undocumented.

Now we can do the property combining:

edgeFinal = GroupBy[
    Transpose[{edgeRules, edgeAttr}],
    First -> Last,
    Merge[Identity]
    ] // Map[Normal] // KeyValueMap[Property]
(* {Property[1 -> 2, {"value" -> {123, 321}}], 
 Property[2 -> 3, {"value" -> {42}}], 
 Property[3 -> 3, {"value" -> {137}}]} *)

vertexFinal = MapThread[Property, {vertexList, vertexAttr}]
(* {Property[1, {"label" -> "one"}], 
 Property[2, {"label" -> "two"}], Property[3, {"label" -> "three"}]} *)

Now we can assemble the graph:

g = Graph[vertexFinal, edgeFinal, DirectedEdges -> directed]

Options[g]    
(* {Properties -> {1 \[DirectedEdge] 2 -> {"value" -> {123, 321}}, 
   2 -> {"label" -> "two"}, 1 -> {"label" -> "one"}, 
   3 -> {"label" -> "three"}, 
   3 \[DirectedEdge] 3 -> {"value" -> {137}}, 
   2 \[DirectedEdge] 3 -> {"value" -> {42}}}} *)

GraphML

The same method works with GraphML as well. The difference is that each of these import elements returns a list. This is because a GraphML file may contain more than one graph.

POSTED BY: Szabolcs Horvát
Answer
5 months ago

Group Abstract Group Abstract