[Boost-users] How to find edge between two vertices of undirected graph?

[Eric Fowler]

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

[Cedric Laczny]

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

_______________________________________________
Boost-users mailing list
Boost...@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/boost-users

[Eric Fowler]

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

[Eric Fowler]

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...@gmx.de> wrote:

[Jeremiah Willcock]

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

[Eric Fowler]

On Fri, Jun 11, 2010 at 12:29 PM, Jeremiah Willcock <jewi...@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

[Jeremiah Willcock]

On Sun, 13 Jun 2010, Eric Fowler wrote:

>
>
> On Fri, Jun 11, 2010 at 12:29 PM, Jeremiah Willcock <jewi...@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