graph

README

Another graph package in Go.

This is really just an experiment in API design. But it's always fun to write a graphing library.

Documentation

Index

• type CycleDetectedErr
  • func (e *CycleDetectedErr) Error() string
  • func (e *CycleDetectedErr) Is(target error) bool
• type Direction
• type DuplicateEdgeErr
  • func (e *DuplicateEdgeErr) Error() string
  • func (e *DuplicateEdgeErr) Is(target error) bool
• type DuplicateVertexErr
  • func (e *DuplicateVertexErr) Error() string
  • func (e *DuplicateVertexErr) Is(target error) bool
• type Graph
  • func NewGraph(isDirected bool) Graph
  • func (g *Graph) AddEdge(a, b interface{}, weight float64) error
  • func (g *Graph) AddVertex(v interface{}) error
  • func (g *Graph) AddVertices(v ...interface{}) error
  • func (g *Graph) BreadthFirstSearch(v interface{}, d Direction) ([]interface{}, error)
  • func (g *Graph) BreadthFirstVisit(v interface{}, d Direction, visitorFunc func(v interface{}) (stop bool)) error
  • func (g *Graph) ConnectedComponent(v interface{}) ([]interface{}, error)
  • func (g *Graph) ConnectedComponents() ([][]interface{}, error)
  • func (g *Graph) DepthFirstSearch(v interface{}, d Direction) ([]interface{}, error)
  • func (g *Graph) DepthFirstVisit(v interface{}, d Direction, visitorFunc func(v interface{}) (stop bool)) error
  • func (g *Graph) Neighborhood(v interface{}, order uint, minimumDistance uint, d Direction) ([]interface{}, error)
  • func (g Graph) Neighbors(v interface{}, d Direction) ([]interface{}, error)
  • func (g Graph) NumVertex() int
  • func (g *Graph) RemoveEdge(a, b interface{}) error
  • func (g *Graph) RemoveVertex(v interface{}) error
  • func (g Graph) String() string
  • func (g *Graph) TopologicalSort() ([]interface{}, error)
• type InvalidArgumentErr
  • func (e InvalidArgumentErr) Error() string
• type MissingEdgeErr
  • func (e *MissingEdgeErr) Error() string
  • func (e *MissingEdgeErr) Is(target error) bool
• type MissingVertexErr
  • func (e *MissingVertexErr) Error() string
  • func (e *MissingVertexErr) Is(target error) bool
• type UndirectedGraphErr
  • func (e *UndirectedGraphErr) Error() string
  • func (e *UndirectedGraphErr) Is(target error) bool

Examples

• Graph

Types

type CycleDetectedErr

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

A CycleDetectedErr describes a graph that contains a cycle.

func (*CycleDetectedErr) Error

func (e *CycleDetectedErr) Error() string

func (*CycleDetectedErr) Is

func (e *CycleDetectedErr) Is(target error) bool

type Direction

type Direction int

Direction is the direction of a relationship between two vertices in a directed graph. It has no meaning in undirected graphs.

const (
	// NoDirection represents the absence of direction. In a directed graph,
	// this means both inbound and outbound edges.
	NoDirection Direction = iota

	// Outbound represents only edges going "out" from a vertex.
	Outbound

	// Inbound represents only edges going "in" to a vertex.
	Inbound
)

type DuplicateEdgeErr

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

A DuplicateEdgeErr describes an edge (a pair of ordered vertices) that already exist in a Graph.

func (*DuplicateEdgeErr) Error

func (e *DuplicateEdgeErr) Error() string

func (*DuplicateEdgeErr) Is

func (e *DuplicateEdgeErr) Is(target error) bool

type DuplicateVertexErr

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

A DuplicateVertexErr describes a vertex that already exists in a Graph.

func (*DuplicateVertexErr) Error

func (e *DuplicateVertexErr) Error() string

func (*DuplicateVertexErr) Is

func (e *DuplicateVertexErr) Is(target error) bool

type Graph

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

A Graph is an unordered set of nodes along with a set of weighted ordered-pair relationships between nodes.

Example

package main

import (
	"fmt"
	"log"
	"strconv"

	"github.com/subpop/go-graph"
)

type Package struct {
	Name     string
	Version  string
	Revision int
}

func (p Package) String() string {
	return p.Name + "-" + p.Version + "-" + strconv.FormatInt(int64(p.Revision), 10)
}

func main() {
	foo := Package{
		Name:     "foo",
		Version:  "1.4.2",
		Revision: 1,
	}

	libfoo := Package{
		Name:     "libfoo",
		Version:  "1.5",
		Revision: 2,
	}

	deps := graph.NewGraph(true)
	if err := deps.AddEdge(foo, libfoo, 0); err != nil {
		log.Fatal(err)
	}

	fmt.Println(deps)
}

Output:

{ (foo-1.4.2-1, libfoo-1.5-2) }

func NewGraph

func NewGraph(isDirected bool) Graph

NewGraph creates a new Graph, enforcing directed edges if isDirected is true.

func (*Graph) AddEdge

func (g *Graph) AddEdge(a, b interface{}, weight float64) error

AddEdge creates a weighted edge from a to b. It adds a and b to the graph if they are not already present. If the graph is an undirected graph, the inverse edge from b to a is also added. If the edge relationship already exists, a DuplicateEdgeErr is returned.

func (*Graph) AddVertex

func (g *Graph) AddVertex(v interface{}) error

AddVertex adds v to g. If the graph already contains vertex v, it returns DuplicateVertexErr.

func (*Graph) AddVertices

func (g *Graph) AddVertices(v ...interface{}) error

AddVertices adds vertices v to g. If the graph already contains a vertex, it returns DuplicateVertexErr.

func (*Graph) BreadthFirstSearch

func (g *Graph) BreadthFirstSearch(v interface{}, d Direction) ([]interface{}, error)

BreadthFirstSearch performs a breadth-first traversal of the graph, starting with vertex v. It returns a slice of vertices visited during the traversal.

func (*Graph) BreadthFirstVisit

func (g *Graph) BreadthFirstVisit(v interface{}, d Direction, visitorFunc func(v interface{}) (stop bool)) error

BreadthFirstVisit performs a breadth-first traversal of the graph, starting with vertex v. The visitorFunc is invoked each time a vertex is visited.

func (*Graph) ConnectedComponent

func (g *Graph) ConnectedComponent(v interface{}) ([]interface{}, error)

ConnectedComponent performs a depth-first traversal of g to return the connected component containing v. In a directed graph, the component returned is the strong component.

func (*Graph) ConnectedComponents

func (g *Graph) ConnectedComponents() ([][]interface{}, error)

ConnectedComponents performs a depth-first traversal of each vertex in g to return the set of connected components in g. In a directed graph, the components returned are the strongly connected components.

func (*Graph) DepthFirstSearch

func (g *Graph) DepthFirstSearch(v interface{}, d Direction) ([]interface{}, error)

DepthFirstSearch performs a depth-first traversal of the graph, starting with vertex v. It returns a slice of vertices visited during the traversal in lexicographic order.

func (*Graph) DepthFirstVisit

func (g *Graph) DepthFirstVisit(v interface{}, d Direction, visitorFunc func(v interface{}) (stop bool)) error

DepthFirstVisit performs a depth-first traversal of the graph, starting with vertex v. The visitorFunc is invoked each time a vertex is visited.

func (*Graph) Neighborhood

func (g *Graph) Neighborhood(v interface{}, order uint, minimumDistance uint, d Direction) ([]interface{}, error)

Neighborhood returns a slice of vertices adjacent to v, based on the provided parameters. - order: the number of "hops" from the vertex to include. - minimumDistance: the minimum number of "hops" from the vertex before collecting. If the graph is undirected, d is ignored. If the graph does not contain vertex v, it returns MissingVertexErr.

func (Graph) Neighbors

func (g Graph) Neighbors(v interface{}, d Direction) ([]interface{}, error)

Neighbors returns a slice of vertices adjacent to v, given direction d. If the graph is undirected, d is ignored. If the graph does not contain vertex v, it returns MissingVertexErr.

func (Graph) NumVertex

func (g Graph) NumVertex() int

NumVertex returns the number of vertices in the graph.

func (*Graph) RemoveEdge

func (g *Graph) RemoveEdge(a, b interface{}) error

RemoveEdge removes an edge from a to b. If a or b are not in the graph, it returns MissingVertexErr. If the graph is an undirected graph, the inverse edge from b to a is also removed. If the edge does not exist, it returns MissingEdgeErr.

func (*Graph) RemoveVertex

func (g *Graph) RemoveVertex(v interface{}) error

RemoveVertex removes v from g. If the graph does not contain vertex v, it returns MissingVertexErr.

func (Graph) String

func (g Graph) String() string

func (*Graph) TopologicalSort

func (g *Graph) TopologicalSort() ([]interface{}, error)

TopologicalSort performs a variation on a depth-first search to order a directed acyclic graph's vertices in such a way that for every vertex, all adjacent vertices appear before it in the list. If graph is undirected, an error is returned. If a cycle is detected, an error is returned.

type InvalidArgumentErr

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

InvalidArgumentErr describes argument parameters that a receiving method considers invalid or incorrectly specified.

func (InvalidArgumentErr) Error

func (e InvalidArgumentErr) Error() string

type MissingEdgeErr

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

A MissingEdgeErr describes an edge (a pair of ordered vertices) that does not exist in a Graph.

func (*MissingEdgeErr) Error

func (e *MissingEdgeErr) Error() string

func (*MissingEdgeErr) Is

func (e *MissingEdgeErr) Is(target error) bool

type MissingVertexErr

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

A MissingVertexErr describes a vertex that does not exist in a Graph.

func (*MissingVertexErr) Error

func (e *MissingVertexErr) Error() string

func (*MissingVertexErr) Is

func (e *MissingVertexErr) Is(target error) bool

type UndirectedGraphErr

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

An UndirectedGraphErr describes a graph that is undirected.

func (*UndirectedGraphErr) Error

func (e *UndirectedGraphErr) Error() string

func (*UndirectedGraphErr) Is

func (e *UndirectedGraphErr) Is(target error) bool