graph

Documentation

Overview

Package graph provides functionality for directed graphs.

Index

• type Edge
• type Graph
  • func New[V comparable](vertices ...V) *Graph[V]
  • func (g *Graph[V]) Add(edge Edge[V])
  • func (g *Graph[V]) InDegree(vtx V) int
  • func (g *Graph[V]) IsAcyclic() ([]V, bool)
  • func (g *Graph[V]) Neighbors(vtx V) []V
  • func (g *Graph[V]) Remove(edge Edge[V])
  • func (g *Graph[V]) Roots() []V
• type TopologicalSorter
  • func TopologicalOrder[V comparable](digraph *Graph[V]) (*TopologicalSorter[V], error)
  • func (alg *TopologicalSorter[V]) Rank(vtx V) (int, bool)

Types

type Edge

type Edge[V comparable] struct {
	From V
	To   V
}

Edge represents one edge of a directed graph.

type Graph

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

Graph represents a directed graph.

func New

func New[V comparable](vertices ...V) *Graph[V]

New initiates a new Graph.

func (*Graph[V]) Add

func (g *Graph[V]) Add(edge Edge[V])

Add adds a connection between two vertices.

func (*Graph[V]) InDegree

func (g *Graph[V]) InDegree(vtx V) int

InDegree returns the number of incoming edges to vtx.

func (*Graph[V]) IsAcyclic

func (g *Graph[V]) IsAcyclic() ([]V, bool)

IsAcyclic checks if the graph is acyclic. If not, return the first detected cycle.

func (*Graph[V]) Neighbors

func (g *Graph[V]) Neighbors(vtx V) []V

Neighbors returns the list of connected vertices from vtx.

func (*Graph[V]) Remove

func (g *Graph[V]) Remove(edge Edge[V])

Remove deletes a connection between two vertices.

func (*Graph[V]) Roots

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

Roots returns a slice of vertices with no incoming edges.

type TopologicalSorter

type TopologicalSorter[V comparable] struct {
	// contains filtered or unexported fields
}

TopologicalSorter ranks vertices using Kahn's algorithm: https://en.wikipedia.org/wiki/Topological_sorting#Kahn's_algorithm However, if two vertices can be scheduled in parallel then the same rank is returned.

func TopologicalOrder

func TopologicalOrder[V comparable](digraph *Graph[V]) (*TopologicalSorter[V], error)

TopologicalOrder determines whether the directed graph is acyclic, and if so then finds a topological-order, or a linear order, of the vertices. Note that this function will modify the original graph.

If there is an edge from vertex V to U, then V must happen before U and results in rank of V < rank of U. When there are ties (two vertices can be scheduled in parallel), the vertices are given the same rank. If the digraph contains a cycle, then an error is returned.

An example graph and their ranks is shown below to illustrate: . ├── a rank: 0 │ ├── c rank: 1 │ │ └── f rank: 2 │ └── d rank: 1 └── b rank: 0

└── e      rank: 1

func (*TopologicalSorter[V]) Rank

func (alg *TopologicalSorter[V]) Rank(vtx V) (int, bool)

Rank returns the order of the vertex. The smallest order starts at 0. The second boolean return value is used to indicate whether the vertex exists in the graph.