I'm having a hard time explaining my problem, therefore, I've drawn an example directed graph, as you can see below. The edges are annotated with colours. Those colours/annotations would be the output of the process. The input would be the graph without colours.

The goal is to find sets of edges. Each edge in a set has the the following property: if one edge is visited during a graph traversal along the directed edges, it is guaranteed that all other edges in this set will be visited as well. A test for a potential set would be checking all possible paths from the starting vertex to the end vertex and finding none that just contains a subset of the proposed set. If such a set is found, the edges are then annotated, in this example with a unique colour.

What algorithm could achieve such an annotation?

I feel like I'm missing the obvious solution. Could anyone please help?

[![Example Graph][1]][1]


  [1]: https://i.sstatic.net/F8R2P.png