Graphs In Golang

Implementation of graph data structure

Definition

Graph: A graph, unlike arrays, is a non-linear data structure composed of vertices and edges.

Directed Graphs: A graph where association between two nodes are mentioned is such a way that A -> B only mentions there is an edge between Point-A and Point-B where A can reach B but B cannot reach A. Such graphs are called directed graphs.

Undirected Graphs: A graph where association between two nodes are mentioned is such a way that A -> B mentions there is an edge between Point-A and Point-B where A can reach B & B can reach A as well. Such graphs are called undirected graphs.

Methods

1. AddEdge: This method is responsible to add a directed edge from Point-A to Point-B.
2. AddVertex: This method is responsible to add a vertex/ node to a graph.

Below we have an implementaton of a directed graph:

package datastructures

import "fmt"

// Graph structure
type Graph struct {
 vertices []*Vertex
}

// Adjacent Vertex
type Vertex struct {
 key      int
 adjacent []*Vertex
}

// AddVertext will add a vertex to a graph
func (g *Graph) AddVertex(vertex int) error {
 if contains(g.vertices, vertex) {
  err := fmt.Errorf("Vertex %d already exists", vertex)
  return err
 } else {
  v := &Vertex{
   key: vertex,
  }
  g.vertices = append(g.vertices, v)
 }
 return nil
}

// AddEdge will add ad endge from a vertex to a vertex
func (g *Graph) AddEdge(to, from int) error {
 toVertex := g.getVertex(to)
 fromVertex := g.getVertex(from)
 if toVertex == nil || fromVertex == nil {
  return fmt.Errorf("Not a valid edge from %d ---> %d", from, to)
 } else if contains(fromVertex.adjacent, toVertex.key) {
  return fmt.Errorf("Edge from vertex %d ---> %d already exists", fromVertex.key, toVertex.key)
 } else {
  fromVertex.adjacent = append(fromVertex.adjacent, toVertex)
  return nil
 }
}

// getVertex will return a vertex point if exists or return nil
func (g *Graph) getVertex(vertex int) *Vertex {
 for i, v := range g.vertices {
  if v.key == vertex {
   return g.vertices[i]
  }
 }
 return nil
}

func contains(v []*Vertex, key int) bool {
 for _, v := range v {
  if v.key == key {
   return true
  }
 }
 return false
}

func (g *Graph) Print() {
 for _, v := range g.vertices {
  fmt.Printf("%d : ", v.key)
  for _, v := range v.adjacent {
   fmt.Printf("%d ", v.key)
  }
  fmt.Println()
 }
}

func PrintEgDirectedGraph() {
 g := &Graph{}
 g.AddVertex(1)
 g.AddVertex(2)
 g.AddVertex(3)
 g.AddEdge(1, 2)
 g.AddEdge(2, 3)
 g.AddEdge(1, 3)
 g.AddEdge(3, 1)
 g.Print()
}

/* 
// Call In Main:: datastructures.PrintEgDirectedGraph()
// Output:
// 1 : 3 
// 2 : 1 
// 3 : 2 1 
*/

I hope this article helps to understand the graph in golang. Please comment below in case of any errors or further suggestions. Thanks!