Why is `FindCycle` crashing for this graph?

Question

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

Answer 1

$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  *)

Answer 2

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.