1

I am reading in an edge list from a file and trying to make a graph out of it using boost graph library. The final goal is to implement the girvan newman algorithm, but right now I'm just working on getting the graph read in. I read the data in as two unordered maps that are duplicated with switch key and value pairs, that way I can use .find with both the key and value. Here is my code:


#include <iostream>
#include <utility>  //std::pair
#include <algorithm>  //std::for_each
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/small_world_generator.hpp>
#include <boost/random/linear_congruential.hpp>
#include <fstream>

typedef adjacency_list< vecS, vecS, bidirectionalS, no_property,
        property< edge_weight_t, float > >
        Graph_type;
typedef std::pair< int, int > Edge;
typedef typename graph_traits< Graph_type >::vertex_descriptor Vertex;

void readInGraph(){



    ifstream myFile("../data/put_data_here.txt");

    //gets first line and turns it to int
    string x;
    myFile >> x;
    stringstream geek(x);
    int numEdges;
    geek >> numEdges;
    Edge edge_array[numEdges];

 string prev = "prev";
    string line;
    myFile.ignore();
    std::unordered_map<string, int> name;
    std::unordered_map<int, string> inverseName;
    int mapCounter = 0;
    string tempVar;

    //loops through file to store names
    //only loops through first column of edges to minimize lookup time
    while(getline(myFile, line)){
        string delimiter = " ";
        string token = line.substr(0, line.find(delimiter));

        if(token != prev){
            name[token] = mapCounter;
            inverseName[mapCounter] = token;
            mapCounter++;
        }
        prev = token;
    }

    myFile.clear();
    myFile.seekg(0, ios::beg);
    myFile >> tempVar; //gets rid of first line of file
    myFile.ignore();

//    loops through the second column of edges and adds any vertices that weren't
//    previously added to the map
    while(getline(myFile, line)){
        string delimiter = "-";
        string token = line.substr(line.find(delimiter) + 2, string::npos);
        if(name.count(token) == 0){
            name[token] = mapCounter;
            inverseName[mapCounter] = token;
            mapCounter++;
        }
    }

    int numVertices = name.size();
    cout << numVertices;

    //now that all the names are collected we can read in the edge array
    //and store it as the integer mapped to that name in the map

    myFile.clear();
    myFile.seekg(0, ios::beg);
    myFile >> tempVar; //gets rid of first line of file
    myFile.ignore();

        for(int i = 0; i < numEdges; i++){
        string hyphen; //gets rid of hyphen
        myFile >> tempVar;
        edge_array[i].first = name.find(tempVar)->second;
        myFile >> hyphen;
        myFile >> tempVar;
        edge_array[i].second = name.find(tempVar)->second;
    }

 float transmission_delay[] = { 1 }; //no edge weights
    Graph_type newGraph(edge_array, edge_array + numEdges, transmission_delay, numVertices);
    std::for_each(vertices(newGraph).first, vertices(newGraph).second, exercise_vertex< Graph_type >(newGraph, inverseName));

After I read in all the data, I create my Graph g and then call the exercise vertex function that boost graph library uses. In their implementation they use a char* name = "ABCDE" which they can use to get different outputs for each of the gets in exercise vertex. I am wanting to do this with my map, but it is not working.

template < class Graph > struct exercise_vertex
{
    //state vars
    Graph& g;
    //const char* name; this is the from the original code
    std::unordered_map<int, string> inverseName;

    //Constructor
    exercise_vertex(Graph& g_, std::unordered_map<int, string> name_) : g(g_), inverseName(name_) {}
    //exercise_vertex(Graph& g_, const char name_[]) : g(g_), name(name_) {} from the original code

    //vertex descriptor
    typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
    void operator()(const Vertex& v) const
    {
        typename property_map< Graph, vertex_index_t >::type vertex_id
                = get(vertex_index, g);
        std::cout << "vertex: " << get(vertex_id, v) << std::endl;
//std::cout << "vertex: " << name[get(vertex_id, v)] << std::endl; this is from the original code
//std::cout << "vertex: " << inverseName.find(get(vertex_id, v))->second << std::endl; this is what I would want to do but it doesn't work
        // 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 (boost::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 (boost::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 (boost::tie(ai, ai_end) = adjacent_vertices(v, g); ai != ai_end;
             ++ai)
            std::cout << get(vertex_id, *ai) << " ";
        std::cout << std::endl;
    }

};

I have been trying to get this working for a whole day now, and I'm not sure what else to try. I think the problem is with the exercise vertex function because I did some testing in my readInGraph function and was able to list all the edges with their corresponding names. I think it might have to do with how i'm accessing the map. In the original code, in the constructor, there were these brackets that I had to remove to get it to compile and I'm not sure why. I think that might have something to do with my problem, maybe its not actually recognizing name as a map and therefore the .find function is working. My other thought was that the get(vertex_id, v) isnt returning something that is in the map, but if the value could previously be used as an index in the char* name then I figured it should be fine to search my map.

Here is a shortened version of my input file just for reference:

78

C - B

D - B

D - C

E - B

E - C

E - D

sehe
  • 374,641
  • 47
  • 450
  • 633
CrashMan123
  • 57
  • 6

1 Answers1

1

Your initial edge weights

 transmission_delay[] = {1}; // no edge weights

is a single element, so the graph construction invokes Undefined Behaviour.

You need an iterator that is valid for the number of edges. These constructors are a bit "unsafe" in the sense that they use raw iterators and hence they aren't checked. BGL is showing some age there.

Fix that (as well as the C99 variable length array use):¹

std::vector<float> transmission_delay(edge_array.size(),
                                      1.f); // no edge weights

int const numVertices = mappings.size();
return Graph_type(edge_array.data(), edge_array.data() + edge_array.size(),
                  transmission_delay.data(), numVertices);

¹ Okay I did some more review/refactor since the question was deleted for a while.

You don't need the overly generalized "exercise_vertex" - that's for non-vecS cases.

The following simplifies the readInGraph to use a single Bimap for the names, and a single pass through the file to parse, index, and create the edges:

using Graph_type =
    boost::adjacency_list<boost::setS, boost::vecS, boost::bidirectionalS,
                          boost::no_property,
                          boost::property<boost::edge_weight_t, float>>;

using Vertex = typename boost::graph_traits<Graph_type>::vertex_descriptor;
using Edge   = std::pair<Vertex, Vertex>;

Graph_type readInGraph(std::string const& fname, Mappings& mappings) {
    std::ifstream myFile(fname);

    // gets first line and turns it to int
    unsigned numEdges = 0;
    myFile >> numEdges;

    std::vector<Edge> edge_array;

    for (std::string src, hyphen, tgt;
         edge_array.size() < numEdges && myFile >> src >> hyphen >> tgt;) {
        // combined lookup/insert:
        auto s = mappings.insert(Mappings::value_type(src, mappings.size()))
                     .first->get_right();
        auto t = mappings.insert(Mappings::value_type(tgt, mappings.size()))
                     .first->get_right();

        // now that all the names are collected we can read in the edge array
        // and store it as the integer mapped to that name in the map
        edge_array.emplace_back(s, t);
    }

    std::vector<float> transmission_delay(edge_array.size(),
                                          1.f); // no edge weights

    int const numVertices = mappings.size();
    return Graph_type(edge_array.data(), edge_array.data() + edge_array.size(),
                      transmission_delay.data(), numVertices);
}

Notice that we now return the graph, so the main program can be like

Mappings mappings;
auto g = readInGraph("put_data_here.txt", mappings);

auto& invmap = mappings.right;

for (Vertex v : boost::make_iterator_range(vertices(g))) {
    std::cout << "Vertex " << v << " name '" << invmap.at(v) << "':\n";

    for (auto e : boost::make_iterator_range(out_edges(v, g))) {
        auto t = target(e, g);
        std::cout << " - adjacent to " << t << " (" << invmap.at(t) << ")\n";
    }
}

Live Demo

Live On Coliru

Prints

Vertex 0 name 'C':
 - adjacent to 1 (B)
Vertex 1 name 'B':
Vertex 2 name 'D':
 - adjacent to 1 (B)
 - adjacent to 0 (C)
Vertex 3 name 'E':
 - adjacent to 1 (B)
 - adjacent to 0 (C)
 - adjacent to 2 (D)
sehe
  • 374,641
  • 47
  • 450
  • 633