README
¶
goraph
Lightweight graph library
Documentation
API docs available on godoc:
Documentation
¶
Index ¶
- type AdjacencyList
- func (g *AdjacencyList) AddEdge(u, v Vertex)
- func (g *AdjacencyList) AddVertex() Vertex
- func (g *AdjacencyList) Edges() []Edge
- func (g *AdjacencyList) Neighbours(v Vertex) []Vertex
- func (g *AdjacencyList) RemoveEdge(u, v Vertex)
- func (g *AdjacencyList) RemoveVertex(v Vertex)
- func (g *AdjacencyList) Vertices() []Vertex
- type DirectedAdjacencyList
- func (g *DirectedAdjacencyList) AddEdge(u, v Vertex)
- func (g *DirectedAdjacencyList) AddVertex() Vertex
- func (g *DirectedAdjacencyList) Edges() []Edge
- func (g *DirectedAdjacencyList) Neighbours(v Vertex) []Vertex
- func (g *DirectedAdjacencyList) Predecessors(v Vertex) (result []Vertex)
- func (g *DirectedAdjacencyList) RemoveEdge(u, v Vertex)
- func (g *DirectedAdjacencyList) RemoveVertex(v Vertex)
- func (g *DirectedAdjacencyList) Successors(v Vertex) []Vertex
- func (g *DirectedAdjacencyList) Vertices() []Vertex
- type Edge
- type EdgeSlice
- type Graph
- type Vertex
- type VertexSlice
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type AdjacencyList ¶
type AdjacencyList struct {
// contains filtered or unexported fields
}
AdjacencyList implements an undirected graph using an adjacency list.
func NewAdjacencyList ¶
func NewAdjacencyList() *AdjacencyList
NewAdjacencyList creates an empty graph.
func (*AdjacencyList) AddEdge ¶
func (g *AdjacencyList) AddEdge(u, v Vertex)
func (*AdjacencyList) AddVertex ¶
func (g *AdjacencyList) AddVertex() Vertex
func (*AdjacencyList) Edges ¶
func (g *AdjacencyList) Edges() []Edge
func (*AdjacencyList) Neighbours ¶
func (g *AdjacencyList) Neighbours(v Vertex) []Vertex
func (*AdjacencyList) RemoveEdge ¶
func (g *AdjacencyList) RemoveEdge(u, v Vertex)
func (*AdjacencyList) RemoveVertex ¶
func (g *AdjacencyList) RemoveVertex(v Vertex)
func (*AdjacencyList) Vertices ¶
func (g *AdjacencyList) Vertices() []Vertex
type DirectedAdjacencyList ¶
type DirectedAdjacencyList struct {
// contains filtered or unexported fields
}
DirectedAdjacencyList is like AdjacencyList, but directed.
func NewDirectedAdjacencyList ¶
func NewDirectedAdjacencyList() *DirectedAdjacencyList
NewDirectedAdjacencyList creates and initializes a DirectedAdjacencyList.
func (*DirectedAdjacencyList) AddEdge ¶
func (g *DirectedAdjacencyList) AddEdge(u, v Vertex)
AddEdge connects vertices u and v in the graph.
func (*DirectedAdjacencyList) AddVertex ¶
func (g *DirectedAdjacencyList) AddVertex() Vertex
func (*DirectedAdjacencyList) Edges ¶
func (g *DirectedAdjacencyList) Edges() []Edge
func (*DirectedAdjacencyList) Neighbours ¶
func (g *DirectedAdjacencyList) Neighbours(v Vertex) []Vertex
func (*DirectedAdjacencyList) Predecessors ¶
func (g *DirectedAdjacencyList) Predecessors(v Vertex) (result []Vertex)
Predecessors returns a slice of vertices that connect to v directionally.
func (*DirectedAdjacencyList) RemoveEdge ¶
func (g *DirectedAdjacencyList) RemoveEdge(u, v Vertex)
func (*DirectedAdjacencyList) RemoveVertex ¶
func (g *DirectedAdjacencyList) RemoveVertex(v Vertex)
func (*DirectedAdjacencyList) Successors ¶
func (g *DirectedAdjacencyList) Successors(v Vertex) []Vertex
Successors returns a slice of vertices that v connects to directionally. This method returns the same thing as Neighbours.
func (*DirectedAdjacencyList) Vertices ¶
func (g *DirectedAdjacencyList) Vertices() []Vertex
type Edge ¶
type Edge struct{ U, V Vertex }
Edge represents an edge between two vertices. In a directed graph, the edge is from U to V.
type Graph ¶
type Graph interface {
// AddVertex creates an returns a new vertex in the graph.
AddVertex() Vertex
// RemoveVertex permanently removes a vertex from the graph.
RemoveVertex(v Vertex)
// AddEdge adds an edge between u and v. If the graph is directional,
// then the edge will go from u to v.
AddEdge(u, v Vertex)
// RemoveEdge removes the edge between u and v.
RemoveEdge(u, v Vertex)
// Vertices returns a slice of the graph's vertices.
Vertices() []Vertex
// Edges returns a slice of the graph's edges.
Edges() []Edge
// Neighbours returns a slice of the vertices that neighbour v.
Neighbours(v Vertex) []Vertex
}
Graph is implemented by all of the graph types. All of the graph algorithms use this data type instead of the concrete types.
type Vertex ¶
type Vertex int
Vertex represents a node in the graph. Users should create new Vertex values with AddVertex.
func ShortestPath ¶
ShortestPath returns the shortest path between source and target using Dijkstra's algorithm.
func TopoSort ¶
TopoSort returns a slice of the vertices in g in topologically sorted order. (https://en.wikipedia.org/wiki/Topological_sorting)
If deterministic is true, then the vertices are sorted by id before the algorithm begins, guaranteeing a repeatable result.
type VertexSlice ¶
type VertexSlice []Vertex
VertexSlice is a convenience type for sorting vertices by ID.
func (VertexSlice) Len ¶
func (p VertexSlice) Len() int
func (VertexSlice) Less ¶
func (p VertexSlice) Less(i, j int) bool
func (VertexSlice) Sort ¶
func (p VertexSlice) Sort()
func (VertexSlice) Swap ¶
func (p VertexSlice) Swap(i, j int)
Source Files
Directories