Documentation
¶
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type BreadthFirstNode ¶
type BreadthFirstNode struct {
Color Color
Parent Vertex // predecessor node in the tree
Distance float64 // number of edges from the root (type float for easy infinity)
}
BreadthFirstNode is a node in BreadthFirstTree
type BreadthFirstTree ¶
type BreadthFirstTree struct {
Root Vertex
Nodes map[Vertex]*BreadthFirstNode
}
BreadthFirstTree is BreadthFirstSearch result
func (BreadthFirstTree) ToTree ¶
func (t BreadthFirstTree) ToTree() *Tree
type DepthFirstForest ¶
type DepthFirstForest struct {
Roots []Vertex
Nodes map[Vertex]*DepthFirstNode
Time int
}
DepthFirstForest is DepthFirstSearch result
func (DepthFirstForest) Draw ¶
func (f DepthFirstForest) Draw() string
func (DepthFirstForest) ToTrees ¶
func (f DepthFirstForest) ToTrees() []*Tree
type DepthFirstNode ¶
type DepthFirstNode struct {
Color Color
Parent Vertex // predecessor node in the tree
Discovered int // timestamps when the vertex is first discovered (color to Gray)
Finished int // timestamps when the search finish examining the vertex adjacent list (color to Black)
}
DepthFirstNode is a node in a tree in a DepthFirstForest
type Graph ¶
type Graph struct {
Adj map[Vertex][]Edge // Adj[u] consists of all the vertices adjacent to u
Vertices []Vertex // list of all vertices in the graph
NEdges int // number of edges in the graph
IsDirected bool
}
Graph G = (V,E) adjacency-list representation consists of an array Adj of len(V) lists, one for each vertex in V. For each vertex u in V, the adjacency list Adj[u] contains all the vertices v such that there is an edge (u,v) in E.
If G is a directed graph, the sum of the lengths of all the adjacency lists is len(E); if G is an undirected graph, the value is 2*len(E).
func NewGraph ¶
NewGraph initializes a graph (directed or undirected) from edges list, returned graph vertices and edges are sorted by dictionary order. Param "edgesTxt" is newline separated, each line has 2 vertices of an edge and an optional weight (separated by whitespace); ignore text after a # (treated as comment). Example input edgesTxt: # Undirected (unweighted) graph, a square with a diagonal ⧄: # Nodes: 4 Edges: 5 # FromNodeId ToNodeId 0 1 0 3 1 2 1 3 2 3
func (Graph) BreadthFirstSearch ¶
func (g Graph) BreadthFirstSearch(s Vertex) BreadthFirstTree
BreadthFirstSearch explores the edges of the graph to discover every vertex that is reachable from the source vertex "s". It computes the distance ( the smallest number of edges) from s to each reachable vertex. Returned BreadthFirstTree has root s, contains all reachable vertices and the shortest path from s to them. The algorithm works on both directed and undirected graphs. Time complexity: O(V+E) (V = number of vertices, E = number of edges). Reference: Introduction to Algorithms (Thomas, Charles, Ronald, Clifford).
func (Graph) DepthFirstSearch ¶
func (g Graph) DepthFirstSearch() DepthFirstForest
DepthFirstSearch searches deeper in the graph whenever possible, go from the most recently discovered vertex to one of it unexplored neighbor vertex then continue from the chosen neighbor. The results of DepthFirstSearch may depend upon the order of vertices, these different visitation orders tend not to cause problems in practice, as we can usually use any DepthFirstForest result effectively, with essentially equivalent results. Time complexity: O(V+E) (V = number of vertices, E = number of edges). Reference: Introduction to Algorithms (Thomas, Charles, Ronald, Clifford).
type Tree ¶
type Tree struct {
Key interface{} // node label or value or a struct data
Parent *Tree
Children []*Tree
}
Tree is just a tree node
func (*Tree) AddChild ¶
AddChild adds a child node to the right of Children, input child.Parent will be set to the receiver node, returns the receiver for easy chain nodes.
func (*Tree) Draw ¶
Draw draws the tree (the node and its descendants) using unicode characters
Example ¶
root := Tree{Key: "0"}
root.AddChild((&Tree{Key: "1a"}).
AddChild(&Tree{Key: "2a"}).AddChild(&Tree{Key: "2b"}).AddChild(&Tree{Key: "2c"}))
root.AddChild(&Tree{Key: "1b"})
root.AddChild((&Tree{Key: "1c"}).AddChild(&Tree{Key: "2d"}).AddChild(&Tree{Key: "2e"}))
fmt.Println(root.Draw())
Output: * 0 ├───1a │ ├───2a │ ├───2b │ ╰───2c ├───1b ╰───1c ├───2d ╰───2e
type Vertex ¶
type Vertex string
Vertex in a graph can be named "1", "2", "a", "b", ... (any non-empty string). Empty string represent an unassigned vertex.
type VertexOrder ¶
type VertexOrder []Vertex // dictionary (lexicographic) order
func (VertexOrder) Len ¶
func (a VertexOrder) Len() int
func (VertexOrder) Less ¶
func (a VertexOrder) Less(i, j int) bool
func (VertexOrder) Swap ¶
func (a VertexOrder) Swap(i, j int)
Source Files