graph

README

go-graph

This implements a weighted, directional graph in Go.

Usage

// Construct an empty graph storing strings inside the node.
// The node value is a generic, TValue. TValue _must_ implement comparable.
g := Graph[string]{}

// Vertices must be added before adding any edges. If you haven't added a vertex,
// the edge add will return an error.
a := &(Vertex[string]{"A"})
b := &(Vertex[string]{"B"})
c := &(Vertex[string]{"C"})
d := &(Vertex[string]{"D"})

// AddVertex will silently continue if a Vertex already exists.
g.AddVertex(a)
g.AddVertex(b)
g.AddVertex(c)
g.AddVertex(d)

// Now that we've added the vertices, we can get to adding edges.
// I'm ignoring error checks here for clarity.
_ = g.AddEdge(a, b, 1, nil)
_ = g.AddEdge(b, c, 10, nil)
_ = g.addEdge(a, d, 5, nil)
_ = g.addEdge(d, c, 5, nil)

// calculate the shortest path between "A" and "C"
path, err := g.ShortestPath(a, c)
if err != nil {
    t.Error(err)
}

Documentation

Index

• type Graph
  • func (g *Graph[TValue]) AddEdge(src *Vertex[TValue], dest *Vertex[TValue], weight uint, tag *string) error
  • func (g *Graph[TValue]) AddSymmetricEdge(src, dest *Vertex[TValue], weight uint, tag *string) error
  • func (g *Graph[TValue]) AddVertex(v *Vertex[TValue])
  • func (g *Graph[TValue]) ContainsEdge(src, dest *Vertex[TValue], tag *string) bool
  • func (g *Graph[TValue]) ContainsSymmetricEdge(src, dest *Vertex[TValue], tag *string) bool
  • func (g *Graph[TValue]) ContainsVertex(v *Vertex[TValue]) bool
  • func (g *Graph[TValue]) GetEdge(src, dest *Vertex[TValue], tag *string) (WeightedEdge[TValue], error)
  • func (g *Graph[TValue]) RemoveEdge(src, dest *Vertex[TValue], tag *string)
  • func (g *Graph[TValue]) RemoveSymmetricEdge(src, dest *Vertex[TValue], tag *string)
  • func (g *Graph[TValue]) ShortestPath(src, dest *Vertex[TValue]) ([]PathEdge[TValue], error)
• type PathEdge
  • func (pe PathEdge[TValue]) String() string
• type Vertex
  • func (n *Vertex[TValue]) String() string
• type WeightedEdge

Types

type Graph

type Graph[TValue comparable] struct {
	// contains filtered or unexported fields
}

Graph - a directed, weighted graph.

func (*Graph[TValue]) AddEdge

func (g *Graph[TValue]) AddEdge(src *Vertex[TValue], dest *Vertex[TValue], weight uint, tag *string) error

AddEdge creates a directed edge from src->dest with a non-zero weight and an optional tag. Supply `nil` if there's no tag.

func (*Graph[TValue]) AddSymmetricEdge

func (g *Graph[TValue]) AddSymmetricEdge(src, dest *Vertex[TValue], weight uint, tag *string) error

AddSymmetricEdge creates an edge from src->dest and dest->src with the same weight for both directions

func (*Graph[TValue]) AddVertex

func (g *Graph[TValue]) AddVertex(v *Vertex[TValue])

AddVertex adds a vertex to the graph without any edges. If the vertex already exists, no action is taken.

func (*Graph[TValue]) ContainsEdge

func (g *Graph[TValue]) ContainsEdge(src, dest *Vertex[TValue], tag *string) bool

ContainsEdge checks if the graph contains the edge src->dest

func (*Graph[TValue]) ContainsSymmetricEdge

func (g *Graph[TValue]) ContainsSymmetricEdge(src, dest *Vertex[TValue], tag *string) bool

ContainsSymmetricEdge checks if the graph contains an edge in both directions AND if that edge has the same weight in both directions.

func (*Graph[TValue]) ContainsVertex

func (g *Graph[TValue]) ContainsVertex(v *Vertex[TValue]) bool

ContainsVertex checks if the graph contains a vertex

func (*Graph[TValue]) GetEdge

func (g *Graph[TValue]) GetEdge(src, dest *Vertex[TValue], tag *string) (WeightedEdge[TValue], error)

GetEdge retrieves an edge from the graph.

func (*Graph[TValue]) RemoveEdge

func (g *Graph[TValue]) RemoveEdge(src, dest *Vertex[TValue], tag *string)

RemoveEdge removes only the edge src->dest. It will not remove dest->src

func (*Graph[TValue]) RemoveSymmetricEdge

func (g *Graph[TValue]) RemoveSymmetricEdge(src, dest *Vertex[TValue], tag *string)

RemoveSymmetricEdge removes src->dest and dest->src

func (*Graph[TValue]) ShortestPath

func (g *Graph[TValue]) ShortestPath(src, dest *Vertex[TValue]) ([]PathEdge[TValue], error)

ShortestPath is an implementation of Dijkstra's algorithm for a single src->dest route.

type PathEdge

type PathEdge[TValue comparable] struct {
	Source      *Vertex[TValue]
	Destination *Vertex[TValue]
	Weight      uint
	Tag         *string
}

func (PathEdge[TValue]) String

func (pe PathEdge[TValue]) String() string

type Vertex

type Vertex[TValue comparable] struct {
	// contains filtered or unexported fields
}

func (*Vertex[TValue]) String

func (n *Vertex[TValue]) String() string

type WeightedEdge

type WeightedEdge[TValue comparable] interface {
	Destination() TValue
	Weight() uint
	Tag() *string
}