# Why is FindCycle crashing for this graph?

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$: 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?)

• 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 – Szabolcs Apr 30 '16 at 12:43
• 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. – Andrew Cheong Apr 30 '16 at 12:46
• 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. – Szabolcs Apr 30 '16 at 13:00
• This crashes as well with 10.4.1 on Windows 8.1 for the directed graph. – user31159 Apr 30 '16 at 13:04
• Thanks @Xavier. Gotcha Szabolcs—I reported it (even before Xavier's input). – Andrew Cheong Apr 30 '16 at 13:08

$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] 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 *)  • Still crashes for me. May I ask what OS and Mathematica version you're using? – Andrew Cheong Apr 30 '16 at 13:40 • @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. – Szabolcs Apr 30 '16 at 13:54 • Ah, that wasn't there in the original post. Thanks. – Andrew Cheong Apr 30 '16 at 14:03 • @Szabolcs - thanks for pointing that out. – Bob Hanlon Apr 30 '16 at 14:39 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.