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$
  • $\begingroup$ @Öskå I don't think that's quite true (see my answer for a starter). $\endgroup$ – Juho Jun 26 '14 at 11:03
  • $\begingroup$ ... except if you rewrite the format manually.. :) But by using Export it's not possible :) $\endgroup$ – Öskå Jun 26 '14 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 '14 at 11:06
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$
  • $\begingroup$ @mrm yes, when I tested, it's faster. $\endgroup$ – halmir Jun 30 '14 at 13:47
  • $\begingroup$ @halmir OK ... removed comments. Though I wouldn't mind talking about it in chat ;-) $\endgroup$ – Szabolcs Jun 30 '14 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$
  • $\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$ – WalkingRandomly Jun 26 '14 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$ – WalkingRandomly Jun 26 '14 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 '14 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$ – WalkingRandomly Jun 26 '14 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 '14 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, privacy policy and cookie policy

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