Re: [boost] BGL: labelled edge graph

Subject: Re: [boost] BGL: labelled edge graph
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2011-10-12 18:00:59

On Wed, 12 Oct 2011, Shaun Jackman wrote:

> 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].

There is a function in BGL called edge(); it is officially a part of the 
Adjacency Matrix concept but is implemented for many more graph types 
(with higher than Adjacency Matrix' required complexity).  Perhaps your 
function should be "edge_by_label" or something?  Also, are you 
considering having an equivalent to edge_range for labeled edges as well 
(it is important for graphs with parallel edges, and so a fully general 
concept should probably have it)?  The function in named_graph is called 
find_vertex, so that could be some inspiration for your name; that class 
also has vertex_by_property.  Do you intend this to be a more general 
mechanism for other properties, or just for some kind of edge name or 
label?

-- Jeremiah Willcock