/
topo.go
110 lines (98 loc) · 2.62 KB
/
topo.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
// Copyright ©2014 The Gonum Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
package topo
import (
"gonum.org/v1/gonum/graph"
"gonum.org/v1/gonum/graph/internal/ordered"
"gonum.org/v1/gonum/graph/traverse"
)
// IsPathIn returns whether path is a path in g.
//
// As special cases, IsPathIn returns true for a zero length path or for
// a path of length 1 when the node in path exists in the graph.
func IsPathIn(g graph.Graph, path []graph.Node) bool {
switch len(path) {
case 0:
return true
case 1:
return g.Node(path[0].ID()) != nil
default:
var canReach func(uid, vid int64) bool
switch g := g.(type) {
case graph.Directed:
canReach = g.HasEdgeFromTo
default:
canReach = g.HasEdgeBetween
}
for i, u := range path[:len(path)-1] {
if !canReach(u.ID(), path[i+1].ID()) {
return false
}
}
return true
}
}
// PathExistsIn returns whether there is a path in g starting at 'from' extending
// to 'to'.
//
// PathExistsIn exists as a helper function. If many tests for path existence
// are being performed, other approaches will be more efficient.
func PathExistsIn(g graph.Graph, from, to graph.Node) bool {
var t traverse.BreadthFirst
return t.Walk(g, from, func(n graph.Node, _ int) bool { return n.ID() == to.ID() }) != nil
}
// ConnectedComponents returns the connected components of the undirected graph g.
func ConnectedComponents(g graph.Undirected) [][]graph.Node {
var (
w traverse.DepthFirst
c []graph.Node
cc [][]graph.Node
)
during := func(n graph.Node) {
c = append(c, n)
}
after := func() {
cc = append(cc, []graph.Node(nil))
cc[len(cc)-1] = append(cc[len(cc)-1], c...)
c = c[:0]
}
w.WalkAll(g, nil, after, during)
return cc
}
// Equal returns whether two graphs are topologically equal. To be
// considered topologically equal, a and b must have identical sets
// of nodes and be identically traversable.
func Equal(a, b graph.Graph) bool {
aNodes := a.Nodes()
bNodes := b.Nodes()
if aNodes.Len() != bNodes.Len() {
return false
}
aNodeSlice := graph.NodesOf(aNodes)
bNodeSlice := graph.NodesOf(bNodes)
ordered.ByID(aNodeSlice)
ordered.ByID(bNodeSlice)
for i, aU := range aNodeSlice {
id := aU.ID()
if id != bNodeSlice[i].ID() {
return false
}
toA := a.From(id)
toB := b.From(id)
if toA.Len() != toB.Len() {
return false
}
aAdjacent := graph.NodesOf(toA)
bAdjacent := graph.NodesOf(toB)
ordered.ByID(aAdjacent)
ordered.ByID(bAdjacent)
for i, aV := range aAdjacent {
id := aV.ID()
if id != bAdjacent[i].ID() {
return false
}
}
}
return true
}