README
¶
Graph
Go implementations of common graph algorithms like Dijkstra, A*, Minimam spanning tree, etc.
Current support
- Directional graph.
- Bidirectional graph.
- Shortest paths. (Dijkstra)
Install
go get -d github.com/isutare412/graph
Documentation
¶
Overview ¶
Package graph implements several graph algorithms like Dijkstra, A*, etc.
Index ¶
- type Graph
- func (g *Graph) AddEdge(from, to Vertex, weight int)
- func (g *Graph) NewVertex() Vertex
- func (g *Graph) RemoveEdges(from, to Vertex)
- func (g *Graph) RemoveVertex(id VertexID) bool
- func (g *Graph) ShortestPath(src, dest Vertex) (p Path)
- func (g *Graph) ShortestPaths(source Vertex) map[Vertex]Path
- func (g *Graph) String() string
- type Path
- type Type
- type Vertex
- type VertexID
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Graph ¶
type Graph struct {
Type
// contains filtered or unexported fields
}
Graph implements an adjacency list. You should create a Graph by calling New(Type) function. As Graph doest have any location or coordinate, Graph cannot use A* algorithm. If you want A* algorithm, use CGraph instead.
func (*Graph) RemoveEdges ¶
RemoveEdges removes all edges from 'from' to 'to'. If Type of g is Directional, the other edges (from 'to' to 'from') are not removed.
func (*Graph) RemoveVertex ¶
RemoveVertex removes the vertex with 'id'. Then edges that point to the removed vertex are also removed. Returns true if the vertex is removed.
func (*Graph) ShortestPath ¶
ShortestPath returns shortest path p from src to dest. You can check whether the path exists by checking p.Destination() or p.Distance(). As g cannot be applied A* algorithm, ShortestPath uses Dijkstra's one instead.
func (*Graph) ShortestPaths ¶
ShortestPaths returns shortest paths from source to every vertices which are reachable from source.
type Path ¶
type Path struct {
// contains filtered or unexported fields
}
Path implements specific path to a vertex.
func (Path) Destination ¶
Destination returns the destination of current path. ok is false if the Path does not include any Vertex yet.
func (Path) Distance ¶
Distance returns a total distance to the destination. Returns negative number if the Path does not include any Vertex.
func (Path) IterateEdge ¶
IterateEdge iterates edges of p sequentially. If handler returns false, iteration will stop.
Source Files