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. For example, if the first green edge is visited, all other green edges will be visited as well. Same goes for all other colours.

A test for a potential set would be checking all possible paths from the starting vertex to the end vertex and finding no path that just contains a subset of the proposed set.

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