## digitalmars.D - A graph data structure usable in safe pure nothrow functions

- "w0rp" <devw0rp gmail.com> May 25 2014
- FG <home fgda.pl> May 25 2014
- "w0rp" <devw0rp gmail.com> May 25 2014
- "w0rp" <devw0rp gmail.com> May 26 2014

I've been updating a git repository which is like my dumping ground for data structures, etc. I write for fun. I think for as long as I have been using D, as a lover of graph theory and also all of D's function qualifiers, I have been wanting graph types which can be used in safe pure nothrow functions. The big blocker on this was what associative arrays could offer. The current associative array implementation couldn't get me all the way there, so I wrote my own hashmap type. Documentation: https://w0rp.com/project/dstruct/dstruct/map/ Source: https://github.com/w0rp/dstruct/blob/master/source/dstruct/map.d I wrote a little benchmark for my hashmaps and the standard associative arrays. As with all my benchmarks, I'm sure I probably made a glaring error which shows how if you do something different your computer will explode. Benchmark: https://gist.github.com/anonymous/4a060b8f65684eb0586c It produced this output on my modern machine, with times on the left representing associative arrays, and the right representing my new HashMap, with just 'rdmd test.d'. AddAndRemove: 163ms -> 111ms AddAndFetch: 112ms -> 108ms AddAndGet: 108ms -> 109ms AddAndIn: 103ms -> 108ms So, about the same performance. This hashmap now has 'keys,' 'values,' and 'items' functions for creating ranges through the maps which can be mutable, tail-const, tail-immutable, const, or immutable, return by reference from the maps, and are all usable in safe pure nothrow functions. nogc is probably possible for all of these too in future. I also added setDefault methods to my HashMap type which lets you get a value from a map or lazily set a new value and then get that back. It's pretty much 'setdefault' from Python, only a bit more lazy, and it only computes a hash once per call. So I can do this in my graph implementation. // Get a currency adjacency list or create a new one. Vertex[] adjacencyList = map.setDefault(vertex); My graph types make use of the hashmap I wrote so the graphs can be implemented in terms of adjacency lists, where an edge is stored by a vertex mapping to a list of vertices with the outgoing vertices for the edge. This is not the best implementation for all scenarios, but it is probably the best way I know of for representing graphs with any type of vertex in the majority of scenarios. Documentation: https://w0rp.com/project/dstruct/dstruct/graph/ Source: https://github.com/w0rp/dstruct/blob/master/source/dstruct/graph.d So when you put everything all together, it means that you can now write this code. import dstruct.graph; safe pure nothrow auto someEdgesIDunno() { Digraph!string graph; graph.addEdge("a", "b"); graph.addEdge("b", "c"); return graph.edges; } void main(string[] argv) { import std.stdio; /* a -> b b -> c */ foreach(edge; someEdgesIDunno()) { writefln("%s -> %s", edge.from, edge.to); } } There you have it. The hardest part recently I posted on d.learn about, which was trying to figure out a way to write ranges which propagate 'constness' nicely. This is a whole other topic... Destroy.

May 25 2014

On 2014-05-25 16:39, w0rp wrote:I have been wanting graph types which can be used in safe pure nothrow functions. The big blocker on this was what associative arrays could offer. The current associative array implementation couldn't get me all the way there, so I wrote my own hashmap type.

get and setDefault are nice, but can be easily done as small UFCS wrappers around the "element in array" expression. What was blocking you in the current implementation of associative arrays? Can't it be fixed without having to come up with a custom map type?

May 25 2014

On Sunday, 25 May 2014 at 17:30:52 UTC, FG wrote:On 2014-05-25 16:39, w0rp wrote:I have been wanting graph types which can be used in safe pure nothrow functions. The big blocker on this was what associative arrays could offer. The current associative array implementation couldn't get me all the way there, so I wrote my own hashmap type.

get and setDefault are nice, but can be easily done as small UFCS wrappers around the "element in array" expression. What was blocking you in the current implementation of associative arrays? Can't it be fixed without having to come up with a custom map type?

My main blocker was that byKey and byValue functions on associative arrays weren't usable in safe pure nothrow functions. So implementing my own gave me ranges I could use for doing the right things. The setDefault implementation is just kind of an added bonus.

May 25 2014

I just added nogc support to the map and graph types, with fallback behaviour for older D compiler versions. I used this. static if(__VERSION__ < 2066) { enum nogc = 1; } So as long as I write nogc left of other attributes, it will compile the library on both DMD 2.065 and DMD 2.066. Now every range, get, and remove function on the maps and graphs can be used in nogc functions, because these functions never allocate more memory on the garbage collected heap.

May 26 2014