Getting a path from list of arcs in C++

Question

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]

Answer 1

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.