Given many unordered sets of colors, each with a defined start and end node, I want an algorithm that produces a directed graph, where
each set defines one path through the graph, that includes all colors in the set, and starts at the sets start node and ends at its end node
all paths from a start node to an end node in the graph must match one of the sets
An example of a set could be
start: 1
end: 2
must include: red, green, blue
The output graph’s paths’ nodes can be in any order, as long as it starts at the start node of the set and ends at the end node. The graph does not have to be connected, so technically a valid solution would be a graph that has all the paths separated (like in example 3), but this is often not the best solution.
I want the graph to have a minimal possible amount of colored nodes. The amount of edges doesn’t matter.
Examples: Each row at the top of an image is a set, with the start node being the black node on the left, and the end node being the one on the right. The graph at the bottom is the output graph i want the algorithm to output.
in this example, one color is shared between the two paths to make the minimal graph
A case where the paths split and rejoin to get the minimal graph
A case where the color can’t be shared because it would create paths not defined by one of the sets (like 1 -> red -> 2)
It would be great if the algorithm could handle nodes with costs as well. Each color would have a cost, and the minimal graph would be the graph with the smallest sum of costs.