2
$\begingroup$

I'm creating random graphs with suitable properties and exporting them in the DIMACS format. Already, for rather small graphs with, say, ~60k vertices and ~240k edges, Export takes several minutes on a high-end machine. My hope is to export much larger graphs in a reasonable time. Here's how I'm doing it now,

g = RandomGraph[DegreeGraphDistribution[Table[8, {60000}]]];
Export["graph.col", g]

The output file is a plaintext file with roughly $e$ lines, where $e$ is the number of edges in the graph. Why does Export run so slow? Is there a way I can speed Export up, or is there another way to do this faster? I can't imagine what makes Mathematica so slow at extracting the edgelist of the graph and writing it to a file.

$\endgroup$
3
  • $\begingroup$ @Öskå I don't think that's quite true (see my answer for a starter). $\endgroup$
    – Juho
    Jun 26, 2014 at 11:03
  • $\begingroup$ ... except if you rewrite the format manually.. :) But by using Export it's not possible :) $\endgroup$
    – Öskå
    Jun 26, 2014 at 11:05
  • $\begingroup$ @Öskå Right, but what's the difference really between "exporting" and "writing the format manually"? Isn't this what Export should be doing in the first place? What on earth does it do to spend so much time? :-) $\endgroup$
    – Juho
    Jun 26, 2014 at 11:06

3 Answers 3

1
$\begingroup$

You could extract adjacency matrix and export it.

g = RandomGraph[DegreeGraphDistribution[Table[8, {10000}]]];

Export["g.col", AdjacencyMatrix[g]]

It will ignore vertex names, but it's not supported in DIMAC any way.

$\endgroup$
2
  • $\begingroup$ @mrm yes, when I tested, it's faster. $\endgroup$
    – halmir
    Jun 30, 2014 at 13:47
  • $\begingroup$ @halmir OK ... removed comments. Though I wouldn't mind talking about it in chat ;-) $\endgroup$
    – Szabolcs
    Jun 30, 2014 at 19:27
3
$\begingroup$

I have no idea why Export is slow.

The graph

g = RandomGraph[DegreeGraphDistribution[Table[8, {10000}]]];

has 10k vertices, and 40k edges. On my machine,

Timing[Export["g.col", g]]

requires 10.822373 seconds. I wrote a very quick & naive function for writing the same graph to a file:

WriteGraph[g_, filename_] :=
 Module[{},
  L = EdgeList[g];
  file = OpenWrite[filename];
  WriteString[file, 
   "p edge " <> ToString[VertexCount[g]] <> " " <> 
    ToString[EdgeCount[g]] <> "\n"];

  For[i = 1, i <= EdgeCount[g], ++i,
   first = L[[i]][[1]];
   second = L[[i]][[2]];
   str = "e "  <> ToString[first] <> " " <> ToString[second];
   WriteString[file, str];
   WriteString[file, "\n"];
   ];

  Close[file];
]

On the same graph, WriteGraph only takes 0.391953 seconds.

$\endgroup$
5
  • $\begingroup$ Beat me to it :) I was planning to do the same thing. I did, however, discover a difference that might explain why Export is slower. Consider g = Graph[{1 -> 2, 3 -> 1, 1 -> 4, 2 -> 3, 4 -> 2, 3 -> 4}]; WriteGraph gives different results from Export. $\endgroup$ Jun 26, 2014 at 11:10
  • $\begingroup$ In particular, Export flips some of the edges. For example, in the above, WriteGraph gives e 3 1 whereas Export gives e 1 3. I think that whatever Mathematica is doing here is the reason for the slow down in Export. $\endgroup$ Jun 26, 2014 at 11:13
  • $\begingroup$ @WalkingRandomly Interesting. I don't see why this is something it should do (AFAIK, the DIMACS format does not specify the order of the endpoints of an edge). Even if Export is sorting the edgelist, it shouldn't spend that much time on it (well, this is just my feeling :-)) $\endgroup$
    – Juho
    Jun 26, 2014 at 11:15
  • $\begingroup$ I don't know enough about the DIMACS format. When I was planning to write my own WriteGraph, I was going to present the answer along with the above observation and ask you if the ordering mattered :) $\endgroup$ Jun 26, 2014 at 11:17
  • $\begingroup$ @WalkingRandomly BTW, if you (or anyone for that matter) have any suggestions for further speeding up WriteGraph, feel free to edit or add a better answer. I'm sure there will be someone else coming after me finding this useful! $\endgroup$
    – Juho
    Jun 26, 2014 at 14:17
1
$\begingroup$

I had a similar problem and was happy to find this post.

But I needed to include the weights of the edges, as well as the source s and the sink t The source would be the first nodes and the sink the last. So, I expanded the formula in https://mathematica.stackexchange.com/a/51592/47448, by https://mathematica.stackexchange.com/users/1152/juho to include the weights of the Graph:

WriteGraphWeighted[g_, filename_] := 
 Module[{},
  L = EdgeList[g]; 
  weight =  Normal[WeightedAdjacencyMatrix[g]];
  file = OpenWrite[filename];
  WriteString[file, 
   "c\np max " <> ToString[VertexCount[g]] <> " " <> 
   ToString[EdgeCount[g]] <> "\n"];

   WriteString[file, "n 1 s\n"];
   WriteString[file, "n " <> ToString[VertexCount[g]] <> " t\n"];

  For[i = 1, i <= EdgeCount[g], ++i, 
   first = L[[i]][[1]];
   second = L[[i]][[2]]; 
   third =  weight[[first, second]];
   str = "a " <> ToString[first] <> " " <> ToString[second] <> " " <> 
    ToString[third];
   WriteString[file, str];
   WriteString[file, "\n"];];

  Close[file];
 ]

This might be useful for anyone looking at the DIMACS format, as used by the Max-flow problem instances in vision by the Computer Vision Research Group at the University of Western Ontario.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.