Composition over inheritance when dealing with relationships

Note: I am not sure of the correct terminology for what I am describing, so if you have suggestions for a better title please feel free to edit it.

Composition over inheritance is generally a good rule to follow, but there are some cases where inheritance is a must, like in the following case:

Node a = ...
Node b = ...
List<Node> path = GraphUtil.shortestPath(a,b);

Here we have a hypothetical graph library that provides some nice functionality for us, but we would like to augment it with some extra properties, like color or something. If we use inheritance, our code can be like this:

MyNode a = ...
MyNode b = ...
List<MyNode> path = (List<MyNode>)GraphUtil.shortestPath(a,b);
// highlight the path:
for (MyNode n : path) { path.setColor("green"); }

This is still not totally amazing due to a runtime cast, but it gets the job done.

However, if we were to use composition, this won’t work at all. We would need some kind of external map in order to achieve this (in C++ maybe some pointer hackery).

The question is: are there any existing strategies to achieve this behavior via composition?

Of course the obvious answer is “just use inheritance”, but if the Node class is made by a factory or is otherwise inconvenient to inherit from, what are the alternatives? Obviously a map is one option, but that is very inconvenient and messy, and not to mention slow.