GoGraph

README

GoGraph

Final project for CIS 1930. Implements a graph data structure and graph algorithms for Go.

Installing

Run $ go get github.com/julcim/GoGraph in your terminal to install the package, and then use it as you desire.

Simple Usages

var g Graph
g.size = 3
g.graph = make([]adjList, 3)
g.InitializeGraph()
g.AddEdge(0, 1, 3)
g.AddEdge(0, 2, 1)
g.AddEdge(2, 3, 1)
g.AddEdge(1, 3, 4)
distances := g.Dijkstra(0)
// distance[0] = 0
// distance[1] = 3
// distance[2] = 1
// distance[3] = 2

Documentation

Documentation for the package can be found here.

Note: When using this library avoid reading and writing to a graph concurrently or writing concurrently to maintain thread safety. Reading concurrently will not pose a threat to thread safety.

License

GoGraph uses MIT License

Documentation

Overview

Package GoGraph implements graph algorithms and a Graph class to build graphs to run those algorithms on.

Index

• type Edge
• type Graph
  • func (g *Graph) AddEdge(u int, v int, newWeight int) error
  • func (g *Graph) AdjList() (adjList []adjList)
  • func (g *Graph) Bfs(source int) []int
  • func (g *Graph) DFS() []int
  • func (g *Graph) Dijkstra(source int) (distance []int)
  • func (g *Graph) GetWeight(u int, v int) (int, error)
  • func (g *Graph) HasEdge(u int, v int) (bool, error)
  • func (g *Graph) InitializeGraph()
  • func (g *Graph) Kahn() (output []int)
  • func (g *Graph) Kruskal() *Graph
  • func (g *Graph) Neighbors(u int) []int
  • func (g *Graph) Size() (size int)

Types

type Edge

type Edge struct {
	// contains filtered or unexported fields
}

An Edge is used by the Kruskal class to correctly use the Union-Find data structure. An Edge has a start vertex, end vertex, and weight, which can be set to 0 for an unweighted graph.

type Graph

type Graph struct {
	// contains filtered or unexported fields
}

Graph represents a graph data structure and has parameters of size of the graph (number of vertices) and a slice adjList which corresponds to the adjacency list of the graph. This is implemented such that the index of the adjList corresponds to the vertex of the Graph.

func (*Graph) AddEdge

func (g *Graph) AddEdge(u int, v int, newWeight int) error

AddEdge creates a vertex from u to v with a weight newWeight in a Graph. If the vertices are not in the bounds of the Graph, AddEdge throws an error.

func (*Graph) AdjList

func (g *Graph) AdjList() (adjList []adjList)

AdjList returns the adjList parameter of the Graph

func (*Graph) Bfs

func (g *Graph) Bfs(source int) []int

Bfs runs the breadth-first-search algorithm on a given Graph and source. It returns the parent array of the Graph produced by the breadth-firt-search. The parent array is structured so that if there exists an edge from vertex a -> b, then in the output, parent[b] = a.

func (*Graph) DFS

func (g *Graph) DFS() []int

DFS runs the depth-first-search algorithm on a Graph. After running, it outputs the parent array from the depth-first-search, which is structured as parent[b] = a if a is deemed to be b's parent in the depth-first-search.

func (*Graph) Dijkstra

func (g *Graph) Dijkstra(source int) (distance []int)

Dijkstra runs the known Dijkstra algorithm on a given Graph and source. It outputs the shortest path from the source to all vertices in the graph in the form of an array. This array is structured such that distance[a] is the distance from the source to a.

func (*Graph) GetWeight

func (g *Graph) GetWeight(u int, v int) (int, error)

GetWeight is called on a Graph and two vertices u and v. It returns the weight of a directed edge from u to v. If the edge u to v does not exist, or the vertices are out of range of the size of the graph, GetWeight throws an error.

func (*Graph) HasEdge

func (g *Graph) HasEdge(u int, v int) (bool, error)

HasEdge is called on a Graph and two vertices. It outputs true if there is a directed edge between the two vertices and false otherwise. HasEdge throws an error if vertices outside the bounds are inputted.

func (*Graph) InitializeGraph

func (g *Graph) InitializeGraph()

InitializeGraph initializes the input Graph by filling the adjancey list with empty maps to avoid errors when adding edges.

func (*Graph) Kahn

func (g *Graph) Kahn() (output []int)

Kahn runs Kahn's algorithm for topologically sorting a Directed Acyclic Graph (DAG). For a DAG, Kahn will return an output slice in topologically sorted order from index 0. The behavior of this function is undefined if not called on a DAG.

func (*Graph) Kruskal

func (g *Graph) Kruskal() *Graph

Kruskal runs the Kruskal algorithm on a given Graph and outputs a Graph pointer to a Minimum Spanning Tree of that graph.

func (*Graph) Neighbors

func (g *Graph) Neighbors(u int) []int

Neighbors returns all the outgoing vertices/edges from a given vertex u in a given Graph.

func (*Graph) Size

func (g *Graph) Size() (size int)

Size returns the size parameter of the Graph