Traverse MultiMap to Find Path from a Given Value to a Given Key

Question

Details:

I have a multimap implementation that represents the adjacency list for the subset of a graph.

I need to find a path through this subset of the graph, which is actually all the possible paths from a start node F to an end node G, acquired by running a breadth first search on the full graph.

Implementation Ideas:

The BFS quits once G is found, so you end up with G only in the values of the multimap. My idea is that if you start at the value G, get G's "key" (let's call it H), if H == F then we have our path. Else you continue and look for H as a value associated to another key (call it D), if D == F then we have our path... and at this point our path starting from F would look like F -> H -> G

Issues:

Will this scale? Since the map only contains the subset of possible paths from F to G, stopping at G, it shouldn't accidentally make a circular path or make duplicate keys. And if the subset is of cardinality n, then n would be the most amount of values for any given key, and therfore the number of edges you connect can never be more than n.

How Would You Code This??

I can think through the logic and the math involved but I don't understand the map library well enough yet to write it out myself. After reading the c++ reference I get the idea I may use the map methods upper/lowerbound but I can't find an example that supports that.

Answer 1

Turns out to be relatively trivial:

typedef multimap<int, int> MapType;
typedef MapType::const_iterator MapItr;
vector<int> path;

path.push_back(G);

int end = G;                                    // we know G, so mark it
    while ( end != F ) {                        // as long as mark is not F

        // now loop through map searching for value that matches G
        for (MapItr iter = pathMap.begin(); iter != pathMap.end(); iter++)
        {
            if (iter->second == end) {          // once we find our marked value/vertex

                path.push_back(iter->first);    // push it's key onto the vector
                end = iter->first;              // and mark it's key for next iteration
                                                // continue this until end reaches F
            }                                   // at which point will have our path
                                                // from G to F
        }
    }
    // avoid this step by using a container with a push_front method
    reverse(path.begin(), path.end());          // reverse path

Answer 2

You can just loop through the entire map as

C++11

for(const auto& key_val: the_map)
{
  std::cout<<key_val.first<<":"<<key_val.second<<std::endl;
}

Non C++11

for(the_map_type::const_iterator itr = the_map.begin(); itr != the_map.end();++itr)
{
  std::cout<<itr->first<<":"<<itr->second<<std::endl;
}

the_map.lower_bound(key) will give you an iterator to the first element having the key key

the_map.upper_bound(key) will give you an iterator to the element one past any element with key key