algorithmmathgraphgraph-theorynetwork-flow

# Optimization trading items - min cost max flow

There is `n` items, $&space;i_1,i_2,...,i_n$. I have `n` items, but some duplicates and some are missing, I need to have exactly one of each item. There is given a trade-table that tells which items can be traded for others. For example:

Item Item For
1 2
2 5
4 3

There is infinite stock of trade items in trade-table. But for each trade, you need to pay 1\$.

Now we want to know which items to trade so that in the end we have each item exactly once and we minimize needed trades (cost). And if it's not possible then we should detect that it is not possible.

Example:

$n=4$, we have $&space;i_1=3,i_2=0,i_3=0,i_4=1$ and the trade-table is: $i_1\rightarrow&space;i_2,i_2\rightarrow&space;i_3$. We need to trade 2x i1 to i2 and 1x i2 to i3.

Solve the problem using max flow min cost algorithm. I'm not in particular interested in time complexity.

How do I construct the graph/flow network?

Solution

• How do I construct the graph/flow network?

Such a network needs sources. The sources are the duplicate items. The output from each source has a capacity equal to the number of spares ( count - 1 )

The network needs sinks. The missing items are the sinks. The input to each sink has a capacity if 1

The trade table provides the rest of the links, each with an infinite capacity.

Apply the Edmonds-Karp algorithm to get your answer https://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm Note that is convenient to have just one source and once sink, so connect a common source to all item sources and all the item sinks to a common sink.

The problem is not feasible if the calculated flow into any sink is zero

The total cost is the total calculated flow through the internal links ( all graph links NOT connected to a source or a sink )

FYI here is some C++ code that solves this problem using the above algorithm and the PathFinder graph theory library

Construct the example:

``````void generate1()
{
// initial holding of each item

}
``````

Construct the graph/flow network

``````void cFlowGraph::make()
{
// setup flow graph
gd.g.clear();
gd.g.directed();

int maxLinkCount = cItem::count() * cItem::count();
const int infinite = 2e9;

for (cHold *hold : cHold::get())
{
if (hold->count() > 1)
{
// source
std::string name = "source_" + hold->name();
"all_source",
name);
name,
hold->name());
gd.edgeWeight[ie] = hold->count() - 1;
}
else if (!hold->count())
{
// sink
hold->name(),
"sink_" + hold->name());
gd.edgeWeight[ie] = 1;
"sink_" + hold->name(),
"all_sink");
}
}

{
}
}
``````

Calculate the flows through the graph

``````void cFlowGraph::calculate()
{
gd.startName = "all_source";
gd.endName = "all_sink";

//Apply Edmonds-Karp algorithm using Pathfinder method
flows(
gd,

}
``````

Check feasability:

``````bool cFlowGraph::isFeasible()
{
// check that every flow into an item sink is 1
// meaning that the missing item was found
{
if (flow( link ) != 1)
return false;
}
return true;
}
``````

``````void cFlowGraph::displayTrades()
{
std::cout << "\n";
{
<< " times " << flow( link )
<< "\n";
}
}
``````

Put this all together and the output is

`````` flow 2 in   all_source -> source_1
flow 2 in     source_1 -> 1
flow 2 in            1 -> 2
flow 1 in            2 -> sink_2
flow 1 in            2 -> 3
flow 1 in       sink_2 -> all_sink
flow 1 in            3 -> sink_3
flow 1 in       sink_3 -> all_sink

trade 1 - > 2 times 2
trade 2 - > 3 times 1
``````

The complete application code is at https://github.com/JamesBremner/trader