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

Also add test case to testgraph corpus.

graph/multi/undirected.go

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 {

graph/multi/weighted_undirected.go

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 {

graph/testgraph/testcases.go

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),
+	},
 }