graph

Documentation

Overview

Implements an adjacency list graph as a slice of generic nodes and includes some useful graph functions.

Index

• type Edge
• type Graph
  • func New(kind GraphType) *Graph
  • func (g *Graph) DijkstraSearch(start Node) []Path
  • func (g *Graph) MakeEdge(from, to Node) error
  • func (g *Graph) MakeEdgeWeight(from, to Node, weight int) error
  • func (g *Graph) MakeNode() Node
  • func (g *Graph) MaxSpacingClustering(n int) ([][]Node, int, error)
  • func (g *Graph) MinimumSpanningTree() []Edge
  • func (g *Graph) Neighbors(n Node) []Node
  • func (g *Graph) RandMinimumCut(iterations, concurrent int) []Edge
  • func (g *Graph) RemoveEdge(from, to Node)
  • func (g *Graph) RemoveNode(remove *Node)
  • func (g *Graph) Reverse() *Graph
  • func (g *Graph) StronglyConnectedComponents() [][]Node
  • func (g *Graph) TopologicalSort() []Node
• type GraphType
• type Node
• type Path

Examples

• Graph.MinimumSpanningTree
• Graph.TopologicalSort

Types

type Edge

type Edge struct {
	Weight int
	Start  Node
	End    Node
}

An Edge connects two Nodes in a graph. To modify Weight, use the MakeEdgeWeight function. Any local modifications will not be seen in the graph.

type Graph

type Graph struct {
	Kind GraphType
	// contains filtered or unexported fields
}

Graph is an adjacency slice representation of a graph. Can be directed or undirected.

func New

func New(kind GraphType) *Graph

New creates and returns an empty graph. If kind is Directed, returns a directed graph. This function returns an undirected graph by default.

func (*Graph) DijkstraSearch

func (g *Graph) DijkstraSearch(start Node) []Path

DijkstraSearch returns the shortest path from the start node to every other node in the graph. All edges must have a positive weight, otherwise this function will return nil.

func (*Graph) MakeEdge

func (g *Graph) MakeEdge(from, to Node) error

MakeEdge calls MakeEdgeWeight with a weight of 0 and returns an error if either of the nodes do not belong in the graph. Calling MakeEdge multiple times on the same nodes will not create multiple edges.

func (*Graph) MakeEdgeWeight

func (g *Graph) MakeEdgeWeight(from, to Node, weight int) error

MakeEdgeWeight creates an edge in the graph with a corresponding weight. It returns an error if either of the nodes do not belong in the graph.

Calling MakeEdgeWeight multiple times on the same nodes will not create multiple edges; this function will update the weight on the node to the new value.

func (*Graph) MakeNode

func (g *Graph) MakeNode() Node

MakeNode creates a node, adds it to the graph and returns the new node.

func (*Graph) MaxSpacingClustering

func (g *Graph) MaxSpacingClustering(n int) ([][]Node, int, error)

MaxSpacingClustering returns a slice of clusters with the distance between the clusters maximized as well as the maximized distance between these clusters. It takes as input the number of clusters to compute.

func (*Graph) MinimumSpanningTree

func (g *Graph) MinimumSpanningTree() []Edge

MinimumSpanningTree will return the edges corresponding to the minimum spanning tree in the graph based off of edge weight values. This will return nil for a directed graph.

Example

package main

import (
	"fmt"
	"github.com/twmb/algoimpl/go/graph"
)

func main() {
	g := graph.New(graph.Undirected)
	nodes := make(map[rune]graph.Node, 0)
	nodes['a'] = g.MakeNode()
	nodes['b'] = g.MakeNode()
	nodes['c'] = g.MakeNode()
	nodes['d'] = g.MakeNode()
	nodes['e'] = g.MakeNode()
	nodes['f'] = g.MakeNode()
	nodes['g'] = g.MakeNode()
	nodes['h'] = g.MakeNode()
	nodes['i'] = g.MakeNode()
	g.MakeEdgeWeight(nodes['a'], nodes['b'], 4)
	g.MakeEdgeWeight(nodes['a'], nodes['h'], 8)
	g.MakeEdgeWeight(nodes['b'], nodes['c'], 8)
	g.MakeEdgeWeight(nodes['b'], nodes['h'], 11)
	g.MakeEdgeWeight(nodes['c'], nodes['d'], 7)
	g.MakeEdgeWeight(nodes['c'], nodes['f'], 4)
	g.MakeEdgeWeight(nodes['c'], nodes['i'], 2)
	g.MakeEdgeWeight(nodes['d'], nodes['e'], 9)
	g.MakeEdgeWeight(nodes['d'], nodes['f'], 14)
	g.MakeEdgeWeight(nodes['e'], nodes['f'], 10)
	g.MakeEdgeWeight(nodes['f'], nodes['g'], 2)
	g.MakeEdgeWeight(nodes['g'], nodes['h'], 1)
	g.MakeEdgeWeight(nodes['g'], nodes['i'], 6)
	g.MakeEdgeWeight(nodes['h'], nodes['i'], 7)
	mst := g.MinimumSpanningTree()
	weightSum := 0
	for i := range mst {
		weightSum += mst[i].Weight
	}
	fmt.Println(weightSum)
}

Output:

37

func (*Graph) Neighbors

func (g *Graph) Neighbors(n Node) []Node

Neighbors returns a slice of nodes that are reachable from the given node in a graph.

func (*Graph) RandMinimumCut

func (g *Graph) RandMinimumCut(iterations, concurrent int) []Edge

RandMinimumCut runs Kargers algorithm to find a random minimum cut on the graph. If iterations is < 1, this will return an empty slice. Otherwise, it returns a slice of the edges crossing the best minimum cut found in any iteration. Call rand.Seed() before using this function.

This function takes a number of iterations to start concurrently. If concurrent is <= 1, it will run one iteration at a time.

If the graph is Directed, this will return a cut of edges in both directions. If the graph is Undirected, this will return a proper min cut.

func (*Graph) RemoveEdge

func (g *Graph) RemoveEdge(from, to Node)

RemoveEdge removes edges starting at the from node and ending at the to node. If the graph is undirected, RemoveEdge will remove all edges between the nodes.

func (*Graph) RemoveNode

func (g *Graph) RemoveNode(remove *Node)

RemoveNode removes a node from the graph and all edges connected to it. This function nils points in the Node structure. If 'remove' is used in a map, you must delete the map index first.

func (*Graph) Reverse

func (g *Graph) Reverse() *Graph

Reverse returns reversed copy of the directed graph g. This function can be used to copy an undirected graph.

func (*Graph) StronglyConnectedComponents

func (g *Graph) StronglyConnectedComponents() [][]Node

StronglyConnectedComponents returns a slice of strongly connected nodes in a directed graph. If used on an undirected graph, this function returns distinct connected components.

func (*Graph) TopologicalSort

func (g *Graph) TopologicalSort() []Node

TopologicalSort topoligically sorts a directed acyclic graph. If the graph is cyclic, the sort order will change based on which node the sort starts on.

The StronglyConnectedComponents function can be used to determine if a graph has cycles.

Example

package main

import (
	"fmt"
	"github.com/twmb/algoimpl/go/graph"
)

func main() {
	g := graph.New(graph.Directed)

	clothes := make(map[string]graph.Node, 0)
	// Make a mapping from strings to a node
	clothes["shirt"] = g.MakeNode()
	clothes["tie"] = g.MakeNode()
	clothes["jacket"] = g.MakeNode()
	clothes["belt"] = g.MakeNode()
	clothes["watch"] = g.MakeNode()
	clothes["undershorts"] = g.MakeNode()
	clothes["pants"] = g.MakeNode()
	clothes["shoes"] = g.MakeNode()
	clothes["socks"] = g.MakeNode()
	// Make references back to the string values
	for key, node := range clothes {
		*node.Value = key
	}
	// Connect the elements
	g.MakeEdge(clothes["shirt"], clothes["tie"])
	g.MakeEdge(clothes["tie"], clothes["jacket"])
	g.MakeEdge(clothes["shirt"], clothes["belt"])
	g.MakeEdge(clothes["belt"], clothes["jacket"])
	g.MakeEdge(clothes["undershorts"], clothes["pants"])
	g.MakeEdge(clothes["undershorts"], clothes["shoes"])
	g.MakeEdge(clothes["pants"], clothes["belt"])
	g.MakeEdge(clothes["pants"], clothes["shoes"])
	g.MakeEdge(clothes["socks"], clothes["shoes"])
	sorted := g.TopologicalSort()
	for i := range sorted {
		fmt.Println(*sorted[i].Value)
	}
}

Output:

socks
undershorts
pants
shoes
watch
shirt
belt
tie
jacket

type GraphType

type GraphType int

Directed or undirected.

const (
	Undirected GraphType = iota
	Directed
)

type Node

type Node struct {

	// Value can be used to store information on the caller side.
	// Its use is optional. See the Topological Sort example for
	// a reason on why to use this pointer.
	// The reason it is a pointer is so that graph function calls
	// can test for equality on Nodes. The pointer wont change,
	// the value it points to will. If the pointer is explicitly changed,
	// graph functions that use Nodes will cease to work.
	Value *interface{}
	// contains filtered or unexported fields
}

Node connects to a backing node on the graph. It can safely be used in maps.

type Path

type Path struct {
	Weight int
	Path   []Edge
}