graph/simple: don't allocate edge maps before they are needed
Also fix incorrect optimisation in WeightedDirected.Nodes.
MODIFY
graph/simple/directed.go
graph/simple/directed.go
@@ -49,8 +49,6 @@ func (g *DirectedGraph) AddNode(n graph.Node) {
panic(fmt.Sprintf("simple: node ID collision: %d", n.ID()))
}
g.nodes[n.ID()] = n
- g.from[n.ID()] = make(map[int64]graph.Edge)
- g.to[n.ID()] = make(map[int64]graph.Edge)
g.nodeIDs.Use(n.ID())
}
@@ -212,8 +210,16 @@ func (g *DirectedGraph) SetEdge(e graph.Edge) {
g.nodes[tid] = to
}
- g.from[fid][tid] = e
- g.to[tid][fid] = e
+ if fm, ok := g.from[fid]; ok {
+ fm[tid] = e
+ } else {
+ g.from[fid] = map[int64]graph.Edge{tid: e}
+ }
+ if tm, ok := g.to[tid]; ok {
+ tm[fid] = e
+ } else {
+ g.to[tid] = map[int64]graph.Edge{fid: e}
+ }
}
// To returns all nodes in g that can reach directly to n.

MODIFY
graph/simple/undirected.go
graph/simple/undirected.go
@@ -47,7 +47,6 @@ func (g *UndirectedGraph) AddNode(n graph.Node) {
panic(fmt.Sprintf("simple: node ID collision: %d", n.ID()))
}
g.nodes[n.ID()] = n
- g.edges[n.ID()] = make(map[int64]graph.Edge)
g.nodeIDs.Use(n.ID())
}
@@ -211,6 +210,14 @@ func (g *UndirectedGraph) SetEdge(e graph.Edge) {
g.nodes[tid] = to
}
- g.edges[fid][tid] = e
- g.edges[tid][fid] = e
+ if fm, ok := g.edges[fid]; ok {
+ fm[tid] = e
+ } else {
+ g.edges[fid] = map[int64]graph.Edge{tid: e}
+ }
+ if tm, ok := g.edges[tid]; ok {
+ tm[fid] = e
+ } else {
+ g.edges[tid] = map[int64]graph.Edge{fid: e}
+ }
}

MODIFY
graph/simple/weighted_directed.go
graph/simple/weighted_directed.go
@@ -57,8 +57,6 @@ func (g *WeightedDirectedGraph) AddNode(n graph.Node) {
panic(fmt.Sprintf("simple: node ID collision: %d", n.ID()))
}
g.nodes[n.ID()] = n
- g.from[n.ID()] = make(map[int64]graph.WeightedEdge)
- g.to[n.ID()] = make(map[int64]graph.WeightedEdge)
g.nodeIDs.Use(n.ID())
}
@@ -143,7 +141,7 @@ func (g *WeightedDirectedGraph) Node(id int64) graph.Node {
// Nodes returns all the nodes in the graph.
func (g *WeightedDirectedGraph) Nodes() graph.Nodes {
- if len(g.from) == 0 {
+ if len(g.nodes) == 0 {
return graph.Empty
}
nodes := make([]graph.Node, len(g.nodes))
@@ -216,8 +214,16 @@ func (g *WeightedDirectedGraph) SetWeightedEdge(e graph.WeightedEdge) {
g.nodes[tid] = to
}
- g.from[fid][tid] = e
- g.to[tid][fid] = e
+ if fm, ok := g.from[fid]; ok {
+ fm[tid] = e
+ } else {
+ g.from[fid] = map[int64]graph.WeightedEdge{tid: e}
+ }
+ if tm, ok := g.to[tid]; ok {
+ tm[fid] = e
+ } else {
+ g.to[tid] = map[int64]graph.WeightedEdge{fid: e}
+ }
}
// To returns all nodes in g that can reach directly to n.

MODIFY
graph/simple/weighted_undirected.go
graph/simple/weighted_undirected.go
@@ -55,7 +55,6 @@ func (g *WeightedUndirectedGraph) AddNode(n graph.Node) {
panic(fmt.Sprintf("simple: node ID collision: %d", n.ID()))
}
g.nodes[n.ID()] = n
- g.edges[n.ID()] = make(map[int64]graph.WeightedEdge)
g.nodeIDs.Use(n.ID())
}
@@ -212,8 +211,16 @@ func (g *WeightedUndirectedGraph) SetWeightedEdge(e graph.WeightedEdge) {
g.nodes[tid] = to
}
- g.edges[fid][tid] = e
- g.edges[tid][fid] = e
+ if fm, ok := g.edges[fid]; ok {
+ fm[tid] = e
+ } else {
+ g.edges[fid] = map[int64]graph.WeightedEdge{tid: e}
+ }
+ if tm, ok := g.edges[tid]; ok {
+ tm[fid] = e
+ } else {
+ g.edges[tid] = map[int64]graph.WeightedEdge{fid: e}
+ }
}
// Weight returns the weight for the edge between x and y if Edge(x, y) returns a non-nil Edge.

graph/simple: don't allocate edge maps before they are needed

Also fix incorrect optimisation in WeightedDirected.Nodes.