johnson_all_pairs_shortest_paths() doesn't take my graph (files)

From: Ramón Casero Cañas (yg-boost-users_at_[hidden])
Date: 2002-11-20 17:11:29

It seems that messages can only be sent in plain text.
So here comes my steiner.hpp, with the description of the graph

---------- steiner.hpp -----------------
#include <utility>                       // for std::pair
#include <boost/graph/adjacency_list.hpp>/* for namespace boost
                                           *     vertex_index_t
                                           *     edge_weight_t
                                           *     listS
                                           *     undirectedS
                                           */

using namespace boost;

/* data structures definitions */
namespace boost {
   enum vertex_to_be_spanned_t { // used to mark vertices of W
     vertex_to_be_spanned
   };
   BOOST_INSTALL_PROPERTY(vertex, to_be_spanned);
}
namespace steiner {
   typedef std::pair<int,int> Edge; // type of edges

   /* Steiner Problem Graph:
    *   - multigraph
    *   - add_edge(), ... stability and speed, bad space overhead
    *   - vertex indices, edge weights
    */
   typedef int WeightType;
   typedef property <vertex_index_t, int,
                     property <vertex_to_be_spanned_t, bool> > 
VertexProperty;
   typedef property <edge_weight_t, WeightType, property<
     edge_weight2_t, int > > EdgeProperty;
//   typedef property <edge_weight_t, WeightType> EdgeProperty;
   typedef adjacency_list <listS, listS, undirectedS,
                           VertexProperty, EdgeProperty > SteinerGraph;
}

/* steiner exceptions definitions */
namespace steiner {
#define EX_FORMAT "not a valid steiner problem file";
}

-------------------------- steiner.hpp (end) ------------------

This is a header file with some general definitions

------------------ rccstd.hpp ---------------------------
/* rccstd.hpp */

#define DEBUG   // set debug mode

#ifdef DEBUG
#define DBCOUT(x) std::cout << x; // standard output debugging macro
#define DB(x) x;                  // function debugging macro
#else
#define DBCOUT
#define DB
#endif

/* debug standard output prints */
#define PUF(x) std::cout << "Puf(" << x << ")!" << endl;

/* exceptions */
#define EX_MEM "error assigning memory"
#define EX_FNOTOPEN "file cannot be opened"
#define EX_FNOTSAVED "file cannot be saved"
/* end exceptions */

----------------------- rccstd.hpp (end) ---------------------

This is the file that gives the compilation error, as describred in the 
former message

--------------------- dnh.cpp ------------------------
#include <iostream>                      // for std::cout
// #include <fstream>                       // for std::ifstream
#include "steiner.hpp"                   // Steiner problem structures
                                          //    using namespace boost;
#include "steiner_io.hpp"                // function constructors
#include "rccstd.hpp"                    // ramón's standard
                                          //    exceptions, functions...
// #include <string>                        // for strcat, strcpy, strlen
// #include "boost/multi_array.hpp"
// #include <boost/config.hpp>
// #include <vector>
// #include <iomanip>
// #include <boost/property_map.hpp>
#include <boost/graph/johnson_all_pairs_shortest.hpp>

using namespace steiner;

namespace steiner {
   template <class WT>
   int dnh(SteinerGraph& g);
}

/* int main(int argc, char *argv[])
  * --------------------------------
  * *argv[] (IN): file names array
  * --------------------------------
  * return n:   n files were succesfully read, n > 0
  * return 0:   no files could be read
  * return -1:  unexpected error
  * --------------------------------
  * read steiner problem from files
  */
int main(int argc, char *argv[]) {
   int nf;   // control function output

   try {
     DBCOUT(argc << endl);
     if (argc != 2) {
       throw (char *)"sintaxis: dnh filename";
     }

     std::cout << "file: " << argv[1]
               << "--------------------" << endl;
     SteinerGraph g;
     nf = readsteinerORfile(g, argv[1]);
     if (nf == -1) {
       throw (char *)"readsteinerORfile: unexpected exception";
     }

     dnh<WeightType>(g);

     nf = writesteinerDOTfile(g, argv[1]);
     if (nf == -1) {
       throw (char *)"writesteinerDOTfile: unexpected exception";
     }

     return 1;
   }
   catch (char *s) { // no files could be read
     std::cout << "exception! " << s << endl;
     return 0;
   }
   catch (...) {
     std::cout << "unexpected exception!" << endl;
     return -1;
   }

}

namespace steiner {
   template <class WT>
   int dnh(SteinerGraph& g) {
//     int i;            // counter

     try {
//       const int num_ver = num_vertices(g);
//       std::vector < int >d_vector(num_ver, std::numeric_limits < int 
 >::max());

//       int **d_matrix;             // make distance matrix
//       d_matrix = new int *[num_ver];
//       if (d_matrix == NULL) throw (char *)EX_MEM;
//       for (i = 0; i < num_ver; i++) {
//      d_matrix[i] = new WT[num_ver];
//      if (d_matrix[i] == NULL) throw (char *)EX_MEM;
//       }

//////////////////////////
       typedef adjacency_list<vecS, vecS, directedS, no_property,
         property< edge_weight_t, int, property< edge_weight2_t, int >
         > > Graph;
       const int V = 6;
       typedef std::pair < int, int >Edge2;
       Edge2 edge_array[] =
         { Edge2(0, 1), Edge2(0, 2), Edge2(0, 3), Edge2(0, 4), Edge2(0, 5),
           Edge2(1, 2), Edge2(1, 5), Edge2(1, 3), Edge2(2, 4), Edge2(2, 5),
           Edge2(3, 2), Edge2(4, 3), Edge2(4, 1), Edge2(5, 4)
         };
       const std::size_t E = sizeof(edge_array) / sizeof(Edge2);
       Graph G(edge_array, edge_array + E, V);
//       Graph G(edge_array, edge_array + E, V);
       property_map < Graph, edge_weight_t >::type w = get(edge_weight,
         G);
       int weights[] = { 0, 0, 0, 0, 0, 3, -4, 8, 1, 7, 4, -5, 2, 6 };
       int *wp = weights;

       graph_traits < Graph >::edge_iterator e, e_end;
       for (boost::tie(e, e_end) = edges(G); e != e_end; ++e)
         w[*e] = *wp++;
//       int d_matrix[10][10];
       std::vector < int >d_vector(V, std::numeric_limits < int >::max());
//       std::vector < int >d_vector(V, std::numeric_limits < int >::max());
       int D[V][V];
//       int D[V][V];
       johnson_all_pairs_shortest_paths(g, D, distance_map(&d_vector[0]));

//       for (i = 0; i < num_ver; i++) { // clear distance matrix
//      if (d_matrix[i] != NULL) delete []d_matrix[i];
//       }
//       if (d_matrix != NULL) delete []d_matrix;

       return 1;
     }
     catch (char *s) { // no files could be read
       std::cout << "exception! " << s << endl;
       return 0;
     }
     catch (...) {
       std::cout << "unexpected exception!" << endl;
       return -1;
     }

   }
}

--------------------- dnh.cpp (end) --------------------------------

steiner_io.hpp and steiner_io.cpp define two functions, 
readsteinerORfile() and writesteinerDOTfile() that read a graph from a 
file of the OR-library and write it in .dot format.

Regards,

Ramón.