Custom sort vector of pair based on their values

Question

I have the following vector:

std::vector< std::pair<int, int> > vectorOfPairs

with the following items:

0, 1
0, 2
1, 4
2, 3
3, 4
4, 5
5, 6

I would like to sort them in a way that the second component of every pair is equal to the first component of the nearest pair in the vector, something like this:

0, 1
1, 4
4, 5
5, 6
0, 2
2, 3
3, 4

I don't know if this is clearly enough, I'll append an image that show what I'm trying to do:

I feel that I should use sort with some kind of comparator but I'm lost right here:

std::sort(vectorOfPairs.begin(), vectorOfPairs.end(), MyComparator);

---

bool MyComparator(pair<int, int> a, pair<int, int> b) {
    if(some_kind_of_comparison){
        return true;
    } 
    return false;
}

I'm newbie with c++ and if someone could help me with a pseudo-code of how to do this, I'll be very grateful.

Answer 1

You can think of this problem as a graph problem. Each of your pairs represents an edge in a directed graph. For example, the pair (0, 2) means "there's an edge from node 0 to node 2," and the pair (2, 5) means "there's an edge from node 2 to node 5."

If you think of things this way, a series of edges where the second element of each pair matches the first element of the next pair corresponds to a path in the graph. For example, the sorted ordering you've given has two paths in it: 0 -> 1 -> 4 -> 5 -> 6 and 0 -> 2 -> 3 -> 4. Consequently, the problem you're trying to solve is the following: how do you break the edges in the graph apart into the smallest number of edge-disjoint paths? Once you've solved that, you can then output those paths in any order you'd like to form a sorted ordering along the lines of what you're trying to do.

You can't solve this problem with std::sort. As an example, suppose that you have the edges (0, 1), (0, 2), (2, 3), and (1, 3). In that case, both of these orderings are valid:

(0, 1)          (0, 2)
(1, 3)          (2, 3)
(0, 2)          (0, 1)
(2, 3)          (1, 3)

This is a problem. Because (0, 1) precedes (0, 2) in the first ordering and (0, 2) precedes (0, 1) in the second ordering, the only way the comparator could be a strict weak ordering is if (0, 1) and (0, 2) are incomparable. That means that in any sorted ordering, all the elements between (0, 1) and (0, 2) (inclusive) must also be incomparable because of transitivity of incomparability. In other words, we should be able to take any ordering, permute the elements between (0, 1) and (0, 2) (inclusive), and get back a new ordering. This would mean that this should be a valid ordering, even though it isn't because there's a vastly better solution:

(0, 1)          (0, 1)
(1, 3)   -->    (0, 2)
(0, 2)          (1, 3)
(2, 3)          (2, 3)

So there's no way to solve this using std::sort.

What I'm not sure about is what the best way to solve this is. This seems related to a flow problem, but I'm not sure how to set it up. If I think of anything, I'll update this answer. Thanks for posting something so interesting!