algorithm - 给定具有节点权重的二部图，基于某些启发式获取一种类型节点的有序列表

Question

给定一个二分图，其中包含 A 类和 B 类节点的节点权重，如下所示:



我想输出由以下启发式定义的 B 类节点的有序列表:

对于类型 B 的每个节点，我们将与该节点具有边的类型 A 的节点权重相加，并将总和与其自己的节点权重相乘以获得节点值。

然后我们从类型 B 中选择具有最高值的节点并将其附加到输出集 S。

我们从类型 B 中删除选定的节点，并从类型 A 中删除它有一条边的所有节点。

返回第 1 步，直到类型 B 中的任何节点都留下了到类型 A 中的节点的边。

按照节点权重的顺序将任何剩余的 B 类型节点附加到输出集。

下图显示了一个示例:



对于此示例，输出集将为: (Y, Z, X)

简单的过程是简单地遍历这个算法，但假设二部图很大，我正在寻找最有效的方法来找到输出集。注意，我只需要 B 类节点的有序列表作为输出，而不需要中间计算值(例如 50、15、2)

Answer 1

这是对 Dave 在评论中建议的算法的进一步改进。它最大限度地减少了需要重新计算节点值的次数。

运行第 1 步，将生成的 B 节点按 val

放置在最大堆中

检查顶部节点是否有任何邻居被删除。如果是，重新计算并重新插入堆。如果不是，则添加到输出并删除邻居。

重复 2 直到所有 B 都输出

我已经基于我的 PathFinder graph class 在 C++ 中实现了这个算法。该代码运行在具有半个 a 和半个 b 节点的 100 万个节点图上，每个 b 节点连接到两个随机 a 节点，需要 1 秒。
这是代码

void cPathFinder::karup()
    {
        raven::set::cRunWatch aWatcher("karup");
        std::cout << "karup on " << nodeCount() << " node graph\n";
        std::vector<int> output;

        // calculate initial values of B nodes
        std::multimap<int, int> mapValueNode;
        for (auto &b : nodes())
        {
            if (b.second.myName[0] != 'b')
                continue;
            int value = 0;
            for (auto a : b.second.myLink)
            {
                value += node(a.first).myCost;
            }
            value *= b.second.myCost;
            mapValueNode.insert(std::make_pair(value, b.first));
        }

        // while not all B nodes output
        while (mapValueNode.size())
        {
            raven::set::cRunWatch aWatcher("select");

            // select node with highest value
            auto remove_it = --mapValueNode.end();
            int remove = remove_it->second;

            if (!remove_it->first)
            {
                /** all remaining nodes have zero value
                 * all the links from B nodes to A nodes have been removed
                 * output remaining nodes in order of decreasing node weight
                 */
                raven::set::cRunWatch aWatcher("Bunlinked");
                std::multimap<int, int> mapNodeValueNode;
                for (auto &nv : mapValueNode)
                {
                   mapNodeValueNode.insert( 
                       std::make_pair( 
                           node(nv.second).myCost,
                           nv.second ));
                }
                for( auto& nv : mapNodeValueNode )
                {
                    myPath.push_back( nv.second );
                }
                break;
            }

            bool OK = true;
            int value = 0;
            {
                raven::set::cRunWatch aWatcher("check");

                // check that no nodes providing value have been removed

                // std::cout << "checking neighbors of " << name(remove) << "\n";

                auto &vl = node(remove).myLink;
                for (auto it = vl.begin(); it != vl.end();)
                {
                    if (!myG.count(it->first))
                    {
                        // A neighbour has been removed
                        OK = false;
                        it = vl.erase(it);
                    }
                    else
                    {
                        // A neighbour remains
                        value += node(it->first).myCost;
                        it++;
                    }
                }
            }

            if (OK)
            {
                raven::set::cRunWatch aWatcher("store");
                // we have a node whose values is highest and valid

                // store result
                output.push_back(remove);

                // remove neighbour A nodes
                auto &ls = node(remove).myLink;
                for (auto &l : ls)
                {
                    myG.erase(l.first);
                }
                // remove the B node
                // std::cout << "remove " << name( remove ) << "\n";
                mapValueNode.erase(remove_it);
            }
            else
            {
                // replace old value with new
                raven::set::cRunWatch aWatcher("replace");
                value *= node(remove).myCost;
                mapValueNode.erase(remove_it);
                mapValueNode.insert(std::make_pair(value, remove));
            }
        }
    }

以下是计时结果

karup on 1000000 node graph
raven::set::cRunWatch code timing profile
Calls           Mean (secs)     Total           Scope
       1        1.16767 1.16767 karup
  581457        1.37921e-06     0.801951        select
  581456        4.71585e-07     0.274206        check
  564546        3.04042e-07     0.171646        replace
       1        0.153269        0.153269        Bunlinked
   16910        8.10422e-06     0.137042        store