COIN-OR::LEMON - Graph Library

Opened 12 years ago

Closed 11 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 12 years ago.
problematic_graph.lgf (97 bytes) - added by Alpar Juttner 12 years ago.
b224fdba7fd8.patch (3.5 KB) - added by Balazs Dezso 11 years ago.
792b426a35f0.patch (2.2 KB) - added by Balazs Dezso 11 years ago.

Download all attachments as: .zip

Change History (14)

Changed 12 years ago by Alpar Juttner

Attachment: bug_here.cpp added

Changed 12 years ago by Alpar Juttner

Attachment: problematic_graph.lgf added

comment:1 Changed 12 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 12 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 11 years ago by Balazs Dezso

Attachment: b224fdba7fd8.patch added

comment:3 Changed 11 years ago by Balazs Dezso

Fix uploaded.

comment:4 Changed 11 years ago by Alpar Juttner

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

comment:5 Changed 11 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 11 years ago by Balazs Dezso

Attachment: 792b426a35f0.patch added

comment:6 Changed 11 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 11 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 11 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 11 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 11 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.