Macaulay2 / Macaulay2/M2

Bug in spanningForest(Graph)

Open
#2,403 1 comment 0 reactions 0 assignees View on GitHub
package issue
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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.