graph/multi: use more efficient and correct direction dedup logic
Also add test case to testgraph corpus.
MODIFY
graph/multi/undirected.go
graph/multi/undirected.go
@@ -77,27 +77,29 @@ func (g *UndirectedGraph) Edges() graph.Edges {
return graph.Empty
}
var edges []graph.Edge
- seen := make(map[int64]struct{})
- for _, u := range g.lines {
- for _, e := range u {
- var lines []graph.Line
- for _, l := range e {
- lid := l.ID()
- if _, ok := seen[lid]; ok {
+ for xid, u := range g.lines {
+ for yid, e := range u {
+ if yid < xid {
+ // Do not consider lines when the To node ID is
+ // before the From node ID. Both orientations
+ // are stored.
continue
}
- seen[lid] = struct{}{}
+ // TODO(kortschak): Add iterator.Lines and use that here.
+ if len(e) == 0 {
+ continue
+ }
+ lines := make([]graph.Line, 0, len(e))
+ for _, l := range e {
lines = append(lines, l)
}
- if len(lines) != 0 {
edges = append(edges, Edge{
- F: g.Node(lines[0].From().ID()),
- T: g.Node(lines[0].To().ID()),
+ F: g.Node(xid),
+ T: g.Node(yid),
Lines: iterator.NewOrderedLines(lines),
})
}
}
- }
if len(edges) == 0 {
return graph.Empty
}

MODIFY
graph/multi/weighted_undirected.go
graph/multi/weighted_undirected.go
@@ -82,28 +82,30 @@ func (g *WeightedUndirectedGraph) Edges() graph.Edges {
return graph.Empty
}
var edges []graph.Edge
- 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 {
+ for xid, u := range g.lines {
+ for yid, e := range u {
+ if yid < xid {
+ // Do not consider lines when the To node ID is
+ // before the From node ID. Both orientations
+ // are stored.
continue
}
- seen[lid] = struct{}{}
+ // TODO(kortschak): Add iterator.WeightedLines and use that here.
+ if len(e) == 0 {
+ continue
+ }
+ lines := make([]graph.WeightedLine, 0, len(e))
+ for _, l := range e {
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()),
+ F: g.Node(xid),
+ T: g.Node(yid),
WeightedLines: iterator.NewOrderedWeightedLines(lines),
WeightFunc: g.EdgeWeightFunc,
})
}
}
- }
if len(edges) == 0 {
return graph.Empty
}
@@ -345,28 +347,30 @@ func (g *WeightedUndirectedGraph) WeightedEdges() graph.WeightedEdges {
return graph.Empty
}
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 {
+ for xid, u := range g.lines {
+ for yid, e := range u {
+ if yid < xid {
+ // Do not consider lines when the To node ID is
+ // before the From node ID. Both orientations
+ // are stored.
continue
}
- seen[lid] = struct{}{}
+ // TODO(kortschak): Add iterator.WeightedLines and use that here.
+ if len(e) == 0 {
+ continue
+ }
+ lines := make([]graph.WeightedLine, 0, len(e))
+ for _, l := range e {
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()),
+ F: g.Node(xid),
+ T: g.Node(yid),
WeightedLines: iterator.NewOrderedWeightedLines(lines),
WeightFunc: g.EdgeWeightFunc,
})
}
}
- }
if len(edges) == 0 {
return graph.Empty
}

MODIFY
graph/testgraph/testcases.go
graph/testgraph/testcases.go
@@ -369,4 +369,15 @@ var testCases = []struct {
self: 0,
absent: math.Inf(1),
},
+ {
+ name: "issue 1686",
+ nodes: []graph.Node{node(0), node(1), node(2)},
+ edges: []WeightedLine{
+ line{F: node(0), T: node(1), UID: 0, W: 0.5},
+ line{F: node(1), T: node(2), UID: 0, W: 0.5},
+ },
+ nonexist: []graph.Node{node(-1), node(4)},
+ self: 0,
+ absent: math.Inf(1),
+ },
}

graph/multi: use more efficient and correct direction dedup logic

Also add test case to testgraph corpus.