goraph

README

goraph

Package goraph provides graph visualizing tools and algorithm implementations.

• Getting Started
• Package Hierarchy
• Example
• Testing Graphs
• List(Linked List) vs. Slice(Array)
• What is Graph? (YouTube Clips)
• Adjacency List vs. Adjacency Matrix
• Channel
• C++ Version
• package gotree

Getting Started

• godoc.org
• gowalker.org

go get github.com/gyuho/goraph

↑ top

Package Hierarchy

goraph/							# Top Package
	
	algorithm/					# Package: Graph Algorithms
		bfs/					# Package: Breadth First Search Algorithm
		dfs/					# Package: Depth First Search Algorithm
		sp/						# Package: Shortest Path Algorithm (Dijkstra, Bellman-Ford)
		spbf/					# Package: Shortest Path Algorithm for Negative Edges (Bellman-Ford)
		spd/					# Package: Shortest Path Algorithm for Positive Edges (Dijkstra)
		spfw/					# Package: Shortest Path Algorithm for Positive Edges (Floyd-Warshall)
		tsdag/					# Package: Topological Sort, Detects whether it is a DAG
		tsdfs/					# Package: Topological Sort using DFS, Not Detecting DAG
		tskahn/					# Package: Topological Sort by Arthur Kahn(1962), Detects DAG
		mst/					# Package: Minimum Spanning Tree (Kruskal, Prim)
			kruskal/			# Package: Kruskal Minimum Spanning Tree Algorithm
			prim/				# Package: Prim Minimum Spanning Tree Algorithm
		scc/					# Package: Strongly Connected Component
			tarjan/				# Package: Tarjan Strongly Connected Component Algorithm
			kosaraju/			# Package: Kosaraju Strongly Connected Component Algorithm
		maxflow/				# Package: Maximum Network Flow
			fdfk/				# Package: Ford-Fulkerson Maximum Network Flow Algorithm

	benchmark/					# Package: Benchmark, Comparison of graph representations

	example_files/				# Learn DOT
	example_files/				# Files for Example
	example_with_script/		# Example Script (Program)
	example_with_testing/		# Example Code

	goroup/						# Package: Disjoint Set for Graph Nodes
		gsdset/					# Package: Set Operation with the package graph/gsd

	graph/						# Package: Graph Data Structure
		gl/						# Package: Adjacency List, Linked List(container/list), No Duplicate Edges
		gld/					# Package: Adjacency List, Linked List(container/list), Allow Duplicate Edges
		gm/						# Package: Adjacency List, Map, No Duplicate Edges
		gs/						# Package: Adjacency List, Slice, No Duplicate Edges
		gsd/					# Package: Adjacency List, Slice, Allow Duplicate Edges
		gsdflow/				# Package: Customized gsd for Network Flow Algorithm
		gt/						# Package: Adjacency Matrix, Map, No Duplicate Edges

	viz/						# Package: Graph Visualization (Graphviz)
		dot/					# Package: Convert JSON graph data to DOT

External Package

• gson: JSON Import Package
• gosequence: Customized Slice(Array) Data Structure
• Graphviz: Graph Visualization

↑ top

Example

Shortest Path

fmt.Println("Dijkstra Shortest Path on testgraph10:")
g10 := gsd.JSONGraph("../example_files/testgraph.json", "testgraph.010")
fmt.Println(spd.SPD(g10, "A", "E"))
fmt.Println(g10.ShowPrev("E"))
fmt.Println(g10.ShowPrev("D"))
fmt.Println(g10.ShowPrev("B"))
fmt.Println(g10.ShowPrev("C"))
fmt.Println(g10.ShowPrev("A"))
/*
   A(=0) → C(=9) → B(=19) → D(=34) → E(=36)
   Prev of E:  C D
   Prev of D:  B
   Prev of B:  C
   Prev of C:  A
   Prev of A:

   BackTrack keeps adding the Prev vertex
   with the biggest StampD, recursively
   until we reach the source
*/

println()
fmt.Println("Dijkstra Shortest Path on testgraph10o:")
g10o := gsd.JSONGraph("../example_files/testgraph.json", "testgraph.010")
fmt.Println(spd.SPD(g10o, "E", "A"))
fmt.Println(g10o.ShowPrev("A"))
fmt.Println(g10o.ShowPrev("B"))
fmt.Println(g10o.ShowPrev("C"))
fmt.Println(g10o.ShowPrev("F"))
fmt.Println(g10o.ShowPrev("E"))
/*
   E(=0) → F(=9) → C(=11) → B(=21) → A(=22)
   Prev of A:  F B
   Prev of B:  C
   Prev of C:  E F
   Prev of F:  E
   Prev of E:

   BackTrack keeps adding the Prev vertex
   with the biggest StampD, recursively
   until we reach the source
*/

↑ top

func Test_JSON_ShowSPD(test *testing.T) {
	g4 := gsd.JSONGraph("../../example_files/testgraph.json", "testgraph.004")
	fmt.Println(ShowSPD(g4, "S", "T", "testgraph.004_spd.dot"))
}

↑ top

---

BFS, DFS

func Test_JSON_ShowBFS(test *testing.T) {
	g4 := gsd.JSONGraph("../../example_files/testgraph.json", "testgraph.004")
	fmt.Println(ShowBFS(g4, g4.FindVertexByID("S"), "testgraph.004_bfs.dot"))
}

func Test_JSON_ShowDFS(test *testing.T) {
	g4 := gsd.JSONGraph("../../example_files/testgraph.json", "testgraph.004")
	fmt.Println(ShowDFS(g4, "testgraph.004_dfs.dot"))
}

↑ top

---

Minimum Spanning Tree

Kruskal Algorithm

func Test_JSON_ShowMST(test *testing.T) {
	g14 := gsd.JSONGraph("../../../example_files/testgraph.json", "testgraph.014")
	ShowMST(g14, "g14mst_kruskal.dot")
}

↑ top

---

Prim Algorithm

func Test_JSON_ShowMST(test *testing.T) {
	g14 := gsd.JSONGraph("../../../example_files/testgraph.json", "testgraph.014")
	ShowMST(g14, "g14mst_prim.dot")
}

↑ top

Testing Graphs

↑ top

List(Linked List) vs. Slice(Array)

Goraph mainly uses customized slice(array) data structure implemented in package gsd, instead of using linked list. To store vertices and edges, we can either use "container/list" or slice(array) data structure. It depends on the number of elements in the lists. Linked list will be more efficient, when we need to do many deletions in the 'middle' of the list. The more elements we have in graph , the less efficient a slice becomes. When the ordering of the elements isn't important, then it is most efficient to use a slice and deleting an element by replacing it by the last element and reslicing to shrink the size(len) by 1. We can mitigate the deletion problem using this slice trick but there is no way to mitigate the slowness of traversing linked list. Both ways are implemented, but mainly this will be run with slice.

Reference

• Go(Golang) Slice vs. List?
• Bjarne Stroustrup: Why you should avoid Linked Lists (C++)
• Why you should never use linked-list

↑ top

What is Graph? (YouTube Clips)

• Tree, Heap, Graph (Playlist)

• Graph: Data Structure with Nodes and Edges

• There are various ways to connect nodes

  • Doubly Connected Directed Graph (Undirected Graph)
  • Singly Connected Directed Graph.

• Path: sequence of vertices connected by edges

• Simple Path: path with NO repeated vertices

• Cycle: path with at least one edge whose first and last vertices are the same

• Simple Cycle: cycle with NO repeated edges or vertices

• Length of path, cycle: its number of edges

• Connectivity: Graph is connected if there is a path from every vertex to every other vertex

• Acyclic Graph: graph with NO cycles

• Acyclic Connected Graph: Tree is an Acyclic Connected Graph

• Forest: Disjoint Set of Trees (have no vertices in common)

• Spanning Tree of a Connected Graph

  • subgraph that contains all of that graph’s vertices subgraph that is a single tree

• Spanning Forest of a Graph

  • the union of spanning trees of its connected components

• Spanning Tree of a Connected Graph

  • subgraph that contains all of that graph’s vertices subgraph that is a single tree

• Degree of a Vertex

  • number of edges incident to the vertex(loop counts as 2).

• Predecessor of a Vertex

• edge(u, v), then vertex v is the descendant of u. Vertex u is the predecessor, or parent/ancestor, of vertex v. v.d is the distance from the source; s.d is 0 when s is the source node. u.d is 1 when the distance from source to u is 1. This is implemented as InVertices in goraph.

↑ top

Adjacency List vs. Adjacency Matrix

• When Graph G = (V, E) = (Vertex, Edge)

  • |V| is the number of vertices in a graph
  • |E| is the number of edges in a graph

• Sparse Graph

  • |E| is much less than |V|^2
  • Relatively few edges present

• Dense Graph

  • |E| is close to |V|^2
  • Relatively few edges missing

• Adjacency List: good for Sparse Graph

  • Use memory in proportion to |E|
  • So save memory when G is sparse
  • Fast to iterate over all edges
  • Slightly slower lookup to check for an edge

• Adjacency Matrix: good for Dense Graph

  • Use O(n^2) memory
  • Fast lookups to check for presence of an edge
  • Slow to iterate over all edges

↑ top

Channel

func (v *VertexT) GetEdgeTsChannelFromThisVertex() chan *EdgeT {
	edgechan := make(chan *EdgeT)

	go func() {
		defer close(edgechan)
		for e := v.OutGetEdge().Front(); e != nil; e = e.Next() {
			edgechan <- e.Value.(*EdgeT)
		}
	}()
	return edgechan
}

It's not idiomatic Go style to use channels, simply for the ability to iterate over them. It's not efficient, and it can easily lead to an accumulation of idle goroutines: Consider what happens when the caller of GetEdgeTsChannelFromThisVertex discards the channel before reading to the end. It's better to use container/list rather than channel.

↑ top

C++ Version

I have another Graph Algorithm project written in C++. It is NOT maintained anymore, but if interested check out HERE.

↑ top

package gotree

Tree is just another kind of graph data structure. If interested check out gotree.

↑ top

Tree

Tree (a graph G with V vertices) if and only if it satisfies any of the following 5 conditions.

• G has V-1 edges and no cycles
• G has V-1 edges and is connected
• G is connected, and removing any edge disconnects the - G
• G is acyclic, and adding any edge creates a cycle in G
• Exactly one simple path connects each pair of vertices in G

↑ top

Documentation

Overview

Package goraph provides graph visualizing tools and algorithm implementations.