lundi 27 avril 2015

Finding cycles in a directed graph implemented using an unordered multimap

So, I've implemented a directed graph using an unordered multimap. Each pair within the map is made up of two strings: the vertex and its adjacent vertex. Now, I am trying to determine if my graph has a cycle, and if so, how big is the cycle. This is the code I have so far:

int findCycle(unordered_multimap<string,string> connectedURLVertices, string y, string key)
{
        string position;

        position=y.find(key);

        if(position!=string::npos)
        {
            return 1;
        }

        auto nodesToCheck=connectedURLVertices.equal_range(key);

        for(auto & node : nodesToCheck)
        {
            int z=findCycle(connectedURLVertices,y+key,node);
        }
}

I've walked through the code on paper and it seems to be logically correct, but I would appreciate it if anyone could take a look and see if I am on the right track or missing anything. Thanks!

Aucun commentaire:

Enregistrer un commentaire