Decorator pattern - how to decorate two types at once

Decorators are implemented using interfaces and delegate methods (not by inheritance).

I think this could be a reason why you're running into a wall. Decorator pattern yields itself nicely in Java by using inheritance and polymorphism. This is a good example of "Programming 'in' a language vs programming 'into' a language".

Your design sounds flawed. Decorators typically "wrap" the class they want to decorate, which is passed into their constructor. Your code should make something like this possible:

Graph myGraph = new BaseGraph();
Graph decoratedGraph = new FlowedGraph(new WeightedGraph(new OrientedGraph(myGraph)));

It seems a mistake to declare the type of decoration that a decorator implements. It also seems wrong for a decorator to know exactly what it is decorating. You can implement a "compound decorator" that relies on other decorator classes to add specific behavior in addition to new behavior that itself provides. Perhaps something like this:

public class FlowEdge implements IEdge // or IFlowEdge
{
    private IEdge decorated;
    private int flow;

    public FlowEdge(IEdge decorated) {
        this.decorated = new WeightedEdge(new OrientedEdge(decorated));
        . . .
    }
}

I let go of this whole decorator idea and implemented the edges just like normal inheritace.

Edge --> WeightedEdge --> OrientedEdge --> FlowEdge

It is maybe not as elegant as using decorations and I cannot now have unweighted oriented edge, but it is straightforward and easy.