Documentation
¶
Index ¶
- Variables
- type Graph
- func (g *Graph[T]) AddEdge(fromKey, toKey string)
- func (g *Graph[T]) AddVertex(key string, value T)
- func (g *Graph[T]) ExportToGraphviz(filename string) error
- func (g *Graph[T]) Print()
- func (g *Graph[T]) SortedKeys() []string
- func (g *Graph[T]) TopologicalSort() ([]*Vertex[T], []string, error)
- func (g *Graph[T]) VerticesWithNoIncomingEdges() []*Vertex[T]
- type Vertex
Constants ¶
This section is empty.
Variables ¶
var ErrCycle = errors.New("graph has a cycle")
ErrCycle is returned by TopologicalSort when the graph has a cycle.
Functions ¶
This section is empty.
Types ¶
type Graph ¶
type Graph[T any] struct { Vertices map[string]*Vertex[T] // Map of Vertices in the graph. IncomingEdges map[string]int // Map of incoming edge counts per vertex. Edges map[string][]*Vertex[T] // Map of Edges represented as adjacency lists. }
Graph represents a generic graph structure with Vertices of any type. It includes maps for Vertices, incoming Edges, and Edges for efficient graph operations.
func (*Graph[T]) AddEdge ¶
AddEdge adds a directed edge from one vertex to another. If either vertex does not exist, it logs a warning and does not add the edge.
func (*Graph[T]) AddVertex ¶
AddVertex adds a new vertex with the specified key and value to the graph. If the vertex already exists, it logs a warning and does not overwrite it.
func (*Graph[T]) ExportToGraphviz ¶
func (*Graph[T]) SortedKeys ¶
SortedKeys returns the keys of all vertices in lexical order, so callers that iterate the graph produce the same output on every run.
func (*Graph[T]) TopologicalSort ¶
TopologicalSort returns the vertices ordered so that every vertex comes after all vertices with an edge into it. Ties are broken by key, so the order is deterministic. When the graph has a cycle, it returns ErrCycle and the keys of the vertices that are part of (or depend on) the cycle.
func (*Graph[T]) VerticesWithNoIncomingEdges ¶
VerticesWithNoIncomingEdges returns a list of Vertices with no incoming Edges.
type Vertex ¶
type Vertex[T any] struct { Key string // Unique identifier of the vertex. Value T // Value stored in the vertex. // contains filtered or unexported fields }
Vertex represents a node in a graph with a key and a value. It also holds a reference to the graph it belongs to for graph operations.
Source Files