Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- int path_between_two_nodes(const std::string& first, const std::string& second)
- {
- // first find both nodes
- planet* first_p = nullptr;
- planet* second_p = nullptr;
- std::stack<planet*> stack;
- for (auto& i : branches)
- stack.push(i.get());
- while (!stack.empty())
- {
- auto current_branch = stack.top();
- stack.pop();
- for (auto& i : current_branch->get_childs())
- {
- stack.push(i.get());
- }
- if (current_branch->name == first)
- {
- first_p = current_branch;
- }
- if (current_branch->name == second)
- {
- second_p = current_branch;
- }
- }
- // done
- // now find find the path to COM from both
- std::vector<planet*> first_path;
- auto temp = first_p;
- while (temp != nullptr)
- {
- first_path.push_back(temp);
- temp = temp->parent;
- }
- std::vector<planet*> second_path;
- temp = second_p;
- while (temp != nullptr)
- {
- second_path.push_back(temp);
- temp = temp->parent;
- }
- // done
- // now find the first same node
- planet* first_intersection = nullptr;
- std::reverse(first_path.begin(), first_path.end());
- std::reverse(second_path.begin(), second_path.end());
- for (auto i = first_path.begin(); i < first_path.end(); ++i)
- {
- for (auto j = second_path.begin(); j < second_path.end(); ++j)
- {
- if (*i == *j)
- first_intersection = *i;
- }
- }
- std::reverse(first_path.begin(), first_path.end());
- std::reverse(second_path.begin(), second_path.end());
- int ctr1 = 0;
- for (auto& e : first_path)
- {
- if (e == first_intersection)
- {
- ++ctr1;
- break;
- }
- ++ctr1;
- }
- int ctr2 = 0;
- for (auto& e : second_path)
- {
- if (e == first_intersection)
- {
- ++ctr2;
- break;
- }
- ++ctr2;
- }
- std::cout << ctr1 << " " << ctr2 << std::endl;
- return ctr1 + ctr2 - 4;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement