You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
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
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.
The text was updated successfully, but these errors were encountered:
Issue
I was just using the
CapacityScalingMinimumCostFlow
implementation to compute a minimum cost flow of a graph. Since the problem declaration interfaceMinimumCostFlowProblem
supports agetArcCosts()
function I assumed that this function is the one being used to calculate the cost of an arc. But as it turns out, theCapacityScalingMinimumCostFlow
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)
Expected behaviour
The CapacityScalingMinimumCostFlow algorithm should use the
getArcCosts()
function instead of the graphgetEdgeWeight()
function to obtain arc costs. Not supplying thegetArcCost()
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.
The text was updated successfully, but these errors were encountered: