3
$\begingroup$

I am trying to find all simple paths in a large directed graph (542 vertex, density ~ 5%) between two nodes. For this purpose, I use the algorithm from this thread. Unfortunately, my computer is running out of memory during this operation. I was thinking it would help to write the paths found directly to a text file, but I don't know how to do it in this case. Maybe, you'll have other suggestions as well. Here's the file with the adjacency matrix.

SetDirectory["C:\\Users\\crazyfrog\\Documents\\ДИПЛОМ"];
findPaths[a_?MatrixQ, s_Integer, t_Integer] := 
  Module[{child, find}, 
   child[v_] := Flatten@Position[a[[v]], Except@0, 1, Heads -> False];
   find[v_, list_] := 
    Scan[If[# === t, Sow[Append[list, #]], 
       If[FreeQ[list, #], find[#, Append[list, #]]]] &, child@v];
   If[# =!= {}, First@#, {}] &@Last@Reap@find[s, {s}]];
findPaths[g_Graph, s_, t_] := 
  Module[{nodes = VertexList@g, convert}, 
   convert = Thread[nodes -> Range@Length@nodes];
   findPaths[Normal@AdjacencyMatrix@g, s /. convert, t /. convert] /. 
    Reverse /@ convert];
<< JLink`;
InstallJava[];
ReinstallJava[JVMArguments -> "-Xmx1024m"]; data = 
 Import["test.xlsx"][[1]]; data2 = Round[data];
g = AdjacencyGraph[data2];
$HistoryLength = 0; findPaths[g, 1, 542] >> "result.txt"
$\endgroup$
6
  • 3
    $\begingroup$ Import's failure to read even modestly large excel files is a well known bug. mathematica.stackexchange.com/questions/42081/… Best bet save your data in some intermediate format such as csv. $\endgroup$
    – george2079
    Mar 1, 2014 at 12:57
  • $\begingroup$ just to check, i'd advise putting your last 4 statements into separate cells so that you can clearly see where the error arises. $\endgroup$
    – george2079
    Mar 1, 2014 at 13:10
  • $\begingroup$ @george2079 Thanks for you idea but excel file is imported sucessfully. The problem occurs when I try to find all paths $\endgroup$ Mar 1, 2014 at 15:07
  • $\begingroup$ break your last statement into seperate cells as as res=findP... amd res>>file and post the exact error message. $\endgroup$
    – george2079
    Mar 1, 2014 at 15:43
  • $\begingroup$ @george2079 did what you said, and after ~3 hours: "No more memory available. Mathematica kernel has shut down. Try quitting other applications and then retry." $\endgroup$ Mar 1, 2014 at 20:34

1 Answer 1

2
$\begingroup$

Here's how to write the results to file as they are found. I can't be sure if this will solve your memory problem as I have not run it for long enough.

The original code uses Sow to collect the results. All that is required is to replace Sow with a Write statement, plus code to open and close the file stream.

I have also made a couple of other minor changes:

  • I converted the XLSX file to CSV (in Excel) so that it can be loaded without mucking about with the Java stack size.
  • I didn't see any point in importing an adjacency matrix, converting it to a graph, and then feeding it into a function which converts it back to an adjacency matrix. So I used just the matrix version of findPaths.
  • I call the recursive find function inside a Block with $RecursionLimit set to infinity, to allow for paths of any length.

.

data = Import["test.csv"];

writePaths[a_?MatrixQ, s_Integer, t_Integer, file_] :=
 Module[{child, find, stream},
  stream = OpenWrite[file];
  child[v_] := Flatten@Position[a[[v]], Except@0, 1, Heads -> False];
  find[v_, list_] := Scan[If[# === t,
      Write[stream, Append[list, #]],
      If[FreeQ[list, #], find[#, Append[list, #]]]] &, child@v];
  Block[{$RecursionLimit = Infinity}, find[s, {s}]];
  Close[stream]]

writePaths[data, 1, 542, "paths.txt"];
$\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.