Optimization trading items - min cost max flow

There is n items, formula. 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.


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


  • 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,

    enter image description here

    Apply the Edmonds-Karp algorithm to get your answer 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
        // 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();
                int ie = gd.g.add(
                gd.edgeWeight[ie] = hold->count() - 1;
            else if (!hold->count())
                // sink
                // create links from trading graph to empty holdings
                int ie = gd.g.add(
                    "sink_" + hold->name());
                gd.edgeWeight[ie] = 1;
                    "sink_" + hold->name(),
        // create the trading links
        for (cTrade *trade : cTrade::get())

    Calculate the flows through the graph

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

    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