8
$\begingroup$

Bug introduced in 10.0 or earlier and fixed in 12.0.


I am working with Mma 11.2 for win 7. I am confusing about the results returned by ConnectedGraphQ described as follows:

Mma believe that Graph[{1}, {}] and Graph[{1, 1}, {}] are the same:

Graph[{1}, {}] === Graph[{1, 1}, {}]

True

However, different results are yeilded:

ConnectedGraphQ[Graph[{1}, {}]]

True

ConnectedGraphQ[Graph[{1, 1}, {}]]

False

Tracing back, one can find:

ConnectedGraphQ[Graph[{1}, {}]] // Trace // InputForm

{{HoldForm[Graph[{1}, {}]], HoldForm[Graph[{1}, {}]]}, HoldForm[ConnectedGraphQ[Graph[{1}, {}]]], HoldForm[True]}

ConnectedGraphQ[Graph[{1, 1}, {}]] // Trace // InputForm

{{HoldForm[Graph[{1, 1}, {}]], HoldForm[Graph[{1}, {}]]}, HoldForm[ConnectedGraphQ[Graph[{1}, {}]]], HoldForm[False]}

What's wrong?

$\endgroup$
1
  • 2
    $\begingroup$ Related. I think it's basically a bug related to the internal representation of Graph objects. $\endgroup$
    – Kiro
    Oct 17, 2017 at 6:41

2 Answers 2

4
$\begingroup$

I think you've stumbled upon a side-effect of Graph objects being "stateful". They're legit objects, which we can get a glimpse of in their atomiticity:

g1 = Graph[{1}, {}];
g2 = Graph[{1, 1}, {}];
g3 = FirstCase[ToExpression@ToBoxes@g1, _Graph, None, \[Infinity]];
g4 = FirstCase[ToExpression@ToBoxes@g2, _Graph, None, \[Infinity]];
g1 === g2 === g3 === g4

True

Quiet[Check[g2[[1]], $Failed, Part::partd]]

$Failed

And of course there's the fact that the reported expression structure doesn't actually correspond to the internal structure.

Here's a cool rundown of all these Qs on these different Graph objects:

gfuncs =
  {GraphQ, PathGraphQ, TreeGraphQ, MixedGraphQ, PlanarGraphQ, 
   SimpleGraphQ, AcyclicGraphQ, CompleteGraphQ, DirectedGraphQ, 
   EulerianGraphQ, LoopFreeGraphQ, WeightedGraphQ, ConnectedGraphQ, 
   IsomorphicGraphQ, UndirectedGraphQ, HamiltonianGraphQ, 
   WeaklyConnectedGraphQ};
Prepend[Through[gfuncs[#]] & /@ {g1, g2, g3, g4}, gfuncs] // 
  Transpose // NewlineateInput

{
 {GraphQ, True, True, True, True},
 {PathGraphQ, True, True, True, True},
 {TreeGraphQ, True, True, True, True},
 {MixedGraphQ, False, False, False, False},
 {PlanarGraphQ, True, True, True, True},
 {SimpleGraphQ, True, True, True, True},
 {AcyclicGraphQ, True, True, True, True},
 {CompleteGraphQ, True, True, True, True},
 {DirectedGraphQ, True, True, True, True},
 {EulerianGraphQ, True, True, True, True},
 {LoopFreeGraphQ, True, True, True, True},
 {WeightedGraphQ, False, False, False, False},
 {ConnectedGraphQ, True, False, True, False},
 {IsomorphicGraphQ, True, True, True, True},
 {UndirectedGraphQ, True, True, True, True},
 {HamiltonianGraphQ, True, True, True, True},
 {WeaklyConnectedGraphQ, True, True, True, True}
 }

We can see that, for whatever reason, only ConnectedGraphQ shows this behavior.

The fact that g4 has the same behavior as g1 is very odd. It might have to do with the memory sharing of that core Expression object, but that's just errant speculation

$\endgroup$
2
  • $\begingroup$ Note the last two steps, I'm very confused what is result to this bug.. $\endgroup$
    – yode
    Oct 17, 2017 at 7:01
  • $\begingroup$ @yode Yeah this is clearly an example of the internal structure not mapping perfectly to the top-level expression. It honestly shows how well tested most of Mathematica is that we see issues like this so infrequently. I'm sure there are lots of places where such things could show up, but they don't. $\endgroup$
    – b3m2a1
    Oct 17, 2017 at 7:03
4
$\begingroup$

These sorts of bugs can often be worked around by cycling the graph through its compound expression representation, like here.

badGraph = Graph[{1, 1}, {}];

ConnectedGraphQ[badGraph]
(* False *)

ConnectedGraphQ@Uncompress@Compress[badGraph]
(* True *)

Graph is atomic and its actual internal representation is not the same what you see when you apply InputForm to it. This is why two seemingly identical graphs can behave differently. As I understand, all atomic expressions also have a compound representation, which is used in some contexts. Converting to this and back forces re-creating the internal representation, which will often fix problems like this.

I am aware of several similar Graph-bugs related to a broken internal representation. Sometimes the breakage is such that it is reflected in the input form, like here, and sometimes it isn't, as in your case. Cycling the graph fixes it only in the latter case.


The simplest practical fix to this problem is defining your own function:

connectedGraphQ[g_?GraphQ /; VertexCount[g] == 1] := True
connectedGraphQ[g_] := ConnectedGraphQ[g]

IGConnectedQ from IGraph/M also works, but I would not recommend it in this specific case as it will be much slower than ConnectedGraphQ on tiny graphs due to the conversion overhead.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.