D graph library updates

Today I pushed a number of important updates to the Dgraph master repository. These will be breaking changes for anyone currently using the library, so I thought I should provide a concise overview of what has been altered and how to tweak your own code.

The first and most important change is that where previously there was a single Graph class, the concept of a graph has been generalized to any type that implements the expected graph API. A new template isGraph can be used to check whether a type conforms to expectations.

The original Graph class has been renamed to IndexedEdgeList, reflecting the name given to this data structure by the authors of igraph. It has been supplemented by a new class, CachedEdgeList, which offers greatly enhanced speed at the cost of a higher overall memory footprint. Other graph types will probably be added to the library in the not-too-distant future.

How to update your code

Because of its performance advantages, I recommend using CachedEdgeList as the default graph type in your code. The additional memory cost will be insignificant for all except the very largest graphs. The simplest way to adapt your code is therefore to do a search-and-replace of Graph for CachedEdgeList (or, in regex, s/Graph/CachedEdgeList/:-).

A better approach is to adapt your code to take advantage of the isGraph template. Here’s an example of a function using the previous version of the library:

Now, using isGraph, we can generalize this to accept any graph type:

You can see examples of this in how the functions in dgraph.metric have been adapted for use with the new design.

I’ll be following up with a more in-depth look at the changes, particularly in terms of how they impact performance. In the meantime, feedback is very welcome on the new design, and I hope that any inconvenience caused by the breaking changes is repaid by improved speed and flexibility.

One thought on “D graph library updates

  1. Pingback: Betweenness centrality in Dgraph | mad science, dreams and diversions

Comments are closed.