graph

Documentation

Index

• func EncodeDOT[V Vertex](g *Graph[V], w io.Writer, sortVertices bool) error
• func IsLowerPriorityFromGetPriority[V Vertex, P Ordered](getPriority func(V) P) func(V, V) bool
• type AdjacencyMatrix
• type Graph
  • func NewGraph[V Vertex]() *Graph[V]
  • func (g *Graph[V]) AddEdge(sourceId, targetId string) error
  • func (g *Graph[V]) AddVertex(v V)
  • func (g *Graph[V]) Copy() *Graph[V]
  • func (g *Graph[V]) GetVertex(id string) V
  • func (g *Graph[V]) HasVertexWithId(id string) bool
  • func (g *Graph[V]) Reverse()
  • func (g *Graph[V]) TopologicallySort() ([]V, error)
  • func (g *Graph[V]) TopologicallySortWithPriority(isLowerPriority func(V, V) bool) ([]V, error)
  • func (g *Graph[V]) Union(new *Graph[V], merge func(old, new V) V) error
• type Ordered
• type Vertex

Functions

func EncodeDOT

func EncodeDOT[V Vertex](g *Graph[V], w io.Writer, sortVertices bool) error

EncodeDOT encodes a graph in DOT format to enable visualization of the graph

func IsLowerPriorityFromGetPriority

func IsLowerPriorityFromGetPriority[V Vertex, P Ordered](getPriority func(V) P) func(V, V) bool

Types

type AdjacencyMatrix

type AdjacencyMatrix map[string]map[string]bool

type Graph

type Graph[V Vertex] struct {
	// contains filtered or unexported fields
}

Graph is a directed graph

func NewGraph

func NewGraph[V Vertex]() *Graph[V]

func (*Graph[V]) AddEdge

func (g *Graph[V]) AddEdge(sourceId, targetId string) error

AddEdge adds an edge to the graph. If the vertex doesn't exist, it will error

func (*Graph[V]) AddVertex

func (g *Graph[V]) AddVertex(v V)

AddVertex adds a vertex to the graph. If the vertex already exists, it will override it and keep the edges

func (*Graph[V]) Copy

func (g *Graph[V]) Copy() *Graph[V]

func (*Graph[V]) GetVertex

func (g *Graph[V]) GetVertex(id string) V

func (*Graph[V]) HasVertexWithId

func (g *Graph[V]) HasVertexWithId(id string) bool

func (*Graph[V]) Reverse

func (g *Graph[V]) Reverse()

Reverse reverses the edges of the map. The sources become the sinks and vice versa.

func (*Graph[V]) TopologicallySort

func (g *Graph[V]) TopologicallySort() ([]V, error)

func (*Graph[V]) TopologicallySortWithPriority

func (g *Graph[V]) TopologicallySortWithPriority(isLowerPriority func(V, V) bool) ([]V, error)

TopologicallySortWithPriority returns a consistent topological sort of the graph taking a greedy approach to put high priority sources first. The output is deterministic. getPriority must be deterministic

func (*Graph[V]) Union

func (g *Graph[V]) Union(new *Graph[V], merge func(old, new V) V) error

Union unions the graph with a new graph. If a vertex exists in both graphs, it uses the merge function to determine what the new vertex is

type Ordered

type Ordered interface {
	~int | ~string
}

type Vertex

type Vertex interface {
	GetId() string
}