COIN-OR::LEMON - Graph Library

Opened 8 years ago

Closed 6 years ago

#439 closed defect (fixed)

Bug in biNodeConnected()

Reported by: Alpar Juttner Owned by: Balazs Dezso
Priority: major Milestone: LEMON 1.3 release
Component: core Version: hg main
Keywords: Cc: kbsandor@…
Revision id:

Description

The attached code and .lgf shows an example where biNodeConnected() gives the wrong answer. It's probably about the handling of isolated nodes.

The bug was reported by Sándor Kisfaludi-Bak.

Attachments (4)

bug_here.cpp (352 bytes) - added by Alpar Juttner 8 years ago.
problematic_graph.lgf (97 bytes) - added by Alpar Juttner 8 years ago.
b224fdba7fd8.patch (3.5 KB) - added by Balazs Dezso 6 years ago.
792b426a35f0.patch (2.2 KB) - added by Balazs Dezso 6 years ago.

Download all attachments as: .zip

Change History (14)

Changed 8 years ago by Alpar Juttner

Attachment: bug_here.cpp added

Changed 8 years ago by Alpar Juttner

Attachment: problematic_graph.lgf added

comment:1 Changed 8 years ago by Balazs Dezso

Currently, the bi-node-connected components are defined as an equivalence relation on the edges in the documentation. Two edges are in the same class, if there is a circle which contains both edges.

By this definition, isolated nodes do not break the bi-node-connectivty property. Unfortunately, it's not intuitive, so we might need to change the definition, and we can require that the graph should be connected.

What is your opinion?

For bi-edge-connected graphs, the equivalence relation is defined on the nodes (two nodes are in relation, when there are two disjoint paths which connect them), so isolated nodes make the graph disconnected.

comment:2 Changed 8 years ago by Alpar Juttner

According to wikipedia (and to my knowledge)

In the mathematical discipline of graph theory, a biconnected graph is a connected graph with no articulation vertices.

To make things a bit more complex it also adds that

The property of being 2-connected is equivalent to biconnectivity, with the caveat that the complete graph of two vertices is sometimes regarded as biconnected but not 2-connected.

Anyway, we should follow the above definition for the output of biNodeConnected().

Changed 6 years ago by Balazs Dezso

Attachment: b224fdba7fd8.patch added

comment:3 Changed 6 years ago by Balazs Dezso

Fix uploaded.

comment:4 Changed 6 years ago by Alpar Juttner

I got confused a bit. Are empty graphs of 0 and 1 vertex bi-node-connected?

comment:5 Changed 6 years ago by Alpar Juttner

The wikipedia definition for bi-node-connected is somewhat ambivalent. Instead, I suggest considering it to be equivalent to 2-node-connected, which has a clear definition:

A graph G=(V,E) is k-node-connected if

  • G has at least k+1 vertices and
  • the result of deleting any (perhaps empty) set of fewer than k vertices is a connected graph.

What about biEdgeConnected()? Does it work properly for small graphs?

Changed 6 years ago by Balazs Dezso

Attachment: 792b426a35f0.patch added

comment:6 Changed 6 years ago by Balazs Dezso

Uploaded a new patch [792b426a35f0], which uses the connected graph with no articulation point definition. In this case, we need to check that there are no isolated nodes in the graph, or there is only one isolated node and there are no other nodes in the graph.

Whether biEdgeConnected() is valid, it just depends on which definition do we follow.

comment:7 in reply to:  6 Changed 6 years ago by Alpar Juttner

Replying to deba:

Whether biEdgeConnected() is valid, it just depends on which definition do we follow.

Hmmm. Very deep observation, indeed... :)

To be more serious, wikipedia says:

Let G = (E,V) be an arbitrary graph. If G' = (E \ X,V) is connected for all X ⊆ E where |X| < k, then G is k-edge-connected.

This looks fine, but. It means that the 1-vertex empty graph is 2 connected, which I'm actually fine with. However, wikipedia also adds that

Minimum vertex degree gives a trivial upper bound on edge-connectivity. That is, if a graph G = (E,V) is k-edge-connected then it is necessary that k ≤ δ(G), where δ(G) is the minimum degree of any vertex v ∈ V

This certainly false for the 1-vertex empty graph.

All in all, I think it is up to us how we define two edge connectivity in this singular case. My proposal is to just follow the definition above, thus 1-vertex empty graph will be 2-edge-connected (in fact, k-edge-connected for any k)

comment:8 Changed 6 years ago by Alpar Juttner

Looking at the code, the current implementation for biEdgeConnected() seems to perfectly follow the definition above.

comment:9 in reply to:  6 Changed 6 years ago by Alpar Juttner

Replying to deba:

Uploaded a new patch [792b426a35f0], which uses the connected graph with no articulation point definition. In this case, we need to check that there are no isolated nodes in the graph, or there is only one isolated node and there are no other nodes in the graph.

But this one does not follow the above definition of 2-vertex-connectedness. However, it is more in line with the definition of 2-edge-connectedness.

comment:10 Changed 6 years ago by Alpar Juttner

Resolution: fixed
Status: newclosed

I rebased the latest patch as [552e3d1242c6] and added some more clarification to the doc ([70b199792735]). They are both merged to branches 1.1, 1.2 and main.

I think we can now close the ticket.

Note: See TracTickets for help on using tickets.