Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

CapacityScalingMinimumCostFlow using the edge weight of the graph as arc costs instead of the getArcCosts() function of the MinimumCostFlowProblem #1139

Open
MarcTM01 opened this issue Dec 11, 2022 · 0 comments

Comments

@MarcTM01
Copy link

 * JGraphT version: 1.5.1
 * Java version (java -version)/platform: OpenJDK 17

Issue
I was just using the CapacityScalingMinimumCostFlow implementation to compute a minimum cost flow of a graph. Since the problem declaration interfaceMinimumCostFlowProblem supports a getArcCosts() function I assumed that this function is the one being used to calculate the cost of an arc. But as it turns out, the CapacityScalingMinimumCostFlow implementation uses the edge weight of the graph even if such a function is supplied. I think this might be undesirable.

Steps to reproduce (small coding example)

public class SampleCode {
    public static void main(String[] args) {
        Graph<Integer, DefaultWeightedEdge> graph = new DefaultDirectedWeightedGraph<>(DefaultWeightedEdge.class);

        // Create a simple graph 1 ----10----> 2
        graph.addVertex(1);
        graph.addVertex(2);

        DefaultWeightedEdge edge = graph.addEdge(1, 2);
        graph.setEdgeWeight(edge, 10);

        // Create a MinCostMaxFlow problem instance
        MinimumCostFlowProblem<Integer, DefaultWeightedEdge> flowProblem = new MinimumCostFlowProblem.MinimumCostFlowProblemImpl<>(
                graph,
                (Integer v) -> v == 1 ? 1 : -1,   // B-Values (send 1 unit from 1 to 2)
                (DefaultWeightedEdge e) -> 1,     // Arc capacity upper bound
                (DefaultWeightedEdge e) -> 0,     // Arc capacity lower bound
                (DefaultWeightedEdge e) -> 20.    // Arc cost override (not working)
        );

        CapacityScalingMinimumCostFlow<Integer, DefaultWeightedEdge> solver = new CapacityScalingMinimumCostFlow<>();
        MinimumCostFlowAlgorithm.MinimumCostFlow<DefaultWeightedEdge> minCostFlow = solver.getMinimumCostFlow(flowProblem);

        // The Min Cost Flow should have cost 20
        if (Math.abs(minCostFlow.getCost() - 20.0) > 0.000001d) {
            throw new RuntimeException("Expected min cost flow of 20.0 but got " + minCostFlow.getCost());
        }
    }
}

Expected behaviour
The CapacityScalingMinimumCostFlow algorithm should use the getArcCosts() function instead of the graph getEdgeWeight() function to obtain arc costs. Not supplying the getArcCost() function still defaults to the edge weight in the default implementation of the interface. So this should not be a breaking change.

Other information
I am no JGraphT veteran. I just recently started using this library. So it could very well be that I am completely missing something here. I'm curious about your thoughts.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant