Boost logo

Boost :

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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk