Troubles with STL list iterators

Question

After a thousand of attempts to Google/bypass that using pointers, I decided myself to post this question to you guys.

Here's the problem: I'm trying to create a minimum spanning tree from a graph that I previously made. I'm using Kruscal's Algorithm for that, which is about checking every arc from the shorter to the longest and taking vertexes that I miss.

To do that, I implemented my graph using a stl::map as an adjaciences matrix. The map is made of the following pair: (double distance, pair-Vertex*, Vertex*- ).

The algorithm requires you to distinguish between a pair you haven't entirely, and one of which you need only one vertex: the former needs you to create another set and you have to gradually connect all of those sets by getting the arcs that connect them (those arcs being of course those having 1 vertex in a set and 1 vertex in another one).

I decided to implement Kruscal this way: my MST (min spanning tree) is a stl::map itself, and so every subset is. They are organized in a list of maps (which I typedef'd map_t): every time I get a node of which I miss 2 vertexes, one tree is added to the list and that node is put into it. The connections will make my MST come into the first node of the list.

Code seems ok to me, but there's no way that list iterators are happy with that. Here's the code:

map_t Grafo::createKruscalMST() {

    mapIterator_t iterator = adjmatrix.begin();
    mapIterator_t end = adjmatrix.end()--;

    list<map_t> MST;
    list<map_t>::iterator listend = MST.end(); // Per puntare alla fine della lista devo fare end()-1 perché end() è il primo dopo la fine

    //MST.resize(1);
    bool zeromatch = true;
    list<map_t>::iterator memo1 = MST.end(); // Valore che non c'è: MST.end() punta al primo elemento dopo la fine della lista
    int common;

    list<map_t>::iterator j = MST.begin();
    MST.resize(1);
    //++j;
    *j = setUnion(*j, iterator); // Inserisco in automatico il primo nodo

    while (iterator != adjmatrix.end() ) 
    {
        ++iterator;
        zeromatch = true;
        memo1 = MST.end();
        for (j = MST.begin(); j != MST.end(); ++j) 
        {
            common = howManyInCommon(*j, iterator);
            if (common == 2) zeromatch = false; 
            if (common == 1) 
            {
                zeromatch = false;
                if (memo1 == MST.end() ) memo1 = j;  // Se nessun altro prima di me aveva 1 e un solo match, mi ricordo della posizione
                else 
                { 
                    *memo1 = treeMerge(*memo1, *j); // Se c'era un altro prima di me, lo copio tutto nel precedente e poi cancello l'altra occorrenza.
                    MST.erase(j);           // Questo farà affiorare l'MST nel nodo di testa, alla lunga.
                    *memo1 = setUnion(*memo1, iterator); // Includo anche il collegamento tra i due semialberi.
                    memo1 = MST.end();  // Fatto ciò, provvedo a resettare l'iteratore di appoggio

                } 
            }
        }
        if (memo1 != MST.end() ) 
            *memo1 = setUnion(*memo1, iterator);
        if (zeromatch == true ) 
        {
            //MST.resize(MST.size()+1);
            //listend = MST.end()--;
            MST.push_back( setUnion(MST.back(), iterator) );
        }
    }
    return MST.front();
}

int howManyInCommon(map_t disjset, mapIterator_t vertexptr) {
int j = 0;  // Parto da 0 e conto direttamente quanti ne ho in comune (molto meglio di una concatenazione di if)
if (vertexptr->second.first->getRepresenter() == disjset.begin()->second.first->getRepresenter() ) 
    j++;
if (vertexptr->second.second->getRepresenter() == disjset.begin()->second.first->getRepresenter() )
    j++;
return j;
}

map_t setUnion(map_t Tree, mapIterator_t i) {
        if (Tree.empty() ) {
        Tree.insert(*i);
        Tree.begin()->second.second->setRepresenter(Tree.begin()->second.first->getRepresenter() ); // Il rappresentante del secondo nodo diventa uguale a quello del primo
    } 
    else {
        i->second.first->setRepresenter(Tree.begin()->second.first->getRepresenter() );
        i->second.second->setRepresenter(Tree.begin()->second.first->getRepresenter() );
        // Nodo della mappa - Nodo con pair <double, pair<Nodo*,Nodo*> - Devo lavorare sul secondo del pair esterno, dunque.
        Tree.insert(*i);
    }
    return Tree;
}

map_t treeMerge(map_t Dest, map_t Source) {
    mapIterator_t srciterator = Source.begin();
    while (srciterator != Source.end() ) {
        Dest = setUnion(Dest, srciterator);
        ++srciterator;
    }
    return Dest;
}

Answer 1

I don't have a direct answer for you, but more a question. Why are you doing this? If to play, I suppose that's fine. If for some application, why not use boost graph, which includes an implementation of Kruscal's Algorithm?

http://www.boost.org/doc/libs/1_43_0/libs/graph/doc/index.html

Granted the documentation for boost graph is sort of weird and learning the library can be a bit tricky, but it's pretty nice once you learn it.

That said the only useful thing I have done with it is write a framework for translating one version of some data to another version. It so happens that the versions are the nodes and the translators themselves are edges. To translate we find a path from one node to another and invoke each translator along the path. Anyway, the code for developing that system was close to trivial using boost graph.

Answer 2

You defined a problem but where is the question?

I don't get why you are doing it in a hard way. Usually you use sorted list of arcs and Union-Find structure to represent trees when implementing Kruskal.

Answer 3

One problem with the current code is that you are essentially dereferencing an end iterator:

list<map_t> MST;
// ...
list<map_t>::iterator j = MST.begin(); // `MST` is empty, so `MST.begin() == MST.end()`.
MST.resize(1);
*j = setUnion(*j, iterator); // oops. `j` still equals `MST.end()`.

Try resizing MST to 1 before setting j to MST.begin().

Another problem is that you likely need to re-read material on how ranges are specified in C++. This line:

mapIterator_t end = adjmatrix.end()--;

is inherently dangerous. Example:

mapIterator_t iterator = adjmatrix.begin(),
    end = adjmatrix.end()--;
for (; iterator != end; ++iterator) { // might not terminate if `iterator == adjmatrix.end()` at the start. Also, the `for` loop body will likely dereference invalid iterators.
}

Answer 4

Hello again guys,

ty for the support =)

@Craig: I'm doing this for a university project, which forces me to stay between the STL boundaries and write everything myself (unfortunately =P ). We might call that 'playing' (I can't say it's got no fun)... But with fire! =D

@Daniel: Gotcha, tho I don't get why I need to pass an end to setUnion: all it's meant to do is to add a single node, setting the representers' pointers while adding. The external "while" (given I set the correct boundaries) should tell setUnion when to stop, shouldn't it?

BTW, may I add another question? The original idea with setUnion was to have it receive pointers and add the node to the pointed tree directly. Even with pointers I wasnt able to make it modify the data, it was still making his own copy, dunno why. I'm not home now, I will paste you the code which used pointers asap