Algorithme de Kruskal (tri)

Question

Je lis une représentation d'un fichier et la stocke dans une liste d'adjacence. Ensuite, je génère le graphique en "format graphviz" et effectuer un algorithme MST sur le graphique. Enfin, je génère le MST en "format graphviz". Je fais cela en C++.

Ma question principale est avec l'algorithme. J'implémente l'algorithme de Kruskals et la fonction de tri ne fonctionne pas.

Quand je compile ce que je reçois cette erreur:

instantiated from ‘void std::sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator*, std::vector, std::allocator > > >, _Compare = bool (*)(Edges, Edges)]’

Voici mon code:

#include <iostream> 
#include <iomanip> 
#include <fstream> 
#include <map> 
#include <vector> 
#include <algorithm> 
#include <cstdlib> 
#include <utility> 


using namespace std; 


#define egdes pair<int ,int > 
#define MAX 9 

struct Edges 
{ 
    int weight; 
    int first,second; 
    char begin,end; 
}; 

    bool EdgeLess(Edges oneE,Edges twoE) 
    { 
     return oneE.weight < twoE.weight; 
    } 

vector<pair<int ,Edges > > graph,MST; 
int parent[MAX],total ; 


bool openInputFile(ifstream &inFile,char* argv); 
bool openOutputFile(ofstream &outFile,char* argv); 
void readInputFile(ifstream &inFile,vector<Edges> &graph); 
int findSet(int x,int *parent); 
void kruskals(); 
void makeSet(); 
bool compareEdgW(Edges oneE,Edges twoE); 

int main (int argc,char **argv) 
{ 

    ifstream inFile; 
    ofstream outFile; 
    int u,v,w; 
    int nodeCount; 
    int edgeCount; 
    char nodeName; 
    Edges edge; 

    vector<Edges> graph; 

     cout<<"hey"<<endl; 
if(openInputFile(inFile,argv[1]) && openOutputFile(outFile,argv[2])) 
    { 
     readInputFile(inFile,graph); 

     outFile.close(); 
    } 

    inFile >> nodeCount; 
    inFile >> edgeCount; 

    for(int i = 0;i < edgeCount; i++) 
    { 
     cin >> u >> v >> w ; 
//  graph.push_back(pair<int ,Edges >(w,edges(u,v))); 
     graph.push_back(edge); 
    } 

    kruskals(); 

    makeSet(); 
    return 0; 
} 


bool openInputFile(ifstream &inFile,char* argv) 
{ 
    inFile.open("input.txt"); 
    if(!inFile) 
    { 
     cout<<"Oops!Input file did not open.\n"; 
     cout<<"Terminating the program.\n"; 
     return false; 
    } 
    return true; 
} 
bool openOutputFile(ofstream &outFile,char* argv) 
{ 
    outFile.open("output.gv"); 
    if(!outFile) 
    { 
     cout<<"Hey!Oops!Input file did not open.\n"; 
     cout<<"Terminating the program.\n"; 
     return false; 
    } 
    return true; 
} 
void readInputFile(ifstream &inFile,vector<Edges> &graph) 
{ 
    int nodeCount; 
    Edges edge; 

    inFile >>nodeCount; 

    char nodeName; 

    for (int i = 0;i < nodeCount;i++) 
    { 
     inFile >> nodeName; 
//  graph.insert(make_pair(nodeName,vector<Edges>())); 

    } 
    int edgeCount; 
    inFile >> edgeCount; 

    for (int i = 0;i < edgeCount;i++) 
    { 
    //  inFile >>nodeName; 
     Edges edge; 
     inFile >> edge.begin; 
     inFile >> edge.weight; 
     inFile >> edge.end; 
     graph.push_back(edge); 

    } 

} 
int findSet(int x,int *parent) 
{ 
    if(x != parent[x]) 
     parent [x] = findSet(parent[x],parent); 
    return parent[x]; 

} 

void kruskals() 
{ 
    int pu; 
    int pv; 
    int edgeCount; 

    sort(graph.begin(),graph.end(),EdgeLess); 
    for (int i = 0;i < edgeCount; i++) 
    { 
     pu = findSet(graph[i].second.first,parent); 
     pv = findSet(graph[i].second.second,parent); 
     if(pu != pv) 
     { 
      MST.push_back(graph[i]); 
      total += graph[i].first; 
      parent[pu] = parent[pv]; 
     } 
    } 
} 
void makeSet() 
{ 
    unsigned long sizeNum; 
    sizeNum = MST.size(); 
    for(int i = 0;i < sizeNum;i++) 
    { 
     cout<< MST[i].second.first <<endl; 
     cout<< MST[i].second.second <<endl; 
     cout<< MST[i].first <<endl; 
    } 
     cout << total <<endl; 
} 

Answer 1

Le problème est que le qui est portée dans l'appel à kruskals est le mondial , déclaré comme vector<pair<int,Edges> >. Donc, vous ne pouvez pas utiliser EdgeLess pour le trier, car EdgeLess compare Edges es, pas pair<int,Edges> es.

Puis-je suggérer qu'il est déroutant inutilement d'avoir une variable globale nommée qui est de type vector<pair<int,Edges> > à côté diverses variables locales nommées qui ont le même type vector<pair<Edges> >? Si a vraiment besoin de toutes ces variables distinctes, avec leurs étendues actuelles et types courants, alors vous devriez probablement renommer la variable globale en quelque chose qui indique qu'elle est globale.