/*
 * (C) Copyright 2020-2023, by Timofey Chudakov and Contributors.
 *
 * JGraphT : a free Java graph-theory library
 *
 * See the CONTRIBUTORS.md file distributed with this work for additional
 * information regarding copyright ownership.
 *
 * This program and the accompanying materials are made available under the
 * terms of the Eclipse Public License 2.0 which is available at
 * http://www.eclipse.org/legal/epl-2.0, or the
 * GNU Lesser General Public License v2.1 or later
 * which is available at
 * http://www.gnu.org/licenses/old-licenses/lgpl-2.1-standalone.html.
 *
 * SPDX-License-Identifier: EPL-2.0 OR LGPL-2.1-or-later
 */
package org.jgrapht.alg.flow;

import org.jgrapht.Graph;
import org.jgrapht.Graphs;
import org.jgrapht.alg.interfaces.MaximumFlowAlgorithm;
import org.jgrapht.graph.DefaultDirectedWeightedGraph;
import org.jgrapht.graph.DefaultUndirectedWeightedGraph;
import org.jgrapht.graph.DefaultWeightedEdge;
import org.junit.Test;

import static junit.framework.TestCase.assertEquals;

/**
 * Tests for {@link BoykovKolmogorovMFImpl}.
 * <p>
 * The directed networks used for the tests were generated using the NetworkGenerator. The
 * undirected networks were obtained from directed networks by using the same edge weights. In the
 * case of parallel edges, their weights were summed.
 *
 * @author Timofey Chudakov
 */
public class BoykovKolmogorovMFImplTest
    extends MaximumFlowAlgorithmTest
{

    private static final double EPS = 1e-9;

    private Graph<Integer, DefaultWeightedEdge> constructDirected(int[][] edges)
    {
        return constructGraph(new DefaultDirectedWeightedGraph<>(DefaultWeightedEdge.class), edges);
    }

    private Graph<Integer, DefaultWeightedEdge> constructUndirected(int[][] edges)
    {
        return constructGraph(
            new DefaultUndirectedWeightedGraph<>(DefaultWeightedEdge.class), edges);
    }

    private Graph<Integer, DefaultWeightedEdge> constructGraph(
        Graph<Integer, DefaultWeightedEdge> graph, int[][] edges)
    {
        for (int[] edge : edges) {
            Graphs.addEdgeWithVertices(graph, edge[0], edge[1], edge[2]);
        }
        return graph;
    }

    private void testOnGraph(
        Graph<Integer, DefaultWeightedEdge> graph, int source, int sink, int expectedFlow)
    {
        MaximumFlowAlgorithm<Integer, DefaultWeightedEdge> flow = createSolver(graph);
        double maxFlow = flow.getMaximumFlowValue(source, sink);
        assertEquals(expectedFlow, maxFlow, EPS);
    }

    private void testDirectedUndirected(
        int[][] edges, int source, int sink, int expectedDirectedFlow, int expectedUndirectedFlow)
    {
        Graph<Integer, DefaultWeightedEdge> directed = constructDirected(edges);
        Graph<Integer, DefaultWeightedEdge> undirected = constructUndirected(edges);

        testOnGraph(directed, source, sink, expectedDirectedFlow);
        testOnGraph(undirected, source, sink, expectedUndirectedFlow);
    }

    /**
     * Network generator parameters: nodeNum = 10 arcNum = 30 supply = 10 sourceNum = 1 sinkNum = 1
     * minCap = 1 maxCap = 50 seed = 1
     */
    @Test
    public void test1()
    {
        int[][] edges = { { 1, 5, 10 }, { 5, 9, 20 }, { 9, 8, 35 }, { 8, 3, 27 }, { 3, 2, 49 },
            { 2, 4, 10 }, { 4, 6, 26 }, { 6, 7, 28 }, { 2, 10, 34 }, { 1, 7, 15 }, { 1, 10, 9 },
            { 3, 7, 26 }, { 3, 4, 25 }, { 3, 9, 25 }, { 3, 8, 18 }, { 4, 9, 28 }, { 4, 3, 4 },
            { 4, 7, 22 }, { 4, 8, 1 }, { 6, 2, 42 }, { 6, 4, 13 }, { 6, 8, 43 }, { 6, 5, 48 },
            { 8, 9, 8 }, { 8, 5, 34 }, { 9, 4, 36 }, { 9, 3, 47 }, { 3, 10, 10 }, { 4, 10, 39 },
            { 5, 10, 16 }, };
        testDirectedUndirected(edges, 1, 10, 19, 34);
    }

    /**
     * Network generator parameters: nodeNum = 10 arcNum = 30 supply = 10 sourceNum = 1 sinkNum = 1
     * minCap = 1 maxCap = 50 seed = 2
     */
    @Test
    public void test2()
    {
        int[][] edges = { { 1, 2, 10 }, { 2, 7, 45 }, { 7, 9, 17 }, { 9, 8, 29 }, { 8, 5, 13 },
            { 5, 3, 10 }, { 3, 6, 18 }, { 6, 4, 43 }, { 7, 10, 17 }, { 1, 8, 27 }, { 2, 5, 3 },
            { 3, 8, 44 }, { 3, 5, 17 }, { 3, 4, 19 }, { 4, 8, 48 }, { 6, 2, 29 }, { 6, 8, 16 },
            { 6, 3, 25 }, { 6, 5, 32 }, { 7, 8, 21 }, { 7, 6, 25 }, { 7, 5, 36 }, { 7, 4, 44 },
            { 9, 7, 37 }, { 9, 2, 25 }, { 9, 3, 15 }, { 9, 6, 33 }, { 3, 10, 7 }, { 4, 10, 23 },
            { 5, 10, 48 }, };
        testDirectedUndirected(edges, 1, 10, 23, 37);
    }

    /**
     * Network generator parameters: nodeNum = 20 arcNum = 40 supply = 20 sourceNum = 2 sinkNum = 2
     * minCap = 1 maxCap = 50 seed = 2
     */
    @Test
    public void test3()
    {
        int[][] edges = { { 1, 16, 20 }, { 2, 17, 35 }, { 16, 11, 50 }, { 17, 12, 50 },
            { 11, 9, 36 }, { 12, 13, 8 }, { 9, 7, 19 }, { 13, 5, 9 }, { 7, 4, 34 }, { 5, 14, 32 },
            { 14, 3, 24 }, { 4, 15, 19 }, { 3, 8, 37 }, { 15, 18, 24 }, { 18, 6, 43 },
            { 6, 10, 19 }, { 1, 19, 47 }, { 10, 20, 19 }, { 3, 19, 48 }, { 3, 6, 14 },
            { 4, 14, 27 }, { 4, 16, 3 }, { 5, 18, 18 }, { 5, 16, 42 }, { 6, 16, 31 }, { 6, 18, 8 },
            { 7, 8, 37 }, { 7, 17, 17 }, { 7, 12, 32 }, { 9, 15, 32 }, { 9, 18, 18 },
            { 10, 18, 11 }, { 10, 12, 23 }, { 10, 16, 25 }, { 13, 17, 37 }, { 13, 8, 17 },
            { 3, 20, 28 }, { 6, 20, 2 }, { 7, 19, 40 }, { 8, 20, 41 }, { 21, 1, 2147483647 },
            { 21, 2, 2147483647 }, { 19, 22, 2147483647 }, { 20, 22, 2147483647 }, };
        testDirectedUndirected(edges, 21, 22, 75, 102);
    }

    /**
     * Network generator parameters: nodeNum = 20 arcNum = 60 supply = 20 sourceNum = 2 sinkNum = 2
     * minCap = 1 maxCap = 50 seed = 1
     */
    @Test
    public void test4()
    {
        int[][] edges = { { 1, 3, 12 }, { 2, 7, 18 }, { 3, 5, 13 }, { 7, 17, 11 }, { 5, 14, 12 },
            { 17, 16, 8 }, { 14, 8, 21 }, { 16, 4, 28 }, { 8, 9, 39 }, { 9, 6, 12 }, { 4, 13, 35 },
            { 6, 11, 47 }, { 11, 18, 17 }, { 18, 10, 32 }, { 13, 12, 9 }, { 10, 15, 12 },
            { 1, 19, 37 }, { 9, 20, 26 }, { 13, 19, 18 }, { 4, 20, 17 }, { 1, 6, 6 }, { 1, 17, 17 },
            { 1, 11, 13 }, { 1, 9, 43 }, { 1, 13, 48 }, { 1, 18, 8 }, { 1, 15, 50 }, { 1, 14, 39 },
            { 1, 16, 36 }, { 3, 12, 37 }, { 3, 11, 14 }, { 4, 9, 20 }, { 4, 6, 27 }, { 6, 10, 1 },
            { 8, 4, 9 }, { 9, 17, 20 }, { 9, 7, 27 }, { 10, 6, 49 }, { 10, 9, 50 }, { 11, 15, 21 },
            { 12, 3, 37 }, { 13, 8, 4 }, { 13, 16, 30 }, { 15, 17, 9 }, { 15, 18, 9 },
            { 15, 13, 37 }, { 16, 11, 32 }, { 17, 15, 18 }, { 17, 8, 14 }, { 17, 6, 14 },
            { 18, 11, 7 }, { 3, 19, 6 }, { 4, 19, 50 }, { 6, 20, 4 }, { 6, 19, 50 }, { 7, 20, 16 },
            { 7, 19, 33 }, { 8, 20, 20 }, { 8, 19, 23 }, { 9, 19, 7 }, { 21, 1, 2147483647 },
            { 21, 2, 2147483647 }, { 19, 22, 2147483647 }, { 20, 22, 2147483647 }, };
        testDirectedUndirected(edges, 21, 22, 239, 307);
    }

    /**
     * Network generator parameters: nodeNum = 30 arcNum = 60 supply = 30 sourceNum = 3 sinkNum = 3
     * minCap = 1 maxCap = 50 seed = 1
     */
    @Test
    public void test5()
    {
        int[][] edges = { { 1, 26, 49 }, { 2, 22, 17 }, { 3, 24, 40 }, { 26, 8, 25 },
            { 22, 17, 17 }, { 24, 23, 14 }, { 8, 10, 35 }, { 17, 18, 28 }, { 23, 4, 8 },
            { 10, 15, 37 }, { 18, 27, 35 }, { 4, 21, 49 }, { 15, 14, 29 }, { 27, 9, 23 },
            { 14, 5, 39 }, { 5, 7, 30 }, { 7, 19, 25 }, { 9, 20, 37 }, { 19, 25, 45 },
            { 25, 12, 18 }, { 12, 13, 28 }, { 20, 16, 41 }, { 13, 11, 35 }, { 21, 6, 46 },
            { 15, 28, 13 }, { 9, 29, 43 }, { 20, 30, 17 }, { 17, 28, 17 }, { 4, 29, 39 },
            { 21, 30, 36 }, { 2, 24, 34 }, { 3, 17, 10 }, { 3, 19, 39 }, { 3, 13, 46 },
            { 3, 30, 14 }, { 4, 22, 4 }, { 5, 27, 6 }, { 5, 26, 4 }, { 6, 16, 36 }, { 6, 9, 9 },
            { 7, 24, 27 }, { 7, 25, 11 }, { 10, 19, 22 }, { 11, 25, 25 }, { 12, 7, 7 },
            { 12, 4, 32 }, { 13, 21, 10 }, { 14, 11, 20 }, { 14, 6, 21 }, { 15, 9, 49 },
            { 17, 10, 19 }, { 18, 8, 50 }, { 18, 13, 35 }, { 19, 5, 13 }, { 19, 14, 20 },
            { 21, 12, 33 }, { 5, 28, 24 }, { 7, 28, 9 }, { 10, 30, 1 }, { 12, 28, 12 },
            { 31, 1, 2147483647 }, { 31, 2, 2147483647 }, { 31, 3, 2147483647 },
            { 28, 32, 2147483647 }, { 29, 32, 2147483647 }, { 30, 32, 2147483647 }, };
        testDirectedUndirected(edges, 31, 32, 135, 190);
    }

    /**
     * Network generator parameters: nodeNum = 30 arcNum = 90 supply = 30 sourceNum = 3 sinkNum = 3
     * minCap = 1 maxCap = 50 seed = 1
     */
    @Test
    public void test6()
    {
        int[][] edges = { { 1, 26, 49 }, { 2, 22, 17 }, { 3, 24, 40 }, { 26, 8, 25 },
            { 22, 17, 17 }, { 24, 23, 14 }, { 8, 10, 35 }, { 17, 18, 28 }, { 23, 4, 8 },
            { 10, 15, 37 }, { 18, 27, 35 }, { 4, 21, 49 }, { 15, 14, 29 }, { 27, 9, 23 },
            { 14, 5, 39 }, { 5, 7, 30 }, { 7, 19, 25 }, { 9, 20, 37 }, { 19, 25, 45 },
            { 25, 12, 18 }, { 12, 13, 28 }, { 20, 16, 41 }, { 13, 11, 35 }, { 21, 6, 46 },
            { 15, 28, 13 }, { 9, 29, 43 }, { 20, 30, 17 }, { 17, 28, 17 }, { 4, 29, 39 },
            { 21, 30, 36 }, { 2, 24, 34 }, { 2, 20, 10 }, { 2, 11, 39 }, { 2, 25, 19 },
            { 2, 15, 30 }, { 3, 15, 25 }, { 3, 10, 23 }, { 3, 18, 32 }, { 3, 9, 21 }, { 1, 28, 40 },
            { 1, 30, 9 }, { 4, 17, 32 }, { 5, 27, 18 }, { 5, 22, 14 }, { 5, 11, 14 }, { 8, 22, 7 },
            { 8, 23, 14 }, { 8, 26, 50 }, { 9, 23, 10 }, { 9, 24, 45 }, { 10, 27, 11 },
            { 10, 23, 13 }, { 10, 21, 50 }, { 10, 6, 35 }, { 11, 5, 13 }, { 12, 5, 20 },
            { 12, 19, 33 }, { 12, 15, 32 }, { 13, 9, 30 }, { 13, 20, 29 }, { 13, 14, 25 },
            { 14, 17, 24 }, { 15, 17, 30 }, { 15, 22, 5 }, { 15, 23, 26 }, { 16, 25, 34 },
            { 16, 14, 12 }, { 16, 13, 13 }, { 18, 13, 45 }, { 18, 6, 44 }, { 18, 23, 38 },
            { 18, 4, 4 }, { 19, 12, 25 }, { 20, 8, 13 }, { 20, 6, 23 }, { 20, 22, 41 },
            { 21, 4, 27 }, { 22, 16, 19 }, { 22, 26, 45 }, { 22, 5, 29 }, { 23, 14, 34 },
            { 23, 25, 38 }, { 23, 19, 27 }, { 23, 26, 31 }, { 24, 5, 35 }, { 25, 27, 10 },
            { 7, 30, 20 }, { 8, 29, 7 }, { 11, 28, 13 }, { 12, 30, 10 }, { 31, 1, 2147483647 },
            { 31, 2, 2147483647 }, { 31, 3, 2147483647 }, { 28, 32, 2147483647 },
            { 29, 32, 2147483647 }, { 30, 32, 2147483647 }, };
        testDirectedUndirected(edges, 31, 32, 251, 264);
    }

    /**
     * Network generator parameters: nodeNum = 50 arcNum = 100 supply = 50 sourceNum = 5 sinkNum = 5
     * minCap = 1 maxCap = 50 seed = 1
     */
    @Test
    public void test7()
    {
        int[][] edges = { { 1, 39, 14 }, { 2, 38, 47 }, { 3, 8, 50 }, { 4, 21, 38 }, { 5, 28, 14 },
            { 39, 30, 26 }, { 38, 18, 38 }, { 8, 12, 5 }, { 21, 14, 12 }, { 28, 37, 14 },
            { 30, 7, 34 }, { 18, 9, 16 }, { 12, 22, 9 }, { 14, 40, 12 }, { 37, 33, 14 },
            { 7, 10, 10 }, { 9, 44, 21 }, { 22, 36, 37 }, { 40, 31, 26 }, { 33, 34, 14 },
            { 10, 6, 34 }, { 44, 16, 13 }, { 36, 11, 27 }, { 31, 24, 35 }, { 6, 26, 46 },
            { 16, 29, 39 }, { 24, 25, 30 }, { 34, 23, 24 }, { 11, 42, 8 }, { 42, 32, 34 },
            { 25, 20, 28 }, { 29, 27, 21 }, { 26, 13, 36 }, { 20, 17, 12 }, { 17, 43, 12 },
            { 23, 19, 47 }, { 32, 35, 33 }, { 19, 45, 37 }, { 43, 15, 25 }, { 45, 41, 41 },
            { 13, 46, 40 }, { 30, 47, 40 }, { 44, 48, 27 }, { 38, 49, 49 }, { 11, 50, 16 },
            { 8, 46, 16 }, { 20, 47, 21 }, { 25, 48, 12 }, { 19, 49, 14 }, { 37, 50, 14 },
            { 1, 10, 34 }, { 1, 6, 24 }, { 2, 24, 32 }, { 2, 8, 10 }, { 2, 47, 21 }, { 3, 48, 49 },
            { 6, 19, 45 }, { 6, 24, 15 }, { 7, 41, 29 }, { 7, 33, 24 }, { 8, 14, 48 }, { 8, 7, 21 },
            { 9, 13, 45 }, { 9, 42, 18 }, { 10, 11, 37 }, { 11, 21, 31 }, { 11, 9, 41 },
            { 16, 9, 26 }, { 17, 11, 14 }, { 18, 37, 19 }, { 18, 21, 6 }, { 19, 10, 26 },
            { 20, 18, 42 }, { 22, 33, 16 }, { 23, 12, 17 }, { 24, 35, 28 }, { 24, 40, 41 },
            { 25, 10, 27 }, { 27, 11, 34 }, { 30, 29, 46 }, { 31, 29, 32 }, { 31, 16, 29 },
            { 34, 29, 26 }, { 35, 23, 17 }, { 35, 15, 45 }, { 38, 36, 2 }, { 40, 33, 47 },
            { 43, 26, 25 }, { 43, 29, 37 }, { 45, 22, 34 }, { 7, 49, 23 }, { 11, 48, 40 },
            { 12, 47, 21 }, { 14, 49, 1 }, { 17, 49, 32 }, { 18, 50, 34 }, { 19, 46, 21 },
            { 23, 47, 40 }, { 24, 50, 46 }, { 25, 46, 44 }, { 51, 1, 2147483647 },
            { 51, 2, 2147483647 }, { 51, 3, 2147483647 }, { 51, 4, 2147483647 },
            { 51, 5, 2147483647 }, { 48, 52, 2147483647 }, { 49, 52, 2147483647 },
            { 50, 52, 2147483647 }, { 46, 52, 2147483647 }, { 47, 52, 2147483647 }, };
        testDirectedUndirected(edges, 51, 52, 290, 327);
    }

    /**
     * Network generator parameters: nodeNum = 50 arcNum = 150 supply = 50 sourceNum = 5 sinkNum = 5
     * minCap = 1 maxCap = 50 seed = 2
     */
    @Test
    public void test8()
    {
        int[][] edges = { { 1, 12, 15 }, { 2, 34, 31 }, { 3, 39, 43 }, { 4, 35, 9 }, { 5, 45, 11 },
            { 12, 23, 18 }, { 34, 29, 20 }, { 39, 10, 37 }, { 35, 27, 32 }, { 45, 8, 21 },
            { 23, 28, 14 }, { 29, 22, 45 }, { 10, 14, 39 }, { 27, 42, 9 }, { 8, 19, 43 },
            { 28, 33, 36 }, { 22, 13, 50 }, { 14, 25, 47 }, { 42, 43, 9 }, { 19, 31, 11 },
            { 33, 17, 9 }, { 13, 15, 18 }, { 25, 21, 45 }, { 43, 11, 9 }, { 21, 18, 36 },
            { 15, 16, 25 }, { 11, 44, 36 }, { 16, 38, 46 }, { 38, 26, 3 }, { 44, 9, 28 },
            { 9, 41, 39 }, { 31, 24, 28 }, { 26, 6, 16 }, { 24, 36, 31 }, { 17, 40, 48 },
            { 6, 30, 2 }, { 36, 20, 16 }, { 40, 7, 17 }, { 20, 32, 29 }, { 7, 37, 11 },
            { 37, 46, 37 }, { 17, 47, 17 }, { 28, 48, 10 }, { 17, 49, 17 }, { 33, 50, 30 },
            { 38, 46, 32 }, { 39, 47, 20 }, { 4, 48, 49 }, { 43, 49, 31 }, { 20, 50, 45 },
            { 1, 10, 40 }, { 1, 15, 12 }, { 1, 41, 47 }, { 3, 8, 13 }, { 4, 33, 23 }, { 4, 8, 20 },
            { 4, 44, 8 }, { 4, 40, 29 }, { 4, 12, 11 }, { 5, 40, 20 }, { 5, 16, 5 }, { 5, 39, 3 },
            { 5, 11, 29 }, { 5, 44, 17 }, { 6, 45, 22 }, { 6, 33, 16 }, { 7, 41, 35 }, { 9, 8, 15 },
            { 9, 35, 30 }, { 9, 33, 5 }, { 11, 22, 13 }, { 12, 20, 36 }, { 12, 10, 29 },
            { 12, 15, 24 }, { 13, 17, 32 }, { 13, 18, 10 }, { 14, 27, 11 }, { 14, 37, 40 },
            { 15, 38, 14 }, { 16, 20, 32 }, { 16, 18, 15 }, { 16, 17, 29 }, { 17, 22, 26 },
            { 17, 42, 25 }, { 17, 41, 1 }, { 17, 33, 36 }, { 18, 10, 17 }, { 19, 28, 49 },
            { 20, 45, 44 }, { 20, 36, 8 }, { 20, 8, 9 }, { 20, 14, 17 }, { 21, 9, 37 },
            { 22, 44, 19 }, { 23, 11, 13 }, { 23, 10, 40 }, { 23, 27, 10 }, { 23, 39, 17 },
            { 26, 24, 35 }, { 26, 9, 43 }, { 26, 11, 20 }, { 26, 43, 24 }, { 27, 23, 20 },
            { 28, 6, 29 }, { 31, 37, 42 }, { 31, 32, 41 }, { 32, 6, 8 }, { 32, 25, 43 },
            { 32, 18, 7 }, { 34, 26, 8 }, { 34, 17, 12 }, { 34, 15, 35 }, { 34, 44, 34 },
            { 35, 36, 6 }, { 35, 19, 15 }, { 35, 11, 47 }, { 36, 44, 20 }, { 36, 14, 34 },
            { 36, 29, 16 }, { 36, 23, 10 }, { 37, 30, 6 }, { 38, 28, 11 }, { 38, 41, 11 },
            { 39, 22, 26 }, { 39, 38, 36 }, { 39, 6, 44 }, { 41, 31, 15 }, { 41, 30, 38 },
            { 41, 28, 35 }, { 42, 17, 30 }, { 42, 22, 25 }, { 42, 35, 38 }, { 43, 26, 33 },
            { 43, 37, 33 }, { 43, 17, 36 }, { 44, 38, 5 }, { 44, 22, 48 }, { 44, 30, 49 },
            { 45, 37, 32 }, { 45, 29, 29 }, { 45, 11, 49 }, { 45, 34, 13 }, { 7, 47, 33 },
            { 10, 50, 16 }, { 11, 46, 38 }, { 12, 47, 7 }, { 18, 48, 33 }, { 20, 49, 28 },
            { 21, 49, 26 }, { 22, 49, 21 }, { 51, 1, 2147483647 }, { 51, 2, 2147483647 },
            { 51, 3, 2147483647 }, { 51, 4, 2147483647 }, { 51, 5, 2147483647 },
            { 48, 52, 2147483647 }, { 49, 52, 2147483647 }, { 50, 52, 2147483647 },
            { 46, 52, 2147483647 }, { 47, 52, 2147483647 }, };
        testDirectedUndirected(edges, 51, 52, 397, 435);
    }

    /**
     * Network generator parameters: nodeNum = 100 arcNum = 200 supply = 100 sourceNum = 10 sinkNum
     * = 10 minCap = 1 maxCap = 50 seed = 1
     */
    @Test
    public void test9()
    {
        int[][] edges = { { 1, 23, 50 }, { 2, 24, 38 }, { 3, 75, 12 }, { 4, 21, 26 }, { 5, 11, 38 },
            { 6, 56, 10 }, { 7, 76, 13 }, { 8, 34, 5 }, { 9, 18, 34 }, { 10, 43, 16 },
            { 23, 27, 9 }, { 24, 77, 8 }, { 75, 37, 12 }, { 21, 39, 10 }, { 11, 53, 21 },
            { 56, 17, 37 }, { 76, 83, 26 }, { 34, 85, 4 }, { 18, 90, 34 }, { 43, 59, 10 },
            { 27, 74, 27 }, { 77, 45, 35 }, { 37, 89, 12 }, { 39, 25, 17 }, { 53, 47, 21 },
            { 17, 60, 43 }, { 83, 69, 48 }, { 85, 61, 8 }, { 90, 71, 50 }, { 59, 38, 39 },
            { 74, 19, 36 }, { 45, 30, 46 }, { 89, 31, 12 }, { 25, 12, 9 }, { 47, 81, 34 },
            { 60, 80, 10 }, { 69, 82, 39 }, { 61, 26, 19 }, { 71, 84, 30 }, { 38, 49, 25 },
            { 19, 20, 23 }, { 30, 15, 32 }, { 31, 32, 21 }, { 12, 54, 25 }, { 81, 70, 21 },
            { 80, 29, 27 }, { 82, 36, 49 }, { 26, 64, 50 }, { 36, 35, 13 }, { 35, 87, 13 },
            { 54, 48, 9 }, { 87, 65, 19 }, { 29, 46, 37 }, { 70, 40, 37 }, { 48, 22, 45 },
            { 64, 51, 22 }, { 46, 78, 30 }, { 65, 42, 24 }, { 84, 88, 14 }, { 49, 28, 10 },
            { 28, 62, 17 }, { 78, 79, 24 }, { 42, 16, 19 }, { 22, 73, 50 }, { 62, 52, 16 },
            { 32, 57, 19 }, { 52, 58, 10 }, { 79, 68, 38 }, { 73, 33, 30 }, { 51, 44, 48 },
            { 40, 66, 21 }, { 66, 41, 34 }, { 15, 14, 9 }, { 44, 55, 26 }, { 14, 50, 8 },
            { 33, 72, 41 }, { 57, 63, 29 }, { 68, 67, 26 }, { 88, 86, 24 }, { 58, 13, 10 },
            { 23, 91, 37 }, { 20, 92, 31 }, { 74, 93, 41 }, { 23, 94, 26 }, { 50, 95, 8 },
            { 2, 96, 40 }, { 45, 97, 43 }, { 50, 98, 42 }, { 2, 99, 25 }, { 2, 100, 31 },
            { 75, 91, 21 }, { 75, 92, 35 }, { 21, 93, 34 }, { 73, 94, 46 }, { 53, 95, 21 },
            { 60, 96, 10 }, { 35, 97, 38 }, { 55, 98, 46 }, { 9, 99, 8 }, { 58, 100, 46 },
            { 1, 65, 3 }, { 1, 12, 29 }, { 1, 70, 23 }, { 2, 63, 9 }, { 2, 90, 10 }, { 5, 69, 18 },
            { 5, 87, 24 }, { 5, 15, 16 }, { 5, 75, 18 }, { 6, 24, 18 }, { 6, 55, 27 },
            { 6, 18, 31 }, { 6, 53, 48 }, { 7, 14, 48 }, { 9, 29, 40 }, { 9, 40, 11 },
            { 10, 64, 14 }, { 10, 33, 27 }, { 3, 98, 1 }, { 13, 72, 33 }, { 14, 71, 50 },
            { 14, 53, 24 }, { 15, 22, 24 }, { 17, 54, 17 }, { 18, 33, 28 }, { 18, 76, 32 },
            { 19, 42, 23 }, { 20, 22, 34 }, { 21, 67, 7 }, { 21, 53, 27 }, { 22, 19, 34 },
            { 22, 31, 3 }, { 23, 80, 39 }, { 24, 55, 25 }, { 25, 54, 9 }, { 25, 16, 34 },
            { 26, 25, 38 }, { 27, 84, 23 }, { 27, 56, 48 }, { 28, 67, 31 }, { 31, 41, 42 },
            { 31, 58, 37 }, { 34, 70, 5 }, { 37, 64, 22 }, { 37, 69, 10 }, { 38, 61, 26 },
            { 39, 13, 5 }, { 40, 89, 3 }, { 40, 41, 26 }, { 41, 67, 44 }, { 43, 85, 20 },
            { 44, 37, 47 }, { 44, 16, 7 }, { 46, 11, 6 }, { 46, 49, 44 }, { 47, 39, 38 },
            { 48, 85, 9 }, { 51, 40, 30 }, { 53, 23, 16 }, { 54, 85, 50 }, { 55, 43, 19 },
            { 55, 52, 42 }, { 56, 39, 43 }, { 56, 15, 31 }, { 58, 65, 36 }, { 58, 40, 44 },
            { 59, 90, 26 }, { 61, 25, 15 }, { 61, 39, 21 }, { 64, 81, 1 }, { 65, 41, 1 },
            { 67, 65, 14 }, { 67, 31, 40 }, { 68, 54, 40 }, { 69, 85, 49 }, { 72, 77, 5 },
            { 72, 17, 9 }, { 73, 77, 17 }, { 75, 82, 41 }, { 75, 68, 14 }, { 76, 39, 33 },
            { 77, 36, 21 }, { 77, 18, 23 }, { 78, 63, 46 }, { 78, 76, 48 }, { 84, 51, 3 },
            { 87, 73, 46 }, { 88, 63, 4 }, { 88, 53, 48 }, { 89, 87, 43 }, { 89, 29, 15 },
            { 90, 46, 46 }, { 90, 25, 38 }, { 12, 99, 30 }, { 18, 91, 39 }, { 23, 93, 30 },
            { 24, 92, 6 }, { 30, 95, 41 }, { 32, 93, 17 }, { 34, 96, 1 }, { 101, 1, 2147483647 },
            { 101, 2, 2147483647 }, { 101, 3, 2147483647 }, { 101, 4, 2147483647 },
            { 101, 5, 2147483647 }, { 101, 6, 2147483647 }, { 101, 7, 2147483647 },
            { 101, 8, 2147483647 }, { 101, 9, 2147483647 }, { 101, 10, 2147483647 },
            { 96, 102, 2147483647 }, { 97, 102, 2147483647 }, { 98, 102, 2147483647 },
            { 99, 102, 2147483647 }, { 100, 102, 2147483647 }, { 91, 102, 2147483647 },
            { 92, 102, 2147483647 }, { 93, 102, 2147483647 }, { 94, 102, 2147483647 },
            { 95, 102, 2147483647 }, };
        testDirectedUndirected(edges, 101, 102, 536, 723);
    }

    /**
     * Network generator parameters: nodeNum = 100 arcNum = 300 supply = 100 sourceNum = 10 sinkNum
     * = 10 minCap = 1 maxCap = 50 seed = 1
     */
    @Test
    public void test10()
    {
        int[][] edges = { { 1, 23, 50 }, { 2, 24, 38 }, { 3, 75, 12 }, { 4, 21, 26 }, { 5, 11, 38 },
            { 6, 56, 10 }, { 7, 76, 13 }, { 8, 34, 5 }, { 9, 18, 34 }, { 10, 43, 16 },
            { 23, 27, 9 }, { 24, 77, 8 }, { 75, 37, 12 }, { 21, 39, 10 }, { 11, 53, 21 },
            { 56, 17, 37 }, { 76, 83, 26 }, { 34, 85, 4 }, { 18, 90, 34 }, { 43, 59, 10 },
            { 27, 74, 27 }, { 77, 45, 35 }, { 37, 89, 12 }, { 39, 25, 17 }, { 53, 47, 21 },
            { 17, 60, 43 }, { 83, 69, 48 }, { 85, 61, 8 }, { 90, 71, 50 }, { 59, 38, 39 },
            { 74, 19, 36 }, { 45, 30, 46 }, { 89, 31, 12 }, { 25, 12, 9 }, { 47, 81, 34 },
            { 60, 80, 10 }, { 69, 82, 39 }, { 61, 26, 19 }, { 71, 84, 30 }, { 38, 49, 25 },
            { 19, 20, 23 }, { 30, 15, 32 }, { 31, 32, 21 }, { 12, 54, 25 }, { 81, 70, 21 },
            { 80, 29, 27 }, { 82, 36, 49 }, { 26, 64, 50 }, { 36, 35, 13 }, { 35, 87, 13 },
            { 54, 48, 9 }, { 87, 65, 19 }, { 29, 46, 37 }, { 70, 40, 37 }, { 48, 22, 45 },
            { 64, 51, 22 }, { 46, 78, 30 }, { 65, 42, 24 }, { 84, 88, 14 }, { 49, 28, 10 },
            { 28, 62, 17 }, { 78, 79, 24 }, { 42, 16, 19 }, { 22, 73, 50 }, { 62, 52, 16 },
            { 32, 57, 19 }, { 52, 58, 10 }, { 79, 68, 38 }, { 73, 33, 30 }, { 51, 44, 48 },
            { 40, 66, 21 }, { 66, 41, 34 }, { 15, 14, 9 }, { 44, 55, 26 }, { 14, 50, 8 },
            { 33, 72, 41 }, { 57, 63, 29 }, { 68, 67, 26 }, { 88, 86, 24 }, { 58, 13, 10 },
            { 23, 91, 37 }, { 20, 92, 31 }, { 74, 93, 41 }, { 23, 94, 26 }, { 50, 95, 8 },
            { 2, 96, 40 }, { 45, 97, 43 }, { 50, 98, 42 }, { 2, 99, 25 }, { 2, 100, 31 },
            { 75, 91, 21 }, { 75, 92, 35 }, { 21, 93, 34 }, { 73, 94, 46 }, { 53, 95, 21 },
            { 60, 96, 10 }, { 35, 97, 38 }, { 55, 98, 46 }, { 9, 99, 8 }, { 58, 100, 46 },
            { 1, 65, 3 }, { 2, 56, 29 }, { 2, 57, 23 }, { 2, 71, 9 }, { 2, 40, 10 }, { 2, 33, 18 },
            { 2, 34, 24 }, { 3, 23, 16 }, { 3, 24, 18 }, { 3, 74, 18 }, { 3, 22, 27 },
            { 3, 78, 31 }, { 3, 50, 48 }, { 4, 14, 48 }, { 4, 88, 40 }, { 5, 58, 11 },
            { 5, 36, 14 }, { 5, 90, 27 }, { 5, 70, 46 }, { 5, 29, 10 }, { 6, 18, 1 }, { 6, 77, 31 },
            { 6, 83, 21 }, { 7, 23, 11 }, { 7, 50, 29 }, { 7, 11, 12 }, { 8, 23, 4 }, { 8, 39, 28 },
            { 8, 81, 28 }, { 8, 14, 45 }, { 8, 77, 17 }, { 9, 61, 24 }, { 9, 41, 7 }, { 9, 57, 19 },
            { 1, 92, 6 }, { 4, 94, 10 }, { 12, 25, 38 }, { 13, 84, 23 }, { 13, 56, 48 },
            { 13, 61, 31 }, { 13, 18, 42 }, { 14, 89, 37 }, { 14, 37, 5 }, { 14, 62, 22 },
            { 15, 16, 10 }, { 15, 89, 26 }, { 15, 71, 5 }, { 15, 66, 3 }, { 16, 80, 26 },
            { 16, 71, 44 }, { 16, 17, 20 }, { 17, 37, 47 }, { 18, 29, 7 }, { 18, 78, 6 },
            { 18, 87, 44 }, { 19, 39, 38 }, { 19, 72, 9 }, { 20, 40, 30 }, { 20, 45, 16 },
            { 21, 85, 50 }, { 22, 43, 19 }, { 22, 52, 42 }, { 22, 75, 43 }, { 23, 38, 31 },
            { 23, 48, 36 }, { 23, 75, 44 }, { 24, 90, 26 }, { 24, 18, 15 }, { 25, 33, 21 },
            { 25, 11, 1 }, { 25, 35, 1 }, { 26, 65, 14 }, { 26, 31, 40 }, { 26, 36, 40 },
            { 27, 85, 49 }, { 27, 14, 5 }, { 27, 89, 9 }, { 27, 15, 17 }, { 28, 82, 41 },
            { 29, 52, 14 }, { 29, 89, 33 }, { 29, 90, 21 }, { 29, 58, 23 }, { 30, 63, 46 },
            { 30, 76, 48 }, { 30, 51, 3 }, { 30, 79, 46 }, { 31, 63, 4 }, { 31, 53, 48 },
            { 32, 87, 43 }, { 32, 29, 15 }, { 32, 34, 46 }, { 33, 90, 38 }, { 33, 80, 47 },
            { 34, 62, 7 }, { 34, 68, 6 }, { 35, 40, 50 }, { 35, 45, 12 }, { 35, 30, 13 },
            { 36, 44, 7 }, { 36, 48, 13 }, { 37, 30, 44 }, { 38, 61, 3 }, { 39, 46, 34 },
            { 39, 83, 32 }, { 39, 20, 49 }, { 40, 56, 35 }, { 40, 13, 43 }, { 40, 80, 13 },
            { 40, 14, 8 }, { 41, 59, 20 }, { 42, 40, 42 }, { 42, 90, 6 }, { 42, 45, 14 },
            { 42, 73, 36 }, { 43, 71, 17 }, { 43, 19, 10 }, { 44, 18, 49 }, { 45, 89, 37 },
            { 45, 53, 42 }, { 45, 86, 12 }, { 45, 62, 37 }, { 46, 21, 1 }, { 47, 70, 39 },
            { 47, 22, 44 }, { 48, 58, 4 }, { 48, 66, 16 }, { 48, 19, 16 }, { 49, 66, 16 },
            { 49, 44, 5 }, { 50, 39, 37 }, { 50, 29, 37 }, { 50, 38, 5 }, { 51, 80, 45 },
            { 52, 22, 17 }, { 52, 12, 20 }, { 53, 85, 50 }, { 54, 67, 43 }, { 54, 69, 50 },
            { 56, 61, 32 }, { 57, 80, 41 }, { 58, 39, 29 }, { 59, 50, 14 }, { 59, 78, 44 },
            { 59, 88, 28 }, { 59, 56, 45 }, { 61, 74, 49 }, { 61, 67, 28 }, { 61, 90, 24 },
            { 62, 66, 26 }, { 62, 53, 1 }, { 62, 68, 7 }, { 63, 33, 1 }, { 63, 21, 49 },
            { 63, 70, 41 }, { 64, 89, 19 }, { 64, 28, 5 }, { 65, 58, 43 }, { 65, 43, 35 },
            { 66, 58, 12 }, { 66, 63, 21 }, { 66, 39, 23 }, { 67, 59, 43 }, { 68, 19, 39 },
            { 68, 54, 21 }, { 69, 87, 13 }, { 69, 77, 6 }, { 69, 59, 36 }, { 69, 23, 8 },
            { 70, 54, 16 }, { 71, 90, 37 }, { 71, 79, 32 }, { 71, 23, 28 }, { 71, 68, 21 },
            { 72, 85, 13 }, { 72, 43, 44 }, { 73, 57, 32 }, { 74, 78, 29 }, { 16, 99, 34 },
            { 17, 93, 13 }, { 21, 92, 11 }, { 22, 97, 29 }, { 24, 99, 45 }, { 26, 96, 2 },
            { 27, 93, 40 }, { 28, 95, 33 }, { 29, 98, 12 }, { 30, 93, 15 }, { 31, 99, 32 },
            { 34, 100, 36 }, { 36, 99, 5 }, { 39, 98, 38 }, { 40, 99, 10 }, { 41, 91, 15 },
            { 42, 91, 31 }, { 44, 91, 16 }, { 45, 99, 19 }, { 47, 92, 33 }, { 50, 99, 20 },
            { 51, 93, 13 }, { 101, 1, 2147483647 }, { 101, 2, 2147483647 }, { 101, 3, 2147483647 },
            { 101, 4, 2147483647 }, { 101, 5, 2147483647 }, { 101, 6, 2147483647 },
            { 101, 7, 2147483647 }, { 101, 8, 2147483647 }, { 101, 9, 2147483647 },
            { 101, 10, 2147483647 }, { 96, 102, 2147483647 }, { 97, 102, 2147483647 },
            { 98, 102, 2147483647 }, { 99, 102, 2147483647 }, { 100, 102, 2147483647 },
            { 91, 102, 2147483647 }, { 92, 102, 2147483647 }, { 93, 102, 2147483647 },
            { 94, 102, 2147483647 }, { 95, 102, 2147483647 } };
        testDirectedUndirected(edges, 101, 102, 906, 1081);
    }

    @Override
    MaximumFlowAlgorithm<Integer, DefaultWeightedEdge> createSolver(
        Graph<Integer, DefaultWeightedEdge> network)
    {
        return new BoykovKolmogorovMFImpl<>(network);
    }
}
