0

我正在尝试使用 LEMON 库，但遇到了我尝试实现的算法的问题。该算法的想法是有一个节点向量的向量，我想将节点移动到具有一定限制的不同向量（颜色类）。这是实现我的算法的代码：

bool moveColor() {
  // pick the smallest color class
  sort(colors.begin(), colors.end(), vectorSort);
  vector< vector< ListGraph::Node > >::iterator smallestColor = colors.begin();

  // shuffle this class
  random_shuffle(smallestColor->begin(), smallestColor->end());

  // try to move any of the nodes to any bigger class
  bool foundNode = false;
  vector< ListGraph::Node >::iterator movingNode;
  vector< vector< ListGraph::Node > >::iterator destinationClass;
  for (movingNode = smallestColor->begin(); movingNode != smallestColor->end() && !foundNode; ++movingNode) {
    for (destinationClass = colors.begin()+1; destinationClass != colors.end() && !foundNode; ++destinationClass) {
      ListGraph::NodeMap<bool> filter(g, false);
      vector< ListGraph::Node >::iterator classNode;
      for (classNode = destinationClass->begin(); classNode != destinationClass->end(); ++classNode) {
        filter[*classNode] = true;
      }
      filter[*movingNode] = true;
      FilterNodes<ListGraph> subgraph(g, filter);
      if (acyclic(subgraph)) {
        foundNode = true;
      }
    }
  }

  // if a movable node was found, move it. otherwise return false
  if (foundNode) {
    destinationClass->push_back(*movingNode);
    smallestColor->erase(movingNode);
    if (smallestColor->empty()) {
      colors.erase(smallestColor);
    }
    return true;
  }
  return false;
}

此函数在 main 中循环调用，直到无法移动节点。我在代码中遇到的主要问题是实际将节点从一个向量移动到另一个向量的部分：

if (foundNode) {
  destinationClass->push_back(*movingNode);
  smallestColor->erase(movingNode);
  if (smallestColor->empty()) {
    colors.erase(smallestColor);
  }
  return true;
}

这部分似乎不起作用，因为我认为在调用擦除函数时节点正在解构。这是调用此函数之前和之后的节点 ID 示例：

NEW ROUND
1 
3 
0 
5 2 
7 6 4 
NEW ROUND
3 
0 32701 
5 2 
7 6 4

如您所见，被移动节点的 id 不正确（32701 而不是 1）。任何帮助表示赞赏。

4

1 回答 1

0

问题实际上在这里：

if (acyclic(subgraph)) {
    foundNode = true;
}

当您定位节点时，您不会break跳出for循环，这会使迭代器在检查条件之前movingNode前进到向量中的下一个位置（在这种情况下） 。在这种情况下，您必须两次，因为您要从嵌套循环中中断。smallestColor->end()!foundNodebreak

或者，您可以将匹配条件的迭代器存储在单独的变量中以在循环外部进行操作（与在 for 循环中迭代的不同）。

关于您突出显示为潜在问题来源的片段： destinationClass->push_back(*movingNode);正在放入该迭代器指向destinationClass的副本中。这意味着，复制构造函数被调用。由于没有用户定义的复制构造函数，编译器会自动生成一个，即复制所有成员的值，因此应该复制值（当然，如果对 使用正确的迭代器）。当然，您要重新定位的节点的原始副本会被破坏，但这不会影响新副本。NodemovingNodeNodeNodeidpush_backerase

于 2017-11-27T21:49:10.133 回答