# A unexpected behavior in RelationGraph

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?

• Regex tip: don't escape - and > to make your regex more readable. ;) – Martin Ender Apr 5 '16 at 11:10
• Interestingly, the problem seems to occur when both 1664 and 1665 are used in a list of at least 78 elements. – Martin Ender Apr 5 '16 at 11:16
• @MartinBüttner Thanks for your tip.And do you think this is a bug? – yode Apr 5 '16 at 12:47
• @Xavier Have you see this? – yode Oct 1 '16 at 19:32

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.

• Thanks for you point out that. – yode Apr 5 '16 at 13:45

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.