School/Anul 1/Semestrul 2/Graph Algo/Labs/Lab 4/DirectedGraphJava/DirectedGraph.java

package DirectedGraphJava;

import java.util.HashSet;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Queue;
import java.util.Set;
import java.util.LinkedList;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Stack;

import javax.swing.event.InternalFrameAdapter;

public class DirectedGraph implements IDirectedGraph {
    private HashSet<Integer> _vertices = new HashSet<Integer>();
    private HashMap<Integer, HashSet<Integer>> _inbounds = new HashMap<Integer, HashSet<Integer>>();
    private HashMap<Integer, HashSet<Integer>> _outbounds = new HashMap<Integer, HashSet<Integer>>();
    private HashMap<Pair<Integer,Integer>,Integer> _edges = new HashMap<Pair<Integer,Integer>,Integer>();
    
    public DirectedGraph() {
        //nothing to do
    }

    public DirectedGraph reindex(){
        HashMap<Integer,Integer> oldToNew = new HashMap<Integer,Integer>();
        int i = 0;
        for (Integer vertex : _vertices) {
            oldToNew.put(vertex,i);
            i++;
        }
        DirectedGraph newGraph = new DirectedGraph();
        for (Integer vertex : _vertices) {
            newGraph.addVertex(oldToNew.get(vertex));
        }
        for (Pair<Integer,Integer> edge : _edges.keySet()) {
            newGraph.addEdge(oldToNew.get(edge.first),oldToNew.get(edge.second),_edges.get(edge));
        }
        return newGraph;
    }

    public Integer numVertices() {
        return _vertices.size();
    }

    public Integer numEdges() {
        return _edges.size();
    }

    public Iterator<Integer> vertices() {
        return _vertices.iterator();
    }

    public Iterator<Pair<Pair<Integer,Integer>,Integer>> edges() {
        HashSet<Pair<Pair<Integer,Integer>,Integer>> keyValues = new HashSet<Pair<Pair<Integer,Integer>,Integer>>();
        for (Pair<Integer,Integer> key : this._edges.keySet()) {
            Pair<Pair<Integer,Integer>,Integer> keyValuePair = new Pair<Pair<Integer,Integer>,Integer>(key,this._edges.get(key)); 
            keyValues.add(keyValuePair);
        }
        return keyValues.iterator();
    }

    public boolean isEdge(Integer v1, Integer v2) {
        if(!_vertices.contains(v1) || !_vertices.contains(v2)) {
            throw new IllegalArgumentException("Vertex does not exist");
        }
        return _edges.containsKey(new Pair<Integer,Integer>(v1,v2));
    }

    public int inDegree(Integer v) {
        if(!_vertices.contains(v)) {
            throw new IllegalArgumentException("Vertex does not exist");
        }
        return _inbounds.get(v).size();
    }

    public int outDegree(Integer v) {
        if(!_vertices.contains(v)) {
            throw new IllegalArgumentException("Vertex does not exist");
        }
        return _outbounds.get(v).size();
    }

    public Iterator<Integer> inbounds(Integer v) {
        if(!_vertices.contains(v)) {
            throw new IllegalArgumentException("Vertex does not exist");
        }
        return _inbounds.get(v).iterator();
    }

    public Iterator<Integer> outbounds(Integer v) {
        if(!_vertices.contains(v)) {
            throw new IllegalArgumentException("Vertex does not exist");
        }
        return _outbounds.get(v).iterator();
    }

    public Integer weight(Integer v1, Integer v2) {
        if(!_vertices.contains(v1) || !_vertices.contains(v2)) {
            throw new IllegalArgumentException("Vertex does not exist");
        }
        if(!_edges.containsKey(new Pair<Integer,Integer>(v1,v2))) {
            throw new IllegalArgumentException("Edge does not exist");
        }
        return _edges.get(new Pair<Integer,Integer>(v1,v2));
    }

    public void weight(Integer v1, Integer v2, Integer w) {
        if(!_vertices.contains(v1) || !_vertices.contains(v2)) {
            throw new IllegalArgumentException("Vertex does not exist");
        }
        if(!_edges.containsKey(new Pair<Integer,Integer>(v1,v2))) {
            throw new IllegalArgumentException("Edge does not exist");
        }
        _edges.put(new Pair<Integer,Integer>(v1,v2),w);
    }

    public void addVertex(Integer v) {
        if(_vertices.contains(v)) {
            throw new IllegalArgumentException("Vertex already exists");
        }
        _vertices.add(v);
        _inbounds.put(v,new HashSet<Integer>());
        _outbounds.put(v,new HashSet<Integer>());
    }

    public void removeVertex(Integer v) {
        if(!_vertices.contains(v)) {
            throw new IllegalArgumentException("Vertex does not exist");
        }
        _vertices.remove(v);
        for (Integer vertex : _inbounds.get(v)) {
            _outbounds.get(vertex).remove(v);
            _edges.remove(new Pair<Integer,Integer>(vertex,v));
        }
        for (Integer vertex : _outbounds.get(v)) {
            _inbounds.get(vertex).remove(v);
            _edges.remove(new Pair<Integer,Integer>(v,vertex));
        }
        _inbounds.remove(v);
        _outbounds.remove(v);
    }

    public void addEdge(Integer v1, Integer v2, Integer w) {
        if(!_vertices.contains(v1) || !_vertices.contains(v2)) {
            throw new IllegalArgumentException("Vertex does not exist");
        }
        if(_edges.containsKey(new Pair<Integer,Integer>(v1,v2))) {
            throw new IllegalArgumentException("Edge already exists");
        }
        _edges.put(new Pair<Integer,Integer>(v1,v2),w);
        _inbounds.get(v2).add(v1);
        _outbounds.get(v1).add(v2);
    }

    public void removeEdge(Integer v1, Integer v2) {
        if(!_vertices.contains(v1) || !_vertices.contains(v2)) {
            throw new IllegalArgumentException("Vertex does not exist");
        }
        if(!_edges.containsKey(new Pair<Integer,Integer>(v1,v2))) {
            throw new IllegalArgumentException("Edge does not exist");
        }
        _edges.remove(new Pair<Integer,Integer>(v1,v2));
        _inbounds.get(v2).remove(v1);
        _outbounds.get(v1).remove(v2);
    }

    public HashMap<Integer,Pair<Integer,Integer>> shortestPath(Integer v){
        //Initializations
        Queue<Integer> queue = new LinkedList<Integer>();
        HashMap<Integer,Pair<Integer,Integer>> map = new HashMap<Integer,Pair<Integer,Integer>>();
        Set<Integer> visited = new HashSet<Integer>();
        for(Iterator<Integer> vertex = this._vertices.iterator();vertex.hasNext();){
            map.put(vertex.next(),new Pair<Integer,Integer>(null,-1));
        }
        //Add the first vertex to the queue, the visited set, and the map of distances and parents with a distance of 0
        map.put(v,new Pair<Integer,Integer>(null,0));
        queue.add(v);
        map.put(v,new Pair<Integer,Integer>(null,0));
        visited.add(v);
        //BFS to find the shortest path
        while(!queue.isEmpty()){
            Integer current = queue.poll(); //Get the next vertex
            //For each neighbor of the current vertex
            for(Integer neighbor : _outbounds.get(current)){
                //If the neighbor has not been visited, add it to the queue, the visited set, and the map of distances and parents with a distance of 1 more than the current vertex
                if(!visited.contains(neighbor)){
                    queue.add(neighbor);
                    visited.add(neighbor);
                    map.put(neighbor,new Pair<Integer,Integer>(current,map.get(current).second+1));
                }
            }
        }
        return map;
    }
    public HashMap<Integer,Pair<Integer,Integer>> shortestPath(Integer v,Integer u){
        //Initializations
        Queue<Integer> queue = new LinkedList<Integer>();
        HashMap<Integer,Pair<Integer,Integer>> map = new HashMap<Integer,Pair<Integer,Integer>>();
        Set<Integer> visited = new HashSet<Integer>();
        for(Iterator<Integer> vertex = this._vertices.iterator();vertex.hasNext();){
            map.put(vertex.next(),new Pair<Integer,Integer>(null,-1));
        }
        //Add the first vertex to the queue, the visited set, and the map of distances and parents with a distance of 0
        map.put(v,new Pair<Integer,Integer>(null,0));
        queue.add(v);
        map.put(v,new Pair<Integer,Integer>(null,0));
        visited.add(v);
        //BFS to find the shortest path
        while(!queue.isEmpty()){
            Integer current = queue.poll(); //Get the next vertex
            //For each neighbor of the current vertex
            for(Integer neighbor : _outbounds.get(current)){
                //If the neighbor has not been visited yet add it to the queue, visited set, and map.
                if(!visited.contains(neighbor)){
                    queue.add(neighbor);
                    visited.add(neighbor);
                    //Add the neighbor to the map with the current vertex as its parent and a distance of the current vertex's distance + 1
                    map.put(neighbor,new Pair<Integer,Integer>(current,map.get(current).second+1));
                    //If the neighbor is the destination vertex return the map
                    if(neighbor == u)
                        return map;
                }
            }
        }
        return map;
    }
    public ArrayList<Integer> path(Integer v1,Integer v2){
        //Get the shortest path from v1 to v2
        HashMap<Integer,Pair<Integer,Integer>> map = shortestPath(v1);
        ArrayList<Integer> path = new ArrayList<Integer>();
        //If there is no path return an empty arraylist
        if(map.get(v2).second == -1) 
            return path;
        path.add(v2);
        //Add each vertex in the path to the arraylist starting from the destination vertex
        while(map.containsKey(v2)){
            path.add(map.get(v2).first);
            v2 = map.get(v2).first;
        }
        //Remove the first element of the arraylist which is null and reverse the arraylist
        path.remove(path.size()-1);
        Collections.reverse(path);
        return path;
    }

    public HashMap<Pair<Integer,Integer>,Pair<Integer,Integer>> shortestCostDynamic(Integer v1, Integer v2){
        HashMap<Pair<Integer,Integer>,Pair<Integer,Integer>> cost_prev_map = new HashMap<Pair<Integer,Integer>,Pair<Integer,Integer>>();
        //Initialize the map with the first vertex having a distance of 0 and all other vertices having a distance of 10000
        for(Integer i : _vertices){
            if(i==v1){
                cost_prev_map.put(new Pair<Integer,Integer>(i,0),new Pair<Integer,Integer>(0,null));
            }
            else{
                cost_prev_map.put(new Pair<Integer,Integer>(i,0),new Pair<Integer,Integer>(10000,null));
            }
        }
        //For each iteration of k
        for(Integer k = 1; k < _vertices.size(); k++){
            for(Integer i : _vertices){
                for(Integer j : _vertices){
                    //If the vertex is an edge and the cost of the previous vertex is greater than the current vertex's cost
                    if(this.isEdge(j,i) && cost_prev_map.get(new Pair<Integer,Integer>(i,k-1)).first > cost_prev_map.get(new Pair<Integer,Integer>(j,k-1)).first + this.weight(j,i)){
                        //Set the cost of the current vertex to the cost of the previous vertex
                        cost_prev_map.put(new Pair<Integer,Integer>(i,k),new Pair<Integer,Integer>(cost_prev_map.get(new Pair<Integer,Integer>(j,k-1)).first + this.weight(j,i),j));
                    }
                }
                //If the vertex is not an edge and the cost of the previous vertex is greater than the current vertex's cost
                if(!cost_prev_map.containsKey(new Pair<Integer,Integer>(i,k))){
                    //Set the cost of the current vertex to the cost of the previous vertex
                    cost_prev_map.put(new Pair<Integer,Integer>(i,k),new Pair<Integer,Integer>(cost_prev_map.get(new Pair<Integer,Integer>(i,k-1)).first,cost_prev_map.get(new Pair<Integer,Integer>(i,k-1)).second));
                }
            }
        }
        //Check for negative cycles
        if(cost_prev_map.get(new Pair<Integer,Integer>(v1,v1)).first < 0){
            throw new IllegalArgumentException("Graph contains negative cycle");
        }
        return cost_prev_map;
    }

    public ArrayList<Integer> costPathDynamic(Integer v1,Integer v2){
        HashMap<Pair<Integer,Integer>,Pair<Integer,Integer>> cost_prev_map = shortestCostDynamic(v1,v2);    
        ArrayList<Integer> path = new ArrayList<Integer>();
        //If the cost of the last vertex is 10000(infinity), then there is no path
        if(cost_prev_map.get(new Pair<Integer,Integer>(v2,_vertices.size()-1)).first == 10000){
            return path;
        }
        //Add the last vertex to the path
        path.add(v2);
        Integer k = _vertices.size()-1;
        //While the previous vertex is not null (the first vertex), add the previous vertex to the path, and set the current vertex to the previous vertex, and decrement k
        while(cost_prev_map.get(new Pair<Integer,Integer>(v2,k)).second != null){
            path.add(cost_prev_map.get(new Pair<Integer,Integer>(v2,k)).second);
            v2 = cost_prev_map.get(new Pair<Integer,Integer>(v2,k)).second;
            k--;
        }
        Collections.reverse(path);
        return path;
    }

    public Boolean TopoSortDFS(Integer x, ArrayList<Integer> sorted , Set<Integer> fullyProcessd, Set<Integer> inProcess){
        // If the vertex is in the inProcess set, then there is a cycle
        inProcess.add(x);
        // For each outbound vertex
        for(Integer y : _inbounds.get(x)){
            // If the vertex is in the inProcess set, then there is a cycle
            if(inProcess.contains(y)){
                return false;
            }
            // If the vertex is not in the fullyProcessd set, then recursively call the function
            else if(!fullyProcessd.contains(y)){
                if(!TopoSortDFS(y,sorted,fullyProcessd,inProcess)){
                    return false;
                }
            }

        }
        inProcess.remove(x);
        fullyProcessd.add(x);
        sorted.add(x);
        return true;
    }

    public ArrayList<Integer> TopoSort(){
        ArrayList<Integer> sorted = new ArrayList<Integer>();
        Set<Integer> fullyProcessd = new HashSet<Integer>();
        Set<Integer> inProcess = new HashSet<Integer>();
        // For each vertex
        for(Integer x : _vertices){
            // If the vertex is not in the fullyProcessd set, then recursively call the function
            if(!fullyProcessd.contains(x)){
                if(!TopoSortDFS(x,sorted,fullyProcessd,inProcess)){
                    return null;
                }
            }
        }
        return sorted;
    }

    public ArrayList<Integer> highestCostPathDAG(Integer v1, Integer v2){
        ArrayList<Integer> sorted = TopoSort();
        if(sorted == null){
            return null;
        }
        // Initialize the distance and previous vertex maps
        HashMap<Integer,Integer> dist = new HashMap<Integer,Integer>();
        HashMap<Integer,Integer> prev = new HashMap<Integer,Integer>();
        for(Integer i : _vertices){
            dist.put(i,-10000);
            prev.put(i,null);
        }
        dist.put(v1,0);
        // For each vertex in the sorted list
        while(!sorted.isEmpty()){
            // Remove the vertex from the sorted list
            Integer u = sorted.remove(0);
            if(dist.get(u) != -10000){
                for(Integer v : _outbounds.get(u)){
                    // If the distance of the current vertex is less than the distance of the previous vertex plus the weight of the edge, then set the distance of the current vertex to the distance of the previous vertex plus the weight of the edge, and set the previous vertex of the current vertex to the previous vertex
                    if(dist.get(v) < dist.get(u) + this.weight(u,v)){
                        dist.put(v,dist.get(u) + this.weight(u,v));
                        prev.put(v,u);
                    }
                }
            }
        }
        ArrayList<Integer> path = new ArrayList<Integer>();
        Integer u = v2;
        while(u != null){
            path.add(u);
            u = prev.get(u);
        }
        Collections.reverse(path);
        return path;        
    }
    
}