A graph data structure usable in @safe pure nothrow functions
w0rp via Digitalmars-d
digitalmars-d at puremagic.com
Sun May 25 07:39:47 PDT 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.
More information about the Digitalmars-d
mailing list