Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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"
share|improve this question
3  
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. –  george2079 Mar 1 at 12:57
    
just to check, i'd advise putting your last 4 statements into separate cells so that you can clearly see where the error arises. –  george2079 Mar 1 at 13:10
    
@george2079 Thanks for you idea but excel file is imported sucessfully. The problem occurs when I try to find all paths –  Evgenii Nikitin Mar 1 at 15:07
    
break your last statement into seperate cells as as res=findP... amd res>>file and post the exact error message. –  george2079 Mar 1 at 15:43
    
@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." –  Evgenii Nikitin Mar 1 at 20:34

1 Answer 1

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"];
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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