Untitled
unknown
plain_text
2 months ago
5.2 kB
2
Indexable
Never
import java.util.Scanner; public class GraphM4A { private int n; private int type; //0 if undirected, 1 if directed private int weighted; // 0 if unweighted, 1 otherwise private float[][] adjmat; public GraphM4A(Scanner sc){ String[] firstline = sc.nextLine().split(" "); this.n = Integer.parseInt(firstline[0]); System.out.println("Number of vertices "+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); this.adjmat = new float[this.n][this.n]; for (int i=0;i<this.n; i++) for(int j=0; j<this.n; j++) adjmat[i][j]=0; // replace 0 with something else if the weights can be 0 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) { if(line.length > 1){ String[] successors= line[1].split(","); System.out.println(i+ " "+ successors.length); for (int h=0;h<successors.length;h++) this.adjmat[i-1][Integer.parseInt(successors[h])-1]=1; } } 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++) this.adjmat[i-1][Integer.parseInt(successors[h])-1]=Float.parseFloat(theirweights[h]); } } } } //method to be applied only when type=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++) for(int j=0;j<this.n;j++) if(this.adjmat[i][j] != 0) tmp[i] = tmp[i] + 1 ; return tmp; } //method to be applied only when type=1 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++) for(int j=0;j<this.n;j++) if(this.adjmat[i][j]!=0){ tmp2[i]= tmp2[i] +1; tmp1[j]=tmp1[j]+1; } return(new TwoArrays4A(tmp1,tmp2)); } public int getType() { return this.type; } public int getSize() { return this.n; } public int getWeighted() { return this.weighted; } public float getValue(int x, int y) { return this.adjmat[x][y]; } public void print() { for(int i=0;i<n;i++) { for(int j=0; j<n; j++) { System.out.print(getValue(i,j) + " "); } System.out.println(); } } public GraphM4A() {} /** * Transpose a graph * the modified object is the one being called * the parameter is not modified **/ public void transpose(GraphM4A 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 GraphM4A(oldGraph); } this.n = oldGraph.n; this.type = oldGraph.type; this.weighted = oldGraph.weighted; this.adjmat = new float [n][n]; for(int i = 0; i<n ; i++) { for(int j = 0; j<n; j++) { this.adjmat[i][j] = oldGraph.adjmat[j][i]; } } } public void transpose(final GraphL4A oldGraph) { if(oldGraph.getType() == 0) { //if undirected, do nothing System.out.println("this graph is not directed, no changes have been made"); return; } GraphM4A graph = new GraphM4A(oldGraph); this.transpose(graph); } //M->M constructor public GraphM4A(GraphM4A oldGraph){ this.n = oldGraph.n; this.type = oldGraph.type; this.weighted = oldGraph.weighted; this.adjmat = new float [n][n]; for(int i = 0; i<n ; i++) { for(int j = 0; j<n; j++) { this.adjmat[i][j] = oldGraph.adjmat[i][j]; } } } //L->M constructor public GraphM4A(GraphL4A oldGraph) { this.n = oldGraph.getSize(); this.type = oldGraph.getType(); this.weighted = oldGraph.getWeighted(); this.adjmat = new float [n][n]; if(weighted == 0) { // unweighted for(int i = 0; i<n ; i++) { for(int j = 0; j<n; j++) { adjmat[i][j] = 0; } Node4A currentNode = oldGraph.getList(i); while(currentNode!=null) { adjmat[i][currentNode.getVal()] = 1; currentNode = currentNode.getNext(); } } }else { for(int i = 0; i<n; i++) { for(int j = 0; j<n; j++) { adjmat[i][j] = 0; } WeightedNode4A currentNode = oldGraph.getListW(i); while(currentNode!=null) { adjmat[i][currentNode.getVal()] = currentNode.getWeight(); currentNode = currentNode.getNext(); } } } } }