Re: [Boost-users] How to test whether a vertex or edge exists?

From: Daniel Mitchell (danmitchell_at_[hidden])
Date: 2006-05-07 16:54:30

On Saturday 06 May 2006 22:49, sean yang wrote:
> I want to add a vertex, which a string as its ID to a graph if a vertex
> representing such a string does not exist in the graph. Is there a function
> call to test if a vertex exists in a graph?

I don't think there's any particularly efficient way of doing that. Could you 
first read the strings into a set and then create vertices based on what's in 
the set?

There isn't a function to test if a vertex is in a graph because it isn't 
needed. The only way to get a vertex is to dereference a vertex_iterator, and 
obviously such a vertex *is* in the graph. Except for default construction, 
there isn't even a general way to construct a vertex. How could there be? 
Vertex descriptors are required to be default constructible, assignable, and 
equality comparable, but beyond that their representation is arbitrary, so 
there's no way for a generic algorithm to create one.

Having said that, it is possible for any particular graph class to provide a 
method for creating valid vertices, and adjacency_list provides the function 
vertex( n, g ), which returns the nth vertex in g. I haven't read the source 
for this function, but I assume that if n is out of range it does something 
reasonable like return graph_traits<adjacency_list>::null_vertex().

> A related question I want to ask is whether there exist a function call
> that test whether an edge representing [vertext string("Node1") --> vertext
> string("Node2") ] exists in a graph.

There's a function edge( u, v, g ) returns the edge between u and v, if it 
exists. This function is required by the AdjacencyMatrix concept.

D.