从嵌套地图中删除重复项(k-core算法)

Question

我正在努力完成一项作业，但出现了一个错误。我想要做的是:有一个无序的映射，它的键包含unordered_set的值，里面可能有“可能与无序的外部映射的键具有相同的名称”的键。

具体地说，我正在尝试实现一个k-core算法，它的count和k数字都在那里。我正在尝试擦除具有小于k大小的unordered_sets(包含邻居，称为N)的unordered_map密钥(让我们称其为P)。但由于我从P节点中删除了N个条目，因此我还需要从外部map中找到N个条目，然后找到P并在那里将其删除。

下面的代码是我到目前为止想出来的(还有更多，但我不想要抄袭或任何东西)。在调试过程中，我注意到在某种程度上cout<

编辑:我已经根据建议更新了代码，但有一个新问题:对于k=1，节点的数量是正确的。但是在k=2，3，4之后..存在最外层循环的无限循环。并且大小保持不变(在使用k=1删除节点之后)

while(nodes.size()!=0)
{
    int count = 0;
    while(stillLeft){
        stillLeft = 0;
        it = nodes.begin();
        while(it != nodes.end()){
            
            if(it->second.size()<=k){
                stillLeft = 1;
                ++count;
                for ( innerit = it->second.begin(); innerit != it->second.end();innerit++ ){
                    nodes.find(*innerit)->second.erase(it->first);

                }
                it = nodes.erase(it);
                }
            else{
                ++it;
            }
                                    }
            
            }
        
    
    cout << nodes.size() << endl;
        
    kCoreNumbers.push_back(count);      
    ++k;
}

Answer 1

你不需要循环到while(nodes.size()!=0)，也就是直到nodes为空。运行k-core算法后，可能会留下顶点的度数大于k的节点。您只需要循环，直到不再有度数小于k的节点。

您的初始代码的方向是正确的，但是在遍历map中的节点时会遇到删除节点的问题。我通过在迭代图时将要删除的顶点添加到向量中来解决这个问题，然后在每次图遍历之后删除所有要删除的节点。以下是我的代码版本，基于您的版本，并对变量名进行了一些更改以反映它们的内容：

void runKCore(size_t k) {
    bool nodesDeleted;
    do {
        // To keep track of how many times the loop needs to run
        nodesDeleted = false;
        // To keep track of the nodes to be deleted after one pass
        std::vector<int> markDeleted;
        for(auto const& node: graph) {
            auto vertex = node.first;
            auto const& neighbours = node.second;
            // Pick vertex if it has less than k neighbours
            if(neighbours.size() < k) {
                for(auto neighbour: neighbours) {
                    // Get the neighbour's list of vertices
                    auto& neighBoursEdges = graph.at(neighbour);
                    // Remove vertex from this list
                    neighBoursEdges.erase(vertex);
                }
                // Mark this node as deleted
                markDeleted.push_back(vertex);
            }
        }
        // Update nodesDeleted if any nodes were marked for deletion
        nodesDeleted = markDeleted.size() > 0;
        for(auto node: markDeleted) {
            // Erase the node and it's neighbours
            graph.erase(node);
        }
    }while(nodesDeleted);
}

Here是完整的程序。

对于初始图

​

​

转换为初始图

8: 6 5 
7: 6 3 4 
6: 7 3 8 5 4 2 
5: 8 6 2 1 
4: 7 3 6 2 
3: 7 6 4 2 
2: 6 3 4 5 1 0 
1: 5 2 0 
0: 2 1 

为k = 3输出运行k-core algo后，程序的输出为：

7: 6 3 4 
6: 7 3 4 2 
4: 7 3 6 2 
3: 7 6 4 2 
2: 6 3 4