4
$\begingroup$

I'm working with a directed graph, previously mentioned in Exporting a high-resolution GraphPlot of a very large graph (65,536 nodes). It can be generated with the following code:

  Hex[exp_] := FromDigits[exp, 16];
  LByte[exp_] := BitAnd[exp, Hex@"00ff"];
  HByte[exp_] := BitAnd[exp, Hex@"ff00"]~BitShiftRight~8;
  PRNG[v_] := Module[{L5, H5, v1, v2, carry},
    L5 = LByte@v*5;
    H5 = HByte@v*5;
    v1 = LByte@H5 + HByte@L5 + 1;
    carry = HByte@v1~BitGet~0;
    v2 = BitShiftLeft[LByte@v1, 8] + LByte@L5;
    Mod[v2 + Hex@"0011" + carry, Hex@"ffff" + 1]
    ];
  graph = # -> PRNG@# & /@ Range[0, Hex@"ffff"];

I know that there are 3 cycles in this graph. (See aforementioned link for a visualization.) However, running

FindCycle@graph

crashes the my kernel with no message in $Mathematica$:

enter image description here

This occurs even when I set limits on cycle length, e.g. {100, 200}, {100, 4000}, {1000,2000}.

Now, in my other question, I can understand why $Mathematica$ would have issues exporting a GraphPlot I rendered to have over 20 billion pixels. But finding a cycle amongst 65,536 vertices should be no problem at all. Why is $Mathematica$ having trouble with this graph? I'm running version 10.4.1.0.


To make sure I wasn't underestimating the complexity of cycle-finding, I put together my own function:

FindDirectedCycles[graph_] := Module[{limit, assoc, visited, count},
   limit = Length@graph;
   assoc = Association@graph;
   visited = <||>;
   count = 0;
   Scan[
    Module[{v, path, subvisited, subcount},
       v = #;
       path = {};
       subvisited = <||>;
       subcount = 0;
       While[count <= limit,
        If[KeyExistsQ[visited, v],
         Break[];
         ];
        If[KeyExistsQ[subvisited, v],
         path = Drop[path, subvisited[v] - 1];
         Print["Found a ", Length@path, "-cycle:"];
         Print[path];
         Break[];
         ];
        subvisited[v] = ++subcount;
        AppendTo[path, v];
        v = assoc@v;
        ++count;
        ];
       AppendTo[visited, subvisited];
       ]; &
    ,
    graph[[All, 1]]
    ];
   ];

This code found the 3 cycles in less than two seconds. Of course, my version makes the assumption that the graph is directed. But $Mathematica$'s documentation states that FindCycle should work for directed graphs. (Is it possibly because the graph consists of 3 unconnected subgraphs?)

$\endgroup$
  • $\begingroup$ Doesn't crash with v10.4.1 on OS X. Anyway, if you see a crash, that's a bug. If you can reproduce it, report to to support: wolfram.com/support $\endgroup$ – Szabolcs Apr 30 '16 at 12:43
  • $\begingroup$ I see, thanks. Can someone with Windows 7 try reproducing this issue please? Just copy and paste the code at the very top, then run FindCycle@graph. I'm running 64-bit. $\endgroup$ – Andrew Cheong Apr 30 '16 at 12:46
  • $\begingroup$ I think you should report it to Wolfram even if not everyone can reproduce the crash. Memory corruption bugs don't always result in a crash, but that does not mean that the bug is not there. $\endgroup$ – Szabolcs Apr 30 '16 at 13:00
  • $\begingroup$ This crashes as well with 10.4.1 on Windows 8.1 for the directed graph. $\endgroup$ – user31159 Apr 30 '16 at 13:04
  • $\begingroup$ Thanks @Xavier. Gotcha Szabolcs—I reported it (even before Xavier's input). $\endgroup$ – Andrew Cheong Apr 30 '16 at 13:08
2
$\begingroup$
$Version

(*  "10.4.1 for Mac OS X x86 (64-bit) (April 11, 2016)"  *)

Hex[exp_] := FromDigits[exp, 16];
LByte[exp_] := BitAnd[exp, Hex@"00ff"];
HByte[exp_] := BitAnd[exp, Hex@"ff00"]~BitShiftRight~8;
PRNG[v_] := Module[{L5, H5, v1, v2, carry}, L5 = LByte@v*5;
   H5 = HByte@v*5;
   v1 = LByte@H5 + HByte@L5 + 1;
   carry = HByte@v1~BitGet~0;
   v2 = BitShiftLeft[LByte@v1, 8] + LByte@L5;
   Mod[v2 + Hex@"0011" + carry, Hex@"ffff" + 1]];
graph = # -> PRNG@# & /@ Range[0, Hex@"ffff"];

Your graph is not a Graph. Use Graph

GraphQ[graph]

(*  False  *)

gr = Graph[graph]

enter image description here

To find all cycles

Length[FindCycle[gr, Infinity, All]] // AbsoluteTiming

(*  {0.513043, 3}  *)

Which confirms that there are three cycles.

EDIT: Supporting Szabolcs comment below that "Since M10.3, most (all?) Graph-processing functions accept a rule list as an alternative graph specification."

And @@ (SameQ @@ (# /@ {gr, graph}) & /@
   {EdgeRules, EdgeList, VertexList,
    AdjacencyMatrix, IncidenceMatrix,
    KirchhoffMatrix, WeightedAdjacencyMatrix,
    FindCycle[#, Infinity, All] &})

(*  True  *)
|improve this answer|||||
$\endgroup$
  • $\begingroup$ Still crashes for me. May I ask what OS and Mathematica version you're using? $\endgroup$ – Andrew Cheong Apr 30 '16 at 13:40
  • 1
    $\begingroup$ @Andrew M10.4.1 for OS X, it's at the top. @Bob: Since M10.3, most (all?) Graph-processing functions accept a rule list as an alternative graph specification. $\endgroup$ – Szabolcs Apr 30 '16 at 13:54
  • 1
    $\begingroup$ Ah, that wasn't there in the original post. Thanks. $\endgroup$ – Andrew Cheong Apr 30 '16 at 14:03
  • $\begingroup$ @Szabolcs - thanks for pointing that out. $\endgroup$ – Bob Hanlon Apr 30 '16 at 14:39
1
$\begingroup$

Oddly, technical support at $Mathematica$ was unable to reproduce the issue, though @Xavier and I were both able. They asked me to try a clean start, but the crash still occurred. I've sent my SystemInformation[], and this issue is being tracked under CASE:3588559. The technician's last comments:

I have filed a report with our developers which includes your SystemInformation so that they can look into this further. I had tested with the FindCycle since I picked that up from the StackExchange thread. Our developers may be able to do something in a future version of Mathematica if they are able to reproduce the problem.

If anyone else encounters this crash, please feel free to leave a comment with your OS and exact $Mathematica$ version; their developers have been forwarded a link to this thread.

|improve this answer|||||
$\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.