There are lots of topics in both practical and theoretical computer science that deal with graphs, lots of different kinds of graphs, lots of ways to represent a graph as a data structure, and lots of operations you’d want to perform on such a data structure. Like, “is this node in this graph?” or “is there any path from this node to that node in this graph?” and so on. Programming with graphs is a huge topic. In this series I want to explore a tiny subset of those topics. Specifically:
- How can we create an immutable data structure which represents a directed graph with labels on the edges?
- Given a directed acyclic graph (DAG), what are all the possible edge traversals through that graph starting from a particular node?
First things first. Like I said, there are a zillion different ways to represent a graph. I want to do so immutably — again, an immutable data type is one where “mutations” return a new object that is a mutated version of the original object, which stays the same. For my purposes today, I want to be able to take an existing graph, possibly empty, and insert new nodes and edges into that graph. The data structure I’m going to choose for my internal representation is that a graph consists of:
- an unordered, no-duplicates set of nodes of arbitrary type. Just like you can have a list of strings or a list of pairs of integers, I want to have a graph where the nodes are strings or giraffes or whatever.
- every node has an unordered, no-duplicates set of outgoing edges of arbitrary type. Again, I want to be able to make the edges anything I want. If I want a graph where the nodes are apples and the edges are tigers, I should be able to get that.
- an edge that leaves one node in a graph goes to another (or the same) node in the graph. That is, the edges have a direction to them; every edge starts at one node and goes to another.
Suppose my edges are integers and my nodes are strings. The constraints above imply that there can be edges 123 and 345 that both leave node “ABC” and arrive at node “XYZ”. But there cannot be an edge 123 from “ABC” to “DEF” and an edge 123 from “ABC” to “XYZ”; the edges leaving node “ABC” must be distinct in their values.
Like I said earlier, there are lots of different kinds of graphs, and these constraints work well for my purposes in this series. If, for example, I wanted edge labels to be costs, say, then this would not work well; if edge labels are costs then you want the opposite characteristics. That is, you want there to be only one edge between any pair of nodes, where that edge indicates the cost of traversal, and it is perfectly reasonable to have two edges leaving the same node with the same cost. But in my case I want the edges to uniquely identify a path through the graph.
With that set of characteristics in mind, we quickly realize that we could say that an immutable directed graph is nothing more than an immutable dictionary, where the dictionary keys are nodes and the dictionary values are themselves immutable dictionaries where the nested dictionary keys are edge values and the nested dictionary values are the destination nodes of those edges.
Rather than making my own immutable dictionary — because that’s not the point of this series — I’ll just use the System.Collections.Immutable package downloadable from NuGet to define my graph. Since this is first, just a super-thin wrapper around a dictionary reference, and second, logically a value, I’ll make it a struct.
using System;
using System.Collections.Generic;
using System.Collections.Immutable;
struct ImmutableDirectedGraph<N, E>
{
public readonly static ImmutableDirectedGraph<N, E> Empty =
new ImmutableDirectedGraph<N, E>(
ImmutableDictionary<N, ImmutableDictionary<E, N>>.Empty);
private ImmutableDictionary<N, ImmutableDictionary<E, N>> graph;
private ImmutableDirectedGraph(
ImmutableDictionary<N, ImmutableDictionary<E, N>> graph)
{
this.graph = graph;
}
To add a new node to the graph we first check to see if the graph already contains this node; if it does, we leave it alone. If not, we add it to the map with an empty set of outgoing edges.
public ImmutableDirectedGraph<N, E> AddNode(N node)
{
if (graph.ContainsKey(node))
return this;
return new ImmutableDirectedGraph<N, E>(
graph.Add(node, ImmutableDictionary<E, N>.Empty));
}
To add an edge to the graph, we first make sure that both nodes are in the graph. Once that’s taken care of, we get the edge set for the start node and add to it the new edge.
public ImmutableDirectedGraph<N, E> AddEdge(N start, N finish, E edge)
{
var g = this.AddNode(start).AddNode(finish);
return new ImmutableDirectedGraph<N, E>(
g.graph.SetItem(
start,
g.graph[start].SetItem(edge, finish))));
}
Remember, setting an item on an immutable dictionary gives you back a different dictionary with the new item added.
Finally, given a graph and a node, what are the outgoing edges? We could give an error if the node is not even in the graph, but I think it is reasonable to say that the edge set of a node that is not in the graph is the empty set:
public IReadOnlyDictionary<E, N> Edges(N node)
{
return graph.ContainsKey(node) ?
graph[node] :
ImmutableDictionary<E,N>.Empty;
}
I’m not going to need edge and node removal for my purposes; doing so is left as an exercise to the reader. Note that the data structure I’ve sketched out here does not have an efficient mechanism for removing the edges that are pointing to a removed node; modifying the data structure to make that efficient is an interesting challenge that I’m not going to get into in this series.
As you’ve likely come to expect, to use this thing we start with the empty graph and add edges (and, if we like, nodes with no edges).
Here is a portion of the Zork map where I’ve removed a whole bunch of edges to make a DAG. (Click for larger.)
We can build that map in our graph structure like this:
var map = ImmutableDirectedGraph<string, string>.Empty
.AddEdge("Troll Room", "East West Passage", "East")
.AddEdge("East West Passage", "Round Room", "East")
.AddEdge("East West Passage", "Chasm", "North")
.AddEdge("Round Room", "North South Passage", "North")
.AddEdge("Round Room", "Loud Room", "East")
.AddEdge("Chasm", "Reservoir South", "Northeast")
.AddEdge("North South Passage", "Chasm", "North")
.AddEdge("North South Passage", "Deep Canyon", "Northeast")
.AddEdge("Loud Room", "Deep Canyon", "Up")
.AddEdge("Reservoir South", "Dam", "East")
.AddEdge("Deep Canyon", "Reservoir South", "Northwest")
.AddEdge("Dam", "Dam Lobby", "North")
.AddEdge("Dam Lobby", "Maintenance Room", "East")
.AddEdge("Dam Lobby", "Maintenance Room", "North");
Notice how there are two paths from the Dam Lobby to the Maintenance room, but our data structure handles that just fine.
Next time: we’ll see how to find all the traversals through that graph starting from any given node.
Fabulous adventures in coding 
I’m interested to see how a start-to-end traversal will be stored. If we’re applying this to Zork, and since nodes and edges are strings, I’m suspecting a sequence of “node(-edge-node)*” that reads like instructions. I’m expecting the algorithm to be recursive, but otherwise I’d ask how they’d be stored as they’re built up. Maybe a deque (mutable or otherwise) would be a good candidate.
I’d do a depth first search to find the maintenance room. Since the graph is acyclic, it will always find all possible paths. Carry a reference to a Stack that contains the directions to go. E.g. start with an empty stack, foreach edge { push edgename; recurse on node; pop stack; }
(Yes, I guess you could also use an immutable stack, that should make no difference)
Yeah, I was definitely thinking “depth first”. Although I think acyclic isn’t enough to find all of them; you need to make sure to repeat the search for every node with no incoming edges. Since that’s not easy to determine with this structure, I think we’re making the assumption that there’s exactly one “start” node. As far as carrying a stack; if we do this recursively, the call stack acts as a natural stack (and sort of an immutable one, I guess? I’ve never considered that before). Then, we can build the sequence by returning a stack, and pushing the “current” node and edge on each result. We wouldn’t need to pass the stack along the arguments this way.
Also, if we want the types to be arbitrary, we can’t assume that nodes and edges have the same types, so we’d have to use a non-generic sequence or a specially made alternating sequence.
I’d be interested to see what follows. I’ve always got stuck around here with testing equality on the nodes, and putting them in a set (for example for Dijkstra), and get lost in a forest of wrapper objects that may have reference or structural equality.
What I’d really like to know is whether Eric created this part of the Zork map from memory…
I have fond memories of maps from the original Adventure game hand-drawn on pieces of 14″ fanfold computer paper – all of these rooms were on those maps 30+ years go.
I did not, though I’m pretty sure I could draw most of the Zork I map from memory with the exception of the mazes.
Did you complete Zork I without any “external” help? I remember there were a few problems very hard to solve (like the jewel encrusted egg).
Certainly not! Those Infocom games were hard, particularly the early ones.
When I started thinking of the possible ways to implement this graph I arrived to a different conclusion:
an immutable HashSet that contains “nodes”. Each “node” contains immutable dictionaries where the keys are edges and the values are the destination nodes of the edges.
Considering that I have almost no experience in using and defining graphs, what is the biggest disadvantage with this implementation, in your opinion?
How would you have two different graphs that contained the same nodes?
You mean the same nodes but different edges?
In that case, in my model, the nodes will be different objects too. Like a “Round Room” with a passage to North and a different “Round Room” with a passage to South.
The cost you pay by that approach is an extra object for every node. Plus the extra level of indirection means not being able to easily pose questions like “what are the nodes in common between these two graphs”? With my scheme the only property that a node must have is that it can be a key in a dictionary, and that is a low bar to meet.
Thank you for the explanation. I had no doubt that your scheme was more appropriate to handle this kind of problems.
It is always a pleasure reading your informative articles here in your blog and in StackExchange.
You’re welcome; I want to point out also that your scheme is entirely reasonable, and in fact in my first draft of this article I was considering using a hash set of edges, where edges were data structures, which is very similar to your proposal. It would be perfectly workable; I just realized that I didn’t *need* that additional mechanism.
Nit-pick: There’s a slight lacunae with your three-bullet definition of a graph. After the definition is provided, an assertion is made that the definition contains an implication regarding the concept of “value” though the term “value” has not been defined (or even referred to). In the context of what comes later, the meaning is certainly clear, though the reader needs to skip ahead to do so.
I was also confused by the lack of talk of “value” in the definition, Although I think “value” itself was understood to mean “instance of the node/edge type”. I was more confused because it wasn’t clear that “duplicate” edges meant only in value and not in what nodes it connected. Still, that very next paragraph explained it.
You’re both right, it is somewhat confusing. I’ll try to clarify the text.
Maybe I’m just caught off guard by the “an edge is an arbitrary type” idea. I’m used to thinking of a nodes as having explicit value of arbitrary type (like a linked list with many “next” pointers); nodes were clearly defined by their value. However, when I think of edges I think of a thin connection between two nodes. It took me an extra few brain processor cycles to realize that edges were real, individual entities defined by value just like nodes; their “edginess” is just a factor of how they’re being arranged in the greater data structure.
Indeed, we’re not used to thinking of the “arrows” in, say, a linked list, a tree or a dictionary as themselves having associated values, except in fairly exotic cases such as tries or DAWGS, or in the trivial cases of the arrows being called “left” and “right”, or “next” and “previous”. But in a labeled directed graph, the fundamental thing we’re manipulating in the data structure is an arrow, so it makes sense to make that every bit as “first class” as a node.
Graphs are fun stuff. The edges as an entity idea is a useful concept, especially when doing analysis.
In biological pathways, some graphs could be modeling metabolism, which then your nodes are metabolites (e.g. sugar) and your edges are enzymes.
Other graphs could be modelling signal transduction (e.g. how the brain sends a signal to move a muscle). The nodes are proteins, and the edges are interactions (activation, repression).
I think this will be a fun group of posts.
Pingback: Eric Lippert on Graph Traversal | Dom's Code
Pingback: The Morning Brew - Chris Alcock » The Morning Brew #1727
Great post (also the previous series about combinations)!
Coming from a formal background I always find it astonishing how enumerator blocks + Linq allow for extremely declarative solutions to such problems in C#.
I already came up with a very slim solution for the traversal problem and cannot wait to compare it to yours (maybe I will also share my code in the next post).
PS: It seems that your sample graph is missing the .AddEdge(“Deep Canyon”, “Dam”, “East”) edge.
Pingback: Graph traversal, part two | Fabulous adventures in coding
“public readonly static ImmutableDirectedGraph Empty = new ImmutableDirectedGraph( ImmutableDictionary<N, ImmutableDictionary>.Empty);”
Or, for readable code, use F# 🙂
Seriously, for this series (and the previous) it was tempting. Languages like F# make this sort of thing much more concise. That said, this is a pretty small implementation detail.
Taking a stab at removal – including edges pointing to the removed node…
public ImmutableDirectedGraph RemoveNode(N node)
{
if (graph.ContainsKey(node) == false)
return this;
var query = graph
//Only the nodes with an edge to the node to be removed
.Where(kvp => kvp.Value.ContainsValue(node))
//select both the start node and the selection of edges where
//the node to be removed is actually the destination
.Select(kvp => new
{
kvp.Key,
Value = kvp.Value
//where within nodes the value (node) is the node to remove
.Where(kvp2 => kvp2.Value.Equals(node))
//Get the entire KeyValuePair so we know
//which edge (key) to pair with the start node (prior query)
.Select(kvp2 => kvp2)
});
var retVal = new ImmutableDirectedGraph(graph.Remove(node));
foreach (var startNode in query.Select(a => a.Key))
{
foreach (var edge in graph[startNode]
.Where(kvp => kvp.Value.Equals(node))
.Select(kvp => kvp.Key))
{
retVal = retVal.RemoveEdge(startNode, edge);
}
}
return retVal;
}
and RemoveEdge is trivial…
public ImmutableDirectedGraph RemoveEdge(N start, E edge)
{
if ((graph.ContainsKey(start) && graph[start]
.ContainsKey(edge)) == false)
return this;
return new ImmutableDirectedGraph(
graph.SetItem(start, graph[start]
.Remove(edge))
);
}
Keeping track of the key relationship to the value in the nested dictionary was challenging and lead to what feels like a naive implementation. Would like see more clever approaches.
Pingback: Producing combinations, part five | Fabulous adventures in coding