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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
|
// Copyright ©2012 The bíogo 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 graph
import (
"errors"
"fmt"
)
var alreadyConnected = errors.New("graph: edge already fully connected")
type Edge interface {
ID() int
Weight() float64
Nodes() (u, v Node)
Head() Node
Tail() Node
index() int
setIndex(int)
setID(int)
join(u, v Node)
disconnect()
reconnect(dst, src Node)
}
var _ Edge = (*edge)(nil)
// EdgeFilter is a function type used for assessment of edges during graph traversal.
type EdgeFilter func(Edge) bool
// An edge is an edge in a graph.
type edge struct {
id int
i int
u, v Node
}
// NewEdge returns a new Edge.
func NewEdge() Edge {
return &edge{}
}
// newEdge returns a new edge.
func newEdge(id, i int, u, v Node) Edge {
return &edge{id: id, i: i, u: u, v: v}
}
// ID returns the id of the edge.
func (e *edge) ID() int {
return e.id
}
func (e *edge) setID(id int) {
e.id = id
}
// Index returns the index of the edge in the compact edge list of the graph. The value returned
// cannot be reliably used after an edge deletion.
func (e *edge) index() int {
return e.i
}
func (e *edge) setIndex(i int) {
e.i = i
}
// Nodes returns the two nodes, u and v, that are joined by the edge.
func (e *edge) Nodes() (u, v Node) {
return e.u, e.v
}
// Head returns the first node of an edge's node pair.
func (e *edge) Head() Node {
return e.v
}
// Tail returns the second node of an edge's node pair.
func (e *edge) Tail() Node {
return e.u
}
// Weight returns the weight of the edge. The default weight is 1.
func (e *edge) Weight() float64 {
return 1
}
func (e *edge) reconnect(u, v Node) {
switch u {
case e.u:
e.u = v
case e.v:
e.v = v
}
}
func (e *edge) disconnect() {
e.u.drop(e)
if e.u != e.v {
e.v.drop(e)
e.v = nil
}
e.u = nil
}
func (e *edge) connect(n Node) (err error) {
switch Node(nil) {
case e.u:
e.u = n
e.u.add(e)
case e.v:
e.v = n
e.v.add(e)
default:
err = alreadyConnected
}
return
}
func (e *edge) join(u, v Node) {
e.u, e.v = u, v
}
func (e *edge) String() string {
return fmt.Sprintf("%d--%d", e.u.ID(), e.v.ID())
}
// Edges is a collection of edges used for internal representation of edge lists in a graph.
type Edges []Edge
func (e Edges) delFromGraph(i int) Edges {
e[i], e[len(e)-1] = e[len(e)-1], e[i]
e[i].setIndex(i)
e[len(e)-1].setIndex(-1)
return e[:len(e)-1]
}
func (e Edges) delFromNode(i int) Edges {
e[i], e[len(e)-1] = e[len(e)-1], e[i]
return e[:len(e)-1]
}
|
