Untitled
unknown
plain_text
2 months ago
13 kB
1
Indexable
Never
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; } } } } } }