views:

152

answers:

3

Hello guys, I'm near the end of a program I had got to code for my university courses, but I got into a last trouble: formatting the output!

It's nothing about code: this is just cosmetics (but I need to fix that cause my output's got to respect some standards).

Basically, my program will read a .csv file and process that by dividing the resulting graph into clusters. I want to have them numbered, no matter how (I don't care if it starts with 2 instead of 1 as long as the numbers are correct ofc). Problem is I can't figure out how to do that O-o

I've already got a proper data structure to handle my clustering activity: every node of the graph points to some list. If I have n clusters, I'll have n lists. The lists are instanced inside the Vertex class and the algorithm will merge them during runtime, so I can't number them as simply as I would, were they in a vector or something.

So now I have, say, n lists. I can start easily by looking at the 1st vertex (they're in the vector V) and following the pointer. After doing that, I'm in the first list. I can move on it and get every node it points to that list, and I'd want my program to put a "1" on that inside the map. Then I'd look inside V for another vertex whose list is different from before, and again get to the list and save the nodes with "2" and so on.

My counter doesn't work properly: asking for 3 clusters on a .csv file, the output was like this:

c 1 1
c 2 1
c 3 1
c 4 1
c 5 1
c 6 5
c 7 1
c 8 1
c 9 1
c 10 1
c 11 1
c 12 5
c 13 5
c 14 1
c 15 1
c 16 1
c 17 1
c 18 17
c 19 17
c 20 17
c 21 17
c 22 5
c 23 17
c 24 17
c 25 17
c 26 17
c 27 17
c 28 17
c 29 17
c 30 17
c 31 5
c 32 5

Clusters labels are 1, 5, 17 instead of 1, 2, 3 lol U_U

Here's the code:

map<int, int> clusterProcessor(Grafo &G, map_t &Map, int clusters, vector<Vertex*> &V {
 map<int, int> clustermap;
 list<Vertex*>::iterator listiter;
 int j;
 int counter = 1;
 for (j=1; j < V.size() ; ++j) {
   if (V[j]->getMyset()->front() != V[j-1]->getMyset()->front() ) counter++;

   for (listiter = V[j]->getMyset()->begin(); listiter !=  V[j]->getMyset()->end(); listiter++)
     {
       clustermap.insert(pair<int, int> ( (*listiter)->id, counter) );
     }
    }
 return clustermap;
 }

void clusterPrinter(map<int, int> m) {
  map<int, int>::iterator i;
  for (i = m.begin() ; i != m.end() ; i++)
  cout << "c " << i->first << " " << i->second << endl;
  }
+1  A: 

Just try to renumber your verticies as you output them. Keep a map of verticies that you've seen before and what their new numbers are. Before you print a vertex number, if you've seen it before, just print the new number you already gave it. If it's a new verted, assign it a new number, record that in your map, and use its new number.

Karmastan
A: 

Ok, got something better. Instead of having another map, I just kept a vector of bool assigned to that.

It's working perfectly, tho I still have a micro bug I can't get rid of. I'll paste you the code and the output(s).

Code:

map<int, int> clusterProcessor(Grafo &G, map_t &Map, int clusters, vector<Vertex*> &V) {
map<int, int> clustermap;
list<Vertex*>::iterator listiter;
int j;
int counter = 1;
vector<bool> checkvertex(V.size(), false); // Got 1 bool per each vertex. When I visit it, it'll be set "true".
for (j=1; j < V.size() ; ++j) {
    //if (V[j]->getMyset()->front() != V[j-1]->getMyset()->front() ) count++;
        if (checkvertex[j] == false) {
            for (listiter = V[j]->getMyset()->begin(); listiter != V[j]->getMyset()->end(); listiter++)
            {
                clustermap.insert(pair<int, int> ( (*listiter)->id, counter) );
                checkvertex[(*listiter)->id-1] = true;
            }
        counter++;
        }
}
return clustermap;
}

Output: c 1 1 c 2 1 c 3 1 c 4 1 c 5 1 c 6 2 c 7 1 c 8 1 c 9 1 c 10 1 c 11 1 c 12 2 c 13 2 c 14 1 c 15 1 c 16 1 c 17 1 c 18 3 c 19 3 c 20 3 c 21 3 c 22 2 c 23 3 c 24 3 c 25 3 c 26 3 c 27 3 c 28 3 c 29 3 c 30 3 c 31 2 c 32 2

That's what I wanted, but I tried to check it at its limits. That's what happens when I ask him 32 clusters: the first vertex just disappears! O.o

c 2 1 c 3 2 c 4 3 c 5 4 c 6 5 c 7 6 c 8 7 c 9 8 c 10 9 c 11 10 c 12 11 c 13 12 c 14 13 c 15 14 c 16 15 c 17 16 c 18 17 c 19 18 c 20 19 c 21 20 c 22 21 c 23 22 c 24 23 c 25 24 c 26 25 c 27 26 c 28 27 c 29 28 c 30 29 c 31 30 c 32 31

Fun fact is that it won't happen only at its limit: for this file, it will happen for any number greater than 13 (13 is still fine).

Davide
Got that to work finally! :Dj was starting from 1! (Didn't edit in the passage between first vesion and new one). Everything's ok with j starting from 0 =)
Davide
+1  A: 

Notice that the number is always the row number of the row right before it appears. This suggests that counter++ is always executing.

And sure enough, it is.

Perhaps you meant to compare the values of the first elements of each cluster, instead of the iterator addresses?

Based on the subsequent mapping you establish, I'd suggest changing

if (V[j]->getMyset()->front() != V[j-1]->getMyset()->front() ) counter++;

to

if (V[j]->getMyset()->begin()->id != V[j-1]->getMyset()->begin()->id) counter++;
Ben Voigt
Uhm tried that, but it won't work.Output is just the same :((I had to edit it like this cause I've got pointers even in the list):if ( (*V[j]->getMyset()->begin())->id != (*V[j-1]->getMyset()->begin())->id ) counter++;I followed Karmastan's advice and got a good result, but it's got its flaws aswell >_>
Davide