[boost] BGL: labelled edge graph

Subject: [boost] BGL: labelled edge graph
From: Shaun Jackman (sjackman_at_[hidden])
Date: 2011-10-12 13:06:53

Hi,

I have a directed acyclic word graph (DAWG) [1] for which the
fundamentally efficient operation takes a vertex descriptor and an edge
label and returns an edge descriptor (if that edge exists). An
out_edge_iterator can be used to iterate over the edges to find the edge
with the specified label, but it's not very efficient. I plan to extend
the BGL API to add the needed functionality. I wanted to check first
that this function doesn't already exist, and if it doesn't, ask for
suggested names. I was thinking of...

pair<edge_descriptor, bool>
out_edge(
        vertex_descriptor u,
        edge_label i,
        Graph g);

The type of edge_label would depend on the graph. For me, it's a char.

This sort of labelled edge navigation also applies to a de Bruijn graph
[2].

Cheers,
Shaun

[1] http://en.wikipedia.org/wiki/Directed_acyclic_word_graph
[2] http://en.wikipedia.org/wiki/De_Bruijn_graph