Untitled

import java.util.Scanner;
import java.util.Stack;

public class GraphL4A {

	private int n;
	private int type; //0 if undirected, 1 if directed
	private int weighted; // 0 if unweighted, 1 otherwise
	private WeightedNode4A[] adjlistW; //one of adjlistW and adjlist is null, depending on the type of the graph
	private Node4A[] adjlist;

	private int nb;
	private int[] d;
	private int[] f;
	
	private Stack<Integer> checkingForCycles;
	public boolean hasCycles = false;

	public GraphL4A(Scanner sc){
	    String[] firstline = sc.nextLine().split(" ");
	    this.n = Integer.parseInt(firstline[0]);
	    System.out.println(this.n);
	    if (firstline[1].equals("undirected"))
	    	this.type = 0;
	    else
	    	this.type=1;
	    System.out.println("Type= "+this.type);
	    if (firstline[2].equals("unweighted"))
	    	this.weighted = 0;
	    else
	    	this.weighted=1;
	    System.out.println("Weighted= "+this.weighted);
	    if (this.weighted==0) {
	    	this.adjlist=new Node4A[this.n];
	    	for (int i=0;i<this.n;i++)
	    		adjlist[i]=null;
	        adjlistW=null;
	    }
	    else {
	    	this.adjlistW=new WeightedNode4A[this.n];
	    	for (int i=0;i<this.n;i++)
	    		adjlistW[i]=null;
	        adjlist=null;
	    }
	    	
	    
	  	for(int k=0;k<this.n;k++){
	  		String[] line = sc.nextLine().replaceAll(" ", "").split(":");
	  		int i = Integer.parseInt(line[0]); //the vertex "source"
	  		if (weighted==0) {
	  			String[] successors= line[1].split(",");
	  			System.out.println(i+ " "+ successors.length);
	  			for (int h=0;h<successors.length;h++) {
	  				Node4A node=new Node4A(Integer.parseInt(successors[h])-1,null);
			        node.setNext(adjlist[i-1]);
			        adjlist[i-1]=node;
	  			}
	  		}
	  		else {
	  			line = line[1].split("//");
	  			if ((line.length==2)&&(line[1].charAt(0)!=' ')){// if there really are some successors, then we must have something different from " " after "// "
	  				  	String[] successors= line[0].split(",");
	  			  	    String[] theirweights= line[1].split(",");
	  				  	for (int h=0;h<successors.length;h++) {
	  				  	  	WeightedNode4A nodeW = new WeightedNode4A(Integer.parseInt(successors[h])-1,null,Float.parseFloat(theirweights[h]));
	  				  	  	nodeW.setNext(adjlistW[i-1]);
	  				  	  	adjlistW[i-1]=nodeW;
	  				  	}
	  			
	  			}
	  		}
	  	}
	  	
	  }
	    
	   
	  	
	
	//method to be applied only when type=0 and weighted=0
	public int[] degree(){
		int[] tmp=new int[this.n];
	    for(int i=0;i<this.n;i++) 
	    	tmp[i]=0;
	    	for(int i=0;i<this.n;i++) {
	    		Node4A p=adjlist[i];
	    		while (p!=null) {
	    			tmp[i]=tmp[i]+1;
	    			p=p.getNext();
	    		}
	    	}
	    	return(tmp);
	  }
	
	//method to be applied only when type=0 and weighted=1
		public int[] degreeW(){
			int[] tmp=new int[this.n];
		    for(int i=0;i<this.n;i++) 
		    	tmp[i]=0;
		    	for(int i=0;i<this.n;i++) {
		    		WeightedNode4A p=adjlistW[i];
		    		while (p!=null) {
		    			tmp[i]=tmp[i]+1;
		    			p=p.getNext();
		    		}
		    	}
		    	return(tmp);
		  }
	

	//method to be applied only when type=1 and weighted=0
	  public TwoArrays4A degrees(){
		  int[] tmp1=new int[this.n]; //indegrees
		  int[] tmp2=new int[this.n]; //outdegrees
		  for(int i=0;i<this.n;i++) { 
		    tmp1[i]=0;
		    tmp2[i]=0;
		  }
    	for(int i=0;i<this.n;i++) {
    		Node4A p=adjlist[i];
    		while (p!=null) {
    			tmp2[i]=tmp2[i]+1;
    			tmp1[p.getVal()]=tmp1[p.getVal()]+1;
    			p=p.getNext();
    		}
    	}	
	    return(new TwoArrays4A(tmp1,tmp2));        
	  }
		
	//method to be applied only when type=1 and weighted=1
	  public TwoArrays4A degreesW(){
		  int[] tmp1=new int[this.n]; //indegrees
		  int[] tmp2=new int[this.n]; //outdegrees
		  for(int i=0;i<this.n;i++) { 
		    tmp1[i]=0;
		    tmp2[i]=0;
		  }
    	for(int i=0;i<this.n;i++) {
    		WeightedNode4A p=adjlistW[i];
    		while (p!=null) {
    			tmp2[i]=tmp2[i]+1;
    			tmp1[p.getVal()]=tmp1[p.getVal()]+1;
    			p=p.getNext();
    		}
    	}	
	    return(new TwoArrays4A(tmp1,tmp2));        
	  }


	/**
	 * Exercices 2 : Implementation de Depth-first Search
	 * Cette fonction initialise les différentes variables pour le parcours :
	 * 	- d[], f[] et nb
	 * Puis pour chaque sommets s du graphe G, on appel la fonction récursive (DFSNumRecursive / DFSNumRecursiveW)
	 *
	 * Complexity :  Running time of ϴ(|S| + |A|)
	 */
	public void DFSNum(){
		System.out.println("Running DFSNum() : ");
		nb = 0;
		checkingForCycles = new Stack<>();
		// Checking for weighted or unweghted graph
		if(this.weighted == 1) {

			//INITIALISATION
			d = new int[this.adjlistW.length];
			f = new int[this.adjlistW.length];
			//Visiting the whole graph
			for (int i = 0; i < this.adjlistW.length; i++) {
				d[i] = 0;
				f[i] = 0;
			}

			for (int s = 0; s < this.adjlistW.length; s++) {
				if (d[s] == 0) DFSNumRecursiveW(s, 0);
			}

			for (int s = 0; s < this.adjlistW.length; s++) {
				System.out.println(s+1 + " : "+ d[s] + " | " + f[s]);
			}


		} else {
			//INITIALISATION
			d = new int[this.adjlist.length];
			f = new int[this.adjlist.length];
			//Visiting the whole graph
			for (int i = 0; i < this.adjlist.length; i++) {
				d[i] = 0;
				f[i] = 0;
			}

			for (int s = 0; s < this.adjlist.length; s++) {
				if (d[s] == 0) DFSNumRecursive(s, 0);
			}

			for (int s = 0; s < this.adjlist.length; s++) {
				System.out.println(s+1 + " : "+ d[s] + " | " + f[s]);
			}
		}
		if(hasCycles){
			System.out.println("has cycles");
		} else System.out.println("has no cycles");
	  }
	
	private void printStack()
	{
		String arrow = "";
		if(type == 1) {
			arrow = " <- ";
		}else{
			arrow = " <-> ";
		}

		Stack<Integer> stack = new Stack<>(); //must empty the stack and fill it back when called
		
		System.out.print("The Cycle of this graph is : ");
		while (!checkingForCycles.empty()) {
			stack.push(checkingForCycles.pop());
			System.out.print(stack.peek() + arrow );
		}
		while (!stack.empty()) {
			checkingForCycles.push(stack.pop());
		}
		System.out.println(checkingForCycles.peek());
	}

	
	  private void DFSNumRecursiveW(int s, int predecessor){
			nb++;
			d[s] = nb;
			checkingForCycles.add(s);
			
			//For each successor of s do...
			WeightedNode4A node = this.adjlistW[s];
			int successor=0;

			while(node != null){
				successor = node.getVal();

				//Added for cycles checking
				if(predecessor != 0) {
					if(type == 1){
						if(checkingForCycles.contains(node.getVal()) && !hasCycles) {
							printStack();
							hasCycles = true;
						}
					}
					else{
						if(successor != predecessor && checkingForCycles.contains(node.getVal()) && !hasCycles) {
							printStack();
							hasCycles = true;
						}
					}
				}

				if(d[successor] == 0) DFSNumRecursiveW(successor, s);
				node = node.getNext();
			}

			nb++;
			f[s] = nb;
			checkingForCycles.pop();
		}
	  
	  private void DFSNumRecursive(int s, int predecessor){
			nb++;
			d[s] = nb;
			checkingForCycles.add(s);
			
			//For each successor of s do...
			Node4A node = this.adjlist[s];
			int successor=0;
			while(node != null){
				successor = node.getVal();
	
				//Added for cycles checking
				if(predecessor != 0) {
					if(type == 1){
						if(checkingForCycles.contains(node.getVal()) && !hasCycles) {
							printStack();
							hasCycles = true;
						}
					}
					else{
						if(successor != predecessor && checkingForCycles.contains(node.getVal()) && !hasCycles) {
							printStack();
							hasCycles = true;
						}
					}
				}
	
				if(d[successor] == 0) DFSNumRecursive(successor, s);
				node = node.getNext();
			}
			
			nb++;
			f[s] = nb;
			checkingForCycles.pop();
		}

	  public int getSize() {
		  return this.n;
	  }
	  
	  public int getType() {
			return this.type;
		}
	  public int getWeighted() {
			return this.weighted;
		}
	  
	  public Node4A getList(int i) {
		  return this.adjlist[i];
	  }
	  
	  public WeightedNode4A getListW(int i) {
		  return this.adjlistW[i];
	  }
	  
	  public void print() {
		  for(int i = 0; i<n; i++) {
			  System.out.print(i+1 + " |");
			  if(weighted == 0) {
				  Node4A node = adjlist[i];
				  while(node!=null) {
					  System.out.print(" -> " + (node.getVal()+1));
					  node=node.getNext();
				  }
			  }else {
				  WeightedNode4A node = adjlistW[i];
				  while(node!=null) {
					  System.out.print(" -> " + (node.getVal()+1) + "|" + node.getWeight());
					  node=node.getNext();
				  }
			  }
			  System.out.println();
		  }
	  }
	  
	  public GraphL4A() {
		  this.adjlistW = null;
		  this.adjlist = null;
	  }
	  

	  /**
	   * Transpose a graph
	   * the modified object is the one being called
	   * the parameter is not modified
	   **/
	  public void transpose(GraphL4A oldGraph){
		  if(oldGraph.type == 0) { //if undirected, do nothing
			  System.out.println("this graph is not directed, no changes have been made");
			  return;
		  }
		  
		  if(this==oldGraph) { //create an other object to prevent conflict
			  oldGraph = new GraphL4A(oldGraph);
		  }
		  
		  this.n = oldGraph.n;
		  this.type = oldGraph.type; 
		  this.weighted = oldGraph.weighted;
		
		  if (this.weighted==0) { // unweighted transpose
			  this.adjlist = new Node4A[n];
			  for(int i=0; i<n; i++) {
				  Node4A currentNode = oldGraph.adjlist[i];
				  
				  while(currentNode != null) {
					  Node4A newNode = new Node4A(i, null);
					  newNode.setNext(this.adjlist[currentNode.getVal()]);
					  this.adjlist[currentNode.getVal()] = newNode;
					  
					  currentNode = currentNode.getNext();
				  }
			  }
		  }else { //weighted transpose
			  this.adjlistW = new WeightedNode4A[n];
			  for(int i=0; i<n; i++) {
				  WeightedNode4A currentNode = oldGraph.adjlistW[i];
				  
				  while(currentNode != null) {
					  WeightedNode4A newNode = new WeightedNode4A(i, null, currentNode.getWeight());
					  newNode.setNext(this.adjlistW[currentNode.getVal()]);
					  this.adjlistW[currentNode.getVal()] = newNode;
					  
					  currentNode = currentNode.getNext();
				  } 
			  }
		  }
		
	  }
	  
	public void transpose(GraphM4A oldGraph) {
		if(oldGraph.getType() == 0) { //if undirected, do nothing
			  System.out.println("this graph is not directed, no changes have been made");
			  return;
		}
		GraphL4A graph = new GraphL4A(oldGraph);
		this.transpose(graph);
	}
	
	//L->L constructor
	  public GraphL4A(GraphL4A graph)
	  {
		  this.n = graph.n;
		  this.type = graph.type; //0 if undirected, 1 if directed
		  this.weighted = graph.weighted;
		  
		  if (this.weighted == 0) {
			  this.adjlist = new Node4A[n];
			  for(int i=0; i<n; i++) {
				  this.adjlist[i]=null;
				  Node4A listNode[] = new Node4A[n];
				  Node4A prevNode =  graph.adjlist[i];
				  int compteur = 0;
				  while(prevNode != null)
				  {
					  Node4A newNode = new Node4A(prevNode.getVal(), null);
					  prevNode = prevNode.getNext();
					  listNode[compteur] = newNode;
					  compteur++;
				  }
				  for(int j = compteur-1; 0<=j; j--) {
					  listNode[j].setNext(this.adjlist[i]);
					  this.adjlist[i] = listNode[j];
				  }
			  }
		  }else {
			  this.adjlistW = new WeightedNode4A[n];
			  for(int i=0; i<n; i++) {
				  this.adjlistW[i]=null;
				  WeightedNode4A listNode[] = new WeightedNode4A[n];
				  WeightedNode4A prevNode =  graph.adjlistW[i];
				  int compteur = 0;
				  while(prevNode != null)
				  {
					  WeightedNode4A newNode = new WeightedNode4A(prevNode.getVal(), null, prevNode.getWeight());
					  prevNode = prevNode.getNext();
					  listNode[compteur] = newNode;
					  compteur++;
				  }
				  for(int j = compteur-1; 0<=j; j--) {
					  listNode[j].setNext(this.adjlistW[i]);
					  this.adjlistW[i] = listNode[j];
				  }
			  }
		  }
	  }
	  
	//M->L constructor
	  public GraphL4A(GraphM4A oldGraph) {
		  this.n = oldGraph.getSize();
		  this.type = oldGraph.getType();
		  this.weighted = oldGraph.getWeighted();
		  
		  if (this.weighted==0) { // unweighted
			  this.adjlist = new Node4A[n];
			  for(int i=0; i<n; i++) {
				  this.adjlist[i] = null;
				  
				  for(int j=0; j<n; j++) {
					  if(oldGraph.getValue(i, j) != 0){
						  Node4A node=new Node4A(j,null);
					      node.setNext(adjlist[i]);
					      adjlist[i]=node;
					  }
				  }
			  }
		  }else {
			  this.adjlistW = new WeightedNode4A[n];
			  for(int i=0; i<n; i++) {
				  this.adjlistW[i] = null;
				  
				  for(int j=0; j<n; j++) {
					  if(oldGraph.getValue(i, j) != 0){
						  WeightedNode4A node=new WeightedNode4A(j,null, oldGraph.getValue(i,j));
					      node.setNext(adjlistW[i]);
					      adjlistW[i]=node;
					  }
				  }
			  }			  
				 
		  }
	  }



}