Return to Revisions

Here are some things that may help you improve your program.

Clarify your specification

In the text, you describe the desired quantity of nodes as "half the amount of coordinates" but what the code actually does is choose half the number of unique edges. There could well be a difference if, say, we had a thousand coordinate pairs that each referred to the same two edges.

Understand standard structures

There is a much simpler way to create your unordered_map that doesn't require any helper function. Because each value is zero initialized, we can rely on this and simplify the code considerably:

std::unordered_map<int, int> node_degree;
for (const auto &coord : coordinates) {
    ++node_degree[coord.x];
    ++node_degree[coord.y];
}

Use appropriate data structures

Your use of an unordered_map is a sound idea, but I'm not so sure about the conversion to a std::vector. It seems to me that a std::priority_queue more directly matches what you're trying to accomplish. Here's the equivalent to your select_coordinates_highest_occurrence (which I find a bit wordy):

void popularEdges(const std::vector<Coordinate> & coordinates) {
    std::unordered_map<int, int> m;
    for (const auto &coord : coordinates) {
        ++m[coord.x];
        ++m[coord.y];
    }
    std::priority_queue<std::pair<int, int>> m2;
    for (const auto &node : m) {
        m2.emplace(node.second, node.first);
    }
    for (auto n=m2.size()/2; n; --n) {
        std::cout << m2.top().second << '\n';
        m2.pop();
    }
}

In my testing on my computer, this version is 25% faster than the original.

Separate I/O from processing

It may depend on your particular needs, but I'd suggest that passing back a vector would be much more generally useful than simply printing from within the function. Similarly, the read_coordinates_into_vector prints the file name back to the user. I'd expect instead that it would be silent. The caller can just as easily print that string if needed.

Make return variables return variables

The read_coordinates_into_vector currently requires the user to pass in a vector, but what would likely make more sense would be to have the code return a newly created vector instead.

Don't use spurious typedef

C++ is not C. The typedef here is not needed:

typedef struct Coordinate { /*...*/ };

because in C++, Coordinate is a proper type without the additional keyword.

Prefer std::istream to file names

The current code for read_coordinates_into_vector is only capable of handing a named file and not, say, a std::stringstream. It could be made more generic and, I think, more durable, if the function prototype were this:

std::vector<Coordinate> read_coordinates_into_vector(std::istream &in);

Use a friend function and custom inserter

Use a friend function and custom inserter to simplify reading coordinates from a file:

struct Coordinate {
    int x;
    int y;
    friend std::istream &operator>>(std::istream &in, Coordinate &c) {
        return in >> c.x >> c.y;
    }
};

std::vector<Coordinate> read(std::istream &in) {
    std::vector<Coordinate> v;
    Coordinate pair;
    while (in >> pair) {
        v.push_back(edge);
    }
    return v;
}