Question: I am implementing a scalingFordFulkerson Algorithm, however i need help with this error and how to solve it when input a graph i should get

I am implementing a scalingFordFulkerson Algorithm, however i need help with this error and how to solve it when input a graph i should get the maxflow and the run time. java code
ResidualGrappBuilder.java code
import graphCode.Edge;
import graphCode.SimpleGraph;
import graphCode.Vertex;
import java.util.Iterator;
public class ResidualGraphBuilder {
public static SimpleGraph build(SimpleGraph graph, Vertex source, Vertex sink, double scalingFactor){
SimpleGraph residualGraph = new SimpleGraph();
VertexAttributes sourceData = new VertexAttributes(true);
source.setData(sourceData);
residualGraph.getVertexList().add(source);
for (Iterator edgeIter = source.getIncidentEdgeList().iterator(); edgeIter.hasNext(); ){
Edge edge =(Edge) edgeIter.next();
Vertex neighbor = graph.opposite(source, edge);
//error is on this line
if (isEligibleEdge(neighbor, edge, scalingFactor)){
residualGraph.getEdgeList().add(edge);
residualGraph.getVertexList().add(neighbor);
if (neighbor == sink){
return residualGraph;
}
SimpleGraph subGraph = build(graph, neighbor, sink, scalingFactor);
if (subGraph.getVertexList().getLast()== sink){
return subGraph;
}
residualGraph.getEdgeList().removeLast();
}
}
residualGraph.getVertexList().removeLast();
return residualGraph;
}
private static boolean isEligibleEdge(Vertex neighbor, Edge edge, double scalingFactor){
VertexAttributes neighborData =(VertexAttributes) neighbor.getData();
EdgeAttributes edgeAttributes =(EdgeAttributes) edge.getData();
//error in the line below
boolean notVisited =!neighborData.isVisited();
boolean hasResidualCapacity = edgeAttributes.getResidualCapacity()>= scalingFactor;
boolean hasBackwardFlow = edgeAttributes.getCurrentFlow()>= scalingFactor;
return notVisited && (hasResidualCapacity || hasBackwardFlow);
}
}
main.java
public static double calculateMaxFlow(SimpleGraph graph, Vertex source, Vertex sink){
double totalFlow =0; // Total flow
double maxCapacity = GraphUtils.findMaxEdgeCapacity(graph); // Find max edge capacity
double scalingFactor = GraphUtils.findInitialScalingFactor(graph, source); // Start with highest power of 2
// Process scaling levels
while (scalingFactor >=1){
// Build the residual graph for the current scaling level
//Error here
SimpleGraph residualGraph = ResidualGraphBuilder.build(graph, source, sink, scalingFactor);
// Augment flow while paths exist
while (residualGraph.numEdges()>0){
double flowToAdd = PathProcessor.processAugmentingPath(residualGraph, source);
totalFlow += flowToAdd; // Update total flow
PathProcessor.updateOriginalGraph(graph, residualGraph, flowToAdd);
residualGraph = ResidualGraphBuilder.build(graph, source, sink, 0); // Rebuild residual graph
}
// Halve the scaling factor
scalingFactor /=2;
}
return totalFlow;
}
}
Vertex Attributes.java file
package scalingFlowAlgorithm;
public class VertexAttributes {
private boolean visited;
public VertexAttributes(){
this.visited = false;
}
public VertexAttributes(boolean visited){
this.visited = visited;
}
public boolean isVisited(){
return visited;
}
public void setVisited(boolean visited){
this.visited = visited;
}
}
error snip
Error snip
I am implementing a scalingFordFulkerson

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Programming Questions!