Implement Ford-Fulkerson Algorithm for Maximum Flow

sr-tester / gralog

Visualize Graphs, Algorithms, Logics and Games

GNU General Public License v3.0

0 stars 0 forks source link

Implement Ford-Fulkerson Algorithm for Maximum Flow #5

Open sweep-ai[bot] opened 1 year ago

sweep-ai[bot] commented 1 year ago

PR Feedback: 👎

Description

This PR implements the Ford-Fulkerson algorithm for maximum flow in a network. The algorithm is added as a new class, FordFulkersonAlgorithm, in the gralog.algorithm package. The implementation includes visual indications of flows, capacities on each edge, direction of flow, concept of cuts, and the variation of these elements during each iteration of the algorithm. The algorithm utilizes the existing graph visualization capabilities provided by the Gralog project.

Summary of Changes

Created a new class FordFulkersonAlgorithm in the gralog.algorithm package.
Extended the Algorithm superclass and implemented the Ford-Fulkerson algorithm in the FordFulkersonAlgorithm class.
Added an AlgorithmDescription annotation to provide detailed information about the Ford-Fulkerson algorithm.
Modified the Algorithm.java class to include a case for FordFulkersonAlgorithm in the getAlgorithm method.
Modified the AlgorithmDescription.java class to include a case for FordFulkersonAlgorithm in the getDescription method.

Please review and merge this PR to incorporate the Ford-Fulkerson algorithm functionality into the Gralog project.

Fixes #4.

🎉 Latest improvements to Sweep:

Sweep can now passively improve your repository! Check out Rules to learn more.

💡 To get Sweep to edit this pull request, you can:

Comment below, and Sweep can edit the entire PR
Comment on a file, Sweep will only modify the commented file
Edit the original issue to get Sweep to recreate the PR from scratch

sweep-ai[bot] commented 1 year ago

Sandbox Executions

[X] Check gralog-core/src/main/java/gralog/algorithm/FordFulkersonAlgorithm.java ✓

Sandbox logs for

trunk fmt gralog-core/src/main/java/gralog/algorithm/FordFulkersonAlgorithm.java || exit 0 1/2 ✓
Found no applicable linters for the requested path
trunk check --fix --print-failures gralog-core/src/main/java/gralog/algorithm/FordFulkersonAlgorithm.java 2/2 ✓
Checked 1 file
✔ No issues
Run trunk upgrade to upgrade 1 linter

[X] Check gralog-core/src/main/java/gralog/algorithm/Algorithm.java ✓

Sandbox logs for

trunk fmt gralog-core/src/main/java/gralog/algorithm/Algorithm.java || exit 0 1/2 ✓
Found no applicable linters for the requested path
trunk check --fix --print-failures gralog-core/src/main/java/gralog/algorithm/Algorithm.java 2/2 ✓
Checked 1 file
✔ No issues
Run trunk upgrade to upgrade 1 linter

[X] Check gralog-core/src/main/java/gralog/algorithm/AlgorithmDescription.java ✗
Run gralog-core/src/main/java/gralog/algorithm/AlgorithmDescription.java through the sandbox.

sweep-ai[bot] commented 1 year ago

Apply Sweep Rules to your PR?

[ ] Apply: All new business logic should have corresponding unit tests in the tests/ directory.
[ ] Apply: Any clearly inefficient or repeated code should be optimized or refactored.

sr-tester commented 1 year ago

We have encountered some compilation errors in our code of the Ford-Fulkerson algorithm implementation, specifically in the 'FordFulkersonAlgorithm' class within the 'gralog.algorithm' package. All errors seem to be related to the use of certain methods that may not exist or have different argument requirements.

Here are the methods causing the errors:

getEdges(node): This method invocation in the findAugmentingPath method seems to require no arguments in class Structure<V,E>, but in the existing code a 'node' argument is given. We need to find a way to get all edges of a given node correctly.
getOtherEndpoint(node): This method invocation in both the findAugmentingPath and updateResidualGraph methods results in a 'cannot find symbol' error. We need to find an alternative way to get the other endpoint of an edge connected to a given node.
getCapacity(): This method invocation again results in a 'cannot find symbol' error. Check the Edge class to find the correct method to retrieve the capacity of an edge.

The requisite changes need to be made to make the code compile as expected. Sweep should suggest adjustments to the current problematic invocations or alternative methods to achieve the same functionality.

This may require a detailed examination of the 'Structure' and 'Edge' classes inside the 'gralog.structure' package to ensure compatibility and proper functionality. The updated code should not disrupt the intended functionality and follow standard conventions.

Sweep, please provide a pull request solving these issues and making the Ford-Fulkerson Algorithm runnable.

sweep-ai[bot] commented 1 year ago

🚀 Wrote Changes

Done.

sr-tester commented 1 year ago

Fix te follwoing issue: "

Task :gralog-core:compileJava FAILED C:\Users\sreeg\OneDrive\Desktop\gralog-master\gralog-core\src\main\java\gralog\algorithm\FordFulkersonAlgorithm.java:37: error: cannot find symbol for (Edge edge : structure.getIncidentEdges(node)) { ^ symbol: method getIncidentEdges(Vertex) location: variable structure of type Structure C:\Users\sreeg\OneDrive\Desktop\gralog-master\gralog-core\src\main\java\gralog\algorithm\FordFulkersonAlgorithm.java:39: error: cannot find symbol if (!parent.containsKey(neighbour) && edge.getWeight() > 0) { ^ symbol: method getWeight() location: variable edge of type Edge C:\Users\sreeg\OneDrive\Desktop\gralog-master\gralog-core\src\main\java\gralog\algorithm\FordFulkersonAlgorithm.java:54: error: cannot find symbol pathCapacity = Math.min(pathCapacity, augmentingPath.get(node).getWeight()); ^ symbol: method getWeight() location: class Edge C:\Users\sreeg\OneDrive\Desktop\gralog-master\gralog-core\src\main\java\gralog\algorithm\FordFulkersonAlgorithm.java:62: error: cannot find symbol edge.setWeight(edge.getWeight() - pathCapacity); ^ symbol: method getWeight() location: variable edge of type Edge C:\Users\sreeg\OneDrive\Desktop\gralog-master\gralog-core\src\main\java\gralog\algorithm\FordFulkersonAlgorithm.java:63: error: cannot find symbol Edge reverseEdge = edge.getReverseEdge(); ^ symbol: method getReverseEdge() location: variable edge of type Edge C:\Users\sreeg\OneDrive\Desktop\gralog-master\gralog-core\src\main\java\gralog\algorithm\FordFulkersonAlgorithm.java:65: error: cannot find symbol reverseEdge.setCapacity(reverseEdge.getCapacity() + pathCapacity); ^ symbol: method getCapacity() location: variable reverseEdge of type Edge Note: Some input files use or override a deprecated API. Note: Recompile with -Xlint:deprecation for details. Note: Some input files use unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details. 6 errors

FAILURE: Build failed with an exception.

What went wrong: Execution failed for task ':gralog-core:compileJava'. "

sweep-ai[bot] commented 1 year ago

🚀 Wrote Changes

Done.

sr-tester commented 1 year ago

C:\Users\sreeg\OneDrive\Desktop\gralog-master\gralog-core\src\main\java\gralog\structure\Edge.java:760: error: class, interface, or enum expected public double getWeight() { ^ C:\Users\sreeg\OneDrive\Desktop\gralog-master\gralog-core\src\main\java\gralog\structure\Edge.java:762: error: class, interface, or enum expected } ^ C:\Users\sreeg\OneDrive\Desktop\gralog-master\gralog-core\src\main\java\gralog\structure\Edge.java:764: error: class, interface, or enum expected public void setWeight(double weight) { ^ C:\Users\sreeg\OneDrive\Desktop\gralog-master\gralog-core\src\main\java\gralog\structure\Edge.java:766: error: class, interface, or enum expected } ^ C:\Users\sreeg\OneDrive\Desktop\gralog-master\gralog-core\src\main\java\gralog\structure\Edge.java:768: error: class, interface, or enum expected public Edge getReverseEdge() { ^ C:\Users\sreeg\OneDrive\Desktop\gralog-master\gralog-core\src\main\java\gralog\structure\Edge.java:770: error: class, interface, or enum expected reverseEdge.setSource(this.target); ^ C:\Users\sreeg\OneDrive\Desktop\gralog-master\gralog-core\src\main\java\gralog\structure\Edge.java:771: error: class, interface, or enum expected reverseEdge.setTarget(this.source); ^ C:\Users\sreeg\OneDrive\Desktop\gralog-master\gralog-core\src\main\java\gralog\structure\Edge.java:772: error: class, interface, or enum expected reverseEdge.setWeight(this.weight); ^ C:\Users\sreeg\OneDrive\Desktop\gralog-master\gralog-core\src\main\java\gralog\structure\Edge.java:773: error: class, interface, or enum expected return reverseEdge; ^ C:\Users\sreeg\OneDrive\Desktop\gralog-master\gralog-core\src\main\java\gralog\structure\Edge.java:774: error: class, interface, or enum expected } ^ C:\Users\sreeg\OneDrive\Desktop\gralog-master\gralog-core\src\main\java\gralog\structure\Edge.java:776: error: class, interface, or enum expected public double getCapacity() { ^ C:\Users\sreeg\OneDrive\Desktop\gralog-master\gralog-core\src\main\java\gralog\structure\Edge.java:779: error: class, interface, or enum expected } ^ 12 errors

FAILURE: Build failed with an exception.

What went wrong: Execution failed for task ':gralog-core:compileJava'.

sweep-ai[bot] commented 1 year ago

🚀 Wrote Changes

Done.