Go: package Graph

graph.go

package graph

type Graph map[string]*vertex

func New() Graph {
	return make(Graph)
}

func (g Graph) Vertices() (answer []string) {
	for v := range g {
		answer = append(answer, v)
	}
	return
}

func (g Graph) Vertex(s string) Labeler {
	return g[s].Labeler
}

func (g Graph) AddVertex(x Labeler) {
	label := x.Label()
	if y, ok := g[label]; ok {
		y.Labeler = x
	} else {
		g[label] = &vertex{Labeler: x}
	}
}

func (g Graph) DeleteVertex(s string) {
	for _, e := range g.InEdges(s) {
		g.DeleteEdge(e)
	}
	for _, e := range g.OutEdges(s) {
		g.DeleteEdge(e)
	}
	delete(g, s)
}

func (g Graph) Edges() (answer []Edger) {
	for v := range g {
		answer = append(answer, g.OutEdges(v)...)
	}
	return
}

func (g Graph) InEdges(s string) []Edger {
	return g[s].in
}

func (g Graph) OutEdges(s string) []Edger {
	return g[s].out
}

func (g Graph) AddEdge(e Edger) {
	from, to := e.From(), e.To()
	if _, ok := g[from]; ok {
		if _, ok := g[to]; ok {
			g[from].out = append(g[from].out, e)
			g[to].in = append(g[to].in, e)
		}
	}
}

func (g Graph) DeleteEdge(e Edger) {
	g[e.From()].removeOutEdge(e)
	g[e.To()].removeInEdge(e)
}

// vertex

type Labeler interface {
	Label() string
}

type vertex struct {
	Labeler
	in  []Edger
	out []Edger
}

func (v *vertex) removeInEdge(e Edger) {
	xs := []Edger{}
	for _, elem := range v.in {
		if elem != e {
			xs = append(xs, elem)
		}
	}
	v.in = xs
}

func (v *vertex) removeOutEdge(e Edger) {
	xs := []Edger{}
	for _, elem := range v.out {
		if elem != e {
			xs = append(xs, elem)
		}
	}
	v.out = xs
}

// Edge

type Edger interface {
	From() string
	To() string
}