Janus: a tiny graph library in Go

Janus: a tiny graph library in Go
Photo by GuerrillaBuzz Blockchain PR Agency / Unsplash

All of the code for this post is at github.com/dylanlott/janus

Janus is my latest toy library that I wrote as a way to experiment with graph structures. I work with networks all day so it feels applicable and maybe even overdue to write a raw graph library like this.

I plan to use this for some network simulation experiments by attaching a generic value type to the Node and exposing it in an asynchronous interface. Stay tuned for that or follow the repo. As always, it's open source.

Implementation details

Writing this was a good exercise in interface design because while it's tempting to treat the graph like a CRUD resource, it serves better to give it some fine tuned functions and compose those CRUD functions as higher abstractions over the library.

// The core of janus' graph model.
// Graph is our new concrete implementation.
type Graph struct {
	nodes []*GraphNode
}

// Edge is a triplet of start node, end node, and the edge weight.
type Edge [3]int64

// GraphNode is a node in our NodeBuilder
type GraphNode struct {
	id    int64
	edges map[int64]int64 // a connection to another node and the connection's weight
}

This is the core of Janus' graph model. We declare a Graph, which is a slice of nodes. Each node has a map of Edges. We define the Edge type as a slice of integers (effectively a triplet) of a start, an end, and a weight. The start and end are the IDs of the nodes in the slice.

// AddNode adds a node to the end of the list with an empty set of edges.
func (n *Graph) AddNode() int64 {
	id := len(n.nodes)
	n.nodes = append(n.nodes, &GraphNode{
		id:    int64(id),
		edges: map[int64]int64{},
	})
	return int64(id)
}

Nodes have int64 IDs and we assign them an ID that is the same as the length of the node array, creating a zero indexed monotonically increasing node ID system. It's simple but effective, since other properties are implementation details. For example, if we want more complicated node identifier types, we would instead make those part of the node's value, which will come later. The id in this context is specifically meant to be an internal value that is decoupled from outside.

// AddEdge adds a start to end edge and gives it a weight of w
func (n *Graph) AddEdge(start int64, end int64, weight int64) {
	n.nodes[start].edges[end] = weight
}

In graph theory, we express a connection between two nodes as an edge.  Edges are a little more complicated than the nodes but still pretty simple. Remember, edges are a triplet of start, end, and weight. The node weight allows you to rank connections between the same set of nodes by a second value. To add an edge, we update starting nodes edges to point at the ending node's ID and assign it the proper weight. This creates a one way connection. If we want bidirectional connection, we would handle that by calling AddEdge with the start and end reversed.

// Neighbors returns a list of all node IDs that share an edge with the node.
func (n *Graph) Neighbors(id int64) []int64 {
	neighbors := []int64{}
	for _, node := range n.nodes {
		// for each edge in the node's list, record its weight.
		for edge := range node.edges {
			if node.id == id {
				neighbors = append(neighbors, edge)
			}
			if edge == id {
				neighbors = append(neighbors, node.id)
			}
		}
	}
	return neighbors
}

The neighbors function is where we start to see how graph search can bubble into crazy space search complexity. To find the neighbors of a given node, we must check all of the nodes for edges that match the target node's ID, make a slice out of that, and then return it. With even moderate numbers of nodes this can start to take a substantial amount of time.

// Edges returns the list of edges in the graph.
func (n *Graph) Edges() []Edge {
	// create a slice of edges as large as the list of nodes we have
	edges := make([]Edge, 0, int64(len(n.nodes)))
	// iterate over all nodes and collect their edges
	for nodeID := range n.nodes {
		for peer, weight := range n.nodes[nodeID].edges {
			// loops over the edges in each node in the ID list and
			// creates an Edge entry for each.
			edges = append(edges, Edge{int64(nodeID), peer, weight})
		}
	}

	return edges
}

Edges is similarly complex. Edges returns the list of all edges in the graph. In order to do this, we again have to iterate over all of the nodes, collect their edges, and return the set of all edges. Querying Nodes and Edges returns data to build the entire graph.

This gives us a graph data structure capable of representing arbitrary complexity between its constituent nodes.

Next time we implement graph search!