graph/{multi,testgraph}: make line ID allocation per node pair
MODIFY
graph/multi/directed.go
graph/multi/directed.go
@@ -32,7 +32,7 @@ type DirectedGraph struct {
to map[int64]map[int64]map[int64]graph.Line
nodeIDs uid.Set
- lineIDs uid.Set
+ lineIDs map[int64]map[int64]*uid.Set
}
// NewDirectedGraph returns a DirectedGraph.
@@ -43,7 +43,7 @@ func NewDirectedGraph() *DirectedGraph {
to: make(map[int64]map[int64]map[int64]graph.Line),
nodeIDs: uid.NewSet(),
- lineIDs: uid.NewSet(),
+ lineIDs: make(map[int64]map[int64]*uid.Set),
}
}
@@ -140,7 +140,22 @@ func (g *DirectedGraph) Lines(uid, vid int64) graph.Lines {
// The returned Line will have a graph-unique ID.
// The Line's ID does not become valid in g until the Line is added to g.
func (g *DirectedGraph) NewLine(from, to graph.Node) graph.Line {
- return Line{F: from, T: to, UID: g.lineIDs.NewID()}
+ fid := from.ID()
+ tid := to.ID()
+ var lineID int64
+ switch {
+ case g.lineIDs[fid] == nil:
+ uids := uid.NewSet()
+ lineID = uids.NewID()
+ g.lineIDs[fid] = map[int64]*uid.Set{tid: &uids}
+ case g.lineIDs[fid][tid] == nil:
+ uids := uid.NewSet()
+ lineID = uids.NewID()
+ g.lineIDs[fid][tid] = &uids
+ default:
+ lineID = g.lineIDs[fid][tid].NewID()
+ }
+ return Line{F: from, T: to, UID: lineID}
}
// NewNode returns a new unique Node to be added to g. The Node's ID does
@@ -190,7 +205,8 @@ func (g *DirectedGraph) RemoveLine(fid, tid, id int64) {
if len(g.to[tid][fid]) == 0 {
delete(g.to[tid], fid)
}
- g.lineIDs.Release(id)
+
+ g.lineIDs[fid][tid].Release(id)
}
// RemoveNode removes the node with the given ID from the graph, as well as any edges attached
@@ -253,7 +269,15 @@ func (g *DirectedGraph) SetLine(l graph.Line) {
g.to[tid][fid][lid] = l
}
- g.lineIDs.Use(lid)
+ switch {
+ case g.lineIDs[fid] == nil:
+ uids := uid.NewSet()
+ g.lineIDs[fid] = map[int64]*uid.Set{tid: &uids}
+ case g.lineIDs[fid][tid] == nil:
+ uids := uid.NewSet()
+ g.lineIDs[fid][tid] = &uids
+ }
+ g.lineIDs[fid][tid].Use(lid)
}
// To returns all nodes in g that can reach directly to n.

MODIFY
graph/multi/undirected.go
graph/multi/undirected.go
@@ -31,7 +31,7 @@ type UndirectedGraph struct {
lines map[int64]map[int64]map[int64]graph.Line
nodeIDs uid.Set
- lineIDs uid.Set
+ lineIDs map[int64]map[int64]*uid.Set
}
// NewUndirectedGraph returns an UndirectedGraph.
@@ -41,7 +41,7 @@ func NewUndirectedGraph() *UndirectedGraph {
lines: make(map[int64]map[int64]map[int64]graph.Line),
nodeIDs: uid.NewSet(),
- lineIDs: uid.NewSet(),
+ lineIDs: make(map[int64]map[int64]*uid.Set),
}
}
@@ -146,7 +146,25 @@ func (g *UndirectedGraph) LinesBetween(xid, yid int64) graph.Lines {
// The returned Line will have a graph-unique ID.
// The Line's ID does not become valid in g until the Line is added to g.
func (g *UndirectedGraph) NewLine(from, to graph.Node) graph.Line {
- return Line{F: from, T: to, UID: g.lineIDs.NewID()}
+ xid := from.ID()
+ yid := to.ID()
+ if yid < xid {
+ xid, yid = yid, xid
+ }
+ var lineID int64
+ switch {
+ case g.lineIDs[xid] == nil:
+ uids := uid.NewSet()
+ lineID = uids.NewID()
+ g.lineIDs[xid] = map[int64]*uid.Set{yid: &uids}
+ case g.lineIDs[xid][yid] == nil:
+ uids := uid.NewSet()
+ lineID = uids.NewID()
+ g.lineIDs[xid][yid] = &uids
+ default:
+ lineID = g.lineIDs[xid][yid].NewID()
+ }
+ return Line{F: from, T: to, UID: lineID}
}
// NewNode returns a new unique Node to be added to g. The Node's ID does
@@ -196,7 +214,13 @@ func (g *UndirectedGraph) RemoveLine(fid, tid, id int64) {
if len(g.lines[tid][fid]) == 0 {
delete(g.lines[tid], fid)
}
- g.lineIDs.Release(id)
+
+ xid := fid
+ yid := tid
+ if yid < xid {
+ xid, yid = yid, xid
+ }
+ g.lineIDs[xid][yid].Release(id)
}
// RemoveNode removes the node with the given ID from the graph, as well as any edges attached
@@ -254,5 +278,18 @@ func (g *UndirectedGraph) SetLine(l graph.Line) {
g.lines[tid][fid][lid] = l
}
- g.lineIDs.Use(lid)
+ xid := fid
+ yid := tid
+ if yid < xid {
+ xid, yid = yid, xid
+ }
+ switch {
+ case g.lineIDs[xid] == nil:
+ uids := uid.NewSet()
+ g.lineIDs[xid] = map[int64]*uid.Set{yid: &uids}
+ case g.lineIDs[xid][yid] == nil:
+ uids := uid.NewSet()
+ g.lineIDs[xid][yid] = &uids
+ }
+ g.lineIDs[xid][yid].Use(lid)
}

MODIFY
graph/multi/weighted_directed.go
graph/multi/weighted_directed.go
@@ -41,7 +41,7 @@ type WeightedDirectedGraph struct {
to map[int64]map[int64]map[int64]graph.WeightedLine
nodeIDs uid.Set
- lineIDs uid.Set
+ lineIDs map[int64]map[int64]*uid.Set
}
// NewWeightedDirectedGraph returns a WeightedDirectedGraph.
@@ -52,7 +52,7 @@ func NewWeightedDirectedGraph() *WeightedDirectedGraph {
to: make(map[int64]map[int64]map[int64]graph.WeightedLine),
nodeIDs: uid.NewSet(),
- lineIDs: uid.NewSet(),
+ lineIDs: make(map[int64]map[int64]*uid.Set),
}
}
@@ -160,7 +160,22 @@ func (g *WeightedDirectedGraph) NewNode() graph.Node {
// The returned WeightedLine will have a graph-unique ID.
// The Line's ID does not become valid in g until the Line is added to g.
func (g *WeightedDirectedGraph) NewWeightedLine(from, to graph.Node, weight float64) graph.WeightedLine {
- return WeightedLine{F: from, T: to, W: weight, UID: g.lineIDs.NewID()}
+ fid := from.ID()
+ tid := to.ID()
+ var lineID int64
+ switch {
+ case g.lineIDs[fid] == nil:
+ uids := uid.NewSet()
+ lineID = uids.NewID()
+ g.lineIDs[fid] = map[int64]*uid.Set{tid: &uids}
+ case g.lineIDs[fid][tid] == nil:
+ uids := uid.NewSet()
+ lineID = uids.NewID()
+ g.lineIDs[fid][tid] = &uids
+ default:
+ lineID = g.lineIDs[fid][tid].NewID()
+ }
+ return WeightedLine{F: from, T: to, W: weight, UID: lineID}
}
// Node returns the node with the given ID if it exists in the graph,
@@ -198,7 +213,8 @@ func (g *WeightedDirectedGraph) RemoveLine(fid, tid, id int64) {
if len(g.to[tid][fid]) == 0 {
delete(g.to[tid], fid)
}
- g.lineIDs.Release(id)
+
+ g.lineIDs[fid][tid].Release(id)
}
// RemoveNode removes the node with the given ID from the graph, as well as any edges attached
@@ -261,7 +277,15 @@ func (g *WeightedDirectedGraph) SetWeightedLine(l graph.WeightedLine) {
g.to[tid][fid][lid] = l
}
- g.lineIDs.Use(l.ID())
+ switch {
+ case g.lineIDs[fid] == nil:
+ uids := uid.NewSet()
+ g.lineIDs[fid] = map[int64]*uid.Set{tid: &uids}
+ case g.lineIDs[fid][tid] == nil:
+ uids := uid.NewSet()
+ g.lineIDs[fid][tid] = &uids
+ }
+ g.lineIDs[fid][tid].Use(lid)
}
// To returns all nodes in g that can reach directly to n.

MODIFY
graph/multi/weighted_undirected.go
graph/multi/weighted_undirected.go
@@ -40,7 +40,7 @@ type WeightedUndirectedGraph struct {
lines map[int64]map[int64]map[int64]graph.WeightedLine
nodeIDs uid.Set
- lineIDs uid.Set
+ lineIDs map[int64]map[int64]*uid.Set
}
// NewWeightedUndirectedGraph returns an WeightedUndirectedGraph.
@@ -50,7 +50,7 @@ func NewWeightedUndirectedGraph() *WeightedUndirectedGraph {
lines: make(map[int64]map[int64]map[int64]graph.WeightedLine),
nodeIDs: uid.NewSet(),
- lineIDs: uid.NewSet(),
+ lineIDs: make(map[int64]map[int64]*uid.Set),
}
}
@@ -164,7 +164,25 @@ func (g *WeightedUndirectedGraph) NewNode() graph.Node {
// The returned WeightedLine will have a graph-unique ID.
// The Line's ID does not become valid in g until the Line is added to g.
func (g *WeightedUndirectedGraph) NewWeightedLine(from, to graph.Node, weight float64) graph.WeightedLine {
- return WeightedLine{F: from, T: to, W: weight, UID: g.lineIDs.NewID()}
+ xid := from.ID()
+ yid := to.ID()
+ if yid < xid {
+ xid, yid = yid, xid
+ }
+ var lineID int64
+ switch {
+ case g.lineIDs[xid] == nil:
+ uids := uid.NewSet()
+ lineID = uids.NewID()
+ g.lineIDs[xid] = map[int64]*uid.Set{yid: &uids}
+ case g.lineIDs[xid][yid] == nil:
+ uids := uid.NewSet()
+ lineID = uids.NewID()
+ g.lineIDs[xid][yid] = &uids
+ default:
+ lineID = g.lineIDs[xid][yid].NewID()
+ }
+ return WeightedLine{F: from, T: to, W: weight, UID: lineID}
}
// Node returns the node with the given ID if it exists in the graph,
@@ -202,7 +220,13 @@ func (g *WeightedUndirectedGraph) RemoveLine(fid, tid, id int64) {
if len(g.lines[tid][fid]) == 0 {
delete(g.lines[tid], fid)
}
- g.lineIDs.Release(id)
+
+ xid := fid
+ yid := tid
+ if yid < xid {
+ xid, yid = yid, xid
+ }
+ g.lineIDs[xid][yid].Release(id)
}
// RemoveNode removes the node with the given ID from the graph, as well as any edges attached
@@ -260,7 +284,20 @@ func (g *WeightedUndirectedGraph) SetWeightedLine(l graph.WeightedLine) {
g.lines[tid][fid][lid] = l
}
- g.lineIDs.Use(lid)
+ xid := fid
+ yid := tid
+ if yid < xid {
+ xid, yid = yid, xid
+ }
+ switch {
+ case g.lineIDs[xid] == nil:
+ uids := uid.NewSet()
+ g.lineIDs[xid] = map[int64]*uid.Set{yid: &uids}
+ case g.lineIDs[xid][yid] == nil:
+ uids := uid.NewSet()
+ g.lineIDs[xid][yid] = &uids
+ }
+ g.lineIDs[xid][yid].Use(lid)
}
// Weight returns the weight for the lines between x and y summarised by the receiver's

MODIFY
graph/testgraph/testgraph.go
graph/testgraph/testgraph.go
@@ -1771,20 +1771,20 @@ func AddLines(t *testing.T, n int, g LineAdder, newNode func(id int64) graph.Nod
}
rnd := rand.New(rand.NewSource(1))
- seen := make(set.Int64s)
+ seen := make(tripleInt64s)
for i := 0; i < n; i++ {
u := newNode(rnd.Int63n(int64(n)))
v := newNode(rnd.Int63n(int64(n)))
prev := g.Lines(u.ID(), v.ID())
l := g.NewLine(u, v)
- if seen.Has(l.ID()) {
+ if seen.has(u.ID(), v.ID(), l.ID()) {
t.Fatalf("NewLine returned an existing line: %#v", l)
}
if g.Lines(u.ID(), v.ID()).Len() != prev.Len() {
t.Fatalf("NewLine added a line: %#v", l)
}
g.SetLine(l)
- seen.Add(l.ID())
+ seen.add(u.ID(), v.ID(), l.ID())
if g.Lines(u.ID(), v.ID()).Len() != prev.Len()+1 {
t.Fatalf("SetLine failed to add line: %#v", l)
}
@@ -1835,20 +1835,20 @@ func AddWeightedLines(t *testing.T, n int, g WeightedLineAdder, w float64, newNo
}
rnd := rand.New(rand.NewSource(1))
- seen := make(set.Int64s)
+ seen := make(tripleInt64s)
for i := 0; i < n; i++ {
u := newNode(rnd.Int63n(int64(n)))
v := newNode(rnd.Int63n(int64(n)))
prev := g.Lines(u.ID(), v.ID())
l := g.NewWeightedLine(u, v, w)
- if seen.Has(l.ID()) {
+ if seen.has(u.ID(), v.ID(), l.ID()) {
t.Fatalf("NewWeightedLine returned an existing line: %#v", l)
}
if g.Lines(u.ID(), v.ID()).Len() != prev.Len() {
t.Fatalf("NewWeightedLine added a line: %#v", l)
}
g.SetWeightedLine(l)
- seen.Add(l.ID())
+ seen.add(u.ID(), v.ID(), l.ID())
curr := g.Lines(u.ID(), v.ID())
if curr.Len() != prev.Len()+1 {
t.Fatalf("SetWeightedLine failed to add line: %#v", l)
@@ -2131,3 +2131,17 @@ func (n *RandomNodes) Reset() {
n.seen = make(set.Int64s)
n.count = 0
}
+
+// tripleInt64s is a set of [3]int64 identifiers.
+type tripleInt64s map[[3]int64]struct{}
+
+// add inserts an element into the set.
+func (s tripleInt64s) add(x, y, z int64) {
+ s[[3]int64{x, y, z}] = struct{}{}
+}
+
+// has reports the existence of the element in the set.
+func (s tripleInt64s) has(x, y, z int64) bool {
+ _, ok := s[[3]int64{x, y, z}]
+ return ok
+}

graph/{multi,testgraph}: make line ID allocation per node pair