1

我有两个班级MaxFlow和MinMaxFlow.

MaxFlow使用 boost graph 从网络拓扑创建图：

class MaxFlow {
 public:
  MaxFlow : g_() { createGraph(); } //constructor
  void createGraph();
  void modifyGraph(); // modify the graph to use boost maxflow algorithm
  int maxFlowAlgo(); // use g_ and some other util local variables
 private:
  Graph g_;
  ...   // some other helper containers created during createGraph()
}

MaxFlow维护一个局部变量g_，因为我们只需要一个实例来完成这里的所有工作。 如果我们失败了（将容量设置为 0）MinMaxFlow，则迭代图中的每条边以找到最小的最大流量：edge

class MinMaxFlow {
 public:
  int getMinMaxFlow() {
    int minMaxFlow = INT_MAX;
    MaxFlow maxFlowObj; // create a new obj
    maxFlowObj.modifyGraph(); // I suppose this modify current obj
    for (auto edge : graph_edges) {
      // maxFlowAlgo will return incorrect value after several runs
      int maxFlowVal = maxFlowObj.maxFlowAlgo();
      int minMaxFlow = std::min(minMaxFlow, maxFlowVal);
    }
    return minMaxFlow;
  }
}

现在的问题是，maxFlowAlgo基于g_类中的局部变量MaxFlow，当我在中创建新对象maxFlowObj时MinMaxFlow，调用maxFlowObj.maxFlowAlgo()将使用它自己的数据，这使得结果不可预测。所以我的问题是：如果方法在中使用局部变量，我如何使用maxFlowAlgo属于MaxFlow第二类的方法（如） ？MinMaxFlowMaxFlow

更新：我发现问题出在boost::boykov_kolmogorov_max_flow，我使用捆绑属性并将容量属性映射传递给它，但是这个算法不仅会修改容量属性映射，还会修改我原来的边缘容量变量！现在的解决方法是我必须在运行算法之前存储容量值并在它之后恢复它们。应该不会修改原来的成员吧？

4

2 回答 2

1

在这种情况下，可以更改边缘容量。

有时算法不会修改输入数据。另一方面，最好更改现有数据以节省资源（内存），因为更改后的数据是有意义的。执行最大流算法后，边缘容量为剩余容量；换句话说，当图被流量饱和时，每条边还剩下多少容量。至少一个边缘将具有零剩余容量；当第二次算法执行后，由于图形饱和，它将返回零。

如果要多次运行最大流量算法，则必须保留初始图并在每次运行算法时复制它。每次循环迭代开始时，您都必须重建图形或从保留的图形中复制它。

由于您多次运行算法，您可能希望在不同的图表上运行它。您可能想要复制图形并将边容量设置为零。

于 2016-04-14T08:42:58.303 回答
0

看来你问了一个XY 问题。

如果您愿意maintains a local variable g_ since we only need one instance，您应该使用单例设计模式，而不是在需要时创建实例。

于 2016-04-14T01:02:41.170 回答