goraph

package module
v0.0.0-...-ad625ac Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Apr 10, 2022 License: MIT Imports: 9 Imported by: 28

README

goraph Go Report Card Build Status Godoc

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.

Index

Examples

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.
  8. Q.add_with_priority(v, distance[v]) 12. 13.
  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
  11. v.lowLink = 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)
  17. v.lowLink = min(v.lowLink, w.lowLink) 25.
  18. else if w is in S:
  19. v.lowLink = min(v.lowLink, w.index) 28.
  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

	// AddNode adds a node to a graph, and returns false
	// if the node already existed in the graph.
	AddNode(nd Node) bool

	// 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

BFS does breadth-first search, and returns the list of vertices. (https://en.wikipedia.org/wiki/Breadth-first_search)

  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.
  8. Q.add_with_priority(v, distance[v]) 12.
  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

Source Files

View all Source files

Directories

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

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.