Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /* I need to find the longest depth in a multimap, I've tried everything I know and I'm lost at this point. I'd appreciate any help.
- I have a program that connects 2 people. The connection is saved to a multimap as key value pair. for e.g `add john tim` adds tim as a connection to john, tim can add more people and his connections can add more people.
- I need to find the depth of a person’s subnetwork, that is, the longest recruitment chain starting from this person. For e.g, given the following set of data
- > add john mary
- > add john tom
- > add mary brad
- > add tom Maria
- > add mary Eli
- > add brad Sofia
- `Depth John` should return 4, because the longest chain `John` has is 4.
- `Mary, Brad, sofia, Eli` (4)
- `tom -> Maria` (2)
- and `Depth sofia` will return 1, since she's on her own and doesn't extend to anyone.
- Here's what I've attempted.
- * for each key, find how many exists in the map (using equal_range)
- * then iterate through that and for each of them, count their depth
- * save the depth as the max and compare it after each iteration and return the max
- Here is the code. */
- void count_depth_recursive(std::multimap<std::string, std::string>networkMap, std::string id, int& depth)
- {
- auto range = networkMap.equal_range(id);
- for(auto it = range.first; it != range.second; ++it)
- {
- ++depth;
- std::cout << it->second << std::endl;
- count_depth_recursive(networkMap, it->second, depth);
- }
- }
- Driver function.
- int count_depth(std::multimap<std::string, std::string>networkMap, std::string id)
- {
- int depth = 0;
- int max = 0;
- if(networkMap.count(id) == 0)
- {
- return 1;
- }
- auto find = networkMap.equal_range(id);
- for(auto itr = find.first; itr != find.second; ++itr)
- {
- std::cout << "id is " << itr->first <<" passing in: " << itr->second << std::endl;
- count_depth_recursive(networkMap, itr->first, depth);
- if(depth > max)
- {
- max = depth;
- depth = 0;
- }
- std::cout << "**************************************************************" << std::endl;
- }
- return max;
- }
- I've been at it for ages now, I can't seem to figure out why it's not working.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement