9
\$\begingroup\$

Problem and goal

Given a large edge list file (such as 2 million nodes, 30 million edges) containing source and destination coordinates, I want to 'convert' them in such a way so that the coordinates start at 0. Hopefully the example will clear this up. My goal is to increase the performance (speed) of my current code.

Example

input_file.txt

54    414
12    54
414   87
20    54
12    3

Output

0    1
2    0
1    3
4    0
2    5

Notice how 54 becomes 0, 414 becomes 1, 12 becomes 2, 87 becomes 3 etc. In other words: if a vertex is re-used like 54, the same coordinate will be used.

My solution

While my solution works fine, it is slow for a large edge list such as: this edge list (or this small one for testing purposes), and I was wondering whether there are areas to improve my code.

Essentially, I am using a dictionary (map) that keeps track of each vertex and its coordinate respectfully. If a vertex is not present in the dictionary, it uses the current coordinate and increments it for any possible new vertex.

Code

#pragma warning (disable : 4996)
#include <iostream>
#include <unordered_map>
#include <iostream>
#include <string>
#include "conio.h"
#include <sstream>
#include <fstream>

using namespace std;

void load_graph_from_edge_list_file_to_coo(vector<int>& , vector<int>&, string);
int add_vertex_as_coordinate(vector<int>&, unordered_map<int, int>&, int, int);

int main() {
    vector<int> source_vertices;
    vector<int> destination_vertices;
    string input_file_path = "C:\\Users\\User\\Desktop\\input_file.txt";
    load_graph_from_edge_list_file_to_coo(source_vertices, destination_vertices, input_file_path);

    return 0;
}

void load_graph_from_edge_list_file_to_coo(vector<int>& source_vertices, vector<int>& destination_vertices, string file_path) {
    unordered_map<int, int> map_from_edge_to_coordinate;
    int current_coordinate = 0;

    std::ifstream infile(file_path);
    string line;
    while (getline(infile, line))
    {
        std::istringstream iss(line);
        int vertex_source, vertex_destination;
        if (!(iss >> vertex_source >> vertex_destination)) { 
            continue; 
        } else {
            current_coordinate = add_vertex_as_coordinate(source_vertices, map_from_edge_to_coordinate, vertex_source, current_coordinate);
            current_coordinate = add_vertex_as_coordinate(destination_vertices, map_from_edge_to_coordinate, vertex_destination, current_coordinate);
        }
    }
    infile.close();

    printf("\nTotal amount of vertices: %d", map_from_edge_to_coordinate.size());
    printf("\nTotal amount of edges: %d", source_vertices.size());
}

int add_vertex_as_coordinate(vector<int>& vertices_type, unordered_map<int, int>& map_from_edge_to_coordinate, int vertex, int coordinate) {
    if (map_from_edge_to_coordinate.count(vertex)) {
        vertices_type.push_back(map_from_edge_to_coordinate.at(vertex));

        return coordinate;
    }
    else {
        map_from_edge_to_coordinate[vertex] = coordinate;
        vertices_type.push_back(coordinate);
        coordinate++;

        return coordinate;
    }
}

Any tips to increase the performance would be greatly appreciated.

\$\endgroup\$
  • 1
    \$\begingroup\$ Given a large edge list file (2 million nodes, 30 million edges) You mean a small to middle sized edge list! :-) \$\endgroup\$ – Martin York May 30 '17 at 18:53
  • \$\begingroup\$ @user2296177 sorry - didn't even thought about that. Here is a smaller one: snap.stanford.edu/data/web-Stanford.txt.gz \$\endgroup\$ – CarrotCake May 30 '17 at 19:03
  • \$\begingroup\$ @LokiAstari Haha true. :) \$\endgroup\$ – CarrotCake May 30 '17 at 19:04
  • \$\begingroup\$ I don't see any output being generated y this code. Nor is there any use for source_vertices and destination_vertices. You can just print the values as you map them (no need to waste space storing them). \$\endgroup\$ – Martin York May 30 '17 at 19:26
  • 3
    \$\begingroup\$ I would describe it as "relabeling the nodes", rather than "changing coordinates to the origin", because the latter is more frequently used with translations, rotations, etc. of 2D, 3D, etc. coordinates. \$\endgroup\$ – Pablo H May 30 '17 at 22:45
3
\$\begingroup\$

I think you overcomplicated your problem. The easy solution that comes to mind (the third attempt I had right now) is to define a struct with a mutable element (The member we want to modify is marked mutable, as elements of a std::set are const qualified):

struct Vertex{
    Vertex(const size_t v) : origIndex(v) {}
    size_t origIndex;
    mutable size_t index;
    bool operator<(const Vertex& other) const {
        return origIndex< other.origIndex;
    }
};

Now you can simply add all the vertices to the set and then change the index afterwards.

Regarding your code, you should definitely put it into a class to better encapsulate it.

class normalizeGraph {
    struct Vertex{
        Vertex(const size_t v) : origIndex(v), index(v) {}
        size_t origIndex;
        mutable size_t index;
        bool operator<(const Vertex& other) const {
            return origIndex< other.origIndex;
        }
    };

private:
    std::set<Vertex> vertices;
    std::vector<std::pair<size_t, size_t>> edges;
}

Note that I have used the ordered versions of the set, as it allows for faster iteration and we get the ordered insertion for free in the set. Your load_graph_from_edge_list_file_to_coo function then becomes the constructor of the class

normalizeGraph(const string& file_path) {
    std::ifstream infile(file_path);
    string line;
    while (getline(infile, line)) {
        std::istringstream iss(line);
        size_t vertex_source; 
        size_t vertex_destination;
        if (!(iss >> vertex_source >> vertex_destination)) { 
            continue; 
        } else {
            vertices.insert(Vertex(vertex_source));
            vertices.insert(Vertex(vertex_destination));
            edges.emplace_back(std::make_pair(vertex_source, vertex_destination));
        }
    }
    infile.close();

    printf("\nTotal amount of vertices: %d", map_from_edge_to_coordinate.size());
    printf("\nTotal amount of edges: %d", source_vertices.size());
}

The rewrite of the vertex index is now a simple loop

void normalizeVertices() {
    size_t newIndex = 0;
    for (auto it = vertices.begin(); it != vertices.end(); ++it) {
        it->index = newIndex++;
    }
}

And rewrite the edges

void normalizeEdges() {
    for (auto&& edge : edges) {
        edge = std::make_pair(vertices[edge.first].index, vertices[edge.second].index);
    }
}

EDIT:

You should obviously follow the suggestion of LokiAstari and optimize the while loop. Also printf is C rather than C++ so use std::cout

Put together this reads:

class normalizeGraph {
    struct Vertex{
        Vertex(const size_t v) : origIndex(v) {}
        size_t origIndex;
        mutable size_t index;
        bool operator<(const Vertex& other) const {
            return origIndex< other.origIndex;
        }
    };

    normalizeGraph(const string& file_path) {
        std::ifstream infile(file_path);
        size_t vertex_source; 
        size_t vertex_destination;
        while (iss >> vertex_source >> vertex_destination) {
            vertices.insert(Vertex(vertex_source));
            vertices.insert(Vertex(vertex_destination));
            edges.emplace_back(std::make_pair(vertex_source, vertex_destination));
        }
        infile.close();

        std::cout << "\nTotal amount of vertices: " << vertices.size();
        std::cout << "\nTotal amount of edges: " << edges.size();
    }

    void normalizeEdges() {
        for (auto&& edge : edges) {
            edge = std::make_pair(vertices[edge.first].index, vertices[edge.second].index);
        }
    }

    void normalizeVertices() {
        size_t newIndex = 0;
        for (auto it = vertices.begin(); it != vertices.end(); ++it) {
            it->index = newIndex++;
        }
    }

private:

    std::set<Vertex> vertices;
    std::vector<std::pair<size_t, size_t>> edges;
}

EDIT2:

The operator[] of a std::set only takes the key as a value. However, one can use find() and overload the comparison operator. The solution is as follows

#include <chrono>
#include <iostream>
#include <fstream>
#include <set>
#include <string>
#include <utility>
#include <vector>

typedef std::chrono::high_resolution_clock::time_point timer;

class normalizeGraph1 {
public:
    struct Vertex{
        Vertex(const size_t v) : origIndex(v) {}
        size_t origIndex;
        mutable size_t index;
        bool operator<(const Vertex& other) const {
            return origIndex< other.origIndex;
        }
    };

    normalizeGraph1(const std::string& file_path) {
        std::ifstream infile(file_path);
        size_t vertex_source;
        size_t vertex_destination;
        while (infile >> vertex_source >> vertex_destination) {
            vertices.insert(Vertex(vertex_source));
            vertices.insert(Vertex(vertex_destination));
            edges.emplace_back(std::make_pair(vertex_source, vertex_destination));
        }
        infile.close();

        std::cout << "Total amount of vertices: " << vertices.size() << "\n";
        std::cout << "Total amount of edges: " << edges.size() << "\n";

        /* Take the time of the simulation */
        timer start = std::chrono::high_resolution_clock::now();
        normalizeVertices();
        normalizeEdges();
        timer end = std::chrono::high_resolution_clock::now();
        double dif = 1E-3*std::chrono::duration_cast<std::chrono::milliseconds>( end - start ).count();
        std::cout << "Normalization took " << dif << " seconds" << "\n";
    }

    void normalizeEdges() {
        for (auto&& edge : edges) {
            edge = std::make_pair(vertices.find(edge.first)->index, vertices.find(edge.second)->index);
        }
    }

    void normalizeVertices() {
        size_t newIndex = 0;
        for (auto it = vertices.begin(); it != vertices.end(); ++it) {
            it->index = newIndex++;
        }
    }

private:
    std::set<Vertex> vertices;
    std::vector<std::pair<size_t, size_t>> edges;
}; 

For the provided sample file this takes 2.6s on my machine. However, there is a much better solution

Solution2

The underlying problem is, that we have to traverse the edges on after of the vertices. This is highly suboptimal, as there are generally many more edges than vertices. The solution is to store the pointer to the vertexIndex in the map rather then the vertexIndex itself

#include <chrono>
#include <iostream>
#include <fstream>
#include <map>
#include <string>
#include <utility>
#include <vector>
class normalizeGraph2 {
public:
    normalizeGraph2(const std::string& file_path) {
        std::ifstream infile(file_path);
        size_t vertex_source;
        size_t vertex_destination;
        while (infile >> vertex_source >> vertex_destination) {
            vertices.emplace(std::make_pair(vertex_source, vertex_source));
            vertices.emplace(std::make_pair(vertex_destination,vertex_destination));
            edges.emplace_back(std::make_pair(&vertices[vertex_source], &vertices[vertex_destination]));
        }
        infile.close();

        std::cout << "Total amount of vertices: " << vertices.size() << "\n";
        std::cout << "Total amount of edges: " << edges.size() << "\n";

        /* Take the time of the simulation */
        timer start = std::chrono::high_resolution_clock::now();
        normalizeVertices();
        timer end = std::chrono::high_resolution_clock::now();
        double dif = 1E-3*std::chrono::duration_cast<std::chrono::milliseconds>( end - start ).count();
        std::cout << "Normalization took " << dif << " seconds" << "\n";
    }

    void normalizeVertices() {
        size_t newIndex = 0;
        for (auto&& vertex : vertices) {
            vertex.second = newIndex++;
        }
    }

private:
    std::map<size_t,size_t> vertices;
    std::vector<std::pair<size_t*, size_t*>> edges;
};

This only takes 0.018s on my machine, which is considerable faster than the other approach. The only caveat is, that you have to dereference the values of the edges.

void printEdges() {
    for (size_t index = 0; index < 10; ++index) {
       std::cout <<  *edges[index].first << "\t" << *edges[index].second << "\n";
    }
}
\$\endgroup\$
  • \$\begingroup\$ Could you clarify why you made index mutable? Just add a small sentence to explain your reasoning. \$\endgroup\$ – yuri May 30 '17 at 21:00
  • \$\begingroup\$ Amazing miscco, truly appreciate it. Will get back to this really soon! \$\endgroup\$ – CarrotCake May 30 '17 at 21:00
  • \$\begingroup\$ @yuri the elements of a set are const qualified, so you can only modify elements of a struct in a set if they are defined as mutable \$\endgroup\$ – miscco May 30 '17 at 21:04
  • \$\begingroup\$ @yuri, elements of set are immutable. Thus, one needs to have mutable on member they want to modify. \$\endgroup\$ – Incomputable May 30 '17 at 21:04
  • \$\begingroup\$ Truly appreciate it, missco. Just a small question (I'm a terrible c/c++ newbie, my apologies): the part of the line vertices[edge.first].indexand vertices[edge.second].index inside the normalizeEdges() function gives me the semantic error: no operator "[]" maches these operands. I tried several ways to fix this, but was unsuccessfull. Not sure whether I might miss an include though for this. Furthermore, I assume that I first have to call normalizeVertices() and then normalizeEdges() correct? Thanks! \$\endgroup\$ – CarrotCake May 31 '17 at 1:07
5
\$\begingroup\$

The only thing I can see that will speed stuff up is this part:

string line;
while (getline(infile, line))
{
    std::istringstream iss(line);
    int vertex_source, vertex_destination;
    if (!(iss >> vertex_source >> vertex_destination)) { 

There is a lot of copying from line to iss. This provides some good error checking and correction ability. But does slow the code down.

Replacing the above with

while (iss >> vertex_source >> vertex_destination)
{

results in a 10% speed improvement in my code (though I took out the vectors; I did not need them).

\$\endgroup\$
3
\$\begingroup\$

You should avoid using namespace std; as it brings in everything declared in that namespace and can lead to collisions.

If you use something from a certain namespace a lot, consider using std::vector; (as an example) instead. Otherwise you can simply qualify something with std::foo as you did in your code with std::ifstream

See these links for a more in-depth explanation

\$\endgroup\$
  • \$\begingroup\$ Thank you, yuri. I'll make sure to think about that in the future! \$\endgroup\$ – CarrotCake May 30 '17 at 19:50
1
\$\begingroup\$

You missed

#include <vector>

I had to add that, and remove the include of "conio.h" (which wasn't provided, but apparently not required). I also removed the second #include <iostream> and the #pragma (you should explain the purpose, in case there's an equivalent for the rest of us).

Having done that (and minor change to read the filename from arguments), I get

Total amount of vertices: 1632803
Total amount of edges: 30622564
29.29user 0.20system 0:29.50elapsed 99%CPU (0avgtext+0avgdata 309840maxresident)k

I get almost exactly the same speed from this simpler version, which acts as a conventional filter, taking input from stdin and writing to stdout:

#include <iostream>
#include <map>
#include <unordered_map>

using label_t = unsigned int;

class Replace
{
    std::unordered_map<label_t,label_t> replacement = {};

public:
    Replace() = default;
    label_t operator[](label_t id)
    {
        auto r = replacement.insert({id, replacement.size()});
        return r.first->second;
    }
};

int main() {
    Replace mapping;

    label_t from, to;
    while (std::cin >> from >> to) {
        from = mapping[from];
        to = mapping[to];
        std::cout << from << "  " << to << "\n";
    }
}

It's not any faster, but it does seem to be clearer. It's possible that the next thing to try is to avoid converting to and from integers when reading and writing the values.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.