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

Subject: Re: [Boost-users] How to find edge between two vertices of undirected graph?
From: Eric Fowler (eric.fowler_at_[hidden])
Date: 2010-06-10 13:35:32

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_at_[hidden]>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_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users