# a ridiculous graph

Sep 2, 2014

Following in the theme of the previous post, here (see linked Gist) is a concurrent graph. Again, this is not an efficient way to do something like this, it’s just a fun example of showing something that’s easy in Go but probably harder or more verbose in other languages.

The basic idea here is that every node is a goroutine. So instead of using some structure like a matrix or an adjacency list to “get a handle” on all the nodes and their connections, you let the nodes take care of that themselves. Graph algorithms (trivial ones here are self-identification and depth calculation) are then constructed as interactions with the nodes, without an explicit traversal of vertices and edges.

``````func node_agent(node *Node) {
for {
cmd := <-node.comm
switch cmd.cmdtype {
case NameCmd:
fmt.Println("I am ", node.name)
case PingCmd:
cmd.cmdchan <- PingCmd
case SetDepthCmd:
// Ask all neighbors to modify depth, and pass
// along the notification channel to them
depth := cmd.cmdarg
if node.state.depth > 0 {
break
}
node.state.depth = depth
for _, ch := range node.neighbors {
ch <- Command{SetDepthCmd, cmd.cmdchan, depth + 1}
}
cmd.cmdchan <- 1
case GetDepthCmd:
cmd.cmdchan <- node.state.depth
}
}
}
``````

The “Hello world” in this scenario is just finding out which nodes exist, which is something as follows:

``````func IsAlive(node *Node) bool {
// Ping the node with a 10ms timeout
pingchan := make(chan int)
node.comm <- Command{PingCmd, pingchan, 0}
select {
case <-pingchan:
return true
case <-time.After(10 * time.Millisecond):
return false
}
}

func printGraph(g *Graph) {
fmt.Println("Graph :")

for _, node := range g.nodes {
if IsAlive(node) {
node.comm <- Command{NameCmd, nil, 0}
}
}
}
``````

A slightly more complicated operation is finding the depth of all nodes relative to the root node:

``````
func calculateDepths(g *Graph) {
// Recursively trigger computation from root node

for i := 0; i < len(g.nodes); i++ {
// Wait for every node to receive this atleast once