Build Directed Graph

Graphs are a fundamental data structure in computer science, used to represent relationships between objects in a wide range of applications. In this article, we will explore how to build a graph in Go, one of the most popular programming languages used for building networked and distributed systems.

Before we start, let’s briefly define what a graph is. A graph is a collection of nodes or vertices, each of which may be connected to other nodes by edges. Edges can be directed or undirected, and can have weights or costs associated with them. Graphs are used to represent a variety of data structures, such as social networks, road networks, computer networks, and more.

Graphs are used in a wide range of applications in computer science and beyond. Here are a few examples of use cases where graphs are particularly useful:

1. Social networks: Social networks are naturally represented as graphs, where users are represented as nodes and their connections as edges. Graph algorithms can be used to analyze social networks, find clusters of users with similar interests, or identify influencers in the network.
2. Mapping and routing: Graphs are commonly used to represent maps, with nodes representing cities or landmarks, and edges representing roads or other routes between them. Graph algorithms can be used to find the shortest path between two points, or to identify regions that are not easily accessible.
3. Computer networks: Networks of computers can be represented as graphs, with nodes representing individual computers or network devices, and edges representing connections between them. Graph algorithms can be used to identify bottlenecks in the network, find the most efficient routing paths, or detect anomalies and security threats.
4. Recommendation systems: Recommendation systems often rely on graph algorithms to analyze large datasets of user preferences and suggest new items or content that users may be interested in. Graphs can be used to model the relationships between users and items, and algorithms can be used to identify patterns and similarities in the data.
5. Biological systems: Graphs are used to represent complex biological systems such as protein interactions, gene regulatory networks, and brain activity. Graph algorithms can be used to analyze these systems and identify patterns or anomalies that may be important for understanding biological processes or developing new therapies.

These are just a few examples of the many applications of graphs in computer science and other fields. By using graph algorithms and data structures, we can solve complex problems and gain new insights into the world around us.

To build a graph in Go, we will create three types: Node, Edge, and Graph.

type Node struct {
	Value string
	Edges []*Edge
}

type Edge struct {
	Start *Node
	End   *Node
	Cost  int
}

type Graph struct {
	Nodes []*Node
}

The Node type represents a node in the graph, and contains a Value field that can be used to store any type of value associated with the node. The Edges field is a slice of Edge pointers that represents the edges of the node.

The Edge type represents an edge in the graph, and contains two fields: Start and End, which are pointers to the start and end nodes of the edge, respectively. The Cost field is an integer that represents the cost or weight of the edge.

The Graph type represents the graph itself, and contains a slice of Node pointers. This allows us to keep track of all the nodes in the graph.

Now that we have defined our types, let’s create some methods to add nodes and edges to the graph.

func (g *Graph) AddNode(value string) *Node {
	node := &Node{
		Value: value,
	}

	g.Nodes = append(g.Nodes, node)

	return node
}

func (g *Graph) AddEdge(start, end *Node, cost int) {
	edge := &Edge{
		Start: start,
		End:   end,
		Cost:  cost,
	}

	start.Edges = append(start.Edges, edge)
}

Now, let’s define a method to get the neighbors of a node.

func (n *Node) Neighbors() []*Node {
    neighbors := []*Node{}

    for _, edge := range n.Edges {
        neighbors = append(neighbors, edge.End)
    }

    return neighbors
}

The Neighbors method returns a slice of its neighboring nodes.

Finally, let’s define a method to find a minimum cost from node start to end using Djikstra algorithms.

func (g *Graph) MinCost(start, end *Node) int {
	visited := make(map[*Node]bool)
	costs := make(map[*Node]int)

	// initialize all costs to infinity except for the starting node
	for _, node := range g.Nodes {
		costs[node] = math.MaxInt32
	}
	costs[start] = 0

	for {
		// find the unvisited node with the smallest cost
		var node *Node
		minCost := math.MaxInt32
		for _, n := range g.Nodes {
			if !visited[n] && costs[n] < minCost {
				minCost = costs[n]
				node = n
			}
		}

		if node == nil {
			break // no path found
		}

		visited[node] = true
		for _, neighbor := range node.Neighbors() {
			if !visited[neighbor] {
				cost := costs[node] + g.getCost(node, neighbor)
				if cost < costs[neighbor] {
					costs[neighbor] = cost
				}
			}
		}
	}

	// return the cost of the path from start to end
	return costs[end]
}

You can find the full code in https://go.dev/play/p/dcAHKXbOGac.