Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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 void run(Graph<E> graph,Vertex<E> startingNode){
- }
- }
- }
- 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);
- }
- @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 class Main{
- public static void main(String[] args){
- Graph<String> g = new Graph<>();
- g.addVertex("A");
- g.addVertex("B");
- g.addVertex("C");
- g.addVertex("D");
- g.addVertex("E");
- g.addVertex("F");
- g.addVertex("G");
- g.addVertex("H");
- g.addDirectedEdge("B", "E", 1);
- g.addDirectedEdge("E", "F", 1);
- g.addDirectedEdge("E", "G", 1);
- g.addDirectedEdge("E", "H", 1);
- g.addDirectedEdge("A", "B", 1);
- g.addDirectedEdge("A", "C", 1);
- g.addDirectedEdge("A", "F", 1);
- g.addDirectedEdge("F", "G", 1);
- g.addDirectedEdge("C", "D", 1);
- g.addDirectedEdge("D", "H", 1);
- g.addDirectedEdge("H", "G", 1);
- g.addUndirectedEdge("H", "G", 2);
- System.out.println(g);
- g.removeUndirectedEdge(new Edge<String>(g.getVertex("B"),g.getVertex("E"),1));
- System.out.println(g);
- /* Graph<String> graph = new Graph<>();
- graph.addVertex("C");
- graph.addVertex("B");
- graph.addVertex("A");
- graph.addVertex("D");
- graph.addVertex("E");
- graph.addVertex("F");
- graph.addVertex("G");
- graph.addVertex("H");
- graph.addVertex("I");
- graph.addVertex("J");
- graph.addDirectedEdge("I", "C", 1);
- graph.addDirectedEdge("J", "E", 1);
- graph.addDirectedEdge("D", "I", 1);
- graph.addDirectedEdge("D", "C", 1);
- graph.addDirectedEdge("A", "B", 1);
- graph.addDirectedEdge("B", "A", 1);
- graph.addDirectedEdge("D", "B", 1);
- System.out.println(graph.getHashtableInEdges());
- System.out.println(graph.getHashtableOutEdges()); */
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement