Merging duplicates in different lines of a text file

Question

I have a text file where the first number on a line is a node number for a graph, and the second number is the number of the node that is connected to the first. The third number is the weight of the edge.

Here is a sample case where two of the lines in the file contain 3 and 5 with a weight of .5:

    1 3 0.5
    3 5 0.5
    3 6 0.5
    3 5 0.5
    6 8 0.5
    4 6 1

I would like to be able to merge these into just one line that has the connection for 3 and 5 but update the weight to be the sum of their weights (in this case 1). The duplicate line then should be deleted.

So I want to check for duplicate node pairs, and if I find duplicates sum up the total weight of all of them and then update one line for that pair to have the correct total weight and then delete all the other lines with those nodes.

I have made a struct for Edges:

struct Edge {
    int c1, c2;
    float weight;
};

I have read the file and put them all into this structure:

if (updateGraph.is_open()) {
    string data[3];
    Edge e;

    while (getline(updateGraph, stri)) {
        stringstream in(stri);
        int i = 0;
        while (in.good() && i < 3) {
            in >> data[i];
            i++;
        }
        e.c1 = atoi(data[0].c_str());
        e.c2 = atoi(data[1].c_str());
        e.weight = atof(data[2].c_str());
        cout << e.c1 << " " << e.c2 << " " << e.weight << endl;
    }
}

But now I am not sure how to compare them to see if any of the edges have the same c1 and c2. How would I do that?

Answer 1

I have read the file and put them all into this structure: [...] But now I am not sure how to compare them to see if any of the edges have the same c1 and c2.

Logically speaking, you know that you need to do more than just read the edges and print them out. Your program has to keep some memory of the edges that it has seen so far. It might have to merge an edge from the very first line with the very last line--for example.

How would I do that?

There's no single "right" way to do it. But if you go about trying to make your own class like the Edge struct you defined, then you'll have to write more code. To use a std::set collection you'll need a comparison operator, for instance. (Note that C++ doesn't even provide a default equality operator.)

C++ can do more work for you if you avoid making a custom structure. Instead, you can store your state as a std::map from a std::tuple<int, int> to a float weight. Tuples will already know how to compare to each other. This way of thinking separates the idea of an edge from the idea of weight.

Without writing your code for you, here's a demonstration of the kind of abilities that you are looking for...done the "conventional" C++ way:

#include <iostream>
#include <map>
#include <tuple>

typedef std::tuple<int, int> Edge;
std::map<Edge, float> mapEdgeToWeight;

int main() {
    Edge e1 {3, 5}; float w1 = 0.5;
    Edge e2 {3, 5}; float w2 = 0.5;

    auto it1 = mapEdgeToWeight.find(e1);
    if (it1 != mapEdgeToWeight.end())
        std::cout << "Existing {3, 5} edge (won't happen)\n";
    else {
        std::cout << "First {3, 5} edge (this is first)\n";
        mapEdgeToWeight[e1] = w1;
    }

    auto it2 = mapEdgeToWeight.find(e2);
    if (it2 != mapEdgeToWeight.end()) {
        std::cout << "Existing {3, 5} edge (now happens)\n";
        it2->second += w2; // first is edge, second is weight
    }
    else
        std::cout << "First {3, 5} edge (it isn't first!)\n";

    for (auto &pair : mapEdgeToWeight)
        std::cout << "Edge: "
            << std::get<0>(pair.first) << ","
            << std::get<1>(pair.first)
            << " Weight: " << pair.second << "\n";
}

As was suggested in the comments, you're better off thinking of reading the file in...processing it...and then writing out a new file than to think of "merging lines" in an existing file.

If you're new to C++ there's a vast amount to learn, and coming to StackOverflow with no idea how to write something and asking "how would I do it?" is definitely going to be a rocky approach. I'd suggest getting a strong foundation by working your way through a book on the subject. Even if you're taking a class with its own text, don't be afraid to second-guess it by picking up a good modern one here:

The Definitive C++ Book Guide and List

But now you know at least one place you can start, by looking into tutorials on how to use std::map and std::tuple.