Bug in spanningForest(Graph)
- Dominant language
- Macaulay2
- Stars
- 435
- Forks
- 297
- Avg merge
- 4d 20h
- Merged PRs (30d)
- 11
Description
It seems that the output of `spanningForest` is occasionally incorrect:
```
needsPackage "Graphs"
G = graph(toList(0..8), {{0,2},{0,4},{0,5},{0,7},{0,8},{1,2},{1,4},{1,5},{1,6},{1,7},{1,8},{3,4},{3,5},{3,6},{3,7},{3,8}})
T = spanningForest G
assert isConnected G
assert isConnected T
```
The last assert is false, which should not be the case for a connected graph.
In the meantime, here is a quick implementation of [Kruskal's algorithm](https://en.wikipedia.org/wiki/Kruskal%27s_algorithm) for finding a spanning forest:
```
kruskalSpanningForest = method()
kruskalSpanningForest Graph := List => G -> (
comps := new MutableList from (vertices G/(v -> set{v}));
k := #connectedComponents G;
graph(vertices G, for e in sort edges G list (
if #comps == k then break;
ic := select(2, comps, c -> #(c*e) > 0);
if #ic == 1 then continue;
comps = append(delete(ic#0, delete(ic#1, comps)), ic#0 + ic#1);
e
))
)
```
which gives a correct output for the graph above, and seems to be of comparable runtime.
Contributor guide
No contributing guide indexed for this repository
Research direction
Start with the spanningForest(Graph) entry point in the Graphs package and reproduce the provided graph example, checking why the returned forest is disconnected. Compare its behavior with the supplied Kruskal implementation; done means the example's connected-graph assertion passes and regression coverage is added for this case.
Written by the indexing model from the issue text.
Assessment
- Domain
- data
- Issue type
- Bug
- Difficulty
- 3/5
- Estimated time
- 1-2 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 45/100