algorithmmathgraphgraph-theorynetwork-flow# Optimization trading items - min cost max flow

There is `n`

items, . 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:

, we have and the trade-table is: . 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.

So, for your example,

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
cHold::add("1", 3);
cHold::add("2", 0);
cHold::add("3", 0);
cHold::add("4", 1);
// possible trades
cTrade::add("2", "1");
cTrade::add("3", "2");
}
```

Construct the graph/flow network

```
void cFlowGraph::make()
{
// setup flow graph
gd.g.clear();
gd.g.directed();
// setup link capacity storage
int maxLinkCount = cItem::count() * cItem::count();
const int infinite = 2e9;
gd.edgeWeight.resize(maxLinkCount, infinite);
for (cHold *hold : cHold::get())
{
if (hold->count() > 1)
{
// source
// create links from holdings with spare items into trading graph
std::string name = "source_" + hold->name();
gd.g.add(
"all_source",
name);
int ie = gd.g.add(
name,
hold->name());
gd.edgeWeight[ie] = hold->count() - 1;
}
else if (!hold->count())
{
// sink
// create links from trading graph to empty holdings
int ie = gd.g.add(
hold->name(),
"sink_" + hold->name());
gd.edgeWeight[ie] = 1;
gd.g.add(
"sink_" + hold->name(),
"all_sink");
}
}
// create the trading links
for (cTrade *trade : cTrade::get())
{
gd.g.add(
trade->giveName(),
trade->getName());
}
}
```

Calculate the flows through the graph

```
void cFlowGraph::calculate()
{
vLinkFlow.clear();
vLinkFlow.resize(gd.g.edgeCount(), 0);
gd.startName = "all_source";
gd.endName = "all_sink";
//Apply Edmonds-Karp algorithm using Pathfinder method
flows(
gd,
vLinkFlow);
displayLinks();
}
```

Check feasability:

```
bool cFlowGraph::isFeasible()
{
// check that every flow into an item sink is 1
// meaning that the missing item was found
for (auto &link : gd.g.edgeList())
{
if (gd.g.userName(link.second).find("sink_") == 0)
if (flow( link ) != 1)
return false;
}
return true;
}
```

Display required trades

```
void cFlowGraph::displayTrades()
{
std::cout << "\n";
for (auto &link : gd.g.edgeList())
{
if (isTrade(link))
std::cout << "trade " << gd.g.userName(link.first)
<< " - > " << gd.g.userName(link.second)
<< " 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

- Minimum Time to Perform One Task of Each Category (with Different Release Times)
- pine-script v5, script error of Mismatched input 'var8' expecting 'end of line without line continuation'
- Worst case in Max-Heapify - How do you get 2n/3?
- How to check whether a matrix is a framed matrix?
- Identify connected subnetworks, constrained by edge attributes
- Is there a way to generate a random variate from a non-standard distribution without computing CDF?
- Most efficient way to calculate VWAP(VOLUME WEIGHTED AVERAGE PRICE) for trading algorithm
- How to find and replace all occurrences of a substring in a string?
- How to find kth smallest element in a BST when the tree may be modified frequently?
- Calculate distance between two latitude-longitude points? (Haversine formula)
- How does one make a Zip bomb?
- How to calculate the midpoints of each triangle edges of an icosahedron
- Calculate circular shift pairs in a list
- Uniformly randomly generate a vector of k unsigned ints that sums to N
- Bin packing with fixed number of bins of varying capacities and item-to-bin compatibility constraints
- Mapping elementwise Tuple Using Template Function
- Find the longest prefix for a table of tokenized strings
- Count Unguarded Cells in the Grid (recursion)
- Kalman Filter Prediction Implementation
- My ALV Tree balance factors calculate incorrectly
- Infix to postfix left one parentheses at the end when expression is fully enclosed
- C++ quick sort algorithm
- Merge Sort Function not working when size of vector is not 2^n
- Given an array a of n integers, and q queries, for each value from index l to index r, add x to the value
- Count mountain arrays
- Get the number of all possible combinations that give a certain product
- getting TLE in leetcode question 212- word search 2 using backtrcaking even after pruning, how do i optimize it more
- Maximizing the sum of Adjacent sum in an array
- Weighted random selection from array
- If f(n) = O(g(n)), is log(f(n)) = O(log(g(n))?