1
\$\begingroup\$

We are given a vector of std::pair<int, int>s, start int and stop int, and I need to extract the path out of it.

For instance: given start = 2, stop = 8 and list of std::pairs as [(0, 5) (6,8), (5,6), (2,0)]. I am ordering the vector into: [(2,0), (0,5), (5,6), (6,8)]. Now I need to isolate the nodes to get the path as [2,0,5,6,8]. (i.e. (2,0) and (0,5) become [2,0,5] and so on).

I have the following code. It works but I feel that it is needlessly long. Any idea to make it more compact and "safe"?

std::vector<int> get_pretty_path(const std::vector<std::pair<int,int>>& path_arcs, int s, int t){

    std::vector<std::pair<int,int>> ordered_arcs;


    assert(path_arcs.size() > 0);

    int _s = s;
    int _t = t;

    bool l_flag= true;

    std::vector<int> path;

    while (l_flag) {
        for(auto &arc: path_arcs){
            if (arc.first == _s){
                ordered_arcs.push_back(arc);
                _s = arc.second;
                if(arc.second == _t){
                    l_flag = false;
                    break;
                }
            }
        }
    }


    if(ordered_arcs.size() == 1){
        path.push_back(ordered_arcs.begin()->first);
        path.push_back(ordered_arcs.begin()->second);
    }
    else if (ordered_arcs.size() == 2){
        for (auto it = ordered_arcs.begin(); it != ordered_arcs.end()-1; ++it){
            if (it->second == (it+1)->first){
                path.push_back(it->first);
                path.push_back(it->second);
            }

            if((it+1) == ordered_arcs.end()-1){
                path.push_back((it+1)->second);
            }
        }
    }
    else{

        for (auto it = ordered_arcs.begin(); it != ordered_arcs.end()-1; ++it){
            if (it->second == (it+1)->first){
                path.push_back(it->first);
            }
            if((it+1) == ordered_arcs.end()-1){
                path.push_back((it+1)->first);
                path.push_back((it+1)->second);
            }
        }
    }

    return path;
}

This function is called in the order of 10,000 times. I was wondering if it can be as fast as possible. The max length of path_arcs is around 7-8 but is is usually 4-5 or less.

Note that the paths are not weighted. There is only one path. I just need it to be ordered from start to end. Some more examples:

input = [(2,0)] // given by the user
start = 2       // given by the user
stop = 0        // given by the user
output = [2,0]  // This should be the output

input = [(1,4), (2,1)] // given by the user
start = 2              // given by the user
stop = 4               // given by the user
output = [2,1,4]

input = [(4,5),(7,4),(2,3),(5,2)] // given by the user
start = 7                         // given by the user
stop =  3                         // given by the user
output = [7,4,5,2,3]
\$\endgroup\$
6
  • 2
    \$\begingroup\$ You should probably explain what the code is supposed to do. ... The path is [2,0,5,6,8]. Why? \$\endgroup\$
    – super
    Jan 11, 2020 at 9:08
  • \$\begingroup\$ Hello! The start is 2 and the end is 8. so we need to go through each of the arc in the list and get the path. \$\endgroup\$
    – Morpheus
    Jan 11, 2020 at 12:14
  • \$\begingroup\$ The question is better now, but there are still some questions: if the arcs are edges in a (non-weighted?) graph, then which path do you want? Any path, or path with least amount of arcs? It would be great to have a runnable example (something we could paste in e.g. [wandbox.org](wandbox.org) to try out and play with it). Otherwise the question sounds good, just needs a bit more elaboration on the description. \$\endgroup\$ Jan 11, 2020 at 14:12
  • \$\begingroup\$ @Incomputable I added more info. \$\endgroup\$
    – Morpheus
    Jan 11, 2020 at 20:15
  • 2
    \$\begingroup\$ (2,0) and (0,5) become [2,5] - it should become [2,0,5], shouldn't it? \$\endgroup\$
    – vnp
    Jan 11, 2020 at 22:30

1 Answer 1

3
\$\begingroup\$

The key is to create a mapping for the edges:

vector<int>
get_pretty_path(const vector<pair<int,int>>& edges, int s, int t) {
    map<int,int> edgeMap = {begin(edges), end(edges)};
    vector<int> path;
    while (s != t) {
        path.push_back(s);
        s = edgeMap[s];
    }
    path.push_back(s);
    return path;
}
int main() {
    const vector<pair<int,int>> edges{{4, 5}, {7, 4}, {2, 3}, {5, 2}};
    const vector<int> path = get_pretty_path(edges, 7, 3);
    for (auto i : path) {
        cout << i << ' ';
    }
    cout << endl;
    return EXIT_SUCCESS;
}

The code assumes using namespace std; which is sometimes frowned upon but which I think is fine for small examples. The code will bug out if you can't walk from s to t or if more than one edge starts at a given node index. If such situations can happen, you have to decide how to best handle them.

\$\endgroup\$
2
  • \$\begingroup\$ Thanks! I just want to profile it against my implementation as this function is called lot of times. \$\endgroup\$
    – Morpheus
    Jan 12, 2020 at 7:09
  • \$\begingroup\$ You should pass edges by const reference. But this is a clean solution. (I added some consts to your solution; feel free to flag my comment as "no longer needed"). \$\endgroup\$
    – Juho
    Jan 17, 2020 at 18:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.