immutable graph

package graph

type Node struct {
    Value interface{}

    id    int
    edges []Node
}

type Graph struct {
    idCounter int
    nodes     map[int]Node
}

func NewGraph(root Node) Graph {
    return Graph{
        idCounter: 1,
        nodes:     map[int]Node{0: root},
    }
}

func (g Graph) AddNode(from int, node Node) (Graph, int) {
    newG := g.Copy()
    start, found := newG.nodes[from]
    if !found {
        panic("cannot add node from non-existent node")
    }

    newN := node
    newG.nodes[newG.idCounter] = newN
    newG.idCounter++
    start.edges = make([]Node, len(start.edges)+1)
    copy(start.edges, g.nodes[from].edges)
    start.edges[len(start.edges)-1] = newN

    return newG, newG.idCounter - 1
}

func (g Graph) Copy() Graph {
    newG := Graph{
        idCounter: g.idCounter,
        nodes:     make(map[int]Node),
    }

    for k, v := range g.nodes {
        newG.nodes[k] = v
    }

    return newG
}

func (g Graph) RemoveNode(id int) Graph {
    newG := g.Copy()

    for id, n := range newG.nodes {
        newG.nodes[id] = n.removeEdge(id)
    }

    delete(newG.nodes, id)

    return newG
}

func (g Graph) GetNode(id int) Node {
    return g.nodes[id]
}

func (g Graph) Nodes() []Node {
    results := make([]Node, 0, len(g.nodes))
    for _, node := range g.nodes {
        results = append(results, node)
    }

    return results
}

func (n Node) Edges() []Node {
    results := make([]Node, len(n.edges))
    copy(results, n.edges)
    return results
}

func (n Node) removeEdge(id int) Node {
    n.edges = make([]Node, 0, len(n.edges))

    for _, otherN := range n.edges {
        if otherN.id == id {
            continue
        }
        n.edges = append(n.edges, otherN)
    }

    return n
}