Graph: Simple implementation non-linear data structure with Go
Tags: datastructures, algorithms, go, computerscience
Published: 2024-01-04 04:44:53

## Brief of Graph

Graph is a non-linear data structure in programming. This data structure commonly implemented for short-path-finding and often use to validate programming skill in a Software Engineer job.

Graph built with connection nodes or commonly called **Vertex**, each connected Vertex called **Edge**, and distance of edge usually called **Adjacent**.

![Simple graph](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/3b8iiz88xh45xjmvh8za.png)

## The Algorithm

First of all, you need to define the data storage, let's use Golang `struct`.

```go
type Graph struct {
	Vertice []*Vertex
}

type Vertex struct {
	Key      int
	Adjacent []*Vertex
}

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

	return false
}
```
There are two data types defined that called _Graph_ and _Vertex_. The Graph is base data type that store all Vertices that inputted in the main code in the future. Then Vertex defined to store the _Key_ and all _Adjacent_.

In the section below the definition of types, the _isExist_ function written to validate is inputted _Key_ exist in vertices or not. We need to check the key to avoid duplicated inserted key into vertices.

Now, let's write a method of type of _Graph_ to add the Vertices. This method consist of:

1. Check is the _Key_ exists?
2. Add _Key_ into graph vertices.
 
```go
func (g *Graph) AddVertex(vertex int) error {
	// Check is vertex available
	if isExist(vertex, g.Vertice) {
		return fmt.Errorf("vertex is exist")
	}

	// Insert vertex into graph
	g.Vertice = append(g.Vertice, &Vertex{
		Key: vertex,
	})

	return nil
}
```

At this moment, we can add the vertex into our struct, but we need to get it. Let's write the _GetVertex_ method in our code. We just need to get our vertex by it's key that inserted before. If the key is match, return the vertex from vertices.

```go
func (g *Graph) GetVertex(vertex int) *Vertex {
	for i, v := range g.Vertice {
		if v.Key == vertex {
			return g.Vertice[i]
		}
	}

	return nil
}
```

Remember, we need to connect the vertex and to set the Edge and append the destination vertex into adjacent of current vertex. So, the logic suppose like this:

1. Get the current Vertex (from Vertex) and destination vertex. If it's not exist, return error.
2. Check the destination vertex in current adjacent is exist or not. It should be doesn't exist.
3. If everything okay, let's insert destination vertex into current adjacent.

```go
func (g *Graph) AddEdge(from int, dest int) error {
	// Check is vertext exists
	fromVertex := g.GetVertex(from)
	destVertex := g.GetVertex(dest)
	if fromVertex == nil || destVertex == nil {
		return fmt.Errorf("vertex from (%v) --> (%v) is not valid", from, dest)
	}

	// Check is adjacent vertex exists or not
	if isExist(destVertex.Key, fromVertex.Adjacent) {
		return fmt.Errorf("edge from vertex (%v) --> (%v) already exists", fromVertex.Key, destVertex.Key)
	}

	// insert new adjacent for from and dest vertex
	fromVertex.Adjacent = append(fromVertex.Adjacent, destVertex)
	return nil
}
```

Finally, everything is set, and we need to print all vertex and its adjacent, let's write the code.

```go
func (g *Graph) Print() {
	for _, val := range g.Vertice {
		fmt.Printf("(%v): ", val.Key)
		for i, adj := range val.Adjacent {
			if i > 0 {
				fmt.Printf(" -> ")
			}
			fmt.Printf("(%v)", adj.Key)
		}
		fmt.Println()
	}
}
```

## Let's run the code

To run these code, we need to write the main function.
```go
func main() {
	graph := &Graph{}
	graph.AddVertex(0)
	graph.AddVertex(1)
	graph.AddVertex(2)
	graph.AddVertex(3)
	graph.AddVertex(4)
	graph.AddVertex(5)
	graph.AddVertex(6)

	// Set the edges
	graph.AddEdge(0, 1)
	graph.AddEdge(0, 2)
	graph.AddEdge(0, 5)

	graph.AddEdge(1, 0)
	graph.AddEdge(2, 0)
	graph.AddEdge(5, 0)

	graph.AddEdge(2, 1)
	graph.AddEdge(2, 3)
	graph.AddEdge(2, 6)

	graph.AddEdge(1, 2)
	graph.AddEdge(3, 2)
	graph.AddEdge(6, 2)

	graph.AddEdge(6, 5)
	graph.AddEdge(5, 6)

	graph.Print()
}
```

Output:
```bash
(0): (1) -> (2) -> (5)
(1): (0) -> (2)
(2): (0) -> (1) -> (3) -> (6)
(3): (2)
(4): 
(5): (0) -> (6)
(6): (2) -> (5)
```

For the full code, please look at my gists here: [Graph Gists](https://gist.github.com/wahyurudiyan/1ae012d17dd53097c1b932da9734e468)