Graph - return edge_descriptor
Can anybody tell my why the find_edge function in the code below fails to get a property if I return the first edge in the list. This is what happens - Find_edge looks for edge A - B It winds it and prints out the edge descriptor, and the weight of the edge It the returns the edge The main code prints out the edge descriptor and the fails when trying to print the weight. BTW - Is there a ready made function to find an edge based on the vertices ? #include <boost/config.hpp> #include <iostream> #include <fstream> #include <boost/graph/graph_traits.hpp> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/dijkstra_shortest_paths.hpp> using namespace boost; // Find edge template <class Graph> std::pair<bool, graph_traits<Graph>::edge_descriptor> find_edge(graph_traits<Graph>::vertex_descriptor u, graph_traits<Graph>::vertex_descriptor v, Graph g) { graph_traits<Graph>::out_edge_iterator ei, edge_end; for (boost::tie(ei,edge_end) = out_edges(u, g); ei != edge_end; ++ei) { if (target(*ei, g) == v) { std::cout << "Inside " << *ei << " " << get(edge_weight, g, *ei) << std::endl; return std::make_pair(true, *ei); } } return std::make_pair(false, *ei); // Is there a null edge that I can return ? } int main(int, char *[]) { typedef adjacency_list < listS, vecS, directedS, no_property, property < edge_weight_t, int > > graph_t; typedef graph_traits < graph_t >::vertex_descriptor vertex_descriptor; typedef graph_traits < graph_t >::edge_descriptor edge_descriptor; typedef std::pair<int, int> Edge; const int num_nodes = 5; enum nodes { A, B, C, D, E }; Edge edge_array[] = { Edge(A, C), Edge(B, B), Edge(B, D), Edge(B, E), Edge(C, B), Edge(C, D), Edge(D, E), Edge(E, A), Edge(E, B) }; int weights[] = { 1, 2, 1, 2, 7, 3, 1, 1, 1 }; int num_arcs = sizeof(edge_array) / sizeof(Edge); #ifdef BOOST_MSVC graph_t g(num_nodes); property_map<graph_t, edge_weight_t>::type weightmap = get(edge_weight, g); for (std::size_t j = 0; j < num_arcs; ++j) { edge_descriptor e; bool inserted; tie(e, inserted) = add_edge(edge_array[j].first, edge_array[j].second, g); weightmap[e] = weights[j]; } #else graph_t g(edge_array, edge_array + num_arcs, weights, num_nodes); property_map<graph_t, edge_weight_t>::type weightmap = get(edge_weight, g); #endif graph_traits < graph_t >::edge_descriptor e; bool found; std::cout << "List All" << std::endl; graph_traits < graph_t >::edge_iterator ei, ei_end; for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) { std::cout << *ei << get(weightmap, *ei) << std::endl; } std::cout << "List Not First" << std::endl; tie(found, e) = find_edge< graph_t >(E, A, g); std::cout << "Outside " << e << get(weightmap, e) << std::endl; // This edge is OK std::cout << "List First" << std::endl; tie(found, e) = find_edge< graph_t >(A, C, g); std::cout << "Outside " << e << get(weightmap, e) << std::endl; // This line fails to get the weight return EXIT_SUCCESS; } Richard Shaw ¤º°`°º¤ø,¸¸,ø¤º°`°º¤ø¤º°`°º¤ø,¸¸,ø¤º°`°º¤ø¤º°`°º¤ø,¸¸,ø¤ Atkins Transport Systems Woodcote Grove Ashley Road Epsom KT18 5BW Direct Dial.: +44 (0) 1372 756407 Switchboard: +44 (0) 1372 726140 Fax: +44 (0) 1372 740055 www.atkinsglobal.com/transportsystems <www.atkinsglobal.com/transportsystems> This email and any attached files are confidential and copyright protected. If you are not the addressee, any dissemination of this communication is strictly prohibited. Unless otherwise expressly agreed in writing, nothing stated in this communication shall be legally binding.
Hi Richard, On Thu, 22 Aug 2002, Shaw, Richard A wrote: richar> Can anybody tell my why the find_edge function in the code below richar> fails to get a property if I return the first edge in the list. I just ran your example with g++ 2.95.2 on solaris, but I could not reproduce the problem (BTW, was the problem a seg fault?). What compiler/OS are you using? richar> BTW - Is there a ready made function to find an edge based on the vertices ? Yes, it is the "edge" function. Cheers, Jeremy ---------------------------------------------------------------------- Jeremy Siek http://php.indiana.edu/~jsiek/ Ph.D. Student, Indiana Univ. B'ton email: jsiek@osl.iu.edu C++ Booster (http://www.boost.org) office phone: (812) 855-3608 ----------------------------------------------------------------------
On Thu, 2002-08-22 at 10:19, Shaw, Richard A wrote:
Can anybody tell my why the find_edge function in the code below fails to get a property if I return the first edge in the list.
This is what happens -
Find_edge looks for edge A - B It winds it and prints out the edge descriptor, and the weight of the edge It the returns the edge The main code prints out the edge descriptor and the fails when trying to print the weight.
BTW - Is there a ready made function to find an edge based on the vertices ?
#include <boost/config.hpp> #include <iostream> #include <fstream>
#include <boost/graph/graph_traits.hpp> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/dijkstra_shortest_paths.hpp>
using namespace boost;
// Find edge template <class Graph> std::pair<bool, graph_traits<Graph>::edge_descriptor> find_edge(graph_traits<Graph>::vertex_descriptor u, graph_traits<Graph>::vertex_descriptor v, Graph g)
It's a lot more efficient to pass a const reference to the graph you're searching in. As Jeremy though, I cannot reproduce your problem using gcc 3.1 and either of boost 1.2.8 or the latest CVS source tree. Regards, Tarjei
On Thu, 2002-08-22 at 10:19, Shaw, Richard A wrote:
Can anybody tell my why the find_edge function in the code below fails to get a property if I return the first edge in the list.
This is what happens -
Find_edge looks for edge A - B It winds it and prints out the edge descriptor, and the weight of
It the returns the edge The main code prints out the edge descriptor and the fails when
I did mean to mention the compiler etc. It is - gcc version 2.95.3-5 (cygwin special) and boost 1.28 I did think after reading the graph introductin that the edge() function may do what I wanted but I couldn't find any other mention of it. Just discovered the adjacency_list_io classes after I'd spend the time writing my own (low tech ones). I'll try using edge instead and see what happens Thanks - it's great to get such a quick response. --- In Boost-Users@y..., Tarjei Knapstad <tarjeik@c...> wrote: the edge trying to
print the weight.
BTW - Is there a ready made function to find an edge based on the vertices ?
#include <boost/config.hpp> #include <iostream> #include <fstream>
#include <boost/graph/graph_traits.hpp> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/dijkstra_shortest_paths.hpp>
using namespace boost;
// Find edge template <class Graph> std::pair<bool, graph_traits<Graph>::edge_descriptor> find_edge(graph_traits<Graph>::vertex_descriptor u, graph_traits<Graph>::vertex_descriptor v, Graph g)
It's a lot more efficient to pass a const reference to the graph you're searching in.
As Jeremy though, I cannot reproduce your problem using gcc 3.1 and either of boost 1.2.8 or the latest CVS source tree.
Regards, Tarjei
On Thu, 2002-08-22 at 10:19, Shaw, Richard A wrote:
Can anybody tell my why the find_edge function in the code below fails to get a property if I return the first edge in the list.
This is what happens -
Find_edge looks for edge A - B It winds it and prints out the edge descriptor, and the weight of
It the returns the edge The main code prints out the edge descriptor and the fails when
In my last mail I didn't say how it failed. It gets a bad address for the property - so for the weight it displays a large meaningless number, for a string property it prints pages of garbage - I was surprised how few zeros were in memory ! I had a look at the implementation of edge() and I see that it returns the following - edge_descriptor(u, v, &(*i).get_property() my code just returns the contents of the out_edge_iterator I changed my function to return - return std::make_pair(true, graph_traits<Graph>::edge_descriptor(u, v, (*ei).get_property())); but it made no difference. I tried using edge() and it works OK. Strange. --- In Boost-Users@y..., Tarjei Knapstad <tarjeik@c...> wrote: the edge trying to
print the weight.
BTW - Is there a ready made function to find an edge based on the vertices ?
#include <boost/config.hpp> #include <iostream> #include <fstream>
#include <boost/graph/graph_traits.hpp> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/dijkstra_shortest_paths.hpp>
using namespace boost;
// Find edge template <class Graph> std::pair<bool, graph_traits<Graph>::edge_descriptor> find_edge(graph_traits<Graph>::vertex_descriptor u, graph_traits<Graph>::vertex_descriptor v, Graph g)
It's a lot more efficient to pass a const reference to the graph you're searching in.
As Jeremy though, I cannot reproduce your problem using gcc 3.1 and either of boost 1.2.8 or the latest CVS source tree.
Regards, Tarjei
participants (4)
-
Jeremy Siek
-
richardshaw11
-
Shaw, Richard A
-
Tarjei Knapstad