graph

package module
v1.0.1 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Apr 19, 2024 License: BSD-2-Clause Imports: 9 Imported by: 2

README

go-graph

Build Status Go Reference Go Report Card codecov

A simple and generic library for working with Graphs in Go.

Example Directed Graph

Installation

Execute the following command.

go get -v gopkg.in/dnaeon/go-graph.v1

Usage

Consider the following undirected graph.

Example Undirected Graph

This snippet creates the graph and performs DFS traversal on it.

package main

import (
	"fmt"

	"gopkg.in/dnaeon/go-graph.v1"
)

func main() {
	g := graph.New[int](graph.KindUndirected)
	g.AddEdge(1, 2)
	g.AddEdge(1, 3)
	g.AddEdge(2, 4)
	g.AddEdge(3, 4)
	g.AddEdge(4, 5)

	walker := func(v *graph.Vertex[int]) error {
		fmt.Println(v.Value)
		return nil
	}

	fmt.Printf("DFS (pre-order) from (1):\n")
	if err := graph.WalkPreOrderDFS(g, 1, walker); err != nil {
		fmt.Printf("DFS (pre-order): %s\n", err)
	}

	fmt.Printf("\nDFS (pre-order) from (3):\n")
	if err := graph.WalkPreOrderDFS(g, 3, walker); err != nil {
		fmt.Printf("DFS (pre-order): %s\n", err)
	}

	fmt.Printf("\nDFS (post-order) from (1):\n")
	if err := graph.WalkPostOrderDFS(g, 1, walker); err != nil {
		fmt.Printf("DFS (pre-order): %s\n", err)
	}

	fmt.Printf("\nDFS (post-order) from (3):\n")
	if err := graph.WalkPostOrderDFS(g, 3, walker); err != nil {
		fmt.Printf("DFS (post-order): %s\n", err)
	}
}

This example creates a directed graph, and then walks over the vertices in topological order.

Example Directed Graph

package main

import (
	"fmt"

	"gopkg.in/dnaeon/go-graph.v1"
)

func main() {
	g := graph.New[int](graph.KindDirected)
	g.AddEdge(1, 2)
	g.AddEdge(1, 3)
	g.AddEdge(2, 4)
	g.AddEdge(3, 4)
	g.AddEdge(4, 5)

	walker := func(v *graph.Vertex[int]) error {
		fmt.Println(v.Value)
		return nil
	}

	fmt.Println("Topo order:")
	if err := graph.WalkTopoOrder(g, walker); err != nil {
		fmt.Printf("WalkTopoOrder: %s\n", err)
	}
}

Output from above code looks like this.

Topo order:
5
4
3
2
1

Generate the Dot representation for a graph.

The following code generates the Dot representation of the directed graph used in the previous example.

package main

import (
	"fmt"
	"os"

	"gopkg.in/dnaeon/go-graph.v1"
)

func main() {
	g := graph.New[int](graph.KindDirected)
	g.AddEdge(1, 2)
	g.AddEdge(1, 3)
	g.AddEdge(2, 4)
	g.AddEdge(3, 4)
	g.AddEdge(4, 5)

	if err := graph.WriteDot(g, os.Stdout); err != nil {
		fmt.Println(err)
	}
}

Consider the following undirected weighted graph. The edges in this graph represent the distance between vertices in the graph.

Example Undirected Weighted Graph

The following code will print the shortest path between the given source and destination vertices, then paint the visited vertices in green, and finally print the Dot representation of the graph.

package main

import (
	"fmt"
	"os"

	"gopkg.in/dnaeon/go-graph.v1"
)

func main() {
	g := graph.New[int](graph.KindUndirected)
	g.AddWeightedEdge(1, 2, 2)
	g.AddWeightedEdge(1, 3, 6)
	g.AddWeightedEdge(2, 3, 7)
	g.AddWeightedEdge(2, 4, 3)
	g.AddWeightedEdge(3, 4, 4)
	g.AddWeightedEdge(4, 5, 9)
	g.AddWeightedEdge(5, 6, 11)
	g.AddWeightedEdge(5, 7, 4)
	g.AddWeightedEdge(6, 7, 6)
	g.AddWeightedEdge(6, 8, 5)
	g.AddWeightedEdge(7, 8, 8)

	var prev *graph.Vertex[int]
	walker := func(v *graph.Vertex[int]) error {
		// Paint vertices, which form the shortest path in
		// green
		v.DotAttributes["color"] = "green"
		v.DotAttributes["fillcolor"] = "green"

		if prev != nil {
			edge := g.GetEdge(prev.Value, v.Value)
			edge.DotAttributes["label"] = fmt.Sprintf("%d", int(v.DistanceFromSource))
		}

		prev = v

		fmt.Println(v.Value)
		return nil
	}

	fmt.Printf("Shortest path from (1) to (8):\n")
	if err := graph.WalkShortestPath(g, 1, 8, walker); err != nil {
		fmt.Println(err)
	}

	fmt.Printf("\nDot representation of graph:\n\n")
	if err := graph.WriteDot(g, os.Stdout); err != nil {
		fmt.Println(err)
	}
}

This is what the shortest path between vertices (1) and (8) looks like in Dot representation.

Example Undirected Weighted Graph - Painted

Make sure to also check the included test cases and examples directory from this repo.

Tests

Run the tests.

make test

License

go-graph is Open Source and licensed under the BSD License.

Documentation

Index

Constants

This section is empty.

Variables

View Source 
var DotDefaultEdgeAttributes = DotAttributes{
	"color": "black",
}

DotDefaultEdgeAttributes represents the map of default attributes to be applied for all edges when representing the graph in Dot format.

View Source 
var DotDefaultNodeAttributes = DotAttributes{
	"color":     "lightblue",
	"fillcolor": "lightblue",
	"fontcolor": "black",
	"shape":     "record",
	"style":     "filled, rounded",
}

DefaultNodeAttributes represents the map of default attributes to be applied for al nodes when representing the graph in Dot format.

View Source 
var ErrCycleDetected = errors.New("cycle detected")

ErrCycleDetected is returned whenever a cycle has been detected in the graph.

View Source 
var ErrIsNotDirectedGraph = errors.New("graph is not directed")

ErrIsNotDirectedGraph is returned whenever an operation cannot be performed, because the graph is not directed.

View Source 
var ErrStopWalking = errors.New("walking stopped")

ErrStopWalking is returned by WalkFunc to signal that further walking of the graph should be stopped.

Functions

func WalkBFS 

func WalkBFS[T comparable](g Graph[T], source T, walkFunc WalkFunc[T]) error

WalkBFS performs Breadth-first Search (BFS) traversal of the graph, starting from the given source vertex.

func WalkDijkstra 

func WalkDijkstra[T comparable](g Graph[T], source T, walkFunc WalkFunc[T]) error

WalkDijkstra implements Dijkstra's algorithm for finding the shortest-path from a given source vertex to all other vertices in the graph.

This method will pass each visited vertex while traversing the shortest path from the source vertex to each other vertex in the graph.

Note, that this method only constructs the shortest-path tree and yields each visited vertex. In order to stop walking the graph callers of this method should return ErrStopWalking error and refer to the shortest-path tree, or use the WalkShortestPath method.

func WalkPostOrderDFS 

func WalkPostOrderDFS[T comparable](g Graph[T], source T, walkFunc WalkFunc[T]) error

WalkPostOrderDFS performs post-order Depth-first Search (DFS) traversal of the graph, starting from the given source vertex.

func WalkPreOrderDFS 

func WalkPreOrderDFS[T comparable](g Graph[T], source T, walkFunc WalkFunc[T]) error

WalkPreOrderDFS performs pre-order Depth-first Search (DFS) traversal of the graph, starting from the given source vertex.

func WalkShortestPath 

func WalkShortestPath[T comparable](g Graph[T], source T, dest T, walkFunc WalkFunc[T]) error

WalkShortestPath yields the vertices which represent the shortest path between SOURCE and DEST.

func WalkTopoOrder 

func WalkTopoOrder[T comparable](g Graph[T], walkFunc WalkFunc[T]) error

WalkTopoOrder performs a topological sort and walks over the vertices in topological order.

In case a cycle exists in the graph, WalkTopoOrder will return ErrCycleDetected.

In case ErrCycleDetected is returned, the vertices which remained Gray are forming a cyclic path in the graph.

func WalkUnreachableVertices 

func WalkUnreachableVertices[T comparable](g Graph[T], source T, walkFunc WalkFunc[T]) error

WalkUnreachableVertices walks over the vertices which are unreachable from the given source vertex

func WriteDot 

func WriteDot[T comparable](g Graph[T], w io.Writer) error

WriteDot generates the Dot representation of the graph

Types

type Collector 

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

Collector provides an easy way to collect vertices while walking a graph

func NewCollector 

func NewCollector[T comparable]() *Collector[T]

NewCollector creates a new collector

func (*Collector[T]) Get 

func (c *Collector[T]) Get() []*Vertex[T]

Get returns the collected vertices

func (*Collector[T]) Reset 

func (c *Collector[T]) Reset()

Reset resets the set of collected vertices

func (*Collector[T]) WalkFunc 

func (c *Collector[T]) WalkFunc(v *Vertex[T]) error

WalkFunc collects the vertices it visits

type Color 

type Color int

Color represents the color with which a vertex is painted 

const (
	// White color means that the vertex has not been seen
	White Color = iota

	// Gray color means that the vertex is seen for the first time
	Gray

	// Black color means that the vertex has already been explored
	Black
)

type Degree 

type Degree struct {
	// The number of incoming edges
	In int

	// The number of outgoing edges
	Out int
}

Degree represents the number of incoming and outgoing edges of a vertex

type DirectedGraph 

type DirectedGraph[T comparable] struct {
	UndirectedGraph[T]
}

DirectedGraph represents a directed graph

func (*DirectedGraph[T]) AddEdge 

func (g *DirectedGraph[T]) AddEdge(from, to T) *Edge[T]

AddEdge adds an edge between two vertices in the graph

func (*DirectedGraph[T]) DeleteEdge 

func (g *DirectedGraph[T]) DeleteEdge(from, to T)

DeleteEdge deletes the edge, which connects the `from` and `to` vertices

func (*DirectedGraph[T]) DeleteVertex added in v1.0.1 

func (g *DirectedGraph[T]) DeleteVertex(v T)

DeleteVertex removes a vertex from the graph

func (*DirectedGraph[T]) EdgeExists 

func (g *DirectedGraph[T]) EdgeExists(from, to T) bool

EdgeExists returns a boolean indicating whether an edge between two vertices exists.

func (*DirectedGraph[T]) GetEdge 

func (g *DirectedGraph[T]) GetEdge(from, to T) *Edge[T]

GetEdge returns the edge connecting the two vertices

type DotAttributes 

type DotAttributes map[string]string

DotAttributes contains the map of key/value pairs, which can be associated with vertices and edges.

type Edge 

type Edge[T comparable] struct {
	// From represents the source vertex of the edge
	From T

	// To represents the destination vertex of the edge
	To T

	// Weight represents the edge weight
	Weight float64

	// DotAttributes represents the list of attributes associated
	// with the edge. The attributes will be used when
	// generating the Dot representation of the graph.
	DotAttributes DotAttributes
}

Edge represents an edge connecting two vertices in the graph

func NewEdge 

func NewEdge[T comparable](from, to T) *Edge[T]

NewEdge creates an edge, which connects the given vertices

type Graph 

type Graph[T comparable] interface {
	// Kind returns the kind of the graph
	Kind() GraphKind

	// AddVertex adds a new vertex to the graph
	AddVertex(v T) *Vertex[T]

	// GetVertex returns the vertex associated with the given value
	GetVertex(v T) *Vertex[T]

	// DeleteVertex deletes the vertex associated with the given value
	DeleteVertex(v T)

	// VertexExists is a predicate for testing whether a vertex
	// associated with the value exists.
	VertexExists(v T) bool

	// GetVertices returns all vertices in the graph
	GetVertices() []*Vertex[T]

	// GetVertexValues returns the values associated with all
	// vertices from the graph
	GetVertexValues() []T

	// AddEdge creates a new edge connecting `from` and `to`
	// vertices
	AddEdge(from, to T) *Edge[T]

	// AddWeightedEdge creates a new edge with the given weight
	AddWeightedEdge(from, to T, weight float64) *Edge[T]

	// GetEdge returns the edge, which connects `from` and `to`
	// vertices
	GetEdge(from, to T) *Edge[T]

	// DeleteEdge deletes the edge which connects `from` and `to`
	// vertices
	DeleteEdge(from, to T)

	// EdgeExists is a predicate for testing whether an edge
	// between `from` and `to` exists
	EdgeExists(from, to T) bool

	// GetEdges returns all edges from the graph
	GetEdges() []*Edge[T]

	// GetNeighbours returns the neighbours of V as values
	GetNeighbours(v T) []T

	// GetNeighbourVertices returns the neighbours of V as
	// vertices
	GetNeighbourVertices(v T) []*Vertex[T]

	// ResetVertexAttributes resets the attributes for all
	// vertices in the graph
	ResetVertexAttributes()

	// NewCollector creates and returns a new collector
	NewCollector() *Collector[T]

	// Clone creates a new copy of the graph
	Clone() Graph[T]

	// GetDotAttribute returns the Dot attributes for the graph
	GetDotAttributes() DotAttributes
}

Graph represents a graph which establishes relationships between various objects.

func New 

func New[T comparable](kind GraphKind) Graph[T]

NewGraph creates a new graph

type GraphKind 

type GraphKind int

GraphKind represents the kind of the graph 

const (
	// A kind which represents a directed graph
	KindDirected GraphKind = iota

	// A kind which represents an undirected graph
	KindUndirected
)

type UndirectedGraph 

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

UndirectedGraph represents an undirected graph

func (*UndirectedGraph[T]) AddEdge 

func (g *UndirectedGraph[T]) AddEdge(from, to T) *Edge[T]

AddEdge adds an edge between two vertices in the graph

func (*UndirectedGraph[T]) AddVertex 

func (g *UndirectedGraph[T]) AddVertex(value T) *Vertex[T]

AddVertex adds a vertex to the graph

func (*UndirectedGraph[T]) AddWeightedEdge 

func (g *UndirectedGraph[T]) AddWeightedEdge(from, to T, weight float64) *Edge[T]

AddWeightedEdge adds an edge between two vertices and sets weight for the edge

func (*UndirectedGraph[T]) Clone 

func (g *UndirectedGraph[T]) Clone() Graph[T]

Clone creates a new copy of the graph.

func (*UndirectedGraph[T]) DeleteEdge 

func (g *UndirectedGraph[T]) DeleteEdge(from, to T)

DeleteEdge deletes the edge, which connects the `from` and `to` vertices

func (*UndirectedGraph[T]) DeleteVertex 

func (g *UndirectedGraph[T]) DeleteVertex(v T)

DeleteVertex removes a vertex from the graph

func (*UndirectedGraph[T]) EdgeExists 

func (g *UndirectedGraph[T]) EdgeExists(from, to T) bool

EdgeExists returns a boolean indicating whether an edge between two vertices exists.

func (*UndirectedGraph[T]) GetDotAttributes added in v1.0.1 

func (g *UndirectedGraph[T]) GetDotAttributes() DotAttributes

GetDotAttributes returns the list of attributes for the graph.

func (*UndirectedGraph[T]) GetEdge 

func (g *UndirectedGraph[T]) GetEdge(from, to T) *Edge[T]

GetEdge returns the edge connecting the two vertices

func (*UndirectedGraph[T]) GetEdges 

func (g *UndirectedGraph[T]) GetEdges() []*Edge[T]

GetEdges returns the set of edges in the graph

func (*UndirectedGraph[T]) GetNeighbourVertices 

func (g *UndirectedGraph[T]) GetNeighbourVertices(v T) []*Vertex[T]

GetNeighbourVertices returns the list of neighbour vertices of V

func (*UndirectedGraph[T]) GetNeighbours 

func (g *UndirectedGraph[T]) GetNeighbours(v T) []T

GetNeighbours returns the list of direct neighbours of V

func (*UndirectedGraph[T]) GetVertex 

func (g *UndirectedGraph[T]) GetVertex(value T) *Vertex[T]

GetVertex returns the vertex associated with the given value

func (*UndirectedGraph[T]) GetVertexValues 

func (g *UndirectedGraph[T]) GetVertexValues() []T

GetVertexValues returns the set of vertex values

func (*UndirectedGraph[T]) GetVertices 

func (g *UndirectedGraph[T]) GetVertices() []*Vertex[T]

GetVertices returns the set of vertices in the graph

func (*UndirectedGraph[T]) Kind 

func (g *UndirectedGraph[T]) Kind() GraphKind

Kind returns the kind of the graph

func (*UndirectedGraph[T]) NewCollector 

func (g *UndirectedGraph[T]) NewCollector() *Collector[T]

NewCollector creates a new collector

func (*UndirectedGraph[T]) ResetVertexAttributes 

func (g *UndirectedGraph[T]) ResetVertexAttributes()

ResetVertexAttributes resets the attributes for each vertex in the graph

func (*UndirectedGraph[T]) VertexExists 

func (g *UndirectedGraph[T]) VertexExists(value T) bool

VertexExists returns a boolean indicating whether a vertex with the given value exists

type Vertex 

type Vertex[T comparable] struct {
	// Value contains the value for the vertex
	Value T

	// Color represents the color the vertex is painted with
	Color Color

	// DistanceFromSource returns the distance of this vertex from
	// the source vertex.  This field is calculated after
	// performing a DFS or BFS.
	DistanceFromSource float64

	// Parent represents the parent vertex, which is calculated
	// during walking of the graph.  The resulting relationships
	// established by this field construct the DFS-tree, BFS-tree
	// or shortest-path tree, depending on how we walked the
	// graph.
	Parent *Vertex[T]

	// DotAttributes represents the list of attributes associated
	// with the vertex. The attributes will be used when
	// generating the Dot representation of the graph.
	DotAttributes DotAttributes

	// Degree represents the degree of the vertex
	Degree Degree
}

Vertex represents a vertex in the graph

func NewVertex 

func NewVertex[T comparable](value T) *Vertex[T]

NewVertex creates a new vertex with the given value

type WalkFunc 

type WalkFunc[T comparable] func(v *Vertex[T]) error

WalkFunc is a function which receives a vertex while traversing the graph

Source Files

View all Source files

Directories

Path Synopsis
examples
bfs
dfs
dot
shortest_path
toposort

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.