Given the following graph:
With the assumptions below:
- A node on the left is linked to several nodes on the right
- Nodes on the right are paired together: one is black, one is white
- Each pair of nodes on the right can be swapped (black becomes white and white becomes black)
- A node on the left is green if linked to only white or only black; red if linked to two colors.
The idea is to minimize the amount of red nodes, by flipping some black and white nodes. What is the best algorithm to do that?
(I think this problem has something to do with some sort of cycle detection? This problem is probably well-known on some equivalent form.)
Of course it will be often impossible to make all nodes green; here node V can never be (it is linked to B0 and B1). Some cycles also make all green impossible.
Extra question — same as above, but with a weight associated to each edge. Minimize the sum (for each node) of absolutes delta between white and black (difference between the sums of weights for white and black for each left node).
Where does this problem comes from?
A transit network is composed of stops, routes and trips.
- Each trip belongs to one route
- Each trip has one natural direction (0 or 1, inbound/outbound)
- Each trip goes through a list of stops.
- The direction of all trips within a route is arbitrary; so it is possible to invert the direction of all trips of a given route (but all trips together).
If all trips passing through a stop do have the same direction (all 0 or all 1) we can compute a "natural" direction for the stop. Otherwise we cannot. The idea is to flip route trips direction to minimize the number of stops where we cannot compute this "natural" direction.
Here the nodes on the left are stops, pair of nodes on the right routes, with black/white all trips for each route direction.