graph/simple: use more efficient dedup logic
MODIFY
graph/simple/undirected.go
graph/simple/undirected.go
@@ -74,16 +74,14 @@ func (g *UndirectedGraph) Edges() graph.Edges {
return graph.Empty
}
var edges []graph.Edge
- seen := make(map[[2]int64]struct{})
- for _, u := range g.edges {
- for _, e := range u {
- uid := e.From().ID()
- vid := e.To().ID()
- if _, ok := seen[[2]int64{uid, vid}]; ok {
+ for xid, u := range g.edges {
+ for yid, e := range u {
+ if yid < xid {
+ // Do not consider edges when the To node ID is
+ // before the From node ID. Both orientations
+ // are stored.
continue
}
- seen[[2]int64{uid, vid}] = struct{}{}
- seen[[2]int64{vid, uid}] = struct{}{}
edges = append(edges, e)
}
}

MODIFY
graph/simple/weighted_undirected.go
graph/simple/weighted_undirected.go
@@ -75,16 +75,14 @@ func (g *WeightedUndirectedGraph) Edges() graph.Edges {
return graph.Empty
}
var edges []graph.Edge
- seen := make(map[[2]int64]struct{})
- for _, u := range g.edges {
- for _, e := range u {
- uid := e.From().ID()
- vid := e.To().ID()
- if _, ok := seen[[2]int64{uid, vid}]; ok {
+ for xid, u := range g.edges {
+ for yid, e := range u {
+ if yid < xid {
+ // Do not consider edges when the To node ID is
+ // before the From node ID. Both orientations
+ // are stored.
continue
}
- seen[[2]int64{uid, vid}] = struct{}{}
- seen[[2]int64{vid, uid}] = struct{}{}
edges = append(edges, e)
}
}
@@ -258,16 +256,14 @@ func (g *WeightedUndirectedGraph) WeightedEdgeBetween(xid, yid int64) graph.Weig
// WeightedEdges returns all the weighted edges in the graph.
func (g *WeightedUndirectedGraph) WeightedEdges() graph.WeightedEdges {
var edges []graph.WeightedEdge
- seen := make(map[[2]int64]struct{})
- for _, u := range g.edges {
- for _, e := range u {
- uid := e.From().ID()
- vid := e.To().ID()
- if _, ok := seen[[2]int64{uid, vid}]; ok {
+ for xid, u := range g.edges {
+ 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[[2]int64{uid, vid}] = struct{}{}
- seen[[2]int64{vid, uid}] = struct{}{}
edges = append(edges, e)
}
}

graph/simple: use more efficient dedup logic