graph

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.

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.

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