find if a structure already exists in a vector c++

Question

I have to find the weight between all edges in a graph, so since the edges are bidirectional I dont want to include 2 -> 1 if I already have 1 -> 2 (since they will have the same weight). The edges are stored in a vector from structure Edge. My initial idea was to look up, if an edge that has the start and end positions swapped and has the same weight already exists, and if this is the case, just dont do anything. However, I dont exactly know how to put it into code, so any help would be appreciated. Also any approaches that could optimise the solution are also welcome.

struct Vertex {
    Vertex(const int i = 0) : index {i}, key {max_key}, parent_index {undef}, processed {false} {}

    int index;        // vertex identifier
    int key;          // temporary minimal weight (Prim algorithm)
    int parent_index; // temporary minimal distance neighboor vertex (Prim algorithm)
    int processed;    // flag used to mark vertices that are already included in V'

    static constexpr int max_key = std::numeric_limits<int>::max();
    static const int undef = -1;
};

struct Edge {
    Edge(int va, int vb, int w) : vi1 {va}, vi2 {vb}, weight {w} { }

    int vi1;    //start point
    int vi2;    //end point 
    int weight;
};

struct Graph {
    int N;                    // number of vertices
    std::vector<Vertex> V;    // set of vertices
    std::vector<Edge> E;      // set of edges
    std::vector<Edge> MST;    // minimal spanning tree
    const int* weights_table; // weights given as distance matrix
};

The problem is here in find I know this is a lot of irrelevant code, but I post it so that you can picture it more clearly. If there is no connection between 2 vertices they have weight of -1

// construct vertices and edges for a given graph
void createGraph(Graph& G) {
    // TODO 5.1a: clear V and E and insert all vertex objects and edge objects
    // - vertices are numbered (labeled) from 0 to N-1
    // - edges exist if and only if there is positive distance between two vertices
    // - edges are bidirectional, that is, edges are inserted only once between two vertices
    G.E.clear();
    G.V.clear();

    for(int i = 0; i < G.N; i++){
        Vertex V (i);
        G.V.push_back(V);
    }
  
    for(int i = 0; i < G.N; i++){
        for(int j = 0; j < G.N; j++){
            Edge Ed (i,j,0);
            int weight = getWeight(G,i,j);
            if(weight > 0){
                Ed.weight = weight;
                auto it = find(G.E.begin(), G.E.end(), ....);
                if( it != G.E.end() ) continue;
                G.E.push_back(Ed);
            }
        }
    }
}

Thanks!

Answer 1

since the edges are bidirectional

You can construct Edges such that v1 <= v2, then there is only one representation of each possible edge.

struct Edge {
    Edge(int va, int vb, int w) : vi1 {std::min(va, vb)}, vi2 {std::max(va, vb)}, weight {w} { }

    int vi1;    // earlier point
    int vi2;    // later point
    int weight;
};

Aside: prefer constructing the Edge in place

for(int i = 0; i < G.N; i++){
    for(int j = G.N - 1; j >= 0 + i; j--){
        int weight = getWeight(G,i,j);
        if(weight > 0){
            G.E.emplace_back(i, j, weight);
        }
    }
}