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
- type Vertex
- type WeightedEdge
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
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 ¶
AddSymmetricEdge creates an edge from src->dest and dest->src with the same weight for both directions
func (*Graph[TValue]) AddVertex ¶
AddVertex adds a vertex to the graph without any edges. If the vertex already exists, no action is taken.
func (*Graph[TValue]) ContainsEdge ¶
ContainsEdge checks if the graph contains the edge src->dest
func (*Graph[TValue]) ContainsSymmetricEdge ¶
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 ¶
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 ¶
RemoveEdge removes only the edge src->dest. It will not remove dest->src
func (*Graph[TValue]) RemoveSymmetricEdge ¶
RemoveSymmetricEdge removes src->dest and dest->src
type PathEdge ¶
type PathEdge[TValue comparable] struct { Source *Vertex[TValue] Destination *Vertex[TValue] Weight uint Tag *string }
type Vertex ¶
type Vertex[TValue comparable] struct { // contains filtered or unexported fields }
type WeightedEdge ¶
type WeightedEdge[TValue comparable] interface { Destination() TValue Weight() uint Tag() *string }
Source Files