[c++] priority_queue invalid heap debug assertion failed

[rewind.]

Ik ben op het moment bezig met het dijkstra algoritme in c++ en loop tegen een probleem van de priority queue aan.. het algoritme werkt compleet alleen moet ik tijdens het uitvoeren eerst een invalid head debug assertion failed melding negeren.

Het probleem zit in de overloaded operator die op z'n bek gaat op het moment dat ik w->dist wijzig in de code.

C++:

struct CompVertex : public std::binary_function<const Vertex*,const Vertex*, bool>
{
    bool operator()(Vertex * a,Vertex* b)
    {
        return b->dist < a->dist; //kunnen we niet controleren.. invalid heap Debug assertion failed
        //return false;
    }
};


void Graph::dijkstra(string fromId, string toId)
{
    Vertex *vStart = vertexes[fromId];
    Vertex *vEnd = vertexes[toId];
    priority_queue<Vertex *, vector<Vertex*>, CompVertex> q;

    map<const string, Vertex *>::iterator it;
    for( it = vertexes.begin(); it != vertexes.end(); it++ ) 
    {
        Vertex * v = (*it).second;
        v->dist = 1000000;
        v->known = false;
        v->path = NULL;
    }
    vStart->dist = 0;

    q.push(vStart);

    while(!q.empty())
    {
        Vertex *temp = q.top();
        temp->known = true;
        q.pop();
        for(list<Edge *>::iterator it = temp->adj.begin(); it != temp->adj.end(); it++)
        {
            Vertex * w = (*it)->endVertex;
            if(!w->known)
            {
                if((temp->dist + (*it)->weight) < w->dist) 
                {
                    w->dist = temp->dist + (*it)->weight;
                    w->path = temp;
                    //w->known = true;
                    q.push(w);
                    //cout << "top:" << q.top()->id << " ";
                }
            }
        }
    }
    Graph::printPath(toId);
}

het werkt wel op het moment dat ik de priority queue voor het wijzigen geheel controleer op de aanwezigheid van de te bewerken vertex en deze verwijder en later weer toevoeg. Ik vind dit echter geen mooie oplossing en er moet toch een goede zijn?

[farlane]

Lijkt me een typisch geval van een breakpoint zetten en debuggen maar. Je pointer wijst naar een plek waar het niet naartoe mag wijzen bijvoorbeeld doordat het geheugen al is vrijgegeven of nog niet gealloceeerd is.

[Verwijderd]

Dat je een invalid heap assertion error krijgt verbaast me weinig. Je zit namelijk de prioriteiten van je vertices te veranderen terwijl ze al in de priority_queue zitten. En dat werkt niet met std::priority_queue.

De std::priority_queue gebruikt namelijk in de achtergrond een heap. Een heap is een binaire boom met daarbij de heap-order-eigenschap, die zegt dat de waarde (in jouw geval de dist-waarde) van een knoop altijd groter dan of gelijk aan de waarde van zijn ouder is. Als je nu zelf de waarde van een knoop verandert (door dit `stiekem' via een pointer te doen), is het goed mogelijk dat je deze eigenschap breekt en daardoor de heap geen geldige heap meer is. Et voilà: invalid heap assertion.

[rewind.]

Daar was ik achter inderdaad! Ik kan de priority queue eerst overzetten naar een gewone queue behalve het te wijzigen item en deze na de bewerking allemaal weer toevoegen maar er moet toch een mooiere oplossing zijn?

[.oisyn]

Je kunt idd geen willekeurige elementen uit een std::priority_queue verwijderen. Wellicht is een std::multiset een handigere optie, en anders zul je een oplossing buiten standaard C++ moeten zoeken (wellicht heeft boost iets, of je kunt zelf een priority_queue class fabriceren - is niet zo heel erg ingewikkeld).

Verder is het gebruikelijk om in deze tak van de wetenschap over vertices te spreken, en niet over vertexes (hoewel allebei idd correct Engels is)

[ Voor 20% gewijzigd door .oisyn op 11-10-2007 12:03 ]

[Verwijderd]

Daar zijn natuurlijk verschillende manieren voor te verzinnen

Een aardige mogelijkheid is om niet de knopen maar juist de kanten van de graaf in de priority_queue te stoppen. Aangezien je een knoop in de graaf per definitie maar één keer expandeert bij Dijkstra's, hoeft dezelfde kant nooit tweemaal in de queue gestopt te worden. En dan hoef je dus ook niet de prioriteit van een kant aan te passen in de queue, en is priority_queue voldoende.

Dit heeft natuurlijk wel gevolgen voor de complexiteit van je algoritme, bedenk ik me net. Hou dan wel rekening met de complexiteitseisen die aan je implementatie worden gesteld...

edit:
Complexiteitsblurb toegevoegd.

[ Voor 21% gewijzigd door Verwijderd op 11-10-2007 12:07 ]

[rewind.]

wat ik zelf ook al bedacht had was om strings toe te voegen aan de priority queue en deze dan aan de hand van de vertexes map uit te lezen. echter krijg ik de map vertexes niet beschikbaar in de struct