API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Nov 18th, 2017
78
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 20.21 KB | None | 0 0
raw download clone embed print report
  1.  
  2. import com.sun.xml.internal.bind.v2.runtime.unmarshaller.XsiNilLoader;
  3. import java.io.File;
  4. import java.io.FileNotFoundException;
  5. import java.io.PrintWriter;
  6. import java.util.Arrays;
  7. import java.util.Scanner;
  8.  
  9.  
  10. /*
  11. Team # 1
  12. Task | Name | Id
  13. part 1 | Aiman Alghamdi | 1535685
  14. part 2 | Mubarak Nawar | 1316585
  15. part 3 | Yousef Bajafar |1324308
  16. */
  17.  
  18. /**
  19. *
  20. * @author Asus
  21. */
  22.  
  23. public class AddGraph //Main Class
  24. {
  25.  
  26. /**
  27. *
  28. * @param args
  29. * @throws FileNotFoundException
  30. */
  31. public static void main(String[] args) throws FileNotFoundException {
  32.  
  33. //Create an object ‘theGraph’ of Graph class
  34. //Write commands for getting the vertices and edges to be added in the graph ,
  35. //from the user here. And call the appropriate methods to add the vertices and
  36. //edges in the graph here
  37. File file = new File("input.in");
  38. Scanner input = new Scanner(file);
  39. PrintWriter output = new PrintWriter("output.out");
  40. // Enter weight or not
  41.  
  42. String quit=input.next();
  43. int numberOfVerticies =0;
  44.  
  45. while(!quit.equalsIgnoreCase("quit")){
  46.  
  47. String weight=quit;
  48. boolean checkWeight=false;
  49. if(weight.equalsIgnoreCase("WEIGHTED")){
  50. checkWeight=true;
  51. }
  52.  
  53. //write a loop and ask the user how many verticies you want to add
  54. // number of verticies
  55. numberOfVerticies = input.nextInt();
  56. Graph theGraph = new Graph(numberOfVerticies);
  57.  
  58.  
  59. int counter = 0;
  60. for (int i = 0; i < numberOfVerticies; i++) {
  61.  
  62.  
  63. String vertix = i+"";
  64. theGraph.addVertex(Integer.parseInt(vertix.charAt(0)+""));
  65. counter++;
  66.  
  67. }
  68.  
  69.  
  70.  
  71.  
  72.  
  73.  
  74.  
  75. int number = input.nextInt();
  76.  
  77. for (int i = 0; i < number; i++) {
  78.  
  79. int one = input.nextInt();
  80. int two = input.nextInt();
  81. if(checkWeight){
  82.  
  83. int weightNum=input.nextInt();
  84. theGraph.addEdgeWeight(one, two, weightNum);
  85. }else{
  86. theGraph.addEdgeUnWeight(one, two);
  87. }
  88. }
  89. quit=input.next();
  90.  
  91. //add the verticies within the look, the loop length is a counter
  92. if(checkWeight){
  93. output.println("Weight Matrix: ");
  94. theGraph.displayGraph(output);
  95. output.println();
  96. }else{
  97. output.println("Adjacency Matrix: ");
  98. theGraph.displayGraph(output);
  99. output.println();
  100. }
  101. theGraph.DisplayADJACENCYMat(output);
  102.  
  103. output.print("\n# of vertices is: "+numberOfVerticies+", # of edges is:"+number+"\n");
  104. theGraph.DisplayADJACENCYList(output);
  105.  
  106. //Call the method displayGraph to display the graph as adjacency matric
  107. output.print("DFS Traversal: ");
  108. theGraph.dfs(output);
  109.  
  110. theGraph.unvisted();
  111. output.println();
  112. output.print("\nBFS Traversal: ");
  113.  
  114. theGraph.bfs(output);
  115. output.println();
  116. theGraph.dijkstraWithHeap(numberOfVerticies,output);
  117. output.println("\n-----------------------------------------");
  118. theGraph.dijkstraWithUnordered(numberOfVerticies,output);
  119.  
  120. if (theGraph.connected()) {
  121. output.println("\nGraph is connected");
  122. } else {
  123. output.println("\nGraph is not connected");
  124. }
  125. }
  126.  
  127. //
  128. input.close();
  129. output.close();
  130. } // end main()
  131.  
  132. } // end class AddGraph
  133.  
  134. class Graph //Class to implement graph
  135. {
  136.  
  137. private final int MAX_VERTS = 20;
  138. private Vertex vertexList[]; // Array of vertices as objects of class Vertex
  139. private int adjMat[][]; // adjacency matrix
  140. private int nVerts; // current number of vertices
  141. public static boolean connected = true;
  142. // -----------------------------------------------------------
  143.  
  144. public Graph(int x) // constructor
  145. {
  146. vertexList = new Vertex[x];
  147. adjMat = new int[x][x];
  148. nVerts = 0;
  149. //Write statements here to initialize the above data members
  150.  
  151. } // end constructor
  152. // -----------------------------------------------------------
  153.  
  154. public void addVertex(int lab) {
  155. //Write statement(s) here to add new vertex
  156. vertexList[nVerts++] = new Vertex(lab);
  157. }
  158.  
  159. public String getVertex(int x) {
  160. return vertexList[x].label + "";
  161. }
  162. // -----------------------------------------------------------
  163.  
  164. public void addEdgeUnWeight(int start, int end) {
  165. //Write statement(s) here to add new edge for undirected graph
  166. adjMat[start][end] = 1;
  167. // adjMat[end][start] = 1;
  168.  
  169. }
  170. // ------------------------------------------------------------
  171. public void addEdgeWeight(int start, int end,int weight) {
  172. //Write statement(s) here to add new edge for undirected graph
  173. adjMat[start][end] = weight;
  174. // adjMat[end][start] = weight;
  175.  
  176. }
  177. // ------------------------------------------------------------
  178. public void displayVertex(int v,PrintWriter output) {
  179. //Write statement(s) here to display the vertex label
  180. output.print(" " + vertexList[v].label);
  181. }
  182.  
  183. // ------------------------------------------------------------
  184. public void displayGraph(PrintWriter output) {
  185. displayGraph(adjMat,output);
  186. }
  187.  
  188. private void displayGraph(int[][] adjMat,PrintWriter output) {
  189. //Write statements here to display the adjacency matrix of the given graph like the output given below
  190. output.print(" ");
  191. for (int i = 0; i < nVerts; i++) {
  192. output.print(" ");
  193. displayVertex(i,output);
  194. output.print(" |");
  195. }
  196. output.println("");
  197. for (int i = 0; i < nVerts; i++) {
  198. displayVertex(i,output);
  199. output.print("|");
  200. for (int j = 0; j < nVerts; j++) {
  201. output.printf(" %2d |" , adjMat[i][j] );
  202. }
  203. output.println("");
  204. }
  205.  
  206. }
  207.  
  208. public void DisplayADJACENCYMat(PrintWriter output) {
  209. DisplayADJACENCYMat(adjMat, vertexList,output);
  210. }
  211.  
  212. private void DisplayADJACENCYMat(int[][] adjMat, Vertex vertexList[], PrintWriter output) {
  213.  
  214. for (int i = 0; i < nVerts; i++) {
  215. //VERTEX: 0 {a} - VISIT: false - ADJACENCY: 3,2,4
  216. output.print("VERTEX: " + i + " {" + getVertex(i) + "} -VISIT: " + vertexList[i].wasVisited + " -ADJACENCY: ->>");
  217. for (int j = 0; j < nVerts; j++) {
  218. if (adjMat[i][j] != 0) {
  219. displayVertex(j,output);
  220. }
  221.  
  222. }
  223. output.println("");
  224.  
  225. }
  226.  
  227. }
  228.  
  229. public void DisplayADJACENCYList(PrintWriter output) {
  230. DisplayADJACENCYList(adjMat, vertexList,output);
  231. }
  232.  
  233. private void DisplayADJACENCYList(int[][] adjMat, Vertex vertexList[], PrintWriter output) {
  234.  
  235. for (int i = 0; i < nVerts; i++) {
  236.  
  237. output.print(i+":");
  238. for (int j = 0; j < nVerts; j++) {
  239. if (adjMat[i][j] != 0) {
  240. output.print(" "+ getVertex(i) + "-" +getVertex(j) +" "+(double) adjMat[i][j]);
  241.  
  242. }
  243.  
  244.  
  245.  
  246. }
  247. output.println("");
  248.  
  249. }
  250. output.println("");
  251.  
  252. }
  253.  
  254. public boolean connected() {
  255. return connected;
  256. }
  257.  
  258. void bfs(PrintWriter output) // breadth-first search
  259. {
  260.  
  261. QueueArray queue = new QueueArray(nVerts);
  262. queue.enqueue(0);
  263.  
  264. while (!queue.isEmpty()) {
  265. int v1 = queue.dequeue();
  266. vertexList[v1].wasVisited = true;
  267.  
  268. for (int j = 0; j < nVerts; j++) {
  269.  
  270. if ((adjMat[v1][j] != 0) && !vertexList[j].wasVisited) {
  271. queue.enqueue(j);
  272. vertexList[j].wasVisited = true;
  273. }
  274.  
  275. }
  276.  
  277. displayVertex(v1,output);
  278. if (queue.isEmpty()) {
  279. for (int i = 0; i < nVerts; i++) {
  280. if (vertexList[i].wasVisited == false) {
  281. connected = false;
  282. queue.enqueue(i);
  283. vertexList[i].wasVisited = true;
  284. break;
  285. }
  286. }
  287. }
  288.  
  289. }
  290.  
  291. } // end bfs()
  292.  
  293. //===========================================
  294. void dfs(PrintWriter output) {
  295. StackLL stack = new StackLL();
  296. stack.push(0);
  297. // String temp = "0 ";
  298.  
  299. // stack.pop();
  300. int count = 0;
  301. displayVertex(stack.peek(),output);
  302. while (!stack.isEmpty()) {
  303. int v1 = stack.peek();
  304.  
  305. vertexList[v1].wasVisited = true;
  306.  
  307. for (int j = 0; j < nVerts; j++) {
  308.  
  309. if ((adjMat[v1][j] != 0) && !vertexList[j].wasVisited) {
  310.  
  311. stack.push(j);
  312. vertexList[j].wasVisited = true;
  313. v1 = j;
  314. displayVertex(v1,output);
  315. j = 0;
  316. count++;
  317. }
  318.  
  319. }
  320. // displayVertex(v1);
  321. stack.pop();
  322.  
  323. if (stack.isEmpty()) {
  324. for (int i = 0; i < nVerts; i++) {
  325. if (vertexList[i].wasVisited == false) {
  326. stack.push(i);
  327. displayVertex(stack.peek(),output);
  328. vertexList[i].wasVisited = true;
  329. count++;
  330. break;
  331. }
  332. }
  333. }
  334.  
  335. }
  336. //System.out.println("count "+ count);
  337. }//End of DFS method
  338.  
  339. void unvisted() {
  340. for (int i = 0; i < nVerts; i++) {
  341. vertexList[i].wasVisited = false;
  342.  
  343. }
  344. }
  345.  
  346. public void dijkstraWithHeap(int x,PrintWriter output){
  347. minHeap q = new minHeap(x);
  348.  
  349. // for (int i = 0; i < x; i++) {
  350. // vertexList[i].setDis(Integer.MAX_VALUE);
  351. // vertexList[i].src=null;
  352. // q.insert(vertexList[i], Integer.MAX_VALUE);
  353. // }
  354. for (int i = 0; i < x; i++) {
  355. vertexList[i].wasVisited=false;
  356. }
  357.  
  358. q.insert(vertexList[0], 0);
  359. vertexList[0].wasVisited=true;
  360. vertexList[0].src="0 ";
  361. Vertex[]array=new Vertex[x];
  362.  
  363. int counter1=0;
  364. int counter =0;
  365. while(!q.isEmpty()) {
  366.  
  367. for (int i = 0; i < x; i++) {
  368. if(adjMat[counter][i]>0&&!vertexList[i].wasVisited){
  369. q.insert(vertexList[i], Integer.MAX_VALUE);
  370. vertexList[i].wasVisited=true;
  371. vertexList[i].src=vertexList[counter].src+vertexList[i].label+" ";
  372. double z=adjMat[counter][i]+vertexList[counter].getDis();
  373. if(z<vertexList[i].getDis()){
  374. q.decreaseKey(vertexList[i],(int)z);
  375. }
  376. }
  377. }
  378. array[counter1++]=q.deleteMin();
  379. for (int i = 0; i < x; i++) {
  380. if(!q.isEmpty()&&vertexList[i].label==q.peek().label){
  381. counter=i;
  382. break;
  383. }
  384. }
  385.  
  386.  
  387.  
  388.  
  389.  
  390. //
  391. // Vertex ux = q.peek();
  392. // array[counter++]=ux;
  393. //
  394. // for (int j = 0; j < x; j++) {
  395. // if(adjMat[ux.label][j]>0){
  396. // if(ux.getDis()+adjMat[ux.label][j]<vertexList[j].getDis()){
  397. // vertexList[j].src=ux;
  398. // // System.out.println(vertexList[j].label+" "+vertexList[j].src.label+" new0 "+vertexList[j].getDis());
  399. // q.decreaseKey(vertexList[j],ux.getDis()+adjMat[ux.label][j]);
  400. // System.out.print("from "+ux.label+" to "+vertexList[j].label +" src ");
  401. // if(ux.src==null){
  402. // System.out.println("null");
  403. // }else
  404. // System.out.println(ux.src.label);
  405. //
  406. //
  407. // }
  408. // }
  409. //
  410. // }
  411. // q.remove();
  412. }
  413. Arrays.sort(array);
  414. output.println("\nShortest paths from 0 are:");
  415.  
  416. for (int i = 0; i < x; i++) {
  417. //Shortest paths from 0 are:
  418. //A path from 0 to 0: 0 (Length: 0.0)
  419. output.println("A path from 0 to "+array[i].label+": "+array[i].src+" (Length: "+array[i].getDis()+")");
  420. }
  421.  
  422.  
  423. }
  424. public void dijkstraWithUnordered(int x, PrintWriter output){
  425. Unoedered q = new Unoedered(x);
  426.  
  427. // for (int i = 0; i < x; i++) {
  428. // vertexList[i].setDis(Integer.MAX_VALUE);
  429. // vertexList[i].src=null;
  430. // q.insert(vertexList[i], Integer.MAX_VALUE);
  431. // }
  432. for (int i = 0; i < x; i++) {
  433. vertexList[i].wasVisited=false;
  434. }
  435.  
  436. q.insert(vertexList[0], 0);
  437. vertexList[0].wasVisited=true;
  438. vertexList[0].src="0 ";
  439. Vertex[]array=new Vertex[x];
  440.  
  441. int counter1=0;
  442. int counter =0;
  443. while(!q.isEmpty()) {
  444.  
  445. for (int i = 0; i < x; i++) {
  446. if(adjMat[counter][i]>0&&!vertexList[i].wasVisited){
  447. q.insert(vertexList[i], Integer.MAX_VALUE);
  448. vertexList[i].wasVisited=true;
  449. vertexList[i].src=vertexList[counter].src+vertexList[i].label+" ";
  450. double z=adjMat[counter][i]+vertexList[counter].getDis();
  451. if(z<vertexList[i].getDis()){
  452. q.decreaseKey(vertexList[i],(int)z);
  453. }
  454. }
  455. }
  456. array[counter1++]=q.deleteMin();
  457. for (int i = 0; i < x; i++) {
  458. if(!q.isEmpty()&&vertexList[i].label==q.peek().label){
  459. counter=i;
  460. break;
  461. }
  462. }
  463.  
  464.  
  465.  
  466.  
  467.  
  468. //
  469. // Vertex ux = q.peek();
  470. // array[counter++]=ux;
  471. //
  472. // for (int j = 0; j < x; j++) {
  473. // if(adjMat[ux.label][j]>0){
  474. // if(ux.getDis()+adjMat[ux.label][j]<vertexList[j].getDis()){
  475. // vertexList[j].src=ux;
  476. // // System.out.println(vertexList[j].label+" "+vertexList[j].src.label+" new0 "+vertexList[j].getDis());
  477. // q.decreaseKey(vertexList[j],ux.getDis()+adjMat[ux.label][j]);
  478. // System.out.print("from "+ux.label+" to "+vertexList[j].label +" src ");
  479. // if(ux.src==null){
  480. // System.out.println("null");
  481. // }else
  482. // System.out.println(ux.src.label);
  483. //
  484. //
  485. // }
  486. // }
  487. //
  488. // }
  489. // q.remove();
  490. }
  491. Arrays.sort(array);
  492. output.println("\nShortest paths from 0 are:");
  493.  
  494. for (int i = 0; i < x; i++) {
  495. //Shortest paths from 0 are:
  496. //A path from 0 to 0: 0 (Length: 0.0)
  497. output.println("A path from 0 to "+array[i].label+": "+array[i].src+" (Length: "+array[i].getDis()+")");
  498. }
  499.  
  500.  
  501. }
  502.  
  503.  
  504.  
  505.  
  506. }// End of Graph class
  507.  
  508.  
  509. // Class from which we can create Stack node objects
  510. class StackNode {
  511.  
  512. private int data;
  513. private StackNode next;
  514.  
  515. // CONSTRUCTORS
  516. public StackNode() {
  517. data = 0;
  518. next = null;
  519. }
  520.  
  521. public StackNode(int data) {
  522. this.data = data;
  523. next = null;
  524. }
  525.  
  526. public StackNode(int data, StackNode next) {
  527. this.data = data;
  528. this.next = next;
  529. }
  530.  
  531. // ACCESSORS
  532. public int getData() {
  533. return data;
  534. }
  535.  
  536. public StackNode getNext() {
  537. return next;
  538. }
  539.  
  540. // MUTATORS
  541. public void setData(int data) {
  542. this.data = data;
  543. }
  544.  
  545. public void setNext(StackNode next) {
  546. this.next = next;
  547. }
  548. } //End class Stack
  549.  
  550. //Class from which we can create fully functional Stacks (using linked lists)
  551. class StackLL {
  552. // top: reference variable to the top of the stack (same as "head" of linked list)
  553.  
  554. private StackNode top;
  555.  
  556. // CONSTRUCTOR
  557. public StackLL() {
  558. top = null;
  559. }
  560.  
  561. /* Below are MANY methods that are used on stacks.
  562. *
  563. * Examples:
  564. * isEmpty, PUSH, POP, PEEK, and more.
  565. */
  566. //
  567. // boolean | isEmpty()
  568. //
  569. public boolean isEmpty() {
  570. return top == null;
  571. }
  572.  
  573. //
  574. // void | PrintStack()
  575. //
  576. public void PrintStack(PrintWriter output) {
  577. PrintStack(top,output);
  578. }
  579. //
  580. // void | PrintStack(StackNode)
  581. //
  582.  
  583. private void PrintStack(StackNode top,PrintWriter output) {
  584. // We need to traverse...so we need a help ptr
  585. StackNode helpPtr = top;
  586. // Traverse to correct insertion point
  587. while (helpPtr != null) {
  588. // Print the data value of the node
  589. output.print(helpPtr.getData() + ", ");
  590. // Step one node over
  591. helpPtr = helpPtr.getNext();
  592. }
  593. System.out.println();
  594. }
  595.  
  596. //
  597. // boolean | search(int)
  598. //
  599. public boolean search(int data) {
  600. return search(top, data);
  601. }
  602. //
  603. // boolean | search(StackNode, int)
  604. //
  605.  
  606. private boolean search(StackNode p, int data) {
  607. // To search, we must traverse. Therefore, we need helpPtr.
  608. StackNode helpPtr = p;
  609. while (helpPtr != null) {
  610. if (helpPtr.getData() == data) {
  611. return true;
  612. }
  613. helpPtr = helpPtr.getNext(); // step one node over
  614. }
  615. return false;
  616. }
  617.  
  618. //
  619. // void | push(int)
  620. //
  621. public void push(int data) {
  622. top = push(top, data);
  623. }
  624. //
  625. // StackNode | push(StackNode, int)
  626. //
  627.  
  628. private StackNode push(StackNode top, int data) {
  629. // Make a new StackNode with "data" as the data value
  630. // and set the "next" of this new node to the same address as top
  631. // * This is the same as addToFront() method for Linked Lists.
  632. top = new StackNode(data, top);
  633.  
  634. // Now, return the newly updated top.
  635. return top;
  636. }
  637.  
  638. //
  639. // StackNode | pop()
  640. //
  641. public StackNode pop() {
  642. // Save a reference to the current top node (because we will change where top points to)
  643. StackNode temp = top;
  644.  
  645. // Now, invoke the pop method with top as a parameter.
  646. // This method will return a new top node.
  647. top = pop(top);
  648.  
  649. // Finally, return temp, which is the previous top node that we just "popped" off the list.
  650. return temp;
  651. }
  652. //
  653. // StackNode | pop(StackNode)
  654. //
  655.  
  656. private StackNode pop(StackNode top) {
  657. // Set top equal to the next node.
  658. // This will make top point to the 2nd node instead of the first node.
  659. top = top.getNext();
  660.  
  661. // return the address/reference of the new top node
  662. return top;
  663. }
  664.  
  665. //
  666. // int | peek()
  667. //
  668. public int peek() {
  669. // Invoke the peek method with top as a parameter
  670. int topValue = peek(top);
  671.  
  672. // return topValue
  673. return topValue;
  674. }
  675. //
  676. // int | peek(StackNode)
  677. //
  678.  
  679. private int peek(StackNode top) {
  680. // Return the data value of the top node.
  681. // You can see that we do NOT pop. We are only returning the data value.
  682. return top.getData();
  683. }
  684. } // End class StackLL
  685.  
  686. //=================================================
  687. //Class from which we can create fully functional Queues (using arrays)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!