hello there
let me explain my work
i have a file i read from it the data
after that i try to get the best vertex that it's max(degree/weight)
when i find it i put it's neighbors into the glist and i put it into blist and delete both of it and
the neighbors from the wlist
here's the code i added comments to make it understandable
but when i compile it keeps displaying the same value of the best vertex with non stop
i really need help

#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <stdlib.h>

using namespace std;

int main(int argc, char **argv) {
//////////////////// reading file///////////////////////
    ifstream inFile;
    inFile.open("Problem1.dat_50_50_0",std::ifstream::in);

    if ( !inFile ) {
        cout << "file could not be opened !" << endl;
        exit(-1);
    }

    string line;
    int n, value;
    vector<int> weight;

    inFile >> n;

    for ( int i = 0; i < n; ++i)
        if ( inFile >> value )
            weight.push_back(value);

    vector<vector<int> > matrix(n , vector<int>(n));
    vector<vector<int> > adj(n);
    vector<int> degree;
    vector<char> color (n , 'w');
    list<int> wlist;
    list<int> glist;
    list<int> blist;

    cout << "color elements test: \n";
    for (int i = 0; i < n; ++i) {
        cout << color.at(i) << ", ";
    }

    cout << "the weights are: \n";
    for (int i = 0; i < n; ++i) {
        cout << weight.at(i) << ", ";
    }

    cout << endl;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            inFile >> value;
            matrix.at(i).at(j) = value;
            if (i == j)
                matrix[i][j] = 0;
            if (value == 1)
                adj.at(i).push_back(j);
        }
        degree.push_back(adj[i].size());    
    }


    cout << "the neighbor of each elemnt are: \n";
    for (int i = 0; i < adj.size(); ++i) {
        cout << "[" << i << "]: ";
        for (int j = 0; j < adj.at(i).size(); ++j) {
            cout << adj.at(i).at(j) << ",";
        }
        cout << endl;
    }
    cout << "the degree are: \n";
    for (int i = 0; i < n; ++i) {
        cout << degree.at(i) << ", ";
    }

   for( int i=0; i < n; i++ ) {
       wlist.push_back(i);
   }
        cout << "\n white list elements are: \n" ;
   for(list<int>::iterator theIterator = wlist.begin(); theIterator != wlist.end(); theIterator++ ) {
     cout << *theIterator << " ";
   }


//////////////////// greedy heuristic algorithm ///////////////////////

    cout << " \n i'm here\n" ;
    int cd;
    int best_vertex = -1;
    double bval;
    double nval;

    while(! wlist.empty()){
    for(list<int>::iterator it = wlist.begin(); it != wlist.end(); it++)
    {
        cd = degree[*it]; 
        nval = (double) cd / (double) weight[*it];
        if (best_vertex == -1)
        {
            bval = nval;
            best_vertex = *it;
        }
        else
            if(nval > bval)
            {
                bval = nval;
                best_vertex = *it;
            }
    }
    // check if the best vertex is in the glist
    for(list<int>::iterator it = glist.begin(); it != glist.end(); it++)
    {
        cd = degree[*it]; 
        nval = (double) cd / (double) weight[*it];
            if(nval > bval)
            {
                bval = nval;
                best_vertex = *it;
            }
    }
    degree[best_vertex] = 0; // while the best vertex is chosen change it dgree to 0
    cout <<"the chosen vertex in this iteration is :" << best_vertex << "\n" ;
    //add neighbors to glist 
    for(vector<int>::iterator it = adj[best_vertex].begin(); it != adj[best_vertex].end(); it++)
    {
        if(color.at(*it) == 'w')
        {
            wlist.remove(*it);
            color.at(*it) = 'g';
            glist.push_back(*it);
        }
    }
    //delete gray vertices that hv no white neighbors  
    for(list<int>::iterator it = glist.begin(); it != glist.end(); it++)
    {
        if (degree.at(*it) == 0)
        {
            it = glist.erase(it);
        }
    }
    // add best_vertex to blist 
    if (color.at(best_vertex) == 'w')
        wlist.remove(best_vertex);
    else
        glist.remove(best_vertex);
    blist.push_back(best_vertex);
    color.at(best_vertex) = 'b';    
    }

   cin.ignore();
    return 0;
}

Recommended Answers

All 4 Replies

Given that the loop will run forever if wlist is never empty, and it runs forever, I'd guess that wlist never empties.

yeah but this loop it remove some of the nodes from wlist

 for(vector<int>::iterator it = adj[best_vertex].begin(); it != adj[best_vertex].end(); it++)
{
if(color.at(*it) == 'w')
{
wlist.remove(*it);
color.at(*it) = 'g';
glist.push_back(*it);
}
}

and i tested to see if it really removes them and yeah it removes them the pb here i guess that the iterator it this loop

for(list<int>::iterator it = wlist.begin(); it != wlist.end(); it++)

never get incremented :(

Stop guessing. How do you know that wlist is being emptied? You don't. So put some print lining in to find out. Have it print out the size of wlist at the start of every loop. Put a line in to tell you when it's removing something from wlist. Check the size of wlist before and after it should have removed something.

You guess that the iterator never gets incremented? Why are you guessing? Stop guessing. Print out the contents of the iterator every time it should have incremented and see if it changes. You have complete power to investigate every line of your code and in doing so find out what your mistakes are. Don't guess. Know.

Once you get sick of adding lines to your code to print out variables, learn how to use the debugger and you can then pause your code while it's running, at any line, and investigate the values in the live, running code as it happens.

i find out the solution thx Moschops
the solution is the bval must return to 0 after each iteration :)

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.