A unexpected behavior in RelationGraph

Question

Bug introduced in 10.2 and fixed in 11.0.1

---

Firstly we get these idiom

web = Import["http://chengyu.t086.com/jielong/zuichang.html"];
idiom = StringCases[web, 
   RegularExpression[
    "(?<=\\s\\-\\>\\s)[一-龥]{4}|[一-龥]{4}(?=\\s\\-\\>\\s)"]];

Then he use the RelationGraph to draw graph.

g = RelationGraph[StringTake[#1, -1] == StringTake[#2, 1] &, 
  idiom[[;; 1664]]]

We can get

Actually the idiom have more element.

idiom // Length

1792

But If I want to get more long graph upto 1665

g = RelationGraph[StringTake[#1, -1] == StringTake[#2, 1] &, 
      idiom[[;; 1665]]]

We'll get a unexpected graph or a error information,But I cannot find any bad stuff surround 1655

Take[idiom, {1663, 1667}]

{依依不舍,舍己为人,轻而易举,举一反三,三生有幸}

Is it a bug of RelationGraph or have I missed something?

Answer 1

There is a duplicated vertex causing this issue:

idiom[[;; 1665]] // Length

1665

idiom[[;; 1665]] // Union // Length

1664

As a workaround, you could take Union over the vertex set:

g = RelationGraph[StringTake[#1, -1] == StringTake[#2, 1] &, 
   Union@idiom[[;; 1665]]];

GraphQ[g]

True

but the output shouldn't be that.

You should report this to Wolfram support.

Answer 2

I'd go ahead and call it a bug, but I don't know what is causing it (sadly, I'm not a kernel developer). I can verify it's a bug below and I can offer a workaround to create the desired graph easily.

Here is a function that should create a RelationGraph but without the vertex labels, although I think that could be added easily enough,

bootstrapRelationGraph[func_, list_] := 
  Select[Tuples[Range@Length@list, 2], 
    func[list[[First@#]], list[[Last@#]]] &] // 
     (Graph[Flatten[{#1 -> #2} & @@@ #]] &);

We can test that it makes a graph equivalent to that from RelationGraph,

graph1 = bootstrapRelationGraph[
  StringTake[#1, -1] === StringTake[#2, 1] &, idiom[[37 ;; 125]]]
graph2 = RelationGraph[StringTake[#1, -1] === StringTake[#2, 1] &, 
  idiom[[37 ;; 125]]]
IsomorphicGraphQ[graph1, graph2]

Now the smallest sublist I found that reproduces the error is {1664, 1665, 1584, 1585, 1586, 1587, 1588, 1589, 1590, 1591}, as seen below the bootstrapped version does not give the erroneous results.

graph1 = bootstrapRelationGraph[
  StringTake[#1, -1] === StringTake[#2, 1] &, 
  idiom[[{1664, 1665, 1584, 1585, 1586, 1587, 1588, 1589, 1590, 
     1591}]]];
graph2 = RelationGraph[StringTake[#1, -1] === StringTake[#2, 1] &, 
  idiom[[{1664, 1665, 1584, 1585, 1586, 1587, 1588, 1589, 1590, 
     1591}]]];
{graph1, graph2}
IsomorphicGraphQ[graph1, graph2]

As far as I can tell, that signals that there is some kind of bug in RelationGraph. You can get the full graph easily enough by

bootstrapRelationGraph[
 StringTake[#1, -1] === StringTake[#2, 1] &, idiom]

Edit

The simplest example I can find that reproduces this bug is

{RelationGraph[Last@#1 == First@#2 &, 
  Join[{{1, 2}, {3, 4}}, Partition[Range[4, 12], 2, 1]]],
 RelationGraph[Last@#1 == First@#2 &, 
  Join[{{1, 2}, {3, 4}}, Partition[Range[3, 11], 2, 1]]]}

So the bug has nothing to do with the Chinese character set and nothing to do with String functions.