graph: use int64 for edge and line removal
MODIFY
graph/graph.go
graph/graph.go
@@ -169,10 +169,10 @@ type WeightedEdgeAdder interface {
// EdgeRemover is an interface for removing nodes from a graph.
type EdgeRemover interface {
- // RemoveEdge removes the given edge, leaving the
- // terminal nodes. If the edge does not exist it
- // is a no-op.
- RemoveEdge(Edge)
+ // RemoveEdge removes the edge with the given end
+ // IDs, leaving the terminal nodes. If the edge
+ // does not exist it is a no-op.
+ RemoveEdge(fid, tid int64)
}
// Builder is a graph that can have nodes and edges added.

MODIFY
graph/multi/directed.go
graph/multi/directed.go
@@ -121,26 +121,25 @@ func (g *DirectedGraph) SetLine(l graph.Line) {
g.lineIDs.Use(lid)
}
-// RemoveLine removes l from the graph, leaving the terminal nodes. If the line does not exist
-// it is a no-op.
-func (g *DirectedGraph) RemoveLine(l graph.Line) {
- from, to := l.From(), l.To()
- if _, ok := g.nodes[from.ID()]; !ok {
+// RemoveLine removes the line with the given end point and line IDs from the graph, leaving
+// the terminal nodes. If the line does not exist it is a no-op.
+func (g *DirectedGraph) RemoveLine(fid, tid, id int64) {
+ if _, ok := g.nodes[fid]; !ok {
return
}
- if _, ok := g.nodes[to.ID()]; !ok {
+ if _, ok := g.nodes[tid]; !ok {
return
}
- delete(g.from[from.ID()][to.ID()], l.ID())
- if len(g.from[from.ID()][to.ID()]) == 0 {
- delete(g.from[from.ID()], to.ID())
+ delete(g.from[fid][tid], id)
+ if len(g.from[fid][tid]) == 0 {
+ delete(g.from[fid], tid)
}
- delete(g.to[to.ID()][from.ID()], l.ID())
- if len(g.to[to.ID()][from.ID()]) == 0 {
- delete(g.to[to.ID()], from.ID())
+ delete(g.to[tid][fid], id)
+ if len(g.to[tid][fid]) == 0 {
+ delete(g.to[tid], fid)
}
- g.lineIDs.Release(l.ID())
+ g.lineIDs.Release(id)
}
// Node returns the node in the graph with the given ID.

MODIFY
graph/multi/undirected.go
graph/multi/undirected.go
@@ -113,23 +113,22 @@ func (g *UndirectedGraph) SetLine(l graph.Line) {
g.lineIDs.Use(lid)
}
-// RemoveLine removes l from the graph, leaving the terminal nodes. If the line does not exist
-// it is a no-op.
-func (g *UndirectedGraph) RemoveLine(l graph.Line) {
- from, to := l.From(), l.To()
- if _, ok := g.nodes[from.ID()]; !ok {
+// RemoveLine removes the line with the given end point and line Ids from the graph, leaving
+// the terminal nodes. If the line does not exist it is a no-op.
+func (g *UndirectedGraph) RemoveLine(fid, tid, id int64) {
+ if _, ok := g.nodes[fid]; !ok {
return
}
- if _, ok := g.nodes[to.ID()]; !ok {
+ if _, ok := g.nodes[tid]; !ok {
return
}
- delete(g.lines[from.ID()], to.ID())
- delete(g.lines[to.ID()], from.ID())
- if len(g.lines[to.ID()][from.ID()]) == 0 {
- delete(g.lines[to.ID()], from.ID())
+ delete(g.lines[fid], tid)
+ delete(g.lines[tid], fid)
+ if len(g.lines[tid][fid]) == 0 {
+ delete(g.lines[tid], fid)
}
- g.lineIDs.Release(l.ID())
+ g.lineIDs.Release(id)
}
// Node returns the node in the graph with the given ID.

MODIFY
graph/multi/weighted_undirected.go
graph/multi/weighted_undirected.go
@@ -117,23 +117,22 @@ func (g *WeightedUndirectedGraph) SetWeighted(l graph.WeightedLine) {
g.lineIDs.Use(lid)
}
-// RemoveLine removes l from the graph, leaving the terminal nodes. If the line does not exist
-// it is a no-op.
-func (g *WeightedUndirectedGraph) RemoveLine(l graph.WeightedLine) {
- from, to := l.From(), l.To()
- if _, ok := g.nodes[from.ID()]; !ok {
+// RemoveLine removes the line with the given end point and line IDs from the graph,
+// leaving the terminal nodes. If the line does not exist it is a no-op.
+func (g *WeightedUndirectedGraph) RemoveLine(fid, tid, id int64) {
+ if _, ok := g.nodes[fid]; !ok {
return
}
- if _, ok := g.nodes[to.ID()]; !ok {
+ if _, ok := g.nodes[tid]; !ok {
return
}
- delete(g.lines[from.ID()], to.ID())
- delete(g.lines[to.ID()], from.ID())
- if len(g.lines[to.ID()][from.ID()]) == 0 {
- delete(g.lines[to.ID()], from.ID())
+ delete(g.lines[fid], tid)
+ delete(g.lines[tid], fid)
+ if len(g.lines[tid][fid]) == 0 {
+ delete(g.lines[tid], fid)
}
- g.lineIDs.Release(l.ID())
+ g.lineIDs.Release(id)
}
// Node returns the node in the graph with the given ID.

MODIFY
graph/multigraph.go
graph/multigraph.go
@@ -125,10 +125,10 @@ type WeightedLineAdder interface {
// LineRemover is an interface for removing lines from a multigraph.
type LineRemover interface {
- // RemoveLine removes the given line, leaving the
- // terminal nodes. If the line does not exist it
- // is a no-op.
- RemoveLine(Line)
+ // RemoveLine removes the line with the given end
+ // and line IDs, leaving the terminal nodes. If
+ // the line does not exist it is a no-op.
+ RemoveLine(fid, tid, id int64)
}
// MultigraphBuilder is a multigraph that can have nodes and lines added.

MODIFY
graph/path/control_flow_bench_test.go
graph/path/control_flow_bench_test.go
@@ -242,7 +242,7 @@ func duplication(n int, delta, alpha, sigma float64) func() *simple.DirectedGrap
}
for _, e := range g.Edges() {
if rnd.Intn(2) == 0 {
- g.RemoveEdge(e)
+ g.RemoveEdge(e.From().ID(), e.To().ID())
}
}
return g.DirectedGraph

MODIFY
graph/simple/dense_directed_matrix.go
graph/simple/dense_directed_matrix.go
@@ -238,14 +238,12 @@ func (g *DirectedMatrix) setWeightedEdge(e graph.Edge, weight float64) {
g.mat.Set(int(fid), int(tid), weight)
}
-// RemoveEdge removes e from the graph, leaving the terminal nodes. If the edge does not exist
-// it is a no-op.
-func (g *DirectedMatrix) RemoveEdge(e graph.Edge) {
- fid := e.From().ID()
+// RemoveEdge removes the edge with the given end point nodes from the graph, leaving the terminal
+// nodes. If the edge does not exist it is a no-op.
+func (g *DirectedMatrix) RemoveEdge(fid, tid int64) {
if !g.has(fid) {
return
}
- tid := e.To().ID()
if !g.has(tid) {
return
}

MODIFY
graph/simple/dense_undirected_matrix.go
graph/simple/dense_undirected_matrix.go
@@ -213,14 +213,12 @@ func (g *UndirectedMatrix) setWeightedEdge(e graph.Edge, weight float64) {
g.mat.SetSym(int(fid), int(tid), weight)
}
-// RemoveEdge removes e from the graph, leaving the terminal nodes. If the edge does not exist
-// it is a no-op.
-func (g *UndirectedMatrix) RemoveEdge(e graph.Edge) {
- fid := e.From().ID()
+// RemoveEdge removes the edge with the given end point IDs from the graph, leaving the terminal
+// nodes. If the edge does not exist it is a no-op.
+func (g *UndirectedMatrix) RemoveEdge(fid, tid int64) {
if !g.has(fid) {
return
}
- tid := e.To().ID()
if !g.has(tid) {
return
}

MODIFY
graph/simple/densegraph_test.go
graph/simple/densegraph_test.go
@@ -82,7 +82,7 @@ func TestDirectedDenseAddRemove(t *testing.T) {
t.Errorf("Adding edge didn't create successor")
}
- dg.RemoveEdge(Edge{F: Node(0), T: Node(2)})
+ dg.RemoveEdge(int64(0), int64(2))
if neighbors := dg.From(int64(0)); len(neighbors) != 0 || dg.Edge(int64(0), int64(2)) != nil {
t.Errorf("Removing edge didn't properly remove successor")
@@ -141,7 +141,7 @@ func TestDenseLists(t *testing.T) {
t.Errorf("Improper number of edges for passable dense graph")
}
- dg.RemoveEdge(Edge{F: Node(12), T: Node(11)})
+ dg.RemoveEdge(int64(12), int64(11))
edges = dg.Edges()
if len(edges) != (15*14)-1 {
t.Errorf("Removing edge didn't affect edge listing properly")

MODIFY
graph/simple/directed.go
graph/simple/directed.go
@@ -105,19 +105,18 @@ func (g *DirectedGraph) SetEdge(e graph.Edge) {
g.to[tid][fid] = e
}
-// RemoveEdge removes e from the graph, leaving the terminal nodes. If the edge does not exist
-// it is a no-op.
-func (g *DirectedGraph) RemoveEdge(e graph.Edge) {
- from, to := e.From(), e.To()
- if _, ok := g.nodes[from.ID()]; !ok {
+// RemoveEdge removes the edge with the given end point IDs from the graph, leaving the terminal
+// nodes. If the edge does not exist it is a no-op.
+func (g *DirectedGraph) RemoveEdge(fid, tid int64) {
+ if _, ok := g.nodes[fid]; !ok {
return
}
- if _, ok := g.nodes[to.ID()]; !ok {
+ if _, ok := g.nodes[tid]; !ok {
return
}
- delete(g.from[from.ID()], to.ID())
- delete(g.to[to.ID()], from.ID())
+ delete(g.from[fid], tid)
+ delete(g.to[tid], fid)
}
// Node returns the node in the graph with the given ID.

MODIFY
graph/simple/undirected.go
graph/simple/undirected.go
@@ -97,19 +97,18 @@ func (g *UndirectedGraph) SetEdge(e graph.Edge) {
g.edges[tid][fid] = e
}
-// RemoveEdge removes e from the graph, leaving the terminal nodes. If the edge does not exist
-// it is a no-op.
-func (g *UndirectedGraph) RemoveEdge(e graph.Edge) {
- from, to := e.From(), e.To()
- if _, ok := g.nodes[from.ID()]; !ok {
+// RemoveEdge removes the edge with the given end IDs from the graph, leaving the terminal nodes.
+// If the edge does not exist it is a no-op.
+func (g *UndirectedGraph) RemoveEdge(fid, tid int64) {
+ if _, ok := g.nodes[fid]; !ok {
return
}
- if _, ok := g.nodes[to.ID()]; !ok {
+ if _, ok := g.nodes[tid]; !ok {
return
}
- delete(g.edges[from.ID()], to.ID())
- delete(g.edges[to.ID()], from.ID())
+ delete(g.edges[fid], tid)
+ delete(g.edges[tid], fid)
}
// Node returns the node in the graph with the given ID.

MODIFY
graph/simple/weighted_directed.go
graph/simple/weighted_directed.go
@@ -111,19 +111,18 @@ func (g *WeightedDirectedGraph) SetWeightedEdge(e graph.WeightedEdge) {
g.to[tid][fid] = e
}
-// RemoveEdge removes e from the graph, leaving the terminal nodes. If the edge does not exist
-// it is a no-op.
-func (g *WeightedDirectedGraph) RemoveEdge(e graph.Edge) {
- from, to := e.From(), e.To()
- if _, ok := g.nodes[from.ID()]; !ok {
+// RemoveEdge removes the edge with the given end point IDs from the graph, leaving the terminal
+// nodes. If the edge does not exist it is a no-op.
+func (g *WeightedDirectedGraph) RemoveEdge(fid, tid int64) {
+ if _, ok := g.nodes[fid]; !ok {
return
}
- if _, ok := g.nodes[to.ID()]; !ok {
+ if _, ok := g.nodes[tid]; !ok {
return
}
- delete(g.from[from.ID()], to.ID())
- delete(g.to[to.ID()], from.ID())
+ delete(g.from[fid], tid)
+ delete(g.to[tid], fid)
}
// Node returns the node in the graph with the given ID.

MODIFY
graph/simple/weighted_undirected.go
graph/simple/weighted_undirected.go
@@ -103,19 +103,18 @@ func (g *WeightedUndirectedGraph) SetWeightedEdge(e graph.WeightedEdge) {
g.edges[tid][fid] = e
}
-// RemoveEdge removes e from the graph, leaving the terminal nodes. If the edge does not exist
-// it is a no-op.
-func (g *WeightedUndirectedGraph) RemoveEdge(e graph.Edge) {
- from, to := e.From(), e.To()
- if _, ok := g.nodes[from.ID()]; !ok {
+// RemoveEdge removes the edge with the given end point IDs from the graph, leaving the terminal
+// nodes. If the edge does not exist it is a no-op.
+func (g *WeightedUndirectedGraph) RemoveEdge(fid, tid int64) {
+ if _, ok := g.nodes[fid]; !ok {
return
}
- if _, ok := g.nodes[to.ID()]; !ok {
+ if _, ok := g.nodes[tid]; !ok {
return
}
- delete(g.edges[from.ID()], to.ID())
- delete(g.edges[to.ID()], from.ID())
+ delete(g.edges[fid], tid)
+ delete(g.edges[tid], fid)
}
// Node returns the node in the graph with the given ID.

graph: use int64 for edge and line removal