Algorithm for searching the disjoint union on dependency graph

Question

First of all, some context about the problem:

I´m working in a system that has several types of resources (A, B, C...). I am given some resources requirements and I need to determine if I can afford them.

For this, I have some sources, each one can provide more than one type of resource, but I need to choose wich of them I am using for each resource.

For example, if I need to pay 1A, 2B and 0C (represented as (1,2,0)) and I have this sources:

1. (1,1,0) //Means I must choose produce A or B
2. (0,1,1) //Means I must choose produce B or C
3. (1,1,0)

It is obvius that I must use source 2 for resource B and I can choose for 1 and 3 wich one produces A and B

My approach to implement this is to view it as a dependence graph where the situation above is represented like this:

So I loop over the resources, and for every resource I loop over the links reaching it. If removing the current node for the current resource means the other resources have enought remaining reaching links to pay the remaining cost to pay, I use it.

For the previous example, I try first to use source 1 for resource A. B still has 2 links, so i can do it. Only type B resources are left to pay, so I use the remaing sources to pay B.

All right up here, but now I need to work in a new scenario, where have two types of source, each one producing one type of resource at cost 1 or cost 2, and I need to minimize the total cost.

A slight change over the example can be this:

The common sense solution should be use 1 and 2 to pay B, and use 3 to pay A for a total cost of 1, but with my implementation, as described above, source 1 is used to pay A because B has still 2 links to it, so at the end i have to use source 3 with a cost of 2.

Solutions implying trying all choice combinations should be avoided if possible.

Do you know about any general algorithmic problem with known solution that can be applied to this case? Or how to improve my actual solution to work in this new scenario? Or should I take another different approach?

Answer 1

This problem reduces to finding a maximum flow in a flow network.

Here's the idea:

1. For each type of resource (A, B, ...) a node with an incoming edge from the source node (the source node has nothing to do with the sources from the problem, it's a common label used in network flow theory, usually marked s) with capacity equal to the required quantity of the given resource. For example if you need 2B, the capacity would be 2.

2. For each source (by this I mean a source as defined by the problem description), you create a node with an outgoing edge to the sink (usually marked t) with capacity 1.

3. From each node from step 1. add an outgoing edge to each of the nodes from step 2. that provide that can provide the required type of resource.

For example, the graph for your situation would look like this:

Now a maximal S-T flow in this network will give you the answer. Basically saturated edges between the type nodes (A, B, C) and the source nodes (src1, src2, src3) will tell you which source should supply which type of resource.

The maximum flow can be found using any of the classical algorithms, such as augmenting path (Ford-Fulkerson, Dinic's, etc.) or one of the push-relabel methods (Goldberg-Tarjan, Relabel-to-Front, etc.).

This particular application of maximum flow can also be viewed as a sort of generalized bipartite matching, where you're matching each type of resource to possibly multiple sources, but each source can handle only one resource. The idea is easily extended to the case where a source may handle more than one type (by simply changing the src - T edge capacities from 1 to the ones desired).