こんにちは。
gonum/graph を利用し、グラフの連結成分(=サブグラフ)内のエッジを列挙してみました。グラフは undirected multigraph で、エッジは複数の lines を持ちます。
DepthFirst.EdgeFilter()
へ edgeFunc()
を渡し、サブグラフ単位で全ての lineID
を列挙させています。
$ go run walkFrom.go
input undirected lines: [[0 1] [1 2] [2 3] [3 0] [0 2] [1 3] [1 0] [4 4] [4 4]]
total 9 lines
lineID ! edge
----------------
2 0 [2 3]
1 1 [1 2]
5 2 [1 3]
0 3 [0 1]
6 3 [0 1]
3 4 [0 3]
4 5 [0 2]
----------------
8 6 [4 4]
7 6 [4 4]
----------------
walkFrom.go
package main
import (
"fmt"
"gonum.org/v1/gonum/graph"
"gonum.org/v1/gonum/graph/multi"
"gonum.org/v1/gonum/graph/traverse"
)
var iEdge int
func printLine(lID, mID, nID int64, iEdge int) {
fmt.Printf("%d %d [%d %d]\n", lID, iEdge, mID, nID)
}
func printHeader() {
iEdge = 0
fmt.Printf("\nlineID ! edge\n")
printSeparator()
}
func printSeparator() {
fmt.Print("----------------\n")
}
func printLines(e graph.Edge) {
mID, nID := e.From().ID(), e.To().ID()
if mID > nID {mID, nID = nID, mID}
l := e.(graph.Lines)
for l.Next() {
printLine(l.Line().ID(), mID, nID, iEdge)
}
iEdge++
}
func makeWalker(edgeFunc func (graph.Edge)) (walker traverse.DepthFirst) {
walker.EdgeFilter = func(e graph.Edge) bool {
if e.From().ID() <= e.To().ID() {
edgeFunc(e)
}
return true
}
return walker
}
func walk(g *multi.UndirectedGraph, walker *traverse.DepthFirst, from graph.Node) {
if !walker.Visited(from) && g.From(from.ID()).Next() { // neither visited nor isolated node
walker.Walk(g, from, nil)
printSeparator()
}
}
func walkAll(g *multi.UndirectedGraph) {
printHeader()
nod := g.Nodes()
w := makeWalker(printLines)
for nod.Next() {
walk(g, &w, nod.Node())
}
}
func makeGraph() *multi.UndirectedGraph {
IDMAX := 9
inputLines := [][]int64{{0, 1}, {1, 2}, {2, 3}, {3, 0}, {0, 2}, {1, 3}, {1, 0}, {4, 4}, {4, 4}}
g := multi.NewUndirectedGraph()
for i := 0; i <= IDMAX; i++ {
g.AddNode(multi.Node(int64(i)))
}
fmt.Print("input undirected lines: [")
for i, e := range inputLines {
g.SetLine(g.NewLine(g.Node(e[0]), g.Node(e[1])))
fmt.Print(e)
if i < len(inputLines)-1 {fmt.Print(" ")}
}
fmt.Printf("]\ntotal %d lines\n", len(inputLines))
return g
}
func main() {
g:= makeGraph()
walkAll(g)
}