Opened 13 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)
Change History (14)
Changed 13 years ago by
| Attachment: | bug_here.cpp added |
|---|
Changed 13 years ago by
| Attachment: | problematic_graph.lgf added |
|---|
comment:1 Changed 13 years ago by
comment:2 Changed 13 years ago by
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
| Attachment: | b224fdba7fd8.patch added |
|---|
comment:4 Changed 11 years ago by
I got confused a bit. Are empty graphs of 0 and 1 vertex bi-node-connected?
comment:5 Changed 11 years ago by
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
| Attachment: | 792b426a35f0.patch added |
|---|
comment:6 follow-ups: 7 9 Changed 11 years ago by
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 Changed 11 years ago by
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
Looking at the code, the current implementation for biEdgeConnected() seems to perfectly follow the definition above.
comment:9 Changed 11 years ago by
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
| Resolution: | → fixed |
|---|---|
| Status: | new → closed |
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.
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.