D graph library

Joseph Rushton Wakeling joseph.wakeling at webdrake.net
Wed May 15 10:58:51 PDT 2013


On 05/15/2013 07:40 PM, w0rp wrote:
> There are two advantages.
> 
> 1. Some functions for undirected and directed graphs are either identical or
> nearly identical. So you can write a single implementation with different policies.
> 2. Storage implementation can be interchangeable, as you change the storage for
> a graph by changing its policy.
> 
> Point 1 could be equally addressed by writing free template functions for the
> graphs. (So two structs and free functions work work there.) Point 2 is more
> interesting because a different method of storage (stack vs heap, nested map vs
> some array combination) implies a different addNode(Node) function, and so on.
> So the policies let you swap the underlying implementation out via a template
> parameter without having to write another struct to deal with it.

Point 1 I'm not so sure matters for the reasons you cite.  On the other hand
point 2 seems quite relevant.  For example, you might prefer to store your data
as an edge list (à la igraph), as an adjacency list, or other functions, because
depending on your needs the information retrieval might be quicker.

Talking of adjacency lists, now I'm trying to think of a clever method for
deriving an adjacency list from an edge list, using slices ...

> bool is a nice convenience for "did this change anything?" So you return false
> when addNode actually had no effect, say when the node was already in the graph.
> This idea is basically borrowed from Java collections.

Maybe I'm being harsh, but I was assuming you might actually throw an error if
someone tries to add an edge that already exists (although perhaps you'd want to
avoid throwing in order not to hit performance).

> I think writing functions that return ranges for the graphs (vertices, edges,
> neighbours, etc.) and building the algorithms based on these ranges is the right
> way to go.

Yep, me too.



More information about the Digitalmars-d mailing list