graph/multi: clean up missed changes and bugs
MODIFY
graph/multi/directed.go
graph/multi/directed.go
@@ -181,15 +181,22 @@ func (g *DirectedGraph) Nodes() graph.Nodes {
// Edges returns all the edges in the graph. Each edge in the returned slice
// is a multi.Edge.
func (g *DirectedGraph) Edges() graph.Edges {
+ if len(g.nodes) == 0 {
+ return nil
+ }
var edges []graph.Edge
for _, u := range g.nodes {
for _, e := range g.from[u.ID()] {
- var lines Edge
+ var lines []graph.Line
for _, l := range e {
lines = append(lines, l)
}
if len(lines) != 0 {
- edges = append(edges, lines)
+ edges = append(edges, Edge{
+ F: g.Node(u.ID()),
+ T: g.Node(lines[0].To().ID()),
+ Lines: iterator.NewOrderedLines(lines),
+ })
}
}
}
@@ -240,11 +247,11 @@ func (g *DirectedGraph) HasEdgeBetween(xid, yid int64) bool {
// The node v must be directly reachable from u as defined by the From method.
// The returned graph.Edge is a multi.Edge if an edge exists.
func (g *DirectedGraph) Edge(uid, vid int64) graph.Edge {
- lines := graph.LinesOf(g.Lines(uid, vid))
- if len(lines) == 0 {
+ l := g.Lines(uid, vid)
+ if l == nil {
return nil
}
- return Edge(lines)
+ return Edge{F: g.Node(uid), T: g.Node(vid), Lines: l}
}
// Lines returns the lines from u to v if such any such lines exists and nil otherwise.

MODIFY
graph/multi/multi.go
graph/multi/multi.go
@@ -18,23 +18,17 @@ func (n Node) ID() int64 {
}
// Edge is a collection of multigraph edges sharing end points.
-type Edge []graph.Line
+type Edge struct {
+ F, T graph.Node
-// From returns the from-node of the edge.
-func (e Edge) From() graph.Node {
- if len(e) == 0 {
- return nil
- }
- return e[0].From()
+ graph.Lines
}
+// From returns the from-node of the edge.
+func (e Edge) From() graph.Node { return e.F }
+
// To returns the to-node of the edge.
-func (e Edge) To() graph.Node {
- if len(e) == 0 {
- return nil
- }
- return e[0].To()
-}
+func (e Edge) To() graph.Node { return e.T }
// Line is a multigraph edge.
type Line struct {
@@ -54,41 +48,45 @@ func (l Line) ID() int64 { return l.UID }
// WeightedEdge is a collection of weighted multigraph edges sharing end points.
type WeightedEdge struct {
- Lines []graph.WeightedLine
+ F, T graph.Node
+
+ graph.WeightedLines
// WeightFunc calculates the aggregate
// weight of the lines in Lines. If
// WeightFunc is nil, the sum of weights
// is used as the edge weight.
- WeightFunc func([]graph.WeightedLine) float64
+ // The graph.WeightedLines can be expected
+ // to be positioned at the first line of
+ // the iterator on entry and must be
+ // Reset before exit.
+ // WeightFunc must accept a nil input.
+ WeightFunc func(graph.WeightedLines) float64
}
// From returns the from-node of the edge.
-func (e WeightedEdge) From() graph.Node {
- if len(e.Lines) == 0 {
- return nil
- }
- return e.Lines[0].From()
-}
+func (e WeightedEdge) From() graph.Node { return e.F }
// To returns the to-node of the edge.
-func (e WeightedEdge) To() graph.Node {
- if len(e.Lines) == 0 {
- return nil
- }
- return e.Lines[0].To()
-}
+func (e WeightedEdge) To() graph.Node { return e.T }
-// Weight returns the weight of the edge.
+// Weight returns the weight of the edge. Weight uses WeightFunc
+// field to calculate the weight, so the WeightedLines field is
+// expected to be positioned at the first line and is reset before
+// Weight returns.
func (e WeightedEdge) Weight() float64 {
+ if e.WeightedLines == nil {
+ return 0
+ }
if e.WeightFunc == nil {
var w float64
- for _, l := range e.Lines {
- w += l.Weight()
+ for e.Next() {
+ w += e.WeightedLine().Weight()
}
+ e.WeightedLines.Reset()
return w
}
- return e.WeightFunc(e.Lines)
+ return e.WeightFunc(e.WeightedLines)
}
// WeightedLine is a weighted multigraph edge.

MODIFY
graph/multi/undirected.go
graph/multi/undirected.go
@@ -171,7 +171,7 @@ func (g *UndirectedGraph) Edges() graph.Edges {
seen := make(map[int64]struct{})
for _, u := range g.lines {
for _, e := range u {
- var lines Edge
+ var lines []graph.Line
for _, l := range e {
lid := l.ID()
if _, ok := seen[lid]; ok {
@@ -181,7 +181,11 @@ func (g *UndirectedGraph) Edges() graph.Edges {
lines = append(lines, l)
}
if len(lines) != 0 {
- edges = append(edges, lines)
+ edges = append(edges, Edge{
+ F: g.Node(lines[0].From().ID()),
+ T: g.Node(lines[0].To().ID()),
+ Lines: iterator.NewOrderedLines(lines),
+ })
}
}
}
@@ -218,11 +222,11 @@ func (g *UndirectedGraph) EdgeBetween(xid, yid int64) graph.Edge {
// The node v must be directly reachable from u as defined by the From method.
// The returned graph.Edge is a multi.Edge if an edge exists.
func (g *UndirectedGraph) Edge(uid, vid int64) graph.Edge {
- lines := graph.LinesOf(g.LinesBetween(uid, vid))
- if len(lines) == 0 {
+ l := g.LinesBetween(uid, vid)
+ if l == nil {
return nil
}
- return Edge(lines)
+ return Edge{F: g.Node(uid), T: g.Node(vid), Lines: l}
}
// Lines returns the lines from u to v if such an edge exists and nil otherwise.
@@ -233,6 +237,9 @@ func (g *UndirectedGraph) Lines(uid, vid int64) graph.Lines {
// LinesBetween returns the lines between nodes x and y.
func (g *UndirectedGraph) LinesBetween(xid, yid int64) graph.Lines {
+ if !g.HasEdgeBetween(xid, yid) {
+ return nil
+ }
var lines []graph.Line
for _, l := range g.lines[xid][yid] {
lines = append(lines, l)

MODIFY
graph/multi/weighted_directed.go
graph/multi/weighted_directed.go
@@ -30,7 +30,11 @@ var (
// WeightedDirectedGraph implements a generalized directed graph.
type WeightedDirectedGraph struct {
- EdgeWeightFunc func([]graph.WeightedLine) float64
+ // EdgeWeightFunc is used to provide
+ // the WeightFunc function for WeightedEdge
+ // values returned by the graph.
+ // WeightFunc must accept a nil input.
+ EdgeWeightFunc func(graph.WeightedLines) float64
nodes map[int64]graph.Node
from map[int64]map[int64]map[int64]graph.WeightedLine
@@ -181,16 +185,23 @@ func (g *WeightedDirectedGraph) Nodes() graph.Nodes {
// Edges returns all the edges in the graph. Each edge in the returned slice
// is a multi.WeightedEdge.
func (g *WeightedDirectedGraph) Edges() graph.Edges {
+ if len(g.nodes) == 0 {
+ return nil
+ }
var edges []graph.Edge
for _, u := range g.nodes {
for _, e := range g.from[u.ID()] {
- var lines WeightedEdge
+ var lines []graph.WeightedLine
for _, l := range e {
- lines.Lines = append(lines.Lines, l)
+ lines = append(lines, l)
}
- if len(lines.Lines) != 0 {
- lines.WeightFunc = g.EdgeWeightFunc
- edges = append(edges, lines)
+ if len(lines) != 0 {
+ edges = append(edges, WeightedEdge{
+ F: g.Node(u.ID()),
+ T: g.Node(lines[0].To().ID()),
+ WeightedLines: iterator.NewOrderedWeightedLines(lines),
+ WeightFunc: g.EdgeWeightFunc,
+ })
}
}
}
@@ -200,16 +211,23 @@ func (g *WeightedDirectedGraph) Edges() graph.Edges {
// WeightedEdges returns all the edges in the graph. Each edge in the returned slice
// is a multi.WeightedEdge.
func (g *WeightedDirectedGraph) WeightedEdges() graph.WeightedEdges {
+ if len(g.nodes) == 0 {
+ return nil
+ }
var edges []graph.WeightedEdge
for _, u := range g.nodes {
for _, e := range g.from[u.ID()] {
- var lines WeightedEdge
+ var lines []graph.WeightedLine
for _, l := range e {
- lines.Lines = append(lines.Lines, l)
+ lines = append(lines, l)
}
- if len(lines.Lines) != 0 {
- lines.WeightFunc = g.EdgeWeightFunc
- edges = append(edges, lines)
+ if len(lines) != 0 {
+ edges = append(edges, WeightedEdge{
+ F: g.Node(u.ID()),
+ T: g.Node(lines[0].To().ID()),
+ WeightedLines: iterator.NewOrderedWeightedLines(lines),
+ WeightFunc: g.EdgeWeightFunc,
+ })
}
}
}
@@ -275,11 +293,15 @@ func (g *WeightedDirectedGraph) Edge(uid, vid int64) graph.Edge {
// The node v must be directly reachable from u as defined by the From method.
// The returned graph.WeightedEdge is a multi.WeightedEdge if an edge exists.
func (g *WeightedDirectedGraph) WeightedEdge(uid, vid int64) graph.WeightedEdge {
- lines := graph.WeightedLinesOf(g.WeightedLines(uid, vid))
- if len(lines) == 0 {
+ lines := g.WeightedLines(uid, vid)
+ if lines == nil {
return nil
}
- return WeightedEdge{Lines: lines, WeightFunc: g.EdgeWeightFunc}
+ return WeightedEdge{
+ F: g.Node(uid), T: g.Node(vid),
+ WeightedLines: lines,
+ WeightFunc: g.EdgeWeightFunc,
+ }
}
// Lines returns the lines from u to v if such any such lines exists and nil otherwise.
@@ -313,6 +335,6 @@ func (g *WeightedDirectedGraph) WeightedLines(uid, vid int64) graph.WeightedLine
// Weight returns the weight for the lines between x and y summarised by the receiver's
// EdgeWeightFunc. Weight returns true if an edge exists between x and y, false otherwise.
func (g *WeightedDirectedGraph) Weight(uid, vid int64) (w float64, ok bool) {
- lines := graph.WeightedLinesOf(g.WeightedLines(uid, vid))
- return WeightedEdge{Lines: lines, WeightFunc: g.EdgeWeightFunc}.Weight(), len(lines) != 0
+ lines := g.WeightedLines(uid, vid)
+ return WeightedEdge{WeightedLines: lines, WeightFunc: g.EdgeWeightFunc}.Weight(), lines != nil
}

MODIFY
graph/multi/weighted_undirected.go
graph/multi/weighted_undirected.go
@@ -30,7 +30,11 @@ var (
// WeightedUndirectedGraph implements a generalized undirected graph.
type WeightedUndirectedGraph struct {
- EdgeWeightFunc func([]graph.WeightedLine) float64
+ // EdgeWEightFunc is used to provide
+ // the WeightFunc function for WeightedEdge
+ // values returned by the graph.
+ // WeightFunc must accept a nil input.
+ EdgeWeightFunc func(graph.WeightedLines) float64
nodes map[int64]graph.Node
lines map[int64]map[int64]map[int64]graph.WeightedLine
@@ -176,7 +180,7 @@ func (g *WeightedUndirectedGraph) Edges() graph.Edges {
seen := make(map[int64]struct{})
for _, u := range g.lines {
for _, e := range u {
- var lines Edge
+ var lines []graph.WeightedLine
for _, l := range e {
lid := l.ID()
if _, ok := seen[lid]; ok {
@@ -186,13 +190,50 @@ func (g *WeightedUndirectedGraph) Edges() graph.Edges {
lines = append(lines, l)
}
if len(lines) != 0 {
- edges = append(edges, lines)
+ edges = append(edges, WeightedEdge{
+ F: g.Node(lines[0].From().ID()),
+ T: g.Node(lines[0].To().ID()),
+ WeightedLines: iterator.NewOrderedWeightedLines(lines),
+ WeightFunc: g.EdgeWeightFunc,
+ })
}
}
}
return iterator.NewOrderedEdges(edges)
}
+// WeightedEdges returns all the edges in the graph. Each edge in the returned slice
+// is a multi.Edge.
+func (g *WeightedUndirectedGraph) WeightedEdges() graph.WeightedEdges {
+ if len(g.lines) == 0 {
+ return nil
+ }
+ var edges []graph.WeightedEdge
+ seen := make(map[int64]struct{})
+ for _, u := range g.lines {
+ for _, e := range u {
+ var lines []graph.WeightedLine
+ for _, l := range e {
+ lid := l.ID()
+ if _, ok := seen[lid]; ok {
+ continue
+ }
+ seen[lid] = struct{}{}
+ lines = append(lines, l)
+ }
+ if len(lines) != 0 {
+ edges = append(edges, WeightedEdge{
+ F: g.Node(lines[0].From().ID()),
+ T: g.Node(lines[0].To().ID()),
+ WeightedLines: iterator.NewOrderedWeightedLines(lines),
+ WeightFunc: g.EdgeWeightFunc,
+ })
+ }
+ }
+ }
+ return iterator.NewOrderedWeightedEdges(edges)
+}
+
// From returns all nodes in g that can be reached directly from n.
func (g *WeightedUndirectedGraph) From(id int64) graph.Nodes {
if _, ok := g.nodes[id]; !ok {
@@ -255,11 +296,15 @@ func (g *WeightedUndirectedGraph) EdgeBetween(xid, yid int64) graph.Edge {
// The node v must be directly reachable from u as defined by the From method.
// The returned graph.WeightedEdge is a multi.WeightedEdge if an edge exists.
func (g *WeightedUndirectedGraph) WeightedEdge(uid, vid int64) graph.WeightedEdge {
- lines := graph.WeightedLinesOf(g.WeightedLines(uid, vid))
- if len(lines) == 0 {
+ lines := g.WeightedLines(uid, vid)
+ if lines == nil {
return nil
}
- return WeightedEdge{Lines: lines, WeightFunc: g.EdgeWeightFunc}
+ return WeightedEdge{
+ F: g.Node(uid), T: g.Node(vid),
+ WeightedLines: lines,
+ WeightFunc: g.EdgeWeightFunc,
+ }
}
// WeightedEdgeBetween returns the weighted edge between nodes x and y.
@@ -295,6 +340,6 @@ func (g *WeightedUndirectedGraph) WeightedLinesBetween(xid, yid int64) graph.Wei
// Weight returns the weight for the lines between x and y summarised by the receiver's
// EdgeWeightFunc. Weight returns true if an edge exists between x and y, false otherwise.
func (g *WeightedUndirectedGraph) Weight(xid, yid int64) (w float64, ok bool) {
- lines := graph.WeightedLinesOf(g.WeightedLines(xid, yid))
- return WeightedEdge{Lines: lines, WeightFunc: g.EdgeWeightFunc}.Weight(), len(lines) != 0
+ lines := g.WeightedLines(xid, yid)
+ return WeightedEdge{WeightedLines: lines, WeightFunc: g.EdgeWeightFunc}.Weight(), lines != nil
}

graph/multi: clean up missed changes and bugs