I have 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. What algorithm could achieve such an annotation?

My approach right now would first find all possible paths through the graph. Then, following every path, I would count how often each edge was visited. The number of visitations would then indicate the different sets of edges. But this would already stop working for a symmetric graph.

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