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
- type Direction
- type DuplicateEdgeErr
- type DuplicateVertexErr
- type 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) 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) 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 MissingEdgeErr
- type MissingVertexErr
- type UndirectedGraphErr
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
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
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.
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
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
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"
"git.sr.ht/~spc/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 (*Graph) AddEdge ¶
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 ¶
AddVertex adds v to g. If the graph already contains vertex v, it returns DuplicateVertexErr.
func (*Graph) AddVertices ¶
AddVertices adds vertices v to g. If the graph already contains a vertex, it returns DuplicateVertexErr.
func (*Graph) BreadthFirstSearch ¶
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) DepthFirstSearch ¶
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) Neighbors ¶
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) RemoveEdge ¶
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 ¶
RemoveVertex removes v from g. If the graph does not contain vertex v, it returns MissingVertexErr.
func (*Graph) TopologicalSort ¶
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 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
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
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
Source Files