Skip to content

Commit

Permalink
graph/multi: use more efficient and correct direction dedup logic
Browse files Browse the repository at this point in the history
Also add test case to testgraph corpus.
kortschak committed Jun 23, 2021
1 parent 82cfcc5 commit 0fb53cb
Showing 3 changed files with 67 additions and 50 deletions.
34 changes: 18 additions & 16 deletions graph/multi/undirected.go
Original file line number Diff line number Diff line change
@@ -77,25 +77,27 @@ 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 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 {
72 changes: 38 additions & 34 deletions graph/multi/weighted_undirected.go
Original file line number Diff line number Diff line change
@@ -82,26 +82,28 @@ 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 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 {
@@ -345,26 +347,28 @@ 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 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 {
11 changes: 11 additions & 0 deletions graph/testgraph/testcases.go
Original file line number Diff line number Diff line change
@@ -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),
},
}

0 comments on commit 0fb53cb

Please sign in to comment.