How to find edge between two vertices of undirected graph?
This should be easy .... typedef adjacency_list<vecS, vecS, undirectedS, POS<position_type>, LEN<position_type> > DG; typedef graph_traits<DG>::vertex_descriptor Vertex; typedef graph_traits<DG>::edge_descriptor Edge; ... Vertex b, d; ...populate b and .... bool bRet; Edge e; tie(e,bRet) = edge(b,d,*this); This earns me a lengthy error message from g++ (following). I notice that there is no function described for looking up an edge on an IncidenceGraph or an AdjacencyGraph ... hmm .... this puzzles me. What am I missing? Eric ../shuttle/trunk/DelaunayGraph.h:273: error: no matching function for call to ‘DelaunayGraph<int>::remove_edge(Edge&, DelaunayGraph<int>&)’ /usr/include/boost/graph/detail/adjacency_list.hpp:848: note: candidates are: void boost::undirected_graph_helper<Config>::remove_edge(typename Config::edge_descriptor) [with Config = boost::detail::adj_list_gen<boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, POS<int>, LEN<int>, boost::no_property, boost::listS>, boost::vecS, boost::vecS, boost::undirectedS, boost::property<boost::vertex_bundle_t, POS<int>, boost::no_property>, boost::property<boost::edge_bundle_t, LEN<int>, boost::no_property>, boost::no_property, boost::listS>::config] /usr/include/boost/graph/detail/adjacency_list.hpp:859: note: void boost::undirected_graph_helper<Config>::remove_edge(typename Config::out_edge_iterator) [with Config = boost::detail::adj_list_gen<boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, POS<int>, LEN<int>, boost::no_property, boost::listS>, boost::vecS, boost::vecS, boost::undirectedS, boost::property<boost::vertex_bundle_t, POS<int>, boost::no_property>, boost::property<boost::edge_bundle_t, LEN<int>, boost::no_property>, boost::no_property, boost::listS>::config] make: *** [MyDialog.o] Error 1
Hi, when I look at the error, I see that it complains about remove_edge(). However, I don't see any call of this in your example code. So I would suggest that you either post a complete and short "working" example, or more carefully select the lines that you post. Concerning the question in the title of your post, one way to check if there is an edge between two vertices could be to get the adjacent vertices of Vertex b and check if Vertex d is among them, or even to check if Vertex b has any adjacent vertices at all. I know, this is probably not the nicest solution but unless you don't use an AdjacencyMatrix graph, I don't know if this would even be possible in a nicer way, so to say in O(1). Best, Cedric On Thursday, 10. June 2010 06:59:24 Eric Fowler wrote:
This should be easy ....
typedef adjacency_list<vecS, vecS, undirectedS, POS<position_type>, LEN<position_type> > DG; typedef graph_traits<DG>::vertex_descriptor Vertex; typedef graph_traits<DG>::edge_descriptor Edge;
... Vertex b, d; ...populate b and ....
bool bRet; Edge e;
tie(e,bRet) = edge(b,d,*this);
This earns me a lengthy error message from g++ (following).
I notice that there is no function described for looking up an edge on an IncidenceGraph or an AdjacencyGraph ... hmm .... this puzzles me.
What am I missing?
Eric
../shuttle/trunk/DelaunayGraph.h:273: error: no matching function for call to ‘DelaunayGraph<int>::remove_edge(Edge&, DelaunayGraph<int>&)’ /usr/include/boost/graph/detail/adjacency_list.hpp:848: note: candidates are: void boost::undirected_graph_helper<Config>::remove_edge(typename Config::edge_descriptor) [with Config = boost::detail::adj_list_gen<boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, POS<int>, LEN<int>, boost::no_property, boost::listS>, boost::vecS, boost::vecS, boost::undirectedS, boost::property<boost::vertex_bundle_t, POS<int>, boost::no_property>, boost::property<boost::edge_bundle_t, LEN<int>, boost::no_property>, boost::no_property, boost::listS>::config] /usr/include/boost/graph/detail/adjacency_list.hpp:859: note: void boost::undirected_graph_helper<Config>::remove_edge(typename Config::out_edge_iterator) [with Config = boost::detail::adj_list_gen<boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, POS<int>, LEN<int>, boost::no_property, boost::listS>, boost::vecS, boost::vecS, boost::undirectedS, boost::property<boost::vertex_bundle_t, POS<int>, boost::no_property>, boost::property<boost::edge_bundle_t, LEN<int>, boost::no_property>, boost::no_property, boost::listS>::config] make: *** [MyDialog.o] Error 1
Whoops ... the compiler must have been hallucinating :-) I know I was; I can look up an edge, but can't remove one. I have tried it two ways: remove_edge(u,v,g); and remove_edge(e,g); with u,v being vertices and e being an edge of course. Possible I do not have a MutableGraph but really I am not sure. I do know an edge exists between vertices u and v. Eric On Thu, Jun 10, 2010 at 12:46 AM, Cedric Laczny <cedric.laczny@gmx.de>wrote:
Hi,
when I look at the error, I see that it complains about remove_edge(). However, I don't see any call of this in your example code. So I would suggest that you either post a complete and short "working" example, or more carefully select the lines that you post.
Concerning the question in the title of your post, one way to check if there is an edge between two vertices could be to get the adjacent vertices of Vertex b and check if Vertex d is among them, or even to check if Vertex b has any adjacent vertices at all. I know, this is probably not the nicest solution but unless you don't use an AdjacencyMatrix graph, I don't know if this would even be possible in a nicer way, so to say in O(1).
Best,
Cedric
On Thursday, 10. June 2010 06:59:24 Eric Fowler wrote:
This should be easy ....
typedef adjacency_list<vecS, vecS, undirectedS, POS<position_type>, LEN<position_type> > DG; typedef graph_traits<DG>::vertex_descriptor Vertex; typedef graph_traits<DG>::edge_descriptor Edge;
... Vertex b, d; ...populate b and ....
bool bRet; Edge e;
tie(e,bRet) = edge(b,d,*this);
This earns me a lengthy error message from g++ (following).
I notice that there is no function described for looking up an edge on an IncidenceGraph or an AdjacencyGraph ... hmm .... this puzzles me.
What am I missing?
Eric
../shuttle/trunk/DelaunayGraph.h:273: error: no matching function for call to ‘DelaunayGraph<int>::remove_edge(Edge&, DelaunayGraph<int>&)’ /usr/include/boost/graph/detail/adjacency_list.hpp:848: note: candidates are: void boost::undirected_graph_helper<Config>::remove_edge(typename Config::edge_descriptor) [with Config = boost::detail::adj_list_gen<boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, POS<int>, LEN<int>, boost::no_property, boost::listS>, boost::vecS, boost::vecS, boost::undirectedS, boost::property<boost::vertex_bundle_t, POS<int>, boost::no_property>, boost::property<boost::edge_bundle_t, LEN<int>, boost::no_property>, boost::no_property, boost::listS>::config] /usr/include/boost/graph/detail/adjacency_list.hpp:859: note: void boost::undirected_graph_helper<Config>::remove_edge(typename Config::out_edge_iterator) [with Config = boost::detail::adj_list_gen<boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, POS<int>, LEN<int>, boost::no_property, boost::listS>, boost::vecS, boost::vecS, boost::undirectedS, boost::property<boost::vertex_bundle_t, POS<int>, boost::no_property>, boost::property<boost::edge_bundle_t, LEN<int>, boost::no_property>, boost::no_property, boost::listS>::config] make: *** [MyDialog.o] Error 1
Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
It seems I do not have a mutable graph. This sort of raises another issue: how do I declare an object that is described by a concept? For example, in this case I know I need a MutableGraph, and I see from the doc (http://www.boost.org/doc/libs/1_43_0/libs/graph/doc/MutableGraph.html) that MutableGraphs have certain properties, such as DefaultConstructible, etc. Now, how do I declare a MutableGraph, and know I have one? I know that: typedef adjacency_list<vecS, vecS, undirectedS, POS<position_type> LEN<position_type> > DG; is not enough. More to the point, how do I read something like: template <class G> struct GraphConcept { typedef typename boost::graph_traits<G>::vertex_descriptor vertex_descriptor; typedef typename boost::graph_traits<G>::edge_descriptor edge_descriptor; ..blah... void constraints() { function_requires< DefaultConstructibleConcept<vertex_descriptor> >(); function_requires< EqualityComparableConcept<vertex_descriptor> >(); function_requires< AssignableConcept<vertex_descriptor> >(); ...blah.... } G g; }; And produce something that looks like: typedef adjacency_list<blahS, blabS, ...etc...> MyGraphType; And supports what I need? Eric On Thu, Jun 10, 2010 at 12:46 AM, Cedric Laczny <cedric.laczny@gmx.de>wrote:
Hi,
when I look at the error, I see that it complains about remove_edge(). However, I don't see any call of this in your example code. So I would suggest that you either post a complete and short "working" example, or more carefully select the lines that you post.
Concerning the question in the title of your post, one way to check if there is an edge between two vertices could be to get the adjacent vertices of Vertex b and check if Vertex d is among them, or even to check if Vertex b has any adjacent vertices at all. I know, this is probably not the nicest solution but unless you don't use an AdjacencyMatrix graph, I don't know if this would even be possible in a nicer way, so to say in O(1).
Best,
Cedric
On Thursday, 10. June 2010 06:59:24 Eric Fowler wrote:
This should be easy ....
typedef adjacency_list<vecS, vecS, undirectedS, POS<position_type>, LEN<position_type> > DG; typedef graph_traits<DG>::vertex_descriptor Vertex; typedef graph_traits<DG>::edge_descriptor Edge;
... Vertex b, d; ...populate b and ....
bool bRet; Edge e;
tie(e,bRet) = edge(b,d,*this);
This earns me a lengthy error message from g++ (following).
I notice that there is no function described for looking up an edge on an IncidenceGraph or an AdjacencyGraph ... hmm .... this puzzles me.
What am I missing?
Eric
../shuttle/trunk/DelaunayGraph.h:273: error: no matching function for call to ‘DelaunayGraph<int>::remove_edge(Edge&, DelaunayGraph<int>&)’ /usr/include/boost/graph/detail/adjacency_list.hpp:848: note: candidates are: void boost::undirected_graph_helper<Config>::remove_edge(typename Config::edge_descriptor) [with Config = boost::detail::adj_list_gen<boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, POS<int>, LEN<int>, boost::no_property, boost::listS>, boost::vecS, boost::vecS, boost::undirectedS, boost::property<boost::vertex_bundle_t, POS<int>, boost::no_property>, boost::property<boost::edge_bundle_t, LEN<int>, boost::no_property>, boost::no_property, boost::listS>::config] /usr/include/boost/graph/detail/adjacency_list.hpp:859: note: void boost::undirected_graph_helper<Config>::remove_edge(typename Config::out_edge_iterator) [with Config = boost::detail::adj_list_gen<boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, POS<int>, LEN<int>, boost::no_property, boost::listS>, boost::vecS, boost::vecS, boost::undirectedS, boost::property<boost::vertex_bundle_t, POS<int>, boost::no_property>, boost::property<boost::edge_bundle_t, LEN<int>, boost::no_property>, boost::no_property, boost::listS>::config] make: *** [MyDialog.o] Error 1
Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
On Thu, 10 Jun 2010, Eric Fowler wrote:
It seems I do not have a mutable graph. This sort of raises another issue: how do I declare an object that is described by a concept?
The best you can do is apply a concept checking class. That doesn't filter the members so you can only use the MutableGraph-required functions, but it at least makes sure that the graph you have is a MutableGraph.
For example, in this case I know I need a MutableGraph, and I see from the doc (http://www.boost.org/doc/libs/1_43_0/libs/graph/doc/MutableGraph.html) that MutableGraphs have certain properties, such as DefaultConstructible, etc.
Now, how do I declare a MutableGraph, and know I have one? I know that:
typedef adjacency_list<vecS, vecS, undirectedS, POS<position_type> LEN<position_type> > DG;
What methods are missing? Could you please try applying the MutableGraph concept checking class to the DG type and see what breaks?
More to the point, how do I read something like:
template <class G> struct GraphConcept { typedef typename boost::graph_traits<G>::vertex_descriptor vertex_descriptor; typedef typename boost::graph_traits<G>::edge_descriptor edge_descriptor; ..blah... void constraints() { function_requires< DefaultConstructibleConcept<vertex_descriptor> >(); function_requires< EqualityComparableConcept<vertex_descriptor> >(); function_requires< AssignableConcept<vertex_descriptor> >(); ...blah....
} G g; };
And produce something that looks like:
typedef adjacency_list<blahS, blabS, ...etc...> MyGraphType;
What do you mean? You want to add methods/functions to the graph type to make it model a specific concept? -- Jeremiah Willcock
On Fri, Jun 11, 2010 at 12:29 PM, Jeremiah Willcock <jewillco@osl.iu.edu>wrote:
On Thu, 10 Jun 2010, Eric Fowler wrote:
It seems I do not have a mutable graph. This sort of raises another issue:
how do I declare an object that is described by a concept?
The best you can do is apply a concept checking class. That doesn't filter the members so you can only use the MutableGraph-required functions, but it at least makes sure that the graph you have is a MutableGraph.
For example, in this case I know I need a MutableGraph, and I see from the
doc ( http://www.boost.org/doc/libs/1_43_0/libs/graph/doc/MutableGraph.html) that MutableGraphs have certain properties, such as DefaultConstructible, etc.
Now, how do I declare a MutableGraph, and know I have one? I know that:
typedef adjacency_list<vecS, vecS, undirectedS, POS<position_type> LEN<position_type> > DG;
What methods are missing? Could you please try applying the MutableGraph concept checking class to the DG type and see what breaks?
Again I must ask: How? I have mined the examples and come up with: BOOST_CONCEPT_ASSERT((MutableGraph<DG>)); and BOOST_CONCEPT_ASSERT((MutableGraph<DG<int>)); BOOST_CONCEPT_ASSERT((BidirectionalGraph<DG<int>)); and put them the head of a .cpp file that uses DG. These have generated obscure and unhelpful error messages. Copying this line from the examples and using it in the same place produces no errors: BOOST_CONCEPT_ASSERT((BidirectionalIterator<std::list<int>::iterator>));
What do you mean? You want to add methods/functions to the graph type to make it model a specific concept?
No. I mean, yes. I want to know how to define my graph type so it models a specific concept. Eric
-- Jeremiah Willcock _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
On Sun, 13 Jun 2010, Eric Fowler wrote:
On Fri, Jun 11, 2010 at 12:29 PM, Jeremiah Willcock <jewillco@osl.iu.edu> wrote: On Thu, 10 Jun 2010, Eric Fowler wrote:
It seems I do not have a mutable graph. This sort of raises another issue: how do I declare an object that is described by a concept?
The best you can do is apply a concept checking class. That doesn't filter the members so you can only use the MutableGraph-required functions, but it at least makes sure that the graph you have is a MutableGraph.
For example, in this case I know I need a MutableGraph, and I see from the doc (http://www.boost.org/doc/libs/1_43_0/libs/graph/doc/MutableGraph.html) that MutableGraphs have certain properties, such as DefaultConstructible, etc.
Now, how do I declare a MutableGraph, and know I have one? I know that:
typedef adjacency_list<vecS, vecS, undirectedS, POS<position_type> LEN<position_type> > DG;
What methods are missing? Could you please try applying the MutableGraph concept checking class to the DG type and see what breaks?
Again I must ask: How? I have mined the examples and come up with: BOOST_CONCEPT_ASSERT((MutableGraph<DG>)); and BOOST_CONCEPT_ASSERT((MutableGraph<DG<int>)); BOOST_CONCEPT_ASSERT((BidirectionalGraph<DG<int>));
and put them the head of a .cpp file that uses DG. These have generated obscure and unhelpful error messages.
The first line is the one that's correct; what errors does that produce? The other two CONCEPT_ASSERT lines you put are not syntactically correct.
Copying this line from the examples and using it in the same place produces no errors:
BOOST_CONCEPT_ASSERT((BidirectionalIterator<std::list<int>::iterator>));
What do you mean? You want to add methods/functions to the graph type to make it model a specific concept?
No. I mean, yes. I want to know how to define my graph type so it models a specific concept.
You'd need to look at the documentation and then write the appropriate functions. Beyond that, the concept checking classes are currently the only compiler-based help you get without actual concepts in C++. -- Jeremiah Willcock
participants (3)
-
Cedric Laczny
-
Eric Fowler
-
Jeremiah Willcock