How to add custom properties to the edges of a grid_graph in Boost Graph Library?

Question

#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <boost/date_time/gregorian/gregorian.hpp>
#include <boost/chrono.hpp>
#include <algorithm>
#include <ctime>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/grid_graph.hpp>
#include <boost/array.hpp>
#include <boost/graph/grid_graph.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/test/unit_test.hpp>
#include <iostream>                  // for std::cout
#include <utility>                   // for std::pair
#include <algorithm>                 // for std::for_each
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#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>
#include <boost/property_map/property_map.hpp>
#include <boost/graph/graphviz.hpp>

using namespace std;
using namespace boost;
using namespace boost::gregorian;


#define DIMENSIONS 2

typedef grid_graph<2> Graph;
typedef graph_traits<Graph> Traits;

// Define a simple function to print vertices
void print_vertex(Traits::vertex_descriptor vertex_to_print) {
    std::cout << "(" << vertex_to_print[0] << ", " << vertex_to_print[1] << ")" << std::endl;
}

int main(int argc, char* argv[]) {

    // Define a 3x5 grid_graph where the second dimension doesn't wrap
//  boost::array<std::size_t, 2> lengths = { { 3, 5 } };
    boost::array<size_t, 2> lengths = { { 3, 5 } };
    Graph graph(lengths);

    // Do a round-trip test of the vertex index functions
    for (Traits::vertices_size_type v_index = 0;
        v_index < num_vertices(graph); ++v_index) {

        // The two indicies should always be equal
        std::cout << "Index of vertex " << v_index << " is " <<
            get(boost::vertex_index, graph, vertex(v_index, graph)) << std::endl;

    }

    // Do a round-trip test of the edge index functions
    for (Traits::edges_size_type e_index = 0;
        e_index < num_edges(graph); ++e_index) {

        // The two indicies should always be equal
        std::cout << "Index of edge " << e_index << " is " <<
            get(boost::edge_index, graph, edge_at(e_index, graph)) << std::endl;
    }


    // Print number of dimensions
    std::cout << graph.dimensions() << std::endl; // prints "3"

                                                  // Print dimension lengths (same order as in the lengths array)
    std::cout << graph.length(0) << "x" << graph.length(1) << std::endl; // prints "3x5x7"


                                                     // Start with the first vertex in the graph
    Traits::vertex_descriptor first_vertex = vertex(0, graph);
    print_vertex(first_vertex); // prints "(0, 0)"

                                // Print the next vertex in dimension 0
    print_vertex(graph.next(first_vertex, 0)); // prints "(1, 0)"

                                               // Print the next vertex in dimension 1
    print_vertex(graph.next(first_vertex, 1)); // prints "(0, 1)"


}

So this is the Grid graph of Boost library. But I dont know how to implement the edges with int weights. What property should I use to do it ? I can traverse the edges and nodes , but only their indecies, not their values.

score 0 · Answer 1 · answered May 06 '17 at 22:46

So, you use the accessors to get the edges by their indices, see e.g.

How to access edge_descriptor with given vertex_descriptor in boost::grid_graph

To also attach properties, see e.g.

Adding custom properties to vertex of a grid in Boost Graph Library

score 0 · Answer 2 · answered May 06 '17 at 22:47

The way to do this is via exterior properties. grid_graph supports the edge_index and vertex_index properties for mapping edge_descriptors and vertex_descriptors to 0-based indices, respectively. To define an exterior edge property map, you can utilize iterator_property_map to combine the grid_graph's edge index property map with a random access iterator.

Here is a complete example:

#include <cstdlib>
#include <iostream>
#include <numeric>
#include <vector>

#include <boost/graph/grid_graph.hpp>
#include <boost/graph/properties.hpp>
#include <boost/graph/write_dimacs.hpp>
#include <boost/property_map/property_map.hpp>

int main() {

  typedef boost::grid_graph<2> Graph;
  typedef boost::graph_traits<Graph> Traits;

  Graph graph {{3, 5}};

  // Create a vector to store the capacity of each edge.
  std::vector<int> capacities(num_edges(graph));
  // Set the edge capacities. Here, we'll just use iota().
  std::iota(capacities.begin(), capacities.end(), 10);

  // Utilize iterator_property_map to make a property map for the edge capacities.
  boost::property_map<Graph, boost::edge_index_t>::type edge_index_map = get(boost::edge_index, graph);
  auto capacities_map = boost::make_iterator_property_map(capacities.begin(), edge_index_map);

  // Select the first and the last vertices as the source and sink nodes, respectively.
  Traits::vertex_descriptor s = vertex(0, graph),
                            t = vertex(num_vertices(graph) - 1, graph);

  boost::write_dimacs_max_flow(
      graph,
      capacities_map,
      get(boost::vertex_index, graph),
      s,
      t,
      std::cout);

  return EXIT_SUCCESS;
}

How to add custom properties to the edges of a grid_graph in Boost Graph Library?

2 Answers2