graph.java

import java.util.*;
public class graph {

    public static class edge{
        int src;
        int dest;
        edge(int s, int d)
    { this.src=s;
        this.dest= d;
        
    }
    }
    public static class wedge{
        int src;
        int dest;
        int weight;
        wedge(int s, int d, int w)
    { this.src=s;
        this.dest= d;
        this.weight=w;
        
    }
    }
    
    public static void creategraph( ArrayList<edge> graph[], int v)
    { for(int i=0;i<v;i++){
        graph[i]= new ArrayList<>();
    }
   // graph[0].add(new edge(0, 1));
// graph[0].add(new wedge(0, 1, 2));
// graph[0].add(new wedge(0, 2, 4));
// graph[1].add(new wedge(1, 2, -4));
// graph[2].add(new wedge(2, 3, 2));
// graph[3].add(new wedge(3, 4, 4));
// graph[4].add(new wedge(4, 1, -10));

graph[0].add( new edge( 0,1));
graph[0].add( new edge( 0,2));
graph[2].add( new edge( 2,3));
graph[1].add( new edge( 1,3));


    }
    public static boolean isCycleDirected(ArrayList<edge> graph[], boolean vis[],int curr, boolean rc[]){
        if(rc[curr]) return true;
      //  boolean ans= false;
      if(! vis[curr]){
        vis[curr]= true;
        rc[curr]= true;
        for(int i=0; i<graph[curr].size();i++){
            edge e= graph[curr].get(i);
            if( isCycleDirected(graph, vis, e.dest, rc)) return true;
            


        }
        rc[curr]= false;}
        return false;
    } 
    public static boolean isCycleUnDirected(ArrayList<edge> graph[], boolean vis[],int curr,  int parent){
       // boolean ans= false;
        //if(! vis[curr]){
            vis[curr]= true;
           
            for(int i=0;i<graph[curr].size();i++){
                edge e= graph[curr].get(i);
                if(vis[e.dest] && e.dest!= parent) return true;
                if(! vis[e.dest]){
                if(isCycleUnDirected(graph, vis, e.dest, curr)) return true;
                }
            }
            
        
        return false;
    }

    public static void topoSort(ArrayList<edge> [] graph, Queue<Integer> q1, boolean vis[], int start){
        if(vis[start]== false){
          q1.add(start);
            vis[start]= true;
            for(int i=0;i<graph[start].size();i++){
                edge e= graph[start].get(i);
                topoSort(graph, q1, vis, e.dest);
            }
             
        }
    }

    public static void bfs(ArrayList<edge> graph[], boolean vis[],int start, int v ){
        //int curr= start;
        Queue<Integer> q1= new LinkedList();
        
        q1.add(start);
        while(! q1.isEmpty()){
            int curr= q1.remove();
            if(vis[curr] == false){
                System.out.println(curr);
                vis[curr]= true;
                for(int i=0;i<graph[curr].size();i++){
                    edge e= graph[curr].get(i);
                    q1.add(e.dest);
                }

            }
                }

            
        
    }

    public static void printAllNeighbour(ArrayList<edge> [] graph)
    {
        for(edge e : graph[2])
        {
            System.out.println(e.dest);
        }
    }
    
    public static void dfs(ArrayList<edge> [] graph, boolean vis[], int start){
        if(vis[start]== false){
            System.out.println(start);
            vis[start]= true;
            for(int i=0;i<graph[start].size();i++){
                edge e= graph[start].get(i);
                dfs(graph, vis, e.dest);
            }
        }
    }
    public static void printAllpaths(ArrayList<edge> [] graph,String path, int start, int tar,boolean vis[]){
        
        if(vis[start] == true) return;
            if( start== tar) 
            {System.out.println(path + start);
                 return ;}
        for(int i=0;i<graph[start].size();i++){
            edge e= graph[start].get(i);
            vis[start]= true;
            printAllpaths(graph, path+ start,e.dest,tar, vis);
            vis[start]= false;

        }
    }
    
    static class Pair implements Comparable<Pair> {
        // using pair to store a node and its path from source
    int n;// stores the node
    int path;// stores the weight between nodes
    public Pair(int n, int path){
        this.n=n;
        this.path= path;
    }
    @Override
    public int compareTo(Pair p2){
        return this.path- p2.path;
    }
        
    }

    public static int[] dijkstra(ArrayList<wedge> graph[], int src){
        PriorityQueue<Pair> pq= new PriorityQueue<>();
        int dist[] = new int[graph.length];
        dist[src]= 0;
        boolean vis[]= new boolean[graph.length];

        for(int i=0;i<dist.length;i++){// intial dist of all nodes will be infinity
            if(i== src) continue;
            else{
                dist[i]= Integer.MAX_VALUE;
            }
        }
        pq.add(new Pair(src, 0));
        while(! pq.isEmpty()){
            // remove all neighbours
            Pair p= pq.remove();
            if(! vis[p.n]){
                vis[p.n]= true;
            for(int i=0;i<graph[p.n].size(); i++){
                wedge E= graph[p.n].get(i);

                // perform relaxation for every next node

                if( ! vis[E.dest] && dist[E.dest] > p.path + E.weight){
                    dist[E.dest]= p.path + E.weight;
                     pq.add(new Pair(E.dest, dist[E.dest]));
                }
               
                
            }
        }

        }
        return dist;

    }
    
    public static void bellman(ArrayList<wedge> graph[], int src){
        int dist[]= new int[graph.length];
        for(int i=0;i<graph.length;i++){
            if(i==src) continue;
            dist[i]= Integer.MAX_VALUE;
        }

        for(int i=0;i<graph.length-1;i++)
        {

            for(int j=0;j<graph.length;j++){
                for(int f=0; f<graph[j].size();f++){
                    wedge curr= graph[j].get(f);
                    // performing relaxation

                    if( dist[curr.src] != Integer.MAX_VALUE && dist[curr.dest]> dist[curr.src] + curr.weight)
                        dist[curr.dest]= dist[curr.src] + curr.weight;

                }
            }
        }
// for checking negative weighted cycle
         for(int j=0;j<graph.length;j++){
                for(int f=0; f<graph[j].size();f++){
                    wedge curr= graph[j].get(f);
                    // performing relaxation

                    if( dist[curr.src] != Integer.MAX_VALUE && dist[curr.dest]> dist[curr.src] + curr.weight)
                       System.out.println("negative weight cycle detected");

                }
            }


        for(int i=0;i<dist.length;i++){
            System.out.println("node "+i+"dist"+dist[i]);
        }
    }
    
    public class node implements Comparable<node>{
        // this is for prims algorithim
        int n;
        int wt;
        node(int n, int wt){
            this.n= n;
            this.wt= wt;
        }
        @Override
        public int compareTo(node a){
            return this.wt- a.wt;
        }
    }
    public static void prims( ArrayList<wedge> graph[], boolean vis[]){
        PriorityQueue <wedge> pq= new PriorityQueue<>();
        
    }
    public static void main(String[] args) {
        int v=4;
        
        ArrayList<edge> [] graph= new ArrayList[v];// considering a graph with 4 nodes
    creategraph(graph,v);
    //printAllNeighbour(graph);
   boolean vis[]= new boolean[v];
   boolean rc[]= new boolean[v];
 
    // int dist[]= new int[v];
    // dist= dijkstra(graph, 0);
    // for(int i=0;i< dist.length;i++){
    //     System.out.println("node "+i+" dist="+dist[i]);
    // }
   //bellman(graph, 0);
   Queue<Integer> q1= new LinkedList<>(); 
    
   
   topoSort(graph, q1, vis, 0);
     
     while (!q1.isEmpty()) {
         System.out.println(q1.remove());
        
     }
   // bfs(graph, 0, v);
  // printAllpaths(graph, "", 0, 5, vis);
 
    }
}