webdrake/dgraph

Graph library written in D.

dgraph's Issues

isEdge and edgeID methods are suboptimal

The current implementations of isEdge and edgeID use a linear search. This should be replaced by a binary search that takes advantage of the sorting of head and tail indexes.

isVertex not exposed in CachedEdgeList

CachedEdgeList doesn't expose isVertex from IndexedEdgeList.
Adding the following to CachedEdgeList works:

bool isVertex(T : size_t)(in T v) @safe const nothrow pure
{
    return _graph.isVertex(v);
}

dub packaging

How about packaging for dub? This way Dgraph will be easier to discover and integrate.

Vertex/edge labels

Is it possible to label edges/vertices with arbitary data type? It'll be great to be able do so. E.g i want to represent path with graph and that graph should have vertices labeled with string type(like street name or whatever) and edges with int type(travel time). Ultimately it should be possible to instantinate these two types of labels(for edges and for vertices) with arbitrary type.

Imaginary code follows for better understandin what i mean.

// Vertex label type.
class Foo { ... };
// Edge label type.
enum Bar { ... };

auto graph = new Graph!(Foo, Bar)(...);

Head/tail are applied in opposition to standard terminology

Dgraph uses head and tail to refer to respectively, the nodes an edge points from and to. This is in opposition to standard terminology where the head of an edge is the head of the arrow -- i.e. the to vertex -- and the tail of the arrow is the vertex the edge points from.

Source: https://en.wikipedia.org/wiki/Graph_(mathematics)#Directed_graph

Given the mix-up over terminology, it might be better to replace current usage with unambiguous terms like from and to, noting their correspondence to other graph-theoretic terms in documentation.

graphviz

It would be great if Dgraph could provide graph serializing facilities(like http://igraph.sourceforge.net/doc/html/ch19s07.html).

Broken build

Hi, having issues with buiding on aa40b50.
Quite self explanatory i think.

➜ Dgraph git:(master) make DC=ldmd2
ldmd2 -O -inline -ofgraphtest graphtest.d dgraph/.d dgraph/test/.d
dgraph/graph.d(172): Error: pure function 'edge' cannot call impure function 'zip'
dgraph/graph.d(172): Error: zip is not nothrow
dgraph/graph.d(171): Error: function dgraph.graph.G!(false).IndexedEdgeList.edge 'edge' is nothrow yet may throw
graphtest.d(42): Error: template instance dgraph.graph.G!(false) error instantiating
make: *** [graphtest] Error 1

By the way how does DGraph conpares to igraph in terms of speed?

Change license to the Boost to allow commercial usage

Please change license from GPLv3 to something more liberal like Boost, MIT or BSD to allow commercial usage.

Also, it would be nice to have graph library in Phobos in a future, and in that case module must be under Boost license. In that case somebody can use Dgraph as initial point.

You can contact igraph authors or use Boost Graph Library (BGL) as a initial point.

See also this topic:
http://forum.dlang.org/thread/[email protected]