Graph Structured Stacks in Clojure
I am currently pondering how best to represent Graph Structured Stacks in Clojure. My first idea was to use maps.
So this GSS would be represented as:
{7 {3 {1 {0 {}}}, 4 {1 {0 {}}}, 5 {2 {0 {}}}}, 8 {6 {2 {0 {}}}}}
Please note that repeated maps in this representation would be shared by construction.
It is all well and good this representation allow me to easily perform stack ops but I want to also be able to traverse the stacks from the bottom. This means to make the graph cyclic so I thought that I need an adjency list or, more realistically, two indexed versions (maps of sets) of this list to be able to traverse the GSS in any direction. Or the map-based representation for direct traversal and an adjency map for reverse traversal.
To me the more boring part with this adjency lists is that I have to name the GSS nodes. Wait! There are natural identifiers for these nodes: their key-value pairs in the map-based representation! [2 {0 {}}] is a natural identifier for node #2 and [2 {0 {}}] the one for node #7.
Now I’m able to represent the GSS as:
[;; direct representation {7 {3 {1 {0 {}}}, 4 {1 {0 {}}}, 5 {2 {0 {}}}}, 8 {6 {2 {0 {}}}}} ;; adjency map for reverse traversal {nil #{[0 {}]}, [0 {}] #{[1 {0 {}}] [2 {0 {}}]}, [1 {0 {}}] #{[3 {1 {0 {}}}] [4 {1 {0 {}}}]}, [2 {0 {}}] #{[5 {2 {0 {}}}] [6 {2 {0 {}}}]}, [3 {1 {0 {}}}] #{[7 {3 {1 {0 {}}}, 4 {1 {0 {}}}, 5 {2 {0 {}}}}]}, [4 {1 {0 {}}}] #{[7 {3 {1 {0 {}}}, 4 {1 {0 {}}}, 5 {2 {0 {}}}}]}, [5 {2 {0 {}}}] #{[7 {3 {1 {0 {}}}, 4 {1 {0 {}}}, 5 {2 {0 {}}}}]}, [6 {2 {0 {}}}] #{[8 {6 {2 {0 {}}}}]}}]
Granted the serialization is verbose but all nodes are shared in memory by construction and I find this model rather simple.
Does anyone have other ideas on how to functionally implement such a structure?
Christophe,
I have to work with a lot of (directed) graphs on the clock. I have found it very useful to simply keep track of a edges. So, I would do something like this
[{:source 7 :dest 3}
{:source 7 :dest 4}
{:source 7 :dest 5}
{:source 3 :dest 1}
{:source 4 :dest 1}
{:source 8 :dest 6}
{:source 5 :dest 2}
{:source 6 :dest 2}
{:source 1 :dest 0}
{:source 2 :dest 0}]
This also makes it very simple to determine what are direct dependencies with a simple filter, and all dependencies with a simple recursive call. It also fits with a classic RDBMS well, or a NoSQL alternative.
HTH,
Sean
Christophe,
I also like to keep my graphs as a set of edges. It matches the mathematical definition of a graph:
A set of vertices V and a set of edges E: {V, E}. The edge is a map like this {:a 7 :b 3} so that it’s directed. It’s also easy to add labels to the edges if you need them.
All sorts of graph operations are easier with this method. You could also build an index of this if you really needed fast lookup times. The index would be vertex to a set of edges containing that vertex. Or you could build two indexes, one for the :a position and one for the :b position.
see you later
Eric
Sean, Eric,
Adjency lists are indeed nice for general graph processing but one doesn’t usually implement, for example, linked lists with adjency lists.
I’m exploring specialized representations for GSS. I’ll keep you posted as I progress: experiment will tell us if a specialized representation is worth its complexity.
[...] Clojure and me ยป Graph Structured Stacks in Clojure (tags: clojure graph) [...]
You’ve rediscovered Boolean Decision Diagrams, which are used to represent combinatorial logic functions for circuit optimization and verification.
http://en.wikipedia.org/wiki/Binary_decision_diagram
@Chris, thanks for the link: it’s interesting to see the same structure applied ti different usecases. By the way GSS are not mine: it’s part of Tomita’s GLR algorithm http://en.wikipedia.org/wiki/GLR_parser.