graph/multi: use more efficient and correct direction dedup logic
Also add test case to testgraph corpus.
diff --git a/graph/multi/undirected.go b/graph/multi/undirected.go
index c6bd747..d28c309 100644
--- a/graph/multi/undirected.go
+++ b/graph/multi/undirected.go
@@ -77,25 +77,27 @@
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 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
+ }
+ // 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 {
- lid := l.ID()
- if _, ok := seen[lid]; ok {
- continue
- }
- seen[lid] = struct{}{}
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()),
- Lines: iterator.NewOrderedLines(lines),
- })
- }
+ edges = append(edges, Edge{
+ F: g.Node(xid),
+ T: g.Node(yid),
+ Lines: iterator.NewOrderedLines(lines),
+ })
}
}
if len(edges) == 0 {
diff --git a/graph/multi/weighted_undirected.go b/graph/multi/weighted_undirected.go
index a2a2944..d8ed075 100644
--- a/graph/multi/weighted_undirected.go
+++ b/graph/multi/weighted_undirected.go
@@ -82,26 +82,28 @@
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 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
+ }
+ // 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 {
- 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,
- })
- }
+ edges = append(edges, WeightedEdge{
+ F: g.Node(xid),
+ T: g.Node(yid),
+ WeightedLines: iterator.NewOrderedWeightedLines(lines),
+ WeightFunc: g.EdgeWeightFunc,
+ })
}
}
if len(edges) == 0 {
@@ -334,26 +336,28 @@
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 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
+ }
+ // 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 {
- 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,
- })
- }
+ edges = append(edges, WeightedEdge{
+ F: g.Node(xid),
+ T: g.Node(yid),
+ WeightedLines: iterator.NewOrderedWeightedLines(lines),
+ WeightFunc: g.EdgeWeightFunc,
+ })
}
}
if len(edges) == 0 {
diff --git a/graph/testgraph/testcases.go b/graph/testgraph/testcases.go
index 347e8a7..fb9a971 100644
--- a/graph/testgraph/testcases.go
+++ b/graph/testgraph/testcases.go
@@ -369,4 +369,15 @@
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),
+ },
}
