3

I am reading a representation from a file and storing it in an adjacency list. Then I output the graph in "graphviz format" and perform a MST algorithm on the graph. Finally, I output the MST in "graphviz format". I am doing this in C++.

My main question is with the algorithm. I'm implementing Kruskals algorithm and the sort function isn't working.

When i compile it i get this error:

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

Here is my 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;
}
2
  • 1
    Isn't working how? Most SO users aren't going to read through all that code to debug what could be a one-line problem. Commented Nov 11, 2011 at 21:11
  • Please post the whole error message. Commented Nov 11, 2011 at 21:19

1 Answer 1

2

The problem is that the graph that's in scope in the call to kruskals is the global graph, declared as a vector<pair<int,Edges> >. So you can't use EdgeLess to sort it, because EdgeLess compares Edgeses, not pair<int,Edges>es.

Might I suggest that it's needlessly confusing to have a global variable named graph that has type vector<pair<int,Edges> > alongside various local variables named graph that have type vector<pair<Edges> >? If you really need all of these distinct variables, with their current scopes and current types, then you should probably rename the global variable to something that indicates that it's global.

Sign up to request clarification or add additional context in comments.

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.