How to test whether a vertex or edge exists?
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? ----------------------------------------------------------------------- //Here is the simpilfied situation that I want to handle, "IF THERE IS NOT a vertex representing the //string of the current line" is the predicate I want to know typedef adjacency_list<vecS, vecS, directedS, property<vertex_color_t, default_color_type>, property<edge_weight_t, int> > Graph; Graph g(); ifstream infile; infile.open(argv[1]); string line; while( getline(infile, line) ){ if(line.find("Node")!= npos && /*IF THERE IS NOT a vertex representing the string of the current line*/) add_vertex( line, g); } -------------------------------------------------------------------- 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. Thanks a lot, Sean _________________________________________________________________ Express yourself instantly with MSN Messenger! Download today - it's FREE! http://messenger.msn.click-url.com/go/onm00200471ave/direct/01/
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.
From: Daniel Mitchell <danmitchell@mail.utexas.edu> Reply-To: boost-users@lists.boost.org
Yeah, I agree with you. For the first question, I think I'd better to save the strings to an vector and build a relationship between strings in this vector and vertices in the graph.
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. Thanks for the reply. I have a question for concept requirements. For example, if I declare a Graph representation by typedef adjacency_list<vecS, vecS, directedS, property<vertex_color_t, default_color_type>, property<edge_weight_t, int> > Graph;
How can I know if this Graph satisfies the reqirement of a certain concept, say AdjacencyMatrix ? Thanks again.
D. _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
_________________________________________________________________ Dont just search. Find. Check out the new MSN Search! http://search.msn.click-url.com/go/onm00200636ave/direct/01/
On Sunday 07 May 2006 17:09, sean yang wrote:
Yeah, I agree with you. For the first question, I think I'd better to save the strings to an vector and build a relationship between strings in this vector and vertices in the graph.
I think that's a reasonable approach. I suggested a set since it would automatically take care of the problem of duplicates, but you obviously know your application better than I do.
Thanks for the reply. I have a question for concept requirements. For example, if I declare a Graph representation by typedef adjacency_list<vecS, vecS, directedS, property<vertex_color_t, default_color_type>, property<edge_weight_t, int> > Graph;
How can I know if this Graph satisfies the reqirement of a certain concept, say AdjacencyMatrix ?
The answer is slightly complex because of the nature of concepts. A concept is a set of syntactic and semantic requirements a type must satisfy to qualify as an argument to a generic function. For example, if objects of type Graph are to qualify as arguments to a function that requires the AdjacencyMatrix concept, the expression edge( u, v, g ) must compile. This can obviously be checked by the compiler, and the BGL makes it easy to do so: #include <boost/graph/graph_concepts.hpp> boost::function_requires<boost::AdjacencyMatrixConcept<Graph> >(); AdjacencyMatrixConcept is called a concept-checking class, and the above will only compile if Graph satisfies the syntactic requirements of AdjacencyMatrix. There are similar concept-checking classes for IncidenceGraph, VertexListGraph, etc. The compiler cannot, however, check that edge( u, v, g ) does the right thing, so you also have to rely on the documentation for Graph. If you look at the documentation for adjacency_list, it says that adjacency_list models the VertexListGraph and EdgeListGraph concepts. Unfortunately, in this case the documentation seems to be incomplete*, since adjacency_list also models IncidenceGraph and AdjacencyGraph, and sometimes BidirectionalGraph. So your best bet is to use the concept-checking classes. Hope that helps. D. *It isn't clear from the documentation if VertexListGraph is a refinement of IncidenceGraph and AdjacencyGraph or not. The language is in the "Design Rational" seems to imply that it is, but those concepts do no appear in the list of concepts refined by VertexListGraph.
participants (2)
-
Daniel Mitchell -
sean yang