C++ KOALA图库最小割结果存储与后续访问技术问询

To save the edges from the minimum cut instead of just printing them, you have two straightforward approaches—either use standard library insert iterators (simplest) or modify your custom edgeIter to store edges in a container. Here's how to implement both:

Option 1: Use Standard Library Insert Iterators (Recommended) #

This approach avoids modifying your existing edgeIter entirely by leveraging std::back_inserter, a built-in insert iterator that adds elements to containers like std::vector.

Step 1: Declare Containers for Cut Data #

First, create vectors to hold the cut edges and vertices (you can skip the vertex container if you don't need that data):

#include <vector>
#include <iterator> // Required for std::back_inserter

// Adjust types to match your MyGraph definitions
std::vector<MyGraph::PEdge> minCutEdges;
std::vector<MyGraph::PVertex> minCutVertices;

Step 2: Call minEdgeCut with Insert Iterators #

Pass std::back_inserter to the outCut function. This tells KOALA to push edges/vertices directly into your vectors:

Flow::minEdgeCut(g, cap, s, t, Flow::outCut(
    std::back_inserter(minCutVertices), // Collects vertices reachable from s post-cut
    std::back_inserter(minCutEdges)     // Collects edges in the minimum cut
));

Step 3: Access Stored Cut Edges Later #

After the function call, minCutEdges will contain all edges from the minimum cut. You can iterate over it like any other vector:

// Example: Process stored cut edges
for (const auto& edge : minCutEdges) {
    std::cout << "Cut edge info: " << edge->info << "\n";
    // Add your custom logic here
}

Option 2: Modify Your Custom edgeIter #

If you prefer to keep using a custom iterator (e.g., for additional logic), update it to store edges in a container instead of printing them.

Step 1: Update the edgeIter Struct #

Modify the struct to hold a reference to a vector and populate it when edges are assigned:

#include <vector>

struct edgeIter {
    std::vector<MyGraph::PEdge>& targetContainer; // Reference to our storage vector

    // Constructor: tie the iterator to a specific container
    explicit edgeIter(std::vector<MyGraph::PEdge>& container) : targetContainer(container) {}

    // Override assignment to add edges to the container
    void operator=(MyGraph::PEdge e) {
        targetContainer.push_back(e);
    }

    // Keep existing no-op methods required by the iterator interface
    void operator++() {}
    edgeIter& operator*() { return *this; }
};

Step 2: Use the Modified Iterator #

Create your containers and pass the custom iterator to outCut:

std::vector<MyGraph::PEdge> minCutEdges;
std::vector<MyGraph::PVertex> minCutVertices;

Flow::minEdgeCut(g, cap, s, t, Flow::outCut(
    std::back_inserter(minCutVertices),
    edgeIter(minCutEdges) // Pass our iterator tied to the minCutEdges vector
));

Step 3: Access Stored Edges #

Just like in Option 1, you can use minCutEdges later in your program to process the cut edges.

Bonus: Ignore Vertex Cut Data (If Unneeded) #

If you don't care about the vertices in the cut, use a dummy iterator to discard that data:

struct DummyVertexIter {
    void operator=(MyGraph::PVertex) {} // Ignore vertex assignments
    void operator++() {}
    DummyVertexIter& operator*() { return *this; }
};

// Call minEdgeCut with the dummy iterator
Flow::minEdgeCut(g, cap, s, t, Flow::outCut(
    DummyVertexIter(),
    std::back_inserter(minCutEdges)
));

内容的提问来源于stack exchange，提问作者scalauser