Documentation Data Using boost::Directed Graph, boost::Undirected Graph and Generating the Undirected graph in a boost::Directed graph

graphBoostTest.cpp

#include <boost/config.hpp>
#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/iteration_macros.hpp>

/* 

To be able to distinguish the edges (source,target) from the (target,source)
"cost" column weights are set to 1 for (source,target)
"reverse_cost" column weights are set to 2 for (target,source)

*/
using namespace boost;

template < typename DirectedGraph > void
simulation_undirected_in_directed_graph()
{
  const int V = 3;
  DirectedGraph digraph(V);
  typename graph_traits < DirectedGraph >::vertex_descriptor vd;
  typedef typename DirectedGraph::edge_property_type Weight;
  typename property_map < DirectedGraph, edge_weight_t >::type
    weight = get(edge_weight, digraph);
  typename graph_traits < DirectedGraph >::out_edge_iterator out, out_end;
  typename graph_traits < DirectedGraph >::edge_iterator ei;
  typename graph_traits < DirectedGraph >::vertex_iterator vi;

  std::deque< typename graph_traits < DirectedGraph >::vertex_descriptor > vert;
  std::cout << "UNDIRECTED ON BOOST::DIRECTED GRAPH DEMO\n";
  for (int i=0; i < 19; ++i) {
    vd = vertex(i, digraph);
    vert.push_back(vd);
  }

  // the "cost" column
  add_edge(vert[1],  vert[2],  Weight(1), digraph); // id 1
  // id 2 has -1
  // id 3 has -1
  add_edge(vert[2],  vert[5],  Weight(1), digraph); // id 4
  add_edge(vert[3],  vert[6],  Weight(1), digraph); // id 5
  add_edge(vert[7],  vert[8],  Weight(1), digraph); // id 6
  add_edge(vert[8],  vert[5],  Weight(1), digraph); // id 7
  add_edge(vert[5],  vert[6],  Weight(1), digraph); // id 8
  add_edge(vert[6],  vert[9],  Weight(1), digraph); // id 9
  add_edge(vert[5],  vert[10], Weight(1), digraph); // id 10
  add_edge(vert[6],  vert[11], Weight(1), digraph); // id 11
  add_edge(vert[10], vert[11], Weight(1), digraph); // id 12
  add_edge(vert[11], vert[12], Weight(1), digraph); // id 13
  add_edge(vert[10], vert[13], Weight(1), digraph); // id 14
  add_edge(vert[9],  vert[12], Weight(1), digraph); // id 15
  add_edge(vert[4],  vert[9],  Weight(1), digraph); // id 16
  add_edge(vert[14], vert[15], Weight(1), digraph); // id 17
  add_edge(vert[16], vert[17], Weight(1), digraph); // id 18

  // the "reverse_cost" column
  add_edge(vert[2],  vert[1], Weight(2), digraph); // id 1
  add_edge(vert[3],  vert[2], Weight(2), digraph); // id 2
  add_edge(vert[4],  vert[3], Weight(2), digraph); // id 3
  add_edge(vert[5],  vert[2], Weight(2), digraph); // id 4
  // id 5 has -1
  add_edge(vert[8],  vert[7], Weight(2), digraph); // id 6
  add_edge(vert[5],  vert[8], Weight(2), digraph); // id 7
  add_edge(vert[6],  vert[5], Weight(2), digraph); // id 8
  add_edge(vert[9],  vert[6], Weight(2), digraph); // id 9
  add_edge(vert[10], vert[5], Weight(2), digraph); // id 10
  // id 11 has -1
  // id 12 has -1
  // id 13 has -1
  add_edge(vert[13], vert[10], Weight(2), digraph); // id 14
  add_edge(vert[12], vert[9],  Weight(2), digraph); // id 15
  add_edge(vert[9],  vert[4],  Weight(2), digraph); // id 16
  add_edge(vert[15], vert[14], Weight(2), digraph); // id 17
  add_edge(vert[17], vert[16], Weight(2), digraph); // id 18


  // the "cost" column (reversing)
  add_edge(vert[2],  vert[1],  Weight(1), digraph); // id 1
  // id 2 has -1
  // id 3 has -1
  add_edge(vert[5],  vert[2],  Weight(1), digraph); // id 4
  add_edge(vert[6],  vert[3],  Weight(1), digraph); // id 5
  add_edge(vert[8],  vert[7],  Weight(1), digraph); // id 6
  add_edge(vert[5],  vert[8],  Weight(1), digraph); // id 7
  add_edge(vert[6],  vert[5],  Weight(1), digraph); // id 8
  add_edge(vert[9],  vert[6],  Weight(1), digraph); // id 9
  add_edge(vert[10], vert[5], Weight(1), digraph); // id 10
  add_edge(vert[11], vert[6], Weight(1), digraph); // id 11
  add_edge(vert[11], vert[10], Weight(1), digraph); // id 12
  add_edge(vert[12], vert[11], Weight(1), digraph); // id 13
  add_edge(vert[13], vert[10], Weight(1), digraph); // id 14
  add_edge(vert[12], vert[9], Weight(1), digraph); // id 15
  add_edge(vert[9],  vert[4],  Weight(1), digraph); // id 16
  add_edge(vert[15], vert[14], Weight(1), digraph); // id 17
  add_edge(vert[17], vert[16], Weight(1), digraph); // id 18

  // the "reverse_cost" column (reversing)
  add_edge(vert[1], vert[2], Weight(2), digraph); // id 1
  add_edge(vert[2], vert[3], Weight(2), digraph); // id 2
  add_edge(vert[3], vert[4], Weight(2), digraph); // id 3
  add_edge(vert[2], vert[5], Weight(2), digraph); // id 4
  // id 5 has -1
  add_edge(vert[7], vert[8], Weight(2), digraph); // id 6
  add_edge(vert[8], vert[5], Weight(2), digraph); // id 7
  add_edge(vert[5], vert[6], Weight(2), digraph); // id 8
  add_edge(vert[6], vert[9], Weight(2), digraph); // id 9
  add_edge(vert[5], vert[10], Weight(2), digraph); // id 10
  // id 11 has -1
  // id 12 has -1
  // id 13 has -1
  add_edge(vert[10], vert[13], Weight(2), digraph); // id 14
  add_edge(vert[9],  vert[12], Weight(2), digraph); // id 15
  add_edge(vert[4],  vert[9],  Weight(2), digraph); // id 16
  add_edge(vert[14], vert[15], Weight(2), digraph); // id 17
  add_edge(vert[16], vert[17], Weight(2), digraph); // id 18

#if 0
  std::cout << "all edges:\n";
  for (ei = edges(digraph).first; ei!=edges(digraph).second; ++ei) 
    std::cout << ' ' << *ei << get(weight, *ei) <<  std::endl;
  std::cout << std::endl;
#endif

  for (vi = vertices(digraph).first; vi!=vertices(digraph).second; ++vi) {
    std::cout << "out_edges(" << *vi << "):";
    for (boost::tie(out, out_end) = out_edges(*vi, digraph); out != out_end; ++out) {
      std::cout << ' ' << *out << "=" << get(weight, *out);
    }
    std::cout << std::endl;
  }
  std::cout << std::endl;

}


template < typename DirectedGraph > void
directed_graph_demo()
{
  const int V = 3;
  DirectedGraph digraph(V);
  typename graph_traits < DirectedGraph >::vertex_descriptor vd;
  typedef typename DirectedGraph::edge_property_type Weight;
  typename property_map < DirectedGraph, edge_weight_t >::type
    weight = get(edge_weight, digraph);
  typename graph_traits < DirectedGraph >::out_edge_iterator out, out_end;
  typename graph_traits < DirectedGraph >::edge_iterator e, ei;
  typename graph_traits < DirectedGraph >::vertex_iterator vi;

  std::deque< typename graph_traits < DirectedGraph >::vertex_descriptor > vert;
  std::cout << "DIRECTED GRAPH DEMO\n";
  for (int i=0; i < 19; ++i) {
    vd = vertex(i, digraph);
    vert.push_back(vd);
  }

  // the "cost" column
  add_edge(vert[1],  vert[2],  Weight(1), digraph); // id 1
  // id 2 has -1
  // id 3 has -1
  add_edge(vert[2],  vert[5],  Weight(1), digraph); // id 4
  add_edge(vert[3],  vert[6],  Weight(1), digraph); // id 5
  add_edge(vert[7],  vert[8],  Weight(1), digraph); // id 6
  add_edge(vert[8],  vert[5],  Weight(1), digraph); // id 7
  add_edge(vert[5],  vert[6],  Weight(1), digraph); // id 8
  add_edge(vert[6],  vert[9],  Weight(1), digraph); // id 9
  add_edge(vert[5],  vert[10], Weight(1), digraph); // id 10
  add_edge(vert[6],  vert[11], Weight(1), digraph); // id 11
  add_edge(vert[10], vert[11], Weight(1), digraph); // id 12
  add_edge(vert[11], vert[12], Weight(1), digraph); // id 13
  add_edge(vert[10], vert[13], Weight(1), digraph); // id 14
  add_edge(vert[9],  vert[12], Weight(1), digraph); // id 15
  add_edge(vert[4],  vert[9],  Weight(1), digraph); // id 16
  add_edge(vert[14], vert[15], Weight(1), digraph); // id 17
  add_edge(vert[16], vert[17], Weight(1), digraph); // id 18

  // the "reverse_cost" column
  add_edge(vert[2],  vert[1], Weight(2), digraph); // id 1
  add_edge(vert[3],  vert[2], Weight(2), digraph); // id 2
  add_edge(vert[4],  vert[3], Weight(2), digraph); // id 3
  add_edge(vert[5],  vert[2], Weight(2), digraph); // id 4
  // id 5 has -1
  add_edge(vert[8],  vert[7], Weight(2), digraph); // id 6
  add_edge(vert[5],  vert[8], Weight(2), digraph); // id 7
  add_edge(vert[6],  vert[5], Weight(2), digraph); // id 8
  add_edge(vert[9],  vert[6], Weight(2), digraph); // id 9
  add_edge(vert[10], vert[5], Weight(2), digraph); // id 10
  // id 11 has -1
  // id 12 has -1
  // id 13 has -1
  add_edge(vert[13], vert[10], Weight(2), digraph); // id 14
  add_edge(vert[12], vert[9],  Weight(2), digraph); // id 15
  add_edge(vert[9],  vert[4],  Weight(2), digraph); // id 16
  add_edge(vert[15], vert[14], Weight(2), digraph); // id 17
  add_edge(vert[17], vert[16], Weight(2), digraph); // id 18



#if 0
  std::cout << "all edges:\n";
  for (ei = edges(digraph).first; ei!=edges(digraph).second; ++ei) 
    std::cout << ' ' << *ei << get(weight, *ei) <<  std::endl;
  std::cout << std::endl;
#endif

  for (vi = vertices(digraph).first; vi!=vertices(digraph).second; ++vi) {
    std::cout << "out_edges(" << *vi << "):";
    for (boost::tie(out, out_end) = out_edges(*vi, digraph); out != out_end; ++out) {
      std::cout << ' ' << *out << "=" << get(weight, *out);
    }
    std::cout << std::endl;
  }
  std::cout << std::endl;

}

template < typename UndirectedGraph > void
undirected_graph_demo()
{
  const int V = 3;
  UndirectedGraph undigraph(V);
  typename graph_traits < UndirectedGraph >::vertex_descriptor vd;
  typedef typename UndirectedGraph::edge_property_type Weight;
  typename property_map < UndirectedGraph, edge_weight_t >::type
    weight = get(edge_weight, undigraph);
  typename graph_traits < UndirectedGraph >::out_edge_iterator out, out_end;
  typename graph_traits < UndirectedGraph >::edge_iterator e, ei;
  typename graph_traits < UndirectedGraph >::vertex_iterator vi;

  std::deque< typename graph_traits < UndirectedGraph >::vertex_descriptor > vert;
  std::cout << "UNDIRECTED GRAPH DEMO\n";
  for (int i=0; i < 19; ++i) {
    vd = vertex(i, undigraph);
    vert.push_back(vd);
  }

  // the "cost" column
  add_edge(vert[1],  vert[2],  Weight(1), undigraph); // id 1
  // id 2 has -1
  // id 3 has -1
  add_edge(vert[2],  vert[5],  Weight(1), undigraph); // id 4
  add_edge(vert[3],  vert[6],  Weight(1), undigraph); // id 5
  add_edge(vert[7],  vert[8],  Weight(1), undigraph); // id 6
  add_edge(vert[8],  vert[5],  Weight(1), undigraph); // id 7
  add_edge(vert[5],  vert[6],  Weight(1), undigraph); // id 8
  add_edge(vert[6],  vert[9],  Weight(1), undigraph); // id 9
  add_edge(vert[5],  vert[10], Weight(1), undigraph); // id 10
  add_edge(vert[6],  vert[11], Weight(1), undigraph); // id 11
  add_edge(vert[10], vert[11], Weight(1), undigraph); // id 12
  add_edge(vert[11], vert[12], Weight(1), undigraph); // id 13
  add_edge(vert[10], vert[13], Weight(1), undigraph); // id 14
  add_edge(vert[9],  vert[12], Weight(1), undigraph); // id 15
  add_edge(vert[4],  vert[9],  Weight(1), undigraph); // id 16
  add_edge(vert[14], vert[15], Weight(1), undigraph); // id 17
  add_edge(vert[16], vert[17], Weight(1), undigraph); // id 18

  // the "reverse_cost" column
  add_edge(vert[2],  vert[1], Weight(2), undigraph); // id 1
  add_edge(vert[3],  vert[2], Weight(2), undigraph); // id 2
  add_edge(vert[4],  vert[3], Weight(2), undigraph); // id 3
  add_edge(vert[5],  vert[2], Weight(2), undigraph); // id 4
  // id 5 has -1
  add_edge(vert[8],  vert[7], Weight(2), undigraph); // id 6
  add_edge(vert[5],  vert[8], Weight(2), undigraph); // id 7
  add_edge(vert[6],  vert[5], Weight(2), undigraph); // id 8
  add_edge(vert[9],  vert[6], Weight(2), undigraph); // id 9
  add_edge(vert[10], vert[5], Weight(2), undigraph); // id 10
  // id 11 has -1
  // id 12 has -1
  // id 13 has -1
  add_edge(vert[13], vert[10], Weight(2), undigraph); // id 14
  add_edge(vert[12], vert[9],  Weight(2), undigraph); // id 15
  add_edge(vert[9],  vert[4],  Weight(2), undigraph); // id 16
  add_edge(vert[15], vert[14], Weight(2), undigraph); // id 17
  add_edge(vert[17], vert[16], Weight(2), undigraph); // id 18

#if 0
  std::cout << "all edges:\n";
  for (ei = edges(digraph).first; ei!=edges(digraph).second; ++ei) 
    std::cout << ' ' << *ei << get(weight, *ei) <<  std::endl;
  std::cout << std::endl;
#endif

  for (vi = vertices(undigraph).first; vi!=vertices(undigraph).second; ++vi) {
    std::cout << "out_edges(" << *vi << "):";
    for (boost::tie(out, out_end) = out_edges(*vi,undigraph); out != out_end; ++out) {
      std::cout << ' ' << *out << "=" << get(weight, *out);
    }
    std::cout << std::endl;
  }
  std::cout << std::endl;

}

int
main()
{
  typedef property < edge_weight_t, double >Weight;
  typedef adjacency_list < listS, vecS, undirectedS,
    no_property, Weight > UndirectedGraph;
  typedef adjacency_list < listS, vecS, directedS,
    no_property, Weight > DirectedGraph;

  undirected_graph_demo < UndirectedGraph > ();
  directed_graph_demo < DirectedGraph > ();
  simulation_undirected_in_directed_graph < DirectedGraph > ();
  return 0;
}