gograph

README

GoGraph

GoGraph is a generic graph library for Go with first-class support for dependency graphs. Acyclic graphs refuse edges that would create a cycle, and TopologySort gives you an order to run things in. It also covers traversal, shortest paths, strongly connected components and graph partitioning, with no dependencies outside the standard library.

• Generic: vertex labels can be any comparable type, such as strings, integers or your own structs.
• Dependency graphs: Acyclic() graphs reject cycles, TopologySort returns a valid order, and the dag package finds what depends on what.
• Traversal: BFS, DFS, topological, closest-first and random-walk iterators.
• Paths: Dijkstra, Bellman-Ford, Floyd-Warshall and transitive reduction.
• Connectivity: strongly connected components with Tarjan, Kosaraju and Gabow.
• Partitioning: maximal cliques (Bron-Kerbosch), Girvan-Newman communities and randomized k-cut.
• Diagrams: encoding/mermaid writes a graph as a Mermaid flowchart that GitHub renders in Markdown.

Imported by 20+ public Go modules.

Quick start

go get github.com/hmdsefi/gograph

package main

import (
	"errors"
	"fmt"

	"github.com/hmdsefi/gograph"
)

func main() {
	// An edge A -> B means A has to happen before B.
	g := gograph.New[string](gograph.Acyclic())

	checkout := g.AddVertexByLabel("checkout")
	build := g.AddVertexByLabel("build")
	test := g.AddVertexByLabel("test")
	release := g.AddVertexByLabel("release")

	_, _ = g.AddEdge(checkout, build)
	_, _ = g.AddEdge(build, test)
	_, _ = g.AddEdge(test, release)

	// Acyclic graphs reject any edge that would create a cycle.
	_, err := g.AddEdge(release, checkout)
	fmt.Println(errors.Is(err, gograph.ErrDAGCycle)) // true

	order, _ := gograph.TopologySort(g)
	for _, v := range order {
		fmt.Println(v.Label()) // checkout, build, test, release
	}
}

When several orders are valid, TopologySort follows the order the vertices and edges were added, so the same graph gives the same result on every run. To choose the order yourself, StableTopologySort takes a compare function such as cmp.Compare and always picks the smallest vertex that is ready.

GetAllVertices returns vertices in the order they were added, and AllEdges and EdgesOf follow the same order. Tarjan, Kosaraju, Gabow, MaximalCliques, GirvanNewman and TransitiveReduction give the same result on every run for a graph built the same way.

Table of contents

• Graphs
  • Directed
  • Acyclic
  • Undirected
  • Weighted
• Traversal
• Algorithms
• Examples
• Roadmap
• Contributing
• License

Graphs

gograph.New[T] creates a graph. T is the vertex label type and must be comparable, so slices, maps and functions can't be labels. Options choose the kind of graph:

• gograph.Directed() creates a directed graph. Without it, graphs are undirected.
• gograph.Acyclic() creates a directed graph that rejects edges that would create a cycle.
• gograph.Weighted() marks the graph as weighted. BellmanFord and FloydWarshall require it.

Every graph implements the Graph[T] interface. See the package documentation for the full list of methods.

AddEdge creates missing vertices, so gograph.NewVertex is enough for quick examples. To keep a reference to a vertex, use AddVertexByLabel, which adds the vertex and returns it.

Directed

g := gograph.New[int](gograph.Directed())

_, _ = g.AddEdge(gograph.NewVertex(1), gograph.NewVertex(2))
_, _ = g.AddEdge(gograph.NewVertex(1), gograph.NewVertex(3))
_, _ = g.AddEdge(gograph.NewVertex(2), gograph.NewVertex(2))
_, _ = g.AddEdge(gograph.NewVertex(3), gograph.NewVertex(4))
_, _ = g.AddEdge(gograph.NewVertex(4), gograph.NewVertex(5))
_, _ = g.AddEdge(gograph.NewVertex(5), gograph.NewVertex(6))

Acyclic

g := gograph.New[int](gograph.Acyclic())

_, _ = g.AddEdge(gograph.NewVertex(1), gograph.NewVertex(2))
_, _ = g.AddEdge(gograph.NewVertex(2), gograph.NewVertex(3))

_, err := g.AddEdge(gograph.NewVertex(3), gograph.NewVertex(1))
fmt.Println(err) // edges would create cycle

Undirected

// Graphs are undirected by default.
g := gograph.New[string]()

a := g.AddVertexByLabel("A")
b := g.AddVertexByLabel("B")
c := g.AddVertexByLabel("C")
d := g.AddVertexByLabel("D")

_, _ = g.AddEdge(a, b)
_, _ = g.AddEdge(a, d)
_, _ = g.AddEdge(b, c)
_, _ = g.AddEdge(b, d)

// Every undirected edge can be followed both ways.
fmt.Println(g.ContainsEdge(a, b), g.ContainsEdge(b, a)) // true true

Weighted

g := gograph.New[string](gograph.Weighted())

a := g.AddVertexByLabel("A")
b := g.AddVertexByLabel("B")
c := g.AddVertexByLabel("C")
d := g.AddVertexByLabel("D")

_, _ = g.AddEdge(a, b, gograph.WithEdgeWeight(4))
_, _ = g.AddEdge(a, d, gograph.WithEdgeWeight(3))
_, _ = g.AddEdge(b, c, gograph.WithEdgeWeight(3))
_, _ = g.AddEdge(b, d, gograph.WithEdgeWeight(1))
_, _ = g.AddEdge(c, d, gograph.WithEdgeWeight(2))

dist := path.Dijkstra(g, "A")
fmt.Println(dist["C"]) // 5

Vertices can have weights too:

g := gograph.New[string](gograph.Directed(), gograph.Weighted())

a := g.AddVertexByLabel("A", gograph.WithVertexWeight(3))
b := g.AddVertexByLabel("B", gograph.WithVertexWeight(2))
c := g.AddVertexByLabel("C", gograph.WithVertexWeight(4))

_, _ = g.AddEdge(a, b)
_, _ = g.AddEdge(b, c)

fmt.Println(a.Weight(), b.Weight(), c.Weight()) // 3 2 4

Traversal

The traverse package provides iterators that all implement the same interface:

type Iterator[T comparable] interface {
	HasNext() bool
	Next() *gograph.Vertex[T]
	Iterate(func(v *gograph.Vertex[T]) error) error
	Reset()
}

g := gograph.New[string](gograph.Directed())

_, _ = g.AddEdge(gograph.NewVertex("A"), gograph.NewVertex("B"))
_, _ = g.AddEdge(gograph.NewVertex("A"), gograph.NewVertex("C"))
_, _ = g.AddEdge(gograph.NewVertex("B"), gograph.NewVertex("D"))

it, err := traverse.NewBreadthFirstIterator(g, "A")
if err != nil {
	fmt.Println(err)
	return
}

for it.HasNext() {
	fmt.Println(it.Next().Label()) // A, B, C, D
}

Available iterators:

• Breadth-first
• Depth-first
• Topological
• Closest-first
• Random walk

Algorithms

• Ordering: gograph.TopologySort (Kahn's algorithm) and gograph.StableTopologySort (smallest ready vertex first).
• Shortest paths (path package): Dijkstra, Bellman-Ford, Floyd-Warshall.
• Transitive reduction (path package): TransitiveReduction.
• Dependencies (dag package): Descendants (what depends on a vertex), Ancestors (what it depends on) and Affected (what a change reaches).
• Strongly connected components (connectivity package): Tarjan, Kosaraju and Gabow.
• Partitioning (partition package): maximal cliques (Bron-Kerbosch), Girvan-Newman, randomized k-cut.

Examples

• gomodgraph: loads go mod graph output and finds requirement cycles, the modules that depend on a module, why a module is needed, and what changed between two versions of go.mod.

Roadmap

Planned work, in the order it's likely to land, is tracked in #136. Issues labeled good first issue are a good place to start.

Contributing

Contributions are welcome. Please read CONTRIBUTING.md before opening a pull request. The README examples are also Go examples in example_test.go, so go test ./... checks that they still compile and print what they claim.

License

Apache License 2.0, see LICENSE for details.

Documentation

Overview

Example

package main

import (
	"errors"
	"fmt"

	"github.com/hmdsefi/gograph"
)

func main() {
	// An edge A -> B means A has to happen before B.
	g := gograph.New[string](gograph.Acyclic())

	checkout := g.AddVertexByLabel("checkout")
	build := g.AddVertexByLabel("build")
	test := g.AddVertexByLabel("test")
	release := g.AddVertexByLabel("release")

	_, _ = g.AddEdge(checkout, build)
	_, _ = g.AddEdge(build, test)
	_, _ = g.AddEdge(test, release)

	// Acyclic graphs reject any edge that would create a cycle.
	_, err := g.AddEdge(release, checkout)
	fmt.Println(errors.Is(err, gograph.ErrDAGCycle))

	order, _ := gograph.TopologySort(g)
	for _, v := range order {
		fmt.Println(v.Label())
	}

}

Output:
true
checkout
build
test
release

Example (BreadthFirst)

package main

import (
	"fmt"

	"github.com/hmdsefi/gograph"
	"github.com/hmdsefi/gograph/traverse"
)

func main() {
	g := gograph.New[string](gograph.Directed())

	_, _ = g.AddEdge(gograph.NewVertex("A"), gograph.NewVertex("B"))
	_, _ = g.AddEdge(gograph.NewVertex("A"), gograph.NewVertex("C"))
	_, _ = g.AddEdge(gograph.NewVertex("B"), gograph.NewVertex("D"))

	it, err := traverse.NewBreadthFirstIterator(g, "A")
	if err != nil {
		fmt.Println(err)
		return
	}

	for it.HasNext() {
		fmt.Println(it.Next().Label())
	}

}

Output:
A
B
C
D

Index

• Variables
• type Edge
  • func NewEdge[T comparable](source *Vertex[T], dest *Vertex[T], options ...EdgeOptionFunc) *Edge[T]
  • func (e *Edge[T]) Destination() *Vertex[T]
  • func (e Edge[T]) Metadata() any
  • func (e *Edge[T]) OtherVertex(v T) *Vertex[T]
  • func (e *Edge[T]) Source() *Vertex[T]
  • func (e *Edge[T]) Weight() float64
• type EdgeOptionFunc
  • func WithEdgeWeight(weight float64) EdgeOptionFunc
• type EdgeProperties
• type Graph
  • func New[T comparable](options ...GraphOptionFunc) Graph[T]
• type GraphOptionFunc
  • func Acyclic() GraphOptionFunc
  • func Directed() GraphOptionFunc
  • func Weighted() GraphOptionFunc
• type GraphProperties
• type GraphType
• type Vertex
  • func NewVertex[T comparable](label T, options ...VertexOptionFunc) *Vertex[T]
  • func StableTopologySort[T comparable](g Graph[T], compare func(a, b T) int) ([]*Vertex[T], error)
  • func TopologySort[T comparable](g Graph[T]) ([]*Vertex[T], error)
  • func (v *Vertex[T]) Degree() int
  • func (v *Vertex[T]) HasNeighbor(vertex *Vertex[T]) bool
  • func (v *Vertex[T]) InDegree() int
  • func (v *Vertex[T]) Label() T
  • func (v *Vertex[T]) Metadata() any
  • func (v *Vertex[T]) NeighborByLabel(label T) *Vertex[T]
  • func (v *Vertex[T]) Neighbors() []*Vertex[T]
  • func (v *Vertex[T]) OutDegree() int
  • func (v *Vertex[T]) Weight() float64
• type VertexOptionFunc
  • func WithVertexWeight(weight float64) VertexOptionFunc
• type VertexProperties

Examples

• Package
• Package (BreadthFirst)
• New (Acyclic)
• New (Directed)
• New (Undirected)
• New (Weighted)
• StableTopologySort
• WithVertexWeight

Variables

var (
	ErrNilVertices        = errors.New("vertices are nil")
	ErrVertexDoesNotExist = errors.New("vertex does not exist")
	ErrEdgeAlreadyExists  = errors.New("edge already exists")
	ErrDAGCycle           = errors.New("edges would create cycle")
	ErrDAGHasCycle        = errors.New("the graph contains a cycle")
	ErrNotDirected        = errors.New("graph is not directed")
)

Types

type Edge

type Edge[T comparable] struct {
	// contains filtered or unexported fields
}

Edge represents an edges in a graph. It contains start and end points.

func NewEdge

func NewEdge[T comparable](source *Vertex[T], dest *Vertex[T], options ...EdgeOptionFunc) *Edge[T]

func (*Edge[T]) Destination

func (e *Edge[T]) Destination() *Vertex[T]

Destination returns edge dest vertex

func (Edge[T]) Metadata

func (e Edge[T]) Metadata() any

Metadata returns the metadata associated with the edge.

func (*Edge[T]) OtherVertex

func (e *Edge[T]) OtherVertex(v T) *Vertex[T]

OtherVertex accepts the label of one the vertices of the edge and returns the other one. If the input label doesn't match to either of the vertices, returns nil.

func (*Edge[T]) Source

func (e *Edge[T]) Source() *Vertex[T]

Source returns edge source vertex

func (*Edge[T]) Weight

func (e *Edge[T]) Weight() float64

Weight returns the weight of the edge.

type EdgeOptionFunc

type EdgeOptionFunc func(properties *EdgeProperties)

EdgeOptionFunc represent an alias of function type that modifies the specified edge properties.

func WithEdgeWeight

func WithEdgeWeight(weight float64) EdgeOptionFunc

WithEdgeWeight sets the edge weight for the specified edge properties in the returned EdgeOptionFunc.

type EdgeProperties

type EdgeProperties struct {
	// contains filtered or unexported fields
}

EdgeProperties represents the properties of an edge.

type Graph

type Graph[T comparable] interface {
	GraphType

	// AddEdge adds an edge from the vertex with the 'from' label to
	// the vertex with the 'to' label by appending the 'to' vertex to the
	// 'neighbors' slice of the 'from' vertex, in directed graph.
	//
	// In undirected graph, it also adds an edge from the vertex with
	// the 'to' label to the vertex with the 'from' label by appending
	// the 'from' vertex to the 'neighbors' slice of the 'to' vertex. it
	// means that it create the edges in both direction between the specified
	// vertices. A self-loop is stored once.
	//
	// This method accepts additional edge options such as weight and adds
	// them to the new edge.
	//
	//
	// It creates the input vertices if they don't exist in the graph, the
	// same way AddVertex does, so a vertex from another graph is copied.
	// If any of the specified vertices is nil, returns nil.
	// If edge already exist, returns error.
	AddEdge(from, to *Vertex[T], options ...EdgeOptionFunc) (*Edge[T], error)

	// GetAllEdges returns a slice of all edges connecting source vertex to
	// target vertex if such vertices exist in this graph.
	//
	// In directed graph, or if both vertices are the same, it returns a single edge.
	//
	// If any of the specified vertices is nil, returns nil.
	// If any of the vertices does not exist, returns nil.
	// If both vertices exist but no edges found, returns an empty set.
	GetAllEdges(from, to *Vertex[T]) []*Edge[T]

	// AllEdges returns all the edges in the graph. The edges are grouped by
	// source vertex in the order of GetAllVertices, and the edges of each
	// source vertex are in the order they were added. In an undirected
	// graph, each edge is stored in both directions, so it appears in the
	// group of both its vertices.
	AllEdges() []*Edge[T]

	// GetEdge returns an edge connecting source vertex to target vertex
	// if such vertices and such edge exist in this graph.
	//
	// In undirected graph, returns only the edge from the "from" vertex to
	// the "to" vertex.
	//
	// If any of the specified vertices is nil, returns nil.
	// If edge does not exist, returns nil.
	GetEdge(from, to *Vertex[T]) *Edge[T]

	// EdgesOf returns a slice of all edges touching the specified vertex.
	// If no edges are touching the specified vertex returns an empty slice.
	//
	// The edges that start from the vertex come first, in the order they
	// were added. The edges that end at the vertex follow, in the order of
	// their source vertices in GetAllVertices.
	//
	// If the input vertex is nil, returns nil.
	// If the input vertex does not exist, returns nil.
	EdgesOf(v *Vertex[T]) []*Edge[T]

	// RemoveEdges removes input edges from the graph from the specified
	// slice of edges, if they exist. In undirected graph, removes edges
	// in both directions.
	RemoveEdges(edges ...*Edge[T])

	// AddVertexByLabel adds a new vertex with the given label to the graph.
	// Label of the vertex is a comparable type. This method also accepts the
	// vertex properties such as weight.
	//
	// If there is a vertex with the same label in the graph, returns nil.
	// Otherwise, returns the created vertex.
	AddVertexByLabel(label T, options ...VertexOptionFunc) *Vertex[T]

	// AddVertex adds the input vertex to the graph. It doesn't add
	// vertex to the graph if the input vertex label is already exists
	// in the graph.
	//
	// A vertex belongs to one graph. If the input vertex has already been
	// added to a graph, including this one before it was removed, the graph
	// stores a copy with the same label, weight and metadata, and no edges.
	AddVertex(v *Vertex[T])

	// GetVertexByID returns the vertex with the input label.
	//
	// If vertex doesn't exist, returns nil.
	GetVertexByID(label T) *Vertex[T]

	// GetAllVerticesByID returns a slice of vertices with the specified label list.
	//
	// If vertex doesn't exist, doesn't add nil to the output list.
	GetAllVerticesByID(label ...T) []*Vertex[T]

	// GetAllVertices returns a slice of all existing vertices in the graph,
	// in the order they were added. A vertex that is removed and added
	// again moves to the end.
	GetAllVertices() []*Vertex[T]

	// RemoveVertices removes all the specified vertices from this graph including
	// all its touching edges if present.
	RemoveVertices(vertices ...*Vertex[T])

	// ContainsEdge returns 'true' if and only if this graph contains an edge
	// going from the source vertex to the target vertex.
	//
	// If any of the specified vertices does not exist in the graph, or if is nil,
	// returns 'false'.
	ContainsEdge(from, to *Vertex[T]) bool

	// ContainsVertex returns 'true' if this graph contains the specified vertex.
	//
	// If the specified vertex is nil, returns 'false'.
	ContainsVertex(v *Vertex[T]) bool

	// Order returns the number of vertices in the graph.
	Order() uint32

	// Size returns the number of edges in the graph
	Size() uint32
}

Graph defines methods for managing a graph with vertices and edges. It is the base interface in the graph hierarchy. Each graph object contains a set of vertices and edges.

Through generics, a graph can be typed to specific classes for vertices' label T.

func New

func New[T comparable](options ...GraphOptionFunc) Graph[T]

New creates a new instance of base graph that implemented the Graph interface.

Example (Acyclic)

package main

import (
	"fmt"

	"github.com/hmdsefi/gograph"
)

func main() {
	g := gograph.New[int](gograph.Acyclic())

	_, _ = g.AddEdge(gograph.NewVertex(1), gograph.NewVertex(2))
	_, _ = g.AddEdge(gograph.NewVertex(2), gograph.NewVertex(3))

	_, err := g.AddEdge(gograph.NewVertex(3), gograph.NewVertex(1))
	fmt.Println(err)

}

Output:
edges would create cycle

Example (Directed)

package main

import (
	"fmt"

	"github.com/hmdsefi/gograph"
)

func main() {
	g := gograph.New[int](gograph.Directed())

	_, _ = g.AddEdge(gograph.NewVertex(1), gograph.NewVertex(2))
	_, _ = g.AddEdge(gograph.NewVertex(1), gograph.NewVertex(3))
	_, _ = g.AddEdge(gograph.NewVertex(2), gograph.NewVertex(2))
	_, _ = g.AddEdge(gograph.NewVertex(3), gograph.NewVertex(4))
	_, _ = g.AddEdge(gograph.NewVertex(4), gograph.NewVertex(5))
	_, _ = g.AddEdge(gograph.NewVertex(5), gograph.NewVertex(6))

	fmt.Println(g.Order(), g.Size())

}

Output:
6 6

Example (Undirected)

package main

import (
	"fmt"

	"github.com/hmdsefi/gograph"
)

func main() {
	// Graphs are undirected by default.
	g := gograph.New[string]()

	a := g.AddVertexByLabel("A")
	b := g.AddVertexByLabel("B")
	c := g.AddVertexByLabel("C")
	d := g.AddVertexByLabel("D")

	_, _ = g.AddEdge(a, b)
	_, _ = g.AddEdge(a, d)
	_, _ = g.AddEdge(b, c)
	_, _ = g.AddEdge(b, d)

	// Every undirected edge can be followed both ways.
	fmt.Println(g.ContainsEdge(a, b), g.ContainsEdge(b, a))

}

Output:
true true

Example (Weighted)

package main

import (
	"fmt"

	"github.com/hmdsefi/gograph"
	"github.com/hmdsefi/gograph/path"
)

func main() {
	g := gograph.New[string](gograph.Weighted())

	a := g.AddVertexByLabel("A")
	b := g.AddVertexByLabel("B")
	c := g.AddVertexByLabel("C")
	d := g.AddVertexByLabel("D")

	_, _ = g.AddEdge(a, b, gograph.WithEdgeWeight(4))
	_, _ = g.AddEdge(a, d, gograph.WithEdgeWeight(3))
	_, _ = g.AddEdge(b, c, gograph.WithEdgeWeight(3))
	_, _ = g.AddEdge(b, d, gograph.WithEdgeWeight(1))
	_, _ = g.AddEdge(c, d, gograph.WithEdgeWeight(2))

	dist := path.Dijkstra(g, "A")
	fmt.Println(dist["C"])

}

Output:
5

type GraphOptionFunc

type GraphOptionFunc func(properties *GraphProperties)

GraphOptionFunc represent an alias of function type that modifies the specified graph properties.

func Acyclic

func Acyclic() GraphOptionFunc

Acyclic returns a GraphOptionFunc that modifies the specified graph properties. It sets the isAcyclic and isDirected to true. Only direct graph can be acyclic.

func Directed

func Directed() GraphOptionFunc

Directed returns a GraphOptionFunc that modifies the specified graph properties. It sets the isDirected to true.

func Weighted

func Weighted() GraphOptionFunc

Weighted returns a GraphOptionFunc that modifies the specified graph properties. It sets the isWeighted to true.

type GraphProperties

type GraphProperties struct {
	// contains filtered or unexported fields
}

GraphProperties represents the properties of a graph.

type GraphType

type GraphType interface {
	// IsDirected returns true if the graph is directed, false otherwise.
	IsDirected() bool

	// IsAcyclic returns true if the graph is acyclic, false otherwise.
	IsAcyclic() bool

	// IsWeighted returns true if the graph is weighted, false otherwise.
	IsWeighted() bool
}

GraphType defines methods to determine the type of graph. A graph can have multiple types. e.g., a directed graph can be a weighted or acyclic.

type Vertex

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

Vertex represents a node or point in a graph

func NewVertex

func NewVertex[T comparable](label T, options ...VertexOptionFunc) *Vertex[T]

NewVertex creates a vertex with the given label and applies the options, such as WithVertexWeight, to it. The vertex doesn't belong to a graph until it's added with AddVertex or AddEdge.

func StableTopologySort

func StableTopologySort[T comparable](g Graph[T], compare func(a, b T) int) ([]*Vertex[T], error)

StableTopologySort performs a topological sort of the graph that picks, at every step, the smallest vertex with no incoming edges left, using compare on the labels. compare returns a negative number if a < b, zero if a == b and a positive number if a > b, so cmp.Compare works for string and number labels.

If compare only returns zero for equal labels, the result doesn't depend on the order the vertices and edges were added. As in TopologySort, an edge from A to B puts A before B.

It returns ErrDAGHasCycle if the graph has a cycle. It runs in O((V + E) log V) time.

Example

package main

import (
	"cmp"
	"fmt"

	"github.com/hmdsefi/gograph"
)

func main() {
	g := gograph.New[string](gograph.Acyclic())

	// "lint" and "build" have no dependencies, so either can go first.
	lint := g.AddVertexByLabel("lint")
	build := g.AddVertexByLabel("build")
	test := g.AddVertexByLabel("test")

	_, _ = g.AddEdge(lint, test)
	_, _ = g.AddEdge(build, test)

	labels := func(vertices []*gograph.Vertex[string]) []string {
		out := make([]string, len(vertices))
		for i, v := range vertices {
			out[i] = v.Label()
		}
		return out
	}

	// TopologySort follows the order the vertices were added.
	order, _ := gograph.TopologySort(g)
	fmt.Println(labels(order))

	// With cmp.Compare, the smallest ready label always comes first.
	order, _ = gograph.StableTopologySort(g, cmp.Compare[string])
	fmt.Println(labels(order))

}

Output:
[lint build test]
[build lint test]

func TopologySort

func TopologySort[T comparable](g Graph[T]) ([]*Vertex[T], error)

TopologySort performs a topological sort of the graph using Kahn's algorithm. If the sorted list of vertices does not contain all vertices in the graph, it means there is a cycle in the graph.

The order is stable: it only depends on the order of GetAllVertices and the order the edges were added, so a graph built the same way gives the same result on every run. Use StableTopologySort to choose the order of the vertices that the edges don't order.

It returns error if it finds a cycle in the graph.

func (*Vertex[T]) Degree

func (v *Vertex[T]) Degree() int

Degree returns the total degree of the vertex which is the sum of in and out degrees.

func (*Vertex[T]) HasNeighbor

func (v *Vertex[T]) HasNeighbor(vertex *Vertex[T]) bool

HasNeighbor checks if the input vertex is the neighbor of the current node or not. It returns 'true' if it finds the input in the neighbors. Otherwise, or if the input is nil, returns 'false'.

func (*Vertex[T]) InDegree

func (v *Vertex[T]) InDegree() int

InDegree returns the number of incoming edges to the current vertex.

func (*Vertex[T]) Label

func (v *Vertex[T]) Label() T

Label returns vertex label.

func (*Vertex[T]) Metadata

func (v *Vertex[T]) Metadata() any

Metadata returns the metadata associated with the vertex.

func (*Vertex[T]) NeighborByLabel

func (v *Vertex[T]) NeighborByLabel(label T) *Vertex[T]

NeighborByLabel iterates over the neighbor slice and returns the vertex which its label is equal to the input label.

It returns nil if there is no neighbor with that label.

func (*Vertex[T]) Neighbors

func (v *Vertex[T]) Neighbors() []*Vertex[T]

Neighbors returns a copy of neighbor slice. If the caller changed the result slice, it won't impact the graph or the vertex.

func (*Vertex[T]) OutDegree

func (v *Vertex[T]) OutDegree() int

OutDegree returns the number of outgoing edges to the current vertex.

func (*Vertex[T]) Weight

func (v *Vertex[T]) Weight() float64

Weight returns vertex label.

type VertexOptionFunc

type VertexOptionFunc func(properties *VertexProperties)

VertexOptionFunc represent an alias of function type that modifies the specified vertex properties.

func WithVertexWeight

func WithVertexWeight(weight float64) VertexOptionFunc

WithVertexWeight sets the edge weight for the specified vertex properties in the returned VertexOptionFunc.

Example

package main

import (
	"fmt"

	"github.com/hmdsefi/gograph"
)

func main() {
	g := gograph.New[string](gograph.Directed(), gograph.Weighted())

	a := g.AddVertexByLabel("A", gograph.WithVertexWeight(3))
	b := g.AddVertexByLabel("B", gograph.WithVertexWeight(2))
	c := g.AddVertexByLabel("C", gograph.WithVertexWeight(4))

	_, _ = g.AddEdge(a, b)
	_, _ = g.AddEdge(b, c)

	fmt.Println(a.Weight(), b.Weight(), c.Weight())

}

Output:
3 2 4

type VertexProperties

type VertexProperties struct {
	// contains filtered or unexported fields
}

VertexProperties represents the properties of an edge.