graph/topo: address review comments
MODIFY
graph/topo/paton_cycles.go
graph/topo/paton_cycles.go
@@ -10,10 +10,8 @@ import (
"gonum.org/v1/gonum/graph/internal/set"
)
-// UndirectedCyclesIn returns the set of cycle bases in the graph g.
-// All cycles in g can be constructed from the returned cycle bases
-// by combining cycle bases such that presence of edges shared by the
-// bases are xored together.
+// UndirectedCyclesIn returns a set of cycles that forms a cycle basis in the graph g.
+// Any cycle in g can be constructed as a symmetric difference of its elements.
func UndirectedCyclesIn(g graph.Undirected) [][]graph.Node {
// From "An algorithm for finding a fundamental set of cycles of a graph"
// https://doi.org/10.1145/363219.363232
@@ -41,10 +39,7 @@ func UndirectedCyclesIn(g graph.Undirected) [][]graph.Node {
vid := v.ID()
switch {
case uid == vid:
- panic("topo: found self loop")
- // TODO(kortschak): When multigraphs are supported
- // this becomes:
- // cycles = append(cycles, []graph.Node{u})
+ cycles = append(cycles, []graph.Node{u})
case !from.has(vid):
done.Add(vid)
to[vid] = u

MODIFY
graph/topo/paton_cycles_test.go
graph/topo/paton_cycles_test.go
@@ -31,6 +31,9 @@ var undirectedCyclesInTests = []struct {
7: nil,
8: nil,
9: nil,
+ 10: linksTo(11, 12),
+ 11: linksTo(12),
+ 12: nil,
},
want: [][][]int64{
{
@@ -39,6 +42,7 @@ var undirectedCyclesInTests = []struct {
{1, 2, 9, 1},
{1, 4, 8, 5, 1},
{2, 4, 8, 5, 7, 2},
+ {10, 11, 12, 10},
},
{
{0, 1, 2, 0},
@@ -46,6 +50,7 @@ var undirectedCyclesInTests = []struct {
{1, 2, 7, 5, 1},
{1, 2, 9, 1},
{1, 4, 8, 5, 1},
+ {10, 11, 12, 10},
},
{
{0, 1, 2, 0},
@@ -53,6 +58,7 @@ var undirectedCyclesInTests = []struct {
{1, 2, 9, 1},
{1, 4, 8, 5, 1},
{2, 4, 8, 5, 7, 2},
+ {10, 11, 12, 10},
},
{
{0, 1, 2, 0},
@@ -60,6 +66,7 @@ var undirectedCyclesInTests = []struct {
{1, 2, 7, 5, 1},
{1, 2, 9, 1},
{2, 4, 8, 5, 7, 2},
+ {10, 11, 12, 10},
},
},
},
@@ -106,6 +113,12 @@ func TestUndirectedCyclesIn(t *testing.T) {
}
}
+// canonicalise returns the cycle path c cyclicly permuted such that
+// the first element has the lowest ID and then conditionally
+// reversed so that the second element has the lowest possible
+// neighbouring ID.
+// c lists each node only onces - the final node must not be a
+// reiteration of the first node.
func canonicalise(c []graph.Node) []graph.Node {
if len(c) < 2 {
return c

graph/topo: address review comments