FordFulkerson

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
import java.util.stream.Collectors;
import jdk.management.resource.ResourceType;



class FordFulkerson<E extends Comparable<E>>{

    class BFS_FF<E extends Comparable<E>>{

    public void run(Graph<E> g,E startingNode,boolean resetVisited){
        Hashtable<Vertex<E>, List<Edge<E>>> table = g.getHashtableOutEdges();

        if (resetVisited){
            for(Vertex<E> vertex : g.getVertices()){
               vertex.setVisited(false);
            }
        }

        for(Vertex<E> vertex : g.getVertices()){
            vertex.setMinDistance(Double.MAX_VALUE);
        }

        Vertex<E> node = g.getVertex(startingNode);
        node.setMinDistance(0);
        node.setVisited(true);
        node.setMaxFlow(Double.MAX_VALUE);
        Queue<Vertex<E>> q = new LinkedList<>();
        q.offer(node);

        while(!q.isEmpty()){
            Vertex<E> currentNode = q.poll();

            List<Vertex<E>> adjNodes = new ArrayList<>();
            for (Edge<E> edge : table.get(currentNode)){
                if (edge.getTransferable() > 0d){
                    adjNodes.add(edge.getDestination());
                }
            }

            for (Vertex<E> ver : adjNodes){
                if (!ver.isVisited()){
                    ver.setPredecessor(currentNode);
                    ver.setMinDistance(currentNode.getMinDistance() + 1);
                    ver.setVisited(true);
                    ver.setMaxFlow(Math.min(currentNode.getMaxFlow(), g.getEdgeBetween(currentNode.getData(), ver.getData()).getTransferable()));
                    q.offer(ver);
                }
            }
        }
    }
  }
    public double run(Graph<E> graph,Vertex<E> startingNode,Vertex<E> endNode){
        BFS_FF bfs = new BFS_FF();
        double result = 0d;
        while (true){
            bfs.run(graph, startingNode.getData(),true);
            if (endNode.getMinDistance() == Double.MAX_VALUE){
                return result;
            }
            double maxFlow = endNode.getMaxFlow();
            List<Vertex<E>> vertices = new ArrayList<>();
            Vertex<E> temp = endNode;
            //System.out.println("Predecessors");
            while(temp.hasPredecessor()){
                //System.out.println(temp);
                vertices.add(temp);
                temp = temp.getPredecessor();
            }
            vertices.add(temp);

            Collections.reverse(vertices);

            for (int i = 0; i < vertices.size() - 1; i++){
                Edge<E> edge = graph.getEdgeBetween(vertices.get(i), vertices.get(i + 1));
                edge.decreaseTransferable(maxFlow);
            }
            //System.out.println("Patot e " + vertices);
            //System.out.println("maxFlow " + maxFlow);
            result += maxFlow;
        }
    }
}

class DFS<E extends Comparable<E>>{
    int time;
    public DFS(){
         time = 0;
    }

    private void visit(Vertex<E> u,Hashtable<Vertex<E>,List<Edge<E > > > table){
        u.setColor(Color.GRAY);
        time++;
        u.setTimeVisited(time);

        Set<Vertex<E>> adjVertices = new HashSet<>();
        List<Edge<E>> adj = table.get(u);
        for (Edge<E> edge : adj){
            adjVertices.add(edge.getDestination());
        }

        for (Vertex<E> ver : adjVertices){
            if (ver.getColor() == Color.WHITE){
                ver.setPredecessor(u);
                ver.setMinDistance(u.getMinDistance() + 1);
                visit(ver,table);
            }
        }
        u.setColor(Color.BLACK);
        time++;
        u.setTimeFinished(time);
    }
    public void run(Graph<E> g){
        this.time = 0;
        Hashtable<Vertex<E>,List<Edge<E>>> table = g.getHashtableOutEdges();

        List<Vertex<E>> vertices = new ArrayList<>();
        vertices = g.getVertices();

        for(Vertex<E> vertex : vertices){
            vertex.setColor(Color.WHITE);
            vertex.setMinDistance(0d);
            vertex.setPredecessor(null);
        }

        for (Vertex<E> vertex : vertices){
            if (vertex.getColor() == Color.WHITE){
                visit(vertex,table);
            }
        }
    }
}

class BFS<E extends Comparable<E>>{

    public void run(Graph<E> g,E startingNode,boolean resetVisited){
        Hashtable<Vertex<E>, List<Edge<E>>> table = g.getHashtableOutEdges();

        if (resetVisited){
            for(Vertex<E> vertex : g.getVertices()){
               vertex.setVisited(false);
            }
        }

        for(Vertex<E> vertex : g.getVertices()){
            vertex.setMinDistance(Double.MAX_VALUE);
        }

        Vertex<E> node = g.getVertex(startingNode);
        node.setMinDistance(0);
        node.setVisited(true);
        Queue<Vertex<E>> q = new LinkedList<>();
        q.offer(node);

        while(!q.isEmpty()){
            Vertex<E> currentNode = q.poll();

            List<Vertex<E>> adjNodes = new ArrayList<>();
            for (Edge<E> edge : table.get(currentNode)){
                adjNodes.add(edge.getDestination());
            }

            for (Vertex<E> ver : adjNodes){
                if (!ver.isVisited()){
                    ver.setPredecessor(currentNode);
                    ver.setMinDistance(currentNode.getMinDistance() + 1);
                    ver.setVisited(true);
                    q.offer(ver);
                }
            }
        }
    }


}

enum Color{
    UNDEFINED,
    WHITE,
    GRAY,
    BLACK
}
class Vertex<E extends Comparable<E>> implements Comparable<Vertex<E>>{
    private E data;
    private double minDistance;
    private Vertex predecessor;
    private Color color;
    private Integer timeVisited;
    private Integer timeFinished;
    boolean visited;
    double maxFlow;

    public double getMaxFlow() {
        return maxFlow;
    }

    public void setMaxFlow(double maxFlow) {
        this.maxFlow = maxFlow;
    }

    public boolean isVisited() {
        return visited;
    }

    public void setVisited(boolean visited) {
        this.visited = visited;
    }

    public Vertex(E data){
        this.data = data;
        this.minDistance = Double.MAX_VALUE;
        this.predecessor = null;
        color = Color.UNDEFINED;
        timeVisited = null;
        timeFinished = null;
        visited = false;
        maxFlow = 0d;
    }

    public Integer getTimeVisited() {
        return timeVisited;
    }

    public void setTimeVisited(Integer timeVisited) {
        this.timeVisited = timeVisited;
    }

    public Integer getTimeFinished() {
        return timeFinished;
    }

    public void setTimeFinished(Integer timeFinished) {
        this.timeFinished = timeFinished;
    }

    public Color getColor() {
        return color;
    }

    public void setColor(Color color) {
        this.color = color;
    }

    public boolean hasPredecessor(){
        return this.predecessor != null;
    }

    public double getMinDistance() {
        return minDistance;
    }

    public void setMinDistance(double minDistance) {
        this.minDistance = minDistance;
    }

    public Vertex<E> getPredecessor() {
        return predecessor;
    }

    public void setPredecessor(Vertex predecessor) {
        this.predecessor = predecessor;
    }

    public E getData() {
        return data;
    }

    public void setData(E data) {
        this.data = data;
    }

    @Override
    public int compareTo(Vertex<E> v) {
        return Double.compare(minDistance, v.getMinDistance());
    }

    @Override
    public int hashCode() {
        int hash = 3;
        hash = 29 * hash + Objects.hashCode(this.data);
        return hash;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }
        if (obj == null) {
            return false;
        }
        if (getClass() != obj.getClass()) {
            return false;
        }
        final Vertex<E> other = (Vertex<E>) obj;
        if (!this.data.equals(other.data)) {
            return false;
        }
        return true;
    }

    @Override
    public String toString(){
      return "Vertex " + this.getData();
    }

    public String toStringMoreInfo(){
          StringBuilder sb = new StringBuilder();
        sb.append("Vertex with data: ")
                .append(this.data)
                .append(" minDist: ");
        if (this.minDistance == Double.MAX_VALUE || this.minDistance == Double.MAX_VALUE / 2){
            sb.append("INF");
        }else{
                sb.append(this.minDistance);
        }

        sb.append("\tvisited: " + timeVisited + " - left: " + timeFinished);
        sb.append("  COLOR: " + this.color);
        return sb.toString();
    }

}

class Edge<E extends Comparable<E>> implements Comparable<Edge<E>>{
    private Vertex<E> source;
    private Vertex<E> destination;
    private double weight;
    private double transferable;


    public Edge(Vertex<E> source, Vertex<E> destination, double weight) {
        this.source = source;
        this.destination = destination;
        this.weight = weight;
        this.transferable = weight;
    }

    public double getTransferable() {
        return transferable;
    }

    public void setTransferable(double transferable) {
        this.transferable = transferable;
    }

    public void decreaseTransferable(double amount){
        this.transferable -= amount;
    }

    public Vertex<E> getSource() {
        return source;
    }

    public void setSource(Vertex<E> source) {
        this.source = source;
    }

    public Vertex<E> getDestination() {
        return destination;
    }

    public void setDestination(Vertex<E> destination) {
        this.destination = destination;
    }

    public double getWeight() {
        return weight;
    }

    public void setWeight(double weight) {
        this.weight = weight;
    }

    public void changeDirection(){
        Vertex<E> source = this.getSource();
        Vertex<E> destination = this.getDestination();

        this.setDestination(source);
        this.setSource(destination);
    }
    @Override
    public String toString(){
        StringBuilder sb = new StringBuilder();
        sb.append("Edge from: ")
                .append(this.source.getData())
                .append("\tto: ")
                .append(this.destination.getData())
                .append("\twith weight: " + this.weight);
        return sb.toString();
    }

    @Override
    public int compareTo(Edge<E> edge) {
        return Double.compare(this.weight, edge.weight);
    }

    @Override
    public int hashCode() {
        int hash = 7;
        hash = 97 * hash + Objects.hashCode(this.source);
        hash = 97 * hash + Objects.hashCode(this.destination);
        hash = 97 * hash + (int) (Double.doubleToLongBits(this.weight) ^ (Double.doubleToLongBits(this.weight) >>> 32));
        return hash;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }
        if (obj == null) {
            return false;
        }
        if (getClass() != obj.getClass()) {
            return false;
        }
        final Edge<?> other = (Edge<?>) obj;

        if (!Objects.equals(this.source, other.source)) {
            return false;
        }
        if (!Objects.equals(this.destination, other.destination)) {
            return false;
        }
        return true;
    }




}

class Graph<E extends Comparable<E>>{

    List<Vertex<E>> vertices;
    List<Edge<E>> edges;
    Map<E,Integer> indexes; // E( name of the vertex) -> Integer (position in list vertices)
    Map<String,Edge<E>> hashedEdges;

    public Graph(){
        vertices = new ArrayList<>();
        edges = new ArrayList<>();
        indexes = new HashMap<>();
        hashedEdges = new HashMap<>();
    }

    public void addVertex(E data){
        Vertex<E> vertex = new Vertex<>(data);
        vertices.add(vertex);
        int index = vertices.size() - 1;
        indexes.put(data, index);
    }
    public boolean removeVertex(E data){
        Vertex<E> v = new Vertex<>(data);
        if (vertices.contains(v)){
            Vertex<E> vertexToRemove = this.getVertex(data);
            vertices.remove(vertexToRemove);
            for (int i = 0; i < this.edges.size(); i++){
                if (edges.get(i).getSource().equals(vertexToRemove) || edges.get(i).getDestination().equals(vertexToRemove)){
                    this.edges.remove(edges.get(i));
                    i--;
                }
            }
            return true;
        }
        return false;
    }

    public Vertex<E> getVertex(E data){
       return vertices.get(indexes.get(data));
    }

    private boolean addEdge(Vertex<E> source,Vertex<E> destination,double weight){
        Edge<E> edge = new Edge<E>(source,destination,weight);
        hashedEdges.put(source.getData() + "-" + destination.getData(),edge);
        return edges.add(edge);
    }

    public boolean removeDirectedEdge(Edge<E> edge){
        return edges.remove(edge);
    }
    public boolean removeUndirectedEdge(Edge<E> edge){
        Edge<E> secondEdge = new Edge<>(edge.getDestination(),edge.getSource(),edge.getWeight());
        return edges.remove(edge) && edges.remove(secondEdge);
    }

    public boolean addDirectedEdge(E source,E destination,double weight){
        Vertex<E> s = vertices.get(indexes.get(source));
        Vertex<E> d = vertices.get(indexes.get(destination));
        return addEdge(s,d,weight);
    }
    public boolean addUndirectedEdge(E source,E destination,double weight){
        Vertex<E> s = vertices.get(indexes.get(source));
        Vertex<E> d = vertices.get(indexes.get(destination));

        return addEdge(s,d,weight) && addEdge(d,s,weight);
    }

    public List<Vertex<E>> getVertices(){
        return this.vertices;
    }

    public List<Edge<E>> getEdges(){
        return this.edges;
    }

    public Edge<E> getEdgeBetween(E source,E destination){
        return hashedEdges.get(source + "-" + destination);
    }
    public Edge<E> getEdgeBetween(Vertex<E> source,Vertex<E> destination){
        return getEdgeBetween(source.getData(),destination.getData());
    }

    @Override
    public String toString(){
        StringBuilder sb = new StringBuilder();
        sb.append("Vertices:\n");
        for (Vertex<E> v : this.getVertices()){
            sb.append(v.toString() + "\n");
        }

        sb.append("\n").append("Edges:\n");
        for (Edge<E> e : this.getEdges()){
            sb.append(e.toString()).append("\n");
        }

        return sb.toString();
    }


    /**
     * Hashtable of Node and list of Edges that start from Node
     *
     * @return Hashtable
     */
    public Hashtable<Vertex<E>, List<Edge<E> > > getHashtableOutEdges(){
        Hashtable<Vertex<E>, List<Edge<E> > > table = new Hashtable<>();
        List<Edge<E>> lst;
        for (Vertex<E> v : this.vertices){
            lst = new LinkedList<>();
            table.put(v,lst);
        }

        for (Edge<E> e : this.edges){
            table.get(e.getSource()).add(e);
        }

        return table;
    }

     /**
     *
     * Hashtable of Node and list of Edges that go in Node
     *
     * @return Hashtable<Node,Edges that go in Node>
     */

    public Hashtable<Vertex<E>, List<Edge<E> > > getHashtableInEdges(){
        Hashtable<Vertex<E>, List<Edge<E> > > table = new Hashtable<>();
        List<Edge<E>> lst;
        for (Vertex<E> v : this.vertices){
            lst = new LinkedList<>();
            table.put(v,lst);
        }

        for (Edge<E> e : this.edges){
            table.get(e.getDestination()).add(e);
        }

        return table;
    }

    public double[][] getAdjMatrix(){
        int N = vertices.size();
        double[][] matrix = new double[N][N];
        for (int i = 0; i < N; i++){
            for (int j = 0; j < N; j++){
                    matrix[i][j] = Double.MAX_VALUE;
            }
        }
        List<Edge<E>> egdes = this.getEdges();
        for (Edge<E> e : edges){
            matrix[indexes.get(e.getSource().getData())][indexes.get(e.getDestination().getData())] = e.getWeight();
        }
        return matrix;
    }

}

public class Main{

 public static void main(String[] args){
     Graph<String> g = new Graph<>();

     g.addVertex("S");
     g.addVertex("A");
     g.addVertex("B");
     g.addVertex("T");

     g.addDirectedEdge("S", "A", 2);
     g.addDirectedEdge("A", "T", 4);
     g.addDirectedEdge("A", "B", 1);
     g.addDirectedEdge("S", "B", 5);
     g.addDirectedEdge("B", "T", 3);


     FordFulkerson<String> fordFulkerson = new FordFulkerson<>();
     System.out.println(fordFulkerson.run(g, g.getVertex("S"), g.getVertex("T")));


    }
}