Re: [boost] [BGL] dijkstra-relax-abs

From: Joel Young (jdy_at_[hidden])
Date: 2001-09-03 12:48:19

Thanks that worked.

I am also getting the following:

In file included from stub.cc:1:
/u/jdy/boost_1_24_0/boost/graph/uniform_cost_search.hpp:173: syntax error before `;'

where line 173 f uniform_cost_search.hpp is:
      PredecessorMap m_predecessor;

and where stub.cc is:

////cut here////
#include <boost/graph/uniform_cost_search.hpp> 

int main(int,char*[])
{
  return 0;
}
////cut here////

Also I get an internal compiler error (gcc 2.95.3) with the following stub:

////cut here////
#include <vector>

#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp> 

  typedef boost::property<
            boost::vertex_distance_t, long int,
            boost::property<
              boost::vertex_index_t, int,
              boost::no_property
            >
          > vertex_property_t;
            
  typedef boost::property<
            boost::edge_weight_t, long int,
            boost::no_property
          > edge_property_t;

  typedef boost::adjacency_list<
            boost::mapS,
            boost::vecS,
            boost::bidirectionalS,
            vertex_property_t,
            edge_property_t
          > basic_graph_t;

int main(int,char*[])
{
  basic_graph_t graph;

  typedef boost::graph_traits<basic_graph_t>::vertex_descriptor Vertex;
  Vertex rootnode = boost::add_vertex(graph); 

  std::vector<Vertex> pred(num_vertices(graph));
 
  boost::dijkstra_shortest_paths(
    graph,
    rootnode,
    boost::distance_map(
      boost::get(boost::vertex_distance,graph)
    ).boost::predecessor_map(&pred[0])
  );

  return 0;
}
////cut here////

jdy.759 ==> g++ -I/u/jdy/boost_1_24_0/ -ftemplate-depth-80 stub.cc
stub.cc: In function `int main(int, char **)':
stub.cc:42: Internal compiler error.
stub.cc:42: Please submit a full bug report.
stub.cc:42: See <URL:http://www.gnu.org/software/gcc/bugs.html> for instructions.

Joel
--------
From: Jeremy Siek <jsiek_at_[hidden]>
Date: Mon, 3 Sep 2001 10:57:37 -0500 (EST)
  To: <boost_at_[hidden]>
  Cc: <jdy_at_[hidden]>
Subj: Re: [boost] [BGL] dijkstra-relax-abs

Hi Joel,

Edge weights do not have to be signed types, however, the type you use
must have a version of std::abs() defined for it.

Urgh, the "std::swap() issue" rears its ugly head again!

Here's a couple of possible workarounds:

1. define a std::abs for unsigned int. This is illegal according
to the C++ standard, but will work.

2. I change the std::abs() call in relax to just plain abs() and put a
using std::abs in front. Then you define an abs() for unsigned
int in the global namespace.

I think the better option is 2), so I'll go ahead and make that change.

On Mon, 3 Sep 2001, Joel Young wrote:
jdy>
jdy> Hi,
jdy>
jdy> With gcc-2.95.3, if the "edge_weight_t" is "unsigned int" in the
jdy> edge properties, than with dijkstra_shortest_path I get the following
jdy> error:
jdy>
jdy> .../boost_1_24_0/boost/graph/dijkstra_shortest_paths.hpp:189:   instantiated from here
jdy> .../boost_1_24_0/boost/graph/relax.hpp:65: call of overloaded `abs (unsigned int)' is ambiguous
jdy> /usr/include/stdlib.h:699: candidates are: int abs(int)
jdy> .../include/g++-3/cstdlib:17:                 long int abs(long int)
jdy> .../include/g++-3/cmath:40:                 float abs(float)
jdy> .../include/g++-3/cmath:42:                 double abs(double)
jdy> .../include/g++-3/cmath:72:                 long double abs(long double)
jdy>
jdy> If I change the edge_weight_t to "long int" for example it build fine.
jdy> Must edge weights be signed types?
jdy>
jdy>
jdy> Also, it would be nice if there was an example on using the
jdy> dijkstra_shortest_paths with no external maps.

Okidoke.

Cheers,
Jeremy

----------------------------------------------------------------------
Jeremy Siek                          http://php.indiana.edu/~jsiek/
Ph.D. Student, Indiana Univ. B'ton   email: jsiek_at_[hidden]
C++ Booster (http://www.boost.org)   office phone: [phone]
----------------------------------------------------------------------