Message Boards Message Boards

GROUPS:

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

Posted 1 year ago
1635 Views
|
1 Reply
|
7 Total Likes
|

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

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.

Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract