Getting a path from list of arcs in C++

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]

• You should probably explain what the code is supposed to do. ... The path is [2,0,5,6,8]. Why? Jan 11, 2020 at 9:08
• 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. Jan 11, 2020 at 12:14
• 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. Jan 11, 2020 at 14:12
• (2,0) and (0,5) become [2,5] - it should become [2,0,5], shouldn't it?
– vnp
Jan 11, 2020 at 22:30

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.

• Thanks! I just want to profile it against my implementation as this function is called lot of times. Jan 12, 2020 at 7:09
• 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").
– Juho
Jan 17, 2020 at 18:26