 Go to latest
Published: Apr 10, 2022 License: MIT

## README ¶

### goraph   Package goraph implements graph data structure and algorithms.

``````go get -v gopkg.in/gyuho/goraph.v2;
``````

I have tutorials and visualizations of graph, tree algorithms:
For fast query and retrieval, please check out Cayley. ## Documentation ¶

### Overview ¶

Package goraph implements graph data structure and algorithms.

### Constants ¶

This section is empty.

### Variables ¶

This section is empty.

### Functions ¶

#### func Kruskal ¶

`func Kruskal(g Graph) (map[Edge]struct{}, error)`

Kruskal finds the minimum spanning tree with disjoint-set data structure. (http://en.wikipedia.org/wiki/Kruskal%27s_algorithm)

1. Kruskal(G) 1.
2. A = ∅ 3.
3. for each vertex v in G:
4. MakeDisjointSet(v) 6.
5. edges = get all edges
6. sort edges in ascending order of weight 9.
7. for each edge (u, v) in edges:
8. if FindSet(u) ≠ FindSet(v):
9. A = A ∪ {(u, v)}
10. Union(u, v) 14.
11. return A

#### func MakeDisjointSet ¶

`func MakeDisjointSet(forests *Forests, name string)`

MakeDisjointSet creates a DisjointSet.

#### func Prim ¶

`func Prim(g Graph, src ID) (map[Edge]struct{}, error)`

Prim finds the minimum spanning tree with min-heap (priority queue). (http://en.wikipedia.org/wiki/Prim%27s_algorithm)

1. Prim(G, source) 1.
2. let Q be a priority queue
3. distance[source] = 0 4.
4. for each vertex v in G: 6.
5. if v ≠ source:
6. distance[v] = ∞
7. prev[v] = undefined 10.
9. while Q is not empty: 15.
10. u = Q.extract_min() 17.
11. for each adjacent vertex v of u: 19.
12. if v ∈ Q and distance[v] > weight(u, v):
13. distance[v] = weight(u, v)
14. prev[v] = u
15. Q.decrease_priority(v, weight(u, v)) 25. 26.
16. return tree from prev

#### func Tarjan ¶

`func Tarjan(g Graph) [][]ID`

Tarjan finds the strongly connected components. In the mathematics, a directed graph is "strongly connected" if every vertex is reachable from every other node. Therefore, a graph is strongly connected if there is a path in each direction between each pair of node of a graph. Then a pair of vertices u and v is strongly connected to each other because there is a path in each direction. "Strongly connected components" of an arbitrary graph partition into sub-graphs that are themselves strongly connected. That is, "strongly connected component" of a directed graph is a sub-graph that is strongly connected. Formally, "Strongly connected components" of a graph is a maximal set of vertices C in G.V such that for all u, v ∈ C, there is a path both from u to v, and from v to u. (https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm)

1. Tarjan(G): 1.
2. globalIndex = 0 // smallest unused index
3. let S be a stack
4. result = [][] 5.
5. for each vertex v in G:
6. if v.index is undefined:
7. tarjan(G, v, globalIndex, S, result) 9.
8. return result 11. 12.
9. tarjan(G, v, globalIndex, S, result): 14.
10. v.index = globalIndex
12. globalIndex++
13. S.push(v) 19.
14. for each child vertex w of v: 21.
15. if w.index is undefined:
16. recursively tarjan(G, w, globalIndex, S, result)
18. else if w is in S:
20. // if v is the root
21. if v.lowLink == v.index: 31.
22. // start a new strongly connected component
23. component = [] 34.
24. while True: 36.
25. u = S.pop()
26. component.push(u) 39.
27. if u == v:
28. result.push(component)
29. break

#### func Union ¶

`func Union(forests *Forests, ds1, ds2 *DisjointSet)`

Union unions two DisjointSet, with ds1's represent.

### Types ¶

#### type DisjointSet ¶

```type DisjointSet struct {
// contains filtered or unexported fields
}```

DisjointSet implements disjoint set. (https://en.wikipedia.org/wiki/Disjoint-set_data_structure)

#### func FindSet ¶

`func FindSet(forests *Forests, name string) *DisjointSet`

FindSet returns the DisjointSet with the represent name.

#### type Edge ¶

```type Edge interface {
Source() Node
Target() Node
Weight() float64
String() string
}```

Edge connects between two Nodes.

#### func NewEdge ¶

`func NewEdge(src, tgt Node, wgt float64) Edge`

#### type EdgeSlice ¶

`type EdgeSlice []Edge`

#### func (EdgeSlice) Len ¶

`func (e EdgeSlice) Len() int`

#### func (EdgeSlice) Less ¶

`func (e EdgeSlice) Less(i, j int) bool`

#### func (EdgeSlice) Swap ¶

`func (e EdgeSlice) Swap(i, j int)`

#### type Forests ¶

```type Forests struct {
// contains filtered or unexported fields
}```

Forests is a set of DisjointSet.

#### func NewForests ¶

`func NewForests() *Forests`

NewForests creates a new Forests.

#### type Graph ¶

```type Graph interface {
// Init initializes a Graph.
Init()

// GetNodeCount returns the total number of nodes.
GetNodeCount() int

// GetNode finds the Node.
GetNode(id ID) (Node, error)

// GetNodes returns a map from node ID to
// empty struct value. Graph does not allow duplicate
// node ID or name.
GetNodes() map[ID]Node

// if the node already existed in the graph.

// DeleteNode deletes a node from a graph.
// It returns true if it got deleted.
// And false if it didn't get deleted.
DeleteNode(id ID) bool

// AddEdge adds an edge from nd1 to nd2 with the weight.
// It returns error if a node does not exist.
AddEdge(id1, id2 ID, weight float64) error

// ReplaceEdge replaces an edge from id1 to id2 with the weight.
ReplaceEdge(id1, id2 ID, weight float64) error

// DeleteEdge deletes an edge from id1 to id2.
DeleteEdge(id1, id2 ID) error

// GetWeight returns the weight from id1 to id2.
GetWeight(id1, id2 ID) (float64, error)

// GetSources returns the map of parent Nodes.
// (Nodes that come towards the argument vertex.)
GetSources(id ID) (map[ID]Node, error)

// GetTargets returns the map of child Nodes.
// (Nodes that go out of the argument vertex.)
GetTargets(id ID) (map[ID]Node, error)

// String describes the Graph.
String() string
}```

Graph describes the methods of graph operations. It assumes that the identifier of a Node is unique. And weight values is float64.

#### func NewGraph ¶

`func NewGraph() Graph`

NewGraph returns a new graph.

Example
```package main

import (
"fmt"
"log"
"os"

"github.com/gyuho/goraph"
)

func main() {
f, err := os.Open("testdata/graph.json")
if err != nil {
log.Fatal(err)
}
defer f.Close()
g, err := goraph.NewGraphFromJSON(f, "graph_00")
if err != nil {
log.Fatal(err)
}
fmt.Println(g.String())

// Output for g.String() but it's unordered because it's map:
// F -- 11.000 -→ D
// F -- 6.000 -→ E
// F -- 6.000 -→ T
// E -- 6.000 -→ F
// E -- 19.000 -→ T
// E -- 18.000 -→ B
// E -- 24.000 -→ C
// E -- 2.000 -→ D
// S -- 100.000 -→ A
// S -- 14.000 -→ B
// S -- 200.000 -→ C
// B -- 14.000 -→ S
// B -- 5.000 -→ A
// B -- 30.000 -→ D
// B -- 18.000 -→ E
// C -- 9.000 -→ S
// C -- 24.000 -→ E
// T -- 16.000 -→ D
// T -- 6.000 -→ F
// T -- 19.000 -→ E
// T -- 44.000 -→ A
// A -- 5.000 -→ B
// A -- 20.000 -→ D
// A -- 44.000 -→ T
// A -- 15.000 -→ S
// D -- 11.000 -→ F
// D -- 16.000 -→ T
// D -- 20.000 -→ A
// D -- 30.000 -→ B
// D -- 2.000 -→ E
}
```
```Output:

```

#### func NewGraphFromJSON ¶

`func NewGraphFromJSON(rd io.Reader, graphID string) (Graph, error)`

NewGraphFromJSON returns a new Graph from a JSON file. Here's the sample JSON data:

```{
"graph_00": {
"S": {
"A": 100,
"B": 14,
"C": 200
},
"A": {
"S": 15,
"B": 5,
"D": 20,
"T": 44
},
"B": {
"S": 14,
"A": 5,
"D": 30,
"E": 18
},
"C": {
"S": 9,
"E": 24
},
"D": {
"A": 20,
"B": 30,
"E": 2,
"F": 11,
"T": 16
},
"E": {
"B": 18,
"C": 24,
"D": 2,
"F": 6,
"T": 19
},
"F": {
"D": 11,
"E": 6,
"T": 6
},
"T": {
"A": 44,
"D": 16,
"F": 6,
"E": 19
}
},
}
```

#### func NewGraphFromYAML ¶

`func NewGraphFromYAML(rd io.Reader, graphID string) (Graph, error)`

NewGraphFromYAML returns a new Graph from a YAML file. Here's the sample YAML data:

graph_00:

```S:
A: 100
B: 14
C: 200
A:
S: 15
B: 5
D: 20
T: 44
B:
S: 14
A: 5
D: 30
E: 18
C:
S: 9
E: 24
D:
A: 20
B: 30
E: 2
F: 11
T: 16
E:
B: 18
C: 24
D: 2
F: 6
T: 19
F:
D: 11
E: 6
T: 6
T:
A: 44
D: 16
F: 6
E: 19
```

#### type ID ¶

```type ID interface {
// String returns the string ID.
String() string
}```

ID is unique identifier.

#### func BFS ¶

`func BFS(g Graph, id ID) []ID`

1. BFS(G, v): 1.
2. let Q be a queue
3. Q.push(v)
4. label v as visited 5.
5. while Q is not empty: 7.
6. u = Q.dequeue() 9.
7. for each vertex w adjacent to u: 11.
8. if w is not visited yet:
9. Q.push(w)
10. label w as visited

#### func BellmanFord ¶

`func BellmanFord(g Graph, source, target ID) ([]ID, map[ID]float64, error)`

BellmanFord returns the shortest path using Bellman-Ford algorithm This algorithm works with negative weight edges. Time complexity is O(|V||E|). (http://courses.csail.mit.edu/6.006/spring11/lectures/lec15.pdf) It returns error when there is a negative-weight cycle. A negatively-weighted cycle adds up to infinite negative-weight.

1. BellmanFord(G, source, target) 1.
2. distance[source] = 0 3.
3. for each vertex v in G: 5.
4. if v ≠ source:
5. distance[v] = ∞
6. prev[v] = undefined 9. 10.
7. for 1 to |V|-1: 12.
8. for every edge (u, v): 14.
9. alt = distance[u] + weight(u, v)
10. if distance[v] > alt:
11. distance[v] = alt
12. prev[v] = u 19. 20.
13. for every edge (u, v): 22.
14. alt = distance[u] + weight(u, v)
15. if distance[v] > alt:
16. there is a negative-weight cycle 26. 27.
17. path = []
18. u = target
19. while prev[u] is defined:
20. path.push_front(u)
21. u = prev[u] 33.
22. return path, prev

#### func DFS ¶

`func DFS(g Graph, id ID) []ID`

DFS does depth-first search, and returns the list of vertices. (https://en.wikipedia.org/wiki/Depth-first_search)

1. DFS(G, v): 1.
2. let S be a stack
3. S.push(v) 4.
4. while S is not empty: 6.
5. u = S.pop() 8.
6. if u is not visited yet: 10.
7. label u as visited 12.
8. for each vertex w adjacent to u: 14.
9. if w is not visited yet:
10. S.push(w)

#### func DFSRecursion ¶

`func DFSRecursion(g Graph, id ID) []ID`

DFSRecursion does depth-first search recursively.

1. DFS(G, v): 1.
2. if v is visited:
3. return 4.
4. label v as visited 6.
5. for each vertex u adjacent to v: 8.
6. if u is not visited yet:
7. recursive DFS(G, u)

#### func Dijkstra ¶

`func Dijkstra(g Graph, source, target ID) ([]ID, map[ID]float64, error)`

Dijkstra returns the shortest path using Dijkstra algorithm with a min-priority queue. This algorithm does not work with negative weight edges. (https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm)

1. Dijkstra(G, source, target) 1.
2. let Q be a priority queue
3. distance[source] = 0 4.
4. for each vertex v in G: 6.
5. if v ≠ source:
6. distance[v] = ∞
7. prev[v] = undefined 10.
9. while Q is not empty: 14.
10. u = Q.extract_min()
11. if u == target:
12. break 18.
13. for each child vertex v of u: 20.
14. alt = distance[u] + weight(u, v)
15. if distance[v] > alt:
16. distance[v] = alt
17. prev[v] = u
18. Q.decrease_priority(v, alt) 26.
19. reheapify(Q) 28. 29.
20. path = []
21. u = target
22. while prev[u] is defined:
23. path.push_front(u)
24. u = prev[u] 35.
25. return path, prev

#### func TopologicalSort ¶

`func TopologicalSort(g Graph) ([]ID, bool)`

TopologicalSort does topological sort(ordering) with DFS. It returns true if the graph is a DAG (no cycle, with a topological sort). False if the graph is not a DAG (cycle, with no topological sort).

1. TopologicalSort(G) 1.
2. L = Empty list that will contain the sorted nodes
3. isDAG = true 4.
4. for each vertex v in G: 6.
5. if v.color == "white": 8.
6. topologicalSortVisit(v, L, isDAG) 10. 11. 12. 13.
7. topologicalSortVisit(v, L, isDAG) 15.
8. if v.color == "gray":
9. isDAG = false
10. return 19.
11. if v.color == "white": 21.
12. v.color = "gray": 23.
13. for each child vertex w of v:
14. topologicalSortVisit(w, L, isDAG) 26.
15. v.color = "black"
16. L.push_front(v)

#### type Node ¶

```type Node interface {
// ID returns the ID.
ID() ID
String() string
}```

Node is vertex. The ID must be unique within the graph.

#### func NewNode ¶

`func NewNode(id string) Node`

#### type StringID ¶

`type StringID string`

#### func (StringID) String ¶

`func (s StringID) String() string`

## Directories ¶

Path Synopsis
Package testgraph contains graph test data.
Package testgraph contains graph test data.