Link to home
Start Free TrialLog in
Avatar of BdLm
BdLmFlag for Germany

asked on

BOOST::GRAPH data types

I tried to define the most needed datatypes in a separate header file,
but I get a compiler error for the first type def  ,

what did I do wrong?
the header file:  BoostTypedefs.h
----------------------------------------------------------------------
 
#pragma once
 
#ifndef _WIN32_WINNT            // Lassen Sie die Verwendung spezifischer Features von
Windows XP oder später zu.
#define _WIN32_WINNT 0x0501     // Ändern Sie dies in den geeigneten Wert für
andere Versionen von Windows.
#endif
 
#include <stdio.h>
#include <tchar.h>
 
 
#include <graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp> #include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/astar_search.hpp>
#include <config.hpp>
 
 
 
typedef adjacency_list<vecS, vecS, bidirectionalS> TGraph; // typedef adjacency_list<vecS, vecS, bidirectionalS, no_property> TGraph; // typedef adjacency_list < listS, vecS, directedS, no_property, property < edge_weight_t, int > > TGraph;
 
 
typedef graph_traits < TGraph >::vertex_descriptor Tvertex_descriptor; typedef graph_traits < TGraph >::edge_descriptor Tedge_descriptor; typedef graph_traits <TGraph>::vertex_iterator Tvertex_iter;
typedef graph_traits <TGraph>::edge_iterator   Tedge_iter;
 typedef property_map<TGraph, vertex_index_t>::type TIndexMap;
 
 
--------
 
the cpp file: BoostTypedefs.cpp:
 
 
#include "stdafx.h"
#include "BoostTypedefs.h"

Open in new window

Avatar of evilrix
evilrix
Flag of United Kingdom of Great Britain and Northern Ireland image

Can you state what compiler errors you get please?
Avatar of BdLm

ASKER

Syntax error, missing ';' before '<' , line 24
Do you not need to prefix the types with boost namespace?

Example...

typedef boost::adjacency_list<...> TGraph;
ASKER CERTIFIED SOLUTION
Avatar of evilrix
evilrix
Flag of United Kingdom of Great Britain and Northern Ireland image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Avatar of BdLm

ASKER

Fine, seems to work;

BTW:  put typedefs in the *.h or *cpp file, what is the better programming style?
>> BTW:  put typedefs in the *.h or *cpp file, what is the better programming style?
Always aim for minimal scope, so if they are only used in a single .cpp file then define the typedefs there. It is best practice to try and reduce code visibility as much as possible -- only put in a header what you must as everything that includes that header is forced to have visibility of what's in it.
>> BTW:  put typedefs in the *.h or *cpp file, what is the better programming style?

Depends on where you are going to use the typedefs. If they're only needed in the .cpp file, then put them there. If they're part of the external interface, then put them in the .h file.
Avatar of BdLm

ASKER

final remark:

during the first compilation I forgot to disable the typedef definitions in my main program,
I did not get any compiler warnings on this redefintion, I feel this a  lack of C++,
Pascal would give me a warning or error msg  on this type redefinition.
// boost_demo_v01.cpp : Definiert den Einstiegspunkt für die Konsolenanwendung.
// Add all the different sample codes from BOOST to one unique demo sample // Debug with help of // http://www.experts-exchange.com/Programming/Languages/CPP/Q_22979666.html
// http://www.experts-exchange.com/Programming/Languages/CPP/Q_22981367.html
//
// () BdLm 27-12-2007
//         05-01-2008, 09-01-2008, 10.1.2008
//  now using the boottypedef.h  file
//
 
 
  #include "stdafx.h"
  #include <iostream>                  // for std::cout
  #include <utility>                   // for std::pair
  #include <algorithm>                 // for std::for_each
  #include <vector>
  #include <graph_traits.hpp>
  #include <boost/graph/adjacency_list.hpp>
  #include <boost/graph/dijkstra_shortest_paths.hpp>
  #include <boost/graph/graphviz.hpp>
  #include <boost/graph/astar_search.hpp>
  #include <config.hpp>
 
  #include "BoostTypedefs.h"
 
 
 
 
 
 
  using namespace boost;
 
 
 
 
  template <class Graph> struct exercise_vertex3 {
    exercise_vertex3(Graph& g_) : g(g_) { }
    typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
    void operator()(const Vertex& v) const
    {
 
      typename property_map<Graph, vertex_index_t>::type
          index = get(vertex_index, g);
      typename graph_traits<Graph>::edge_descriptor e;
 
      std::cout << "in-edges: ";
      typedef typename graph_traits<Graph> GraphTraits;
      typename GraphTraits::in_edge_iterator in_i, in_end;
      for (tie(in_i, in_end) = in_edges(v,g);
           in_i != in_end; ++in_i) {
        e = *in_i;
        Vertex src = source(e, g), targ = target(e, g);
        std::cout << "(" << index[src] << "," << index[targ] << ") ";
      }
      std::cout << std::endl;
      //...
    }
    //...
        Graph& g;
  };
 
 
 
  template <class Graph> struct exercise_vertex2 {
    exercise_vertex2(Graph& g_) : g(g_) { }
    typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
    void operator()(const Vertex& v) const
    {
      typedef graph_traits<Graph> GraphTraits;
      typename property_map<Graph, vertex_index_t>::type
        index = get(vertex_index, g);
 
      std::cout << "out-edges: ";
      typename GraphTraits::out_edge_iterator out_i, out_end;
      typename GraphTraits::edge_descriptor e;
      for (tie(out_i, out_end) = out_edges(v, g);
           out_i != out_end; ++out_i) {
        e = *out_i;
        Vertex src = source(e, g), targ = target(e, g);
        std::cout << "(" << index[src] << ","
                  << index[targ] << ") ";
      }
      std::cout << std::endl;
      //...
    }
    //...
        Graph& g;
  };
 
 
 
 
  template <class Graph> struct exercise_vertex {
  exercise_vertex(Graph& g_) : g(g_) { }
  typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
  void operator()(const Vertex& v) const
  {
    using namespace boost;
    typename property_map<Graph, vertex_index_t>::type
      vertex_id = get(vertex_index, g);
    std::cout << "vertex: " << get(vertex_id, v) << std::endl;
 
    // Write out the outgoing edges
    std::cout << "\tout-edges: ";
    typename graph_traits<Graph>::out_edge_iterator out_i, out_end;
    typename graph_traits<Graph>::edge_descriptor e;
    for (tie(out_i, out_end) = out_edges(v, g);
         out_i != out_end; ++out_i)
    {
      e = *out_i;
      Vertex src = source(e, g), targ = target(e, g);
      std::cout << "(" << get(vertex_id, src)
                << "," << get(vertex_id, targ) << ") ";
    }
    std::cout << std::endl;
 
    // Write out the incoming edges
    std::cout << "\tin-edges: ";
    typename graph_traits<Graph>::in_edge_iterator in_i, in_end;
    for (tie(in_i, in_end) = in_edges(v, g); in_i != in_end; ++in_i)
    {
      e = *in_i;
      Vertex src = source(e, g), targ = target(e, g);
      std::cout << "(" << get(vertex_id, src)
                << "," << get(vertex_id, targ) << ") ";
    }
    std::cout << std::endl;
 
    // Write out all adjacent vertices
    std::cout << "\tadjacent vertices: ";
    typename graph_traits<Graph>::adjacency_iterator ai, ai_end;
    for (tie(ai,ai_end) = adjacent_vertices(v, g);  ai != ai_end; ++ai)
      std::cout << get(vertex_id, *ai) <<  " ";
    std::cout << std::endl;
  }
  Graph& g;
};
 
 
 
 
 
 
 
int _tmain(int argc, _TCHAR* argv[])
{
 
/*Constructing a Graph
In this example we will use the BGL adjacency_list class to demonstrate the main ideas in the BGL interface. The adjacency_list class provides a generalized version of the classic "adjacency list"
data structure. The adjacency_list is a template class with six template parameters, though here we only fill in the first three parameters and use the defaults for the remaining three.
The first two template arguments (
vecS, vecS) determine the data structure used to represent the out-edges for each vertex in the graph and the data structure used to represent the graph's vertex set (see section Choosing the Edgelist and VertexList for information about the tradeoffs of the different data structures). The third argument, bidirectionalS, selects a directed graph that provides access to both out and in-edges. The other options for the third argument are directedS which selects a directed graph with only out-edges, and undirectedS which selects an undirected graph.
 
Once we have the graph type selected, we can create the graph in Figure 2 by declaring a graph object and filling in edges using the add_edge() function of the MutableGraph interface (which adjacency_list implements).
We use the array of pairs edge_array merely as a convenient way to explicitly create the edges for this example.*/
 
 
 
 
    // create a typedef for the Graph type with several options
 
        // typedef adjacency_list<vecS, vecS, bidirectionalS> TGraph;
    // typedef adjacency_list<vecS, vecS, bidirectionalS, no_property> TGraph;
    // typedef adjacency_list < listS, vecS, directedS, no_property, property < edge_weight_t, int > > TGraph;
 
 
    // typedef graph_traits < TGraph >::vertex_descriptor Tvertex_descriptor;
    // typedef graph_traits < TGraph >::edge_descriptor Tedge_descriptor;
        // typedef graph_traits <TGraph>::vertex_iterator Tvertex_iter;
    // typedef graph_traits <TGraph>::edge_iterator   Tedge_iter;
 
        // typedef property_map<TGraph, vertex_index_t>::type TIndexMap;
 
 
 
        //   writing out the edges in the graph
        //   for dynamic arrays use the vector of edges ....
    typedef std::pair<int, int> TEdge;
    typedef std::vector <TEdge> TEdge_array;
        typedef std::vector <int> TWeights;
 
 
 
    // Make convenient labels for the vertices
    enum  { A, B, C, D, E, N };
    enum  nodes { AA, BB, CC, DD, EE, NN };
 
        // const int num_vertices = N;
        // int num_vertices;
 
    const char* name = "ABCDE";
 
 
        int  i;
 
 
    TIndexMap   index;
 
 
    TWeights    Weights;
        TEdge       OneEdge;
        TEdge_array Edge_array;
    TEdge       edge_array2[] =
               { TEdge(A,B), TEdge(A,D), TEdge(C,A), TEdge(D,C),
                 TEdge(C,E), TEdge(B,D), TEdge(D,E),TEdge(5,5),TEdge(A,5), TEdge(C,7), TEdge(B,7), TEdge(D,8), TEdge(5,8), TEdge(9,5),
                     TEdge(13,E), TEdge(12,D), TEdge(16,E),TEdge(14,55),TEdge(31,5), TEdge(33,7), TEdge(33,31),
                     TEdge(31,41), TEdge(42,52)};
 
 
    std::pair<Tvertex_iter, Tvertex_iter> vp;
    Tedge_iter   ei, ei_end;
 
 
        const int num_edges = sizeof(edge_array2)/sizeof(edge_array2[0]);
 
 
    std::cout <<  "  BOOST GRAPH DEMO PROGRAM                    \n";
    std::cout <<  "  Compile@01:00 Version 06.02.2008  V.01A  \n\n";
 
 
        //  stupid code:  copy from Fixed Array to a dynamic array (vector, STL)
        for (i=0; i<num_edges; i++)
                {
            Edge_array.push_back(edge_array2[i]);
                Weights.push_back((rand()%10)+1);
                }
 
 
 
 
    // declare a graph object
    // Graph g(num_vertices);
        //
    //  alternative syntax : Graph G(edges + sizeof(edges) / sizeof(E), weights, num_nodes);
 
    TGraph g(num_edges);
 
    // add the edges to the graph object
    for (i = 0; i < num_edges; ++i)
           {
        OneEdge = Edge_array[i];
                add_edge(OneEdge.first, OneEdge.second, g);
           }
 
//Accessing the Vertex Set
//Now that we have created a graph, we can use the graph interface to access the graph data in different ways.
//First we can access all of the vertices in the graph using the vertices() function of the VertexListGraph //interface. This function returns a std::pair of vertex iterators (the first iterator points to the "beginning"
//of the vertices and the second iterator points "past the end").
Dereferencing a vertex iterator gives a
//vertex object. The type of the vertex iterator is given by the graph_traits class. Note that different //graph classes can have different associated vertex iterator types, which is why we need the graph_traits class.
//Given some graph type, the graph_traits class will provide access to the vertex_iterator type.
//
//The following example prints out the index for each of the vertices in the graph. All vertex and edge properties, //including index, are accessed via property map objects. The property_map class is used to obtain the property map //type for a specific property (specified by vertex_index_t, one of the BGL predefined properties) and function //call get(vertex_index, g) returns the actual property map object.
 
    index = get(vertex_index, g);
 
    std::cout << "vertices(g) = ";
 
    for (vp = vertices(g); vp.first != vp.second; ++vp.first)
      std::cout << index[*vp.first] <<  " ";
    std::cout << std::endl;
 
//Accessing the Edge Set
//The set of edges for a graph can be accessed with the edges() function of the EdgeListGraph interface.
//Similar to the vertices() function, this returns a pair of iterators, but in this case the iterators //are edge iterators. Dereferencing an edge iterator gives an edge object.
The source() and target()
//functions return the two vertices that are connected by the edge. Instead of explicitly creating a std::pair //for the iterators, this time we will use the tie() helper function. This handy function can be used to assign //the parts of a std::pair into two separate variables, in this case ei and ei_end. This is usually more convenient //than creating a std::pair and is our method of choice for the BGL.
 
    std::cout << "edges(g) = ";
 
 
        for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
        std::cout << "(" << index[source(*ei, g)]
                  << "," << index[target(*ei, g)] << ") ";
    std::cout << std::endl;
 
// -------------------------------------------------------------------------
-----------------------------------
//  The Adjacency Structure
//  will encapsulate this in an "exercise vertex" function, and apply it to each vertex in the graph.
//  std::for_each(vertices(g).first, vertices(g).second, exercise_vertex<Graph>(g));
 
 
     std::for_each(vertices(g).first, vertices(g).second, exercise_vertex<TGraph>(g));
 
 
//Out-Edges, In-Edges, and Edge Descriptors //The out-edges of a vertex are accessed with the out_edges() function of the IncidenceGraph interface.
//The out_edges() function takes two arguments: the first argument is the vertex and the second is the //graph object. The function returns a pair of iterators which provide access to all of the out-edges //of a vertex (similar to how the vertices() function returned a pair of iterators). The iterators are //called out-edge iterators and dereferencing one of these iterators gives an edge descriptor object.
//An edge descriptor plays the same kind of role as the vertex descriptor object, it is a "black box"
//provided by the graph type. The following code snippet prints the source-target pairs for each out-edge //of vertex v.
 
 
         std::for_each(vertices(g).first, vertices(g).second, exercise_vertex2<TGraph>(g));
 
 
 
//The in_edges() function of the BidirectionalGraph interface provides access to all the in-edges of a //vertex through in-edge iterators. The in_edges() function is only available for the adjacency_list if //bidirectionalS is supplied for the Directed template parameter. There is an extra cost in space when //bidirectionalS is specified instead of directedS.
 
 
 
          std::for_each(vertices(g).first, vertices(g).second, exercise_vertex3<TGraph>(g));
 
 
 
 
 
//   Version  A, somewhere derived from the sample code
//   http://www.boost.org/libs/graph/doc/Graph.html
//   http://www.boost.org/libs/graph/doc/dijkstra_shortest_paths.html
//   Associated Types  boost::graph_traits<G>::vertex_descriptor
//    void dijkstra_shortest_paths
//    (const Graph& g,
//     typename graph_traits<Graph>::vertex_descriptor s,
//     PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
//     VertexIndexMap index_map,
//     CompareFunction compare, CombineFunction combine, DistInf inf,
DistZero zero,
//     DijkstraVisitor vis, ColorMap color = default)
 
 
 
 
 
         // vector for storing distance property
 
         std::vector<Tvertex_descriptor> p(num_vertices(g));
     std::vector<int> d(num_vertices(g));
 
     // Tvertex_descriptor s = vertex(A, g);
    Tvertex_descriptor s = *(vertices(g).first);
 
 
 
 
//  from here, can't run this demo code ...
// invoke variant 1..3 of Dijkstra's algorithm
 
 
//   dijkstra_shortest_paths(g, s, distance_map(&d[0]));
 
 
//   dijkstra_shortest_paths(g, s,
predecessor_map(&p[0]).distance_map(&d[0]));   // Compiler fails now  here
....
 
//   dijkstra_shortest_paths(g, s, distance_map(&d[0]).
visitor(make_predecessor_recorder(&p[0])));
 
 
 
 
 
 
 
 
 
 
 
 
        system ("pause");
 
 
    return 0;
 
}

Open in new window

If the typedef was identical it is ignored. If it is different you get an error: -


typedef int foo;
typedef int foo; // No error
typedef char foo; // Error: main.cpp(3) : error C2371: 'foo' : redefinition; different basic types
 
int main(){}

Open in new window

>> I did not get any compiler warnings on this redefintion, I feel this a  lack of C++,
If the typedef is identical it's not a redefinition :)

>> Pascal would give me a warning or error msg  on this type redefinition.
Good for Pascal :-p