Ford-Fulkerson算法:最大流

Question

我在福特-富尔克森算法上工作过，有以下代码。

代码工作正常，但我可以做更多的代码优化，我已经工作了几天。

• 问:对于代码改进是否有任何评论或评论？

/**
 * src = source
 * dst = destination
 */
public class MaxFlowAlgo {

    private int vertexTotal;
    private int edgeSrcDstDirectionTotal;
    private List<Edge> edgeList = new ArrayList<>();
    private List<Vertex> vertexList = new ArrayList<>();
    private List<Vertex> minCutVertexList = new ArrayList<>();

    protected void dataParsing(String folderName, String fileName) throws IOException {
        int lineCounter = 0;
        int mCounter = 0;
        String filePath = folderName + fileName;
        File fileObj = new File(filePath);
        Scanner input = new Scanner(fileObj);

        vertexTotal = Integer.parseInt(input.nextLine());
        while (input.hasNext()) {
            if (lineCounter < vertexTotal) {
                vertexList.add(new Vertex(input.nextLine().trim()));
            }
            if (lineCounter == vertexTotal) {
                edgeSrcDstDirectionTotal = Integer.parseInt(input.nextLine());
                mCounter = 0;
            }
            if ((edgeSrcDstDirectionTotal + vertexTotal) >= lineCounter && lineCounter > vertexTotal) {
                Vertex srcVertex = vertexList.get(input.nextInt());
                Vertex dstVertex = vertexList.get(input.nextInt());
                int capacity = input.nextInt();
                if (capacity == -1)
                    capacity = Integer.MAX_VALUE;
                Edge edge = new Edge(srcVertex, dstVertex, capacity, null);
                srcVertex.edges.add(edge);
                dstVertex.edges.add(edge);
                srcVertex.edges.add(edge.edgeBack);
                dstVertex.edges.add(edge.edgeBack);
                edgeList.add(edge);
                edgeList.add(edge.edgeBack);
                mCounter++;
            }

            lineCounter++;
        }
    }

    private List<Edge> bfs(Vertex srcVertex, Vertex sinkVertex) {
        boolean hasPathTo = false;
        Queue<Vertex> queue = new LinkedList<>();
        queue.add(srcVertex);
        minCutVertexList.clear();
        minCutVertexList.add(srcVertex);

        while (queue.size() > 0) {
            Vertex currVertex = queue.poll();
            for (Edge edge : currVertex.edges) {
                Vertex dstVertex = edge.dstVertex;
                if (minCutVertexList.contains(dstVertex) || edge.capacityRemain() == 0)
                    continue;
                dstVertex.edgeTo = edge;
                minCutVertexList.add(dstVertex);
                if (dstVertex.equals(sinkVertex)) {
                    hasPathTo = true;
                    break;
                }
                queue.add(dstVertex);
            }
        }

        List<Edge> edgePathList = new ArrayList<>();
        if (hasPathTo) {
            Vertex vertex = sinkVertex;
            while (!vertex.equals(srcVertex)) {
                edgePathList.add(vertex.edgeTo);
                vertex = vertex.edgeTo.srcVertex;
            }
        }
        return edgePathList.size() > 0 ? edgePathList : null;
    }

    protected List<String> fordFulkerson() {
        int maxFlow = 0;
        Vertex srcVertex = vertexList.get(0);
        Vertex sinkVertex = vertexList.get(vertexTotal - 1);
        List<String> resultList = new ArrayList<>();

        List<Edge> augmentPath;
        while ((augmentPath = bfs(srcVertex, sinkVertex)) != null) {
            int maxCapacity = Integer.MAX_VALUE;
            for (Edge e : augmentPath)
                maxCapacity = Math.min(e.capacityRemain(), maxCapacity);
            for (Edge e : augmentPath)
                e.flowInc(maxCapacity);
            //maxFlow results
            maxFlow += maxCapacity;
        }

        //minimum cut results
        for (Edge e : edgeList) {
            if (minCutVertexList.contains(e.srcVertex) == true && minCutVertexList.contains(e.dstVertex) == false) {
                resultList.add(vertexList.indexOf(e.srcVertex) + " " + vertexList.indexOf(e.dstVertex) + " " + e.capacity);
            }
        }

        return resultList;
    }

    private class Edge {
        public Vertex srcVertex;
        public Vertex dstVertex;
        public Integer capacity = 0;
        public Integer flow = 0;
        public Edge edgeBack;

        public Edge(Vertex srcVertex, Vertex dstVertex, Integer capacity, Edge srcEdge) {
            this.srcVertex = srcVertex;
            this.dstVertex = dstVertex;
            this.capacity = capacity;
            if (srcEdge == null)
                this.edgeBack = new Edge(dstVertex, srcVertex, capacity, this);
            else
                this.edgeBack = srcEdge;
        }

        public void flowInc(int flow) {
            this.flow += flow;
            this.edgeBack.flow -= flow;
        }

        public int capacityRemain() {
            return capacity - flow;
        }

    }

    private class Vertex {
        public String vertexStationName;
        public List<Edge> edges = new ArrayList<>();
        public Edge edgeTo;

        public Vertex(String vertexStationName) {
            this.vertexStationName = vertexStationName;
        }
    }

}

Answer 1

输入解析.

您需要声明一个Scanner来处理您的输入，但是您并不能非常有效地使用它。你的代码：

input = new Scanner(fileObj); vertexTotal = Integer.parseInt(input.nextLine()); while (input.hasNext()) { if (lineCounter < vertexTotal) { vertexList.add(new Vertex(input.nextLine().trim())); } if (lineCounter == vertexTotal) { edgeSrcDstDirectionTotal = Integer.parseInt(input.nextLine()); mCounter = 0; } if ((edgeSrcDstDirectionTotal + vertexTotal) >= lineCounter && lineCounter > vertexTotal) { Vertex srcVertex = vertexList.get(input.nextInt()); Vertex dstVertex = vertexList.get(input.nextInt()); int capacity = input.nextInt(); if (capacity == -1) capacity = Integer.MAX\_VALUE; Edge edge = new Edge(srcVertex, dstVertex, capacity, null); srcVertex.edges.add(edge); dstVertex.edges.add(edge); srcVertex.edges.add(edge.edgeBack); dstVertex.edges.add(edge.edgeBack); edgeList.add(edge); edgeList.add(edge.edgeBack); mCounter++; } lineCounter++; }

最好是：

    input = new Scanner(fileObj);
    vertexTotal = input.nextInt();
    for (int i = 0; i < vertexTotal; i++) {
        vertexList.add(new Vertex(scanner.nextLine().trim());
    }
    edgeSrcDstDirectionTotal = input.nextInt();
    for (int i = 0; i < edgeSrcDstDirectionTotal; i++) {
        Vertex srcVertex = vertexList.get(input.nextInt());
        Vertex dstVertex = vertexList.get(input.nextInt());
        int capacity = input.nextInt();
        if (capacity == -1)
            capacity = Integer.MAX_VALUE;
        Edge edge = new Edge(srcVertex, dstVertex, capacity, null);
        srcVertex.edges.add(edge);
        dstVertex.edges.add(edge);
        srcVertex.edges.add(edge.edgeBack);
        dstVertex.edges.add(edge.edgeBack);
        edgeList.add(edge);
        edgeList.add(edge.edgeBack);
    }

General

总的来说，我对你的代码印象深刻。它很整洁，变量名很好，逻辑结构也很好，而且我几乎不用运行它就可以遵循它。这是件好事。一些小东西也给我留下了深刻的印象：

• 您使用的是变量接口，而不是它们的具体实现。像Queue<Vertex> queue = new LinkedList<>();这样的代码是好的。人们通常会将队列设置为LinkedList，这是您避免的一种反模式。
• 你的变量有很好的名字，而且是自我记录的。
• 你的仿制品似乎都是“对的”。

另一方面，你有很多小东西，但也错了：

• size()是循环条件下的反模式.您的代码while (queue.size() > 0) {应该是：while (!queue.isEmpty()) {
• 即使是1-线如果-块应该有大括号-它可以防止以后的维护错误。这段代码: if (minCutVertexList.contains(dstVertex)欧元/ edge.capacityRemain() == 0)继续；应该是: if (minCutVertexList.contains(dstVertex)欧元/ edge.capacityRemain() == 0) {继续；}当我们在上面的时候，如果你把容量检查放在第一位，你可能会提高性能。
• bfs方法中完整的while-循环应该是一个函数，它应该返回true。break条件应该改为return true。然后您的代码变成: if(!hasPathTo(sinkVertex)) {返回null；} List edgePathList =新的ArrayList<>()；顶点= sinkVertex；while (!vertex.equals(srcVertex)) { edgePathList.add(vertex.edgeTo)；顶点= vertex.edgeTo.srcVertex；}返回edgePathList；
• 您的Edge类和Vertex类都应该是静态的--这将节省一个指向您从未使用过的外部类的指针。

Answer 2

现在的答案遗漏了几点，其中一项我认为相当重要。

数据类型

    private List<Edge> edgeList = new ArrayList<>();
    private List<Vertex> vertexList = new ArrayList<>();
    private List<Vertex> minCutVertexList = new ArrayList<>();

为什么是这些名单？

edgeList在解析阶段被附加，在输出阶段被迭代，所以它可以是任何Collection。List和任何东西一样合理；我个人会使用Set，但我可以看到一个论点，即List更有效。

vertexList在解析阶段被附加并在解析边缘时通过索引查找，因此它必须是一个List。但是输出阶段在循环中调用vertexList.indexOf，在那里预计算Map<Vertex, Integer> (或者将索引存储为Vertex的一个字段)会更有效。

minCutVertexList被清除，添加到contains中，并进行测试。它应该是一个Set，因为List.contains总是一个O(n)操作。

未使用变量

除了mCounter或maxFlow的自我更新(分别是++和+= )之外，我没有看到它们的任何读取。也许它们是用于调试的，或者是您改变了对方法的签名的想法，但是现在可以删除它们。

风格

风格总是有争议的，所以这些都是观点，但我希望它们至少是大多数的观点。

• edgeList等是匈牙利符号的一种形式。IDE将告诉我们它们是列表(或设置，在最小切割顶点的情况下，在应用上述建议之后)。我更喜欢edges，vertices，或者minCutVertices，或者只是minCut。
• 与布尔文本的比较是丑陋的。if (minCutVertexList.contains(e.srcVertex) == true && minCutVertexList.contains(e.dstVertex) == false)可能就是if (minCutVertexList.contains(e.srcVertex) && !minCutVertexList.contains(e.dstVertex))