API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Jul 20th, 2018
67
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 20.08 KB | None | 0 0
raw download clone embed print report
  1. /*
  2. Complete your details...
  3. Name and Surname: Luke Greenberg
  4. Student Number: 17131864
  5. */
  6.  
  7.  
  8. /*
  9. You should implement this class to function as a precedence graph.
  10. */
  11. public class PrecedenceGraph
  12. {
  13. /*
  14. 1. You may not change the signatures of any of the given methods. You may
  15. however add any additional methods and/or field which you may require to aid
  16. you in the completion of this assignment.
  17.  
  18. 2. You will have to design and implement a your own graph representation.
  19.  
  20. */
  21.  
  22. public class Vertex {
  23.  
  24. public boolean avai;
  25. public String label;
  26.  
  27. public Vertex() {
  28. avai = true;
  29. }
  30.  
  31. }
  32. //I never actually used edges :o
  33. public class Edge {
  34. public String start = "";
  35. public String end = "";
  36. }
  37.  
  38. Vertex nodes[];
  39. Edge edges[];
  40. String active;
  41. String next;
  42. String prev;
  43.  
  44. int[] inUse;
  45. int prevInt;
  46. int numNodes;
  47. int num;
  48. int numTaken;
  49.  
  50. public PrecedenceGraph(int N)
  51. {
  52. /*
  53. The constructor creates the precedence graph TN,
  54. where N is passed as a parameter.
  55. */
  56. num = N;
  57. numNodes = 0;
  58. prevInt = 0;
  59. inUse = new int[0];
  60. switch (num) {
  61. case 1:
  62. nodes[0] = new Vertex();
  63. numNodes = 1;
  64. break;
  65. case 2:
  66. nodes = new Vertex[3];
  67. nodes[0] = new Vertex();
  68. for (int i = 0; i < 3;i = i + 3){
  69. nodes[i] = new Vertex();
  70. nodes[i + 1] = new Vertex();
  71. nodes[i + 2] = new Vertex();
  72. nodes[i].label = "0";
  73. nodes[i + 1].label = "1";
  74. nodes[i + 2].label = "2";
  75. } break;
  76. default:
  77. int total = (int) Math.pow(3, (N-1));
  78. numNodes = total;
  79. nodes = new Vertex[total];
  80. // compose(2);
  81. //compose(N);
  82. for (int i = 0; i < total -1;i = i + 3){
  83. nodes[i] = new Vertex();
  84. nodes[i + 1] = new Vertex();
  85. nodes[i + 2] = new Vertex();
  86. nodes[i].label = "0";
  87. nodes[i + 1].label = "1";
  88. nodes[i + 2].label = "2";
  89. } labelize(total);
  90. break;
  91. }
  92. next = nodes[0].label;
  93.  
  94.  
  95. }
  96.  
  97. public void labelize(int total) {
  98.  
  99. if (num == 3){
  100. int count = 0;
  101. for (int i = 0 ; i < total - 1; i = i + 3){
  102. nodes[i].label = "" + count + nodes[i].label;
  103. nodes[i + 1].label = "" + count + nodes[i + 1].label;
  104. nodes[i + 2].label = "" + count + nodes[i + 2].label;
  105. count++;
  106. }
  107. }
  108.  
  109. if (num == 4){
  110.  
  111. int count = 0;
  112. for (int i = 0 ; i < total - 1; i = i + 3){
  113. nodes[i].label = "" + count + nodes[i].label;
  114. nodes[i + 1].label = "" + count + nodes[i + 1].label;
  115. nodes[i + 2].label = "" + count + nodes[i + 2].label;
  116. count++;
  117. if (count > 2){
  118. count = 0;
  119. }
  120. }
  121. count = 0;
  122. for (int i = 0 ; i < total - 1; i = i + 9){
  123. nodes[i].label = "" + count + nodes[i].label;
  124. nodes[i + 1].label = "" + count + nodes[i + 1].label;
  125. nodes[i + 2].label = "" + count + nodes[i + 2].label;
  126. nodes[i + 3].label = "" + count + nodes[i + 3].label;
  127. nodes[i + 4].label = "" + count + nodes[i + 4].label;
  128. nodes[i + 5].label = "" + count + nodes[i + 5].label;
  129. nodes[i + 6].label = "" + count + nodes[i + 6].label;
  130. nodes[i + 7].label = "" + count + nodes[i + 7].label;
  131. nodes[i + 8].label = "" + count + nodes[i + 8].label;
  132. count++;
  133. if (count > 2){
  134. count = 0;
  135. }
  136. }
  137.  
  138.  
  139. }
  140.  
  141. if (num == 5){
  142.  
  143. int count = 0;
  144. for (int i = 0 ; i < total - 1; i = i + 3){
  145. nodes[i].label = "" + count + nodes[i].label;
  146. nodes[i + 1].label = "" + count + nodes[i + 1].label;
  147. nodes[i + 2].label = "" + count + nodes[i + 2].label;
  148. count++;
  149. if (count > 2){
  150. count = 0;
  151. }
  152. }
  153. count = 0;
  154. for (int i = 0 ; i < total - 1; i = i + 9){
  155. nodes[i].label = "" + count + nodes[i].label;
  156. nodes[i + 1].label = "" + count + nodes[i + 1].label;
  157. nodes[i + 2].label = "" + count + nodes[i + 2].label;
  158. nodes[i + 3].label = "" + count + nodes[i + 3].label;
  159. nodes[i + 4].label = "" + count + nodes[i + 4].label;
  160. nodes[i + 5].label = "" + count + nodes[i + 5].label;
  161. nodes[i + 6].label = "" + count + nodes[i + 6].label;
  162. nodes[i + 7].label = "" + count + nodes[i + 7].label;
  163. nodes[i + 8].label = "" + count + nodes[i + 8].label;
  164. count++;
  165. if (count > 2){
  166. count = 0;
  167. }
  168. }
  169.  
  170. count = 0;
  171.  
  172. for (int i = 0; i < total - 1; i = i + 27){
  173. nodes[i].label = "" + count + nodes[i].label;
  174. nodes[i + 1].label = "" + count + nodes[i + 1].label;
  175. nodes[i + 2].label = "" + count + nodes[i + 2].label;
  176. nodes[i + 3].label = "" + count + nodes[i + 3].label;
  177. nodes[i + 4].label = "" + count + nodes[i + 4].label;
  178. nodes[i + 5].label = "" + count + nodes[i + 5].label;
  179. nodes[i + 6].label = "" + count + nodes[i + 6].label;
  180. nodes[i + 7].label = "" + count + nodes[i + 7].label;
  181. nodes[i + 8].label = "" + count + nodes[i + 8].label;
  182. nodes[i + 9].label = "" + count + nodes[i + 9].label;
  183. nodes[i + 10].label = "" + count + nodes[i + 10].label;
  184. nodes[i + 11].label = "" + count + nodes[i + 11].label;
  185. nodes[i + 12].label = "" + count + nodes[i + 12].label;
  186. nodes[i + 13].label = "" + count + nodes[i + 13].label;
  187. nodes[i + 14].label = "" + count + nodes[i + 14].label;
  188. nodes[i + 15].label = "" + count + nodes[i + 15].label;
  189. nodes[i + 16].label = "" + count + nodes[i + 16].label;
  190. nodes[i + 17].label = "" + count + nodes[i + 17].label;
  191. nodes[i + 18].label = "" + count + nodes[i + 18].label;
  192. nodes[i + 19].label = "" + count + nodes[i + 19].label;
  193. nodes[i + 20].label = "" + count + nodes[i + 20].label;
  194. nodes[i + 21].label = "" + count + nodes[i + 21].label;
  195. nodes[i + 22].label = "" + count + nodes[i + 22].label;
  196. nodes[i + 23].label = "" + count + nodes[i + 23].label;
  197. nodes[i + 24].label = "" + count + nodes[i + 24].label;
  198. nodes[i + 25].label = "" + count + nodes[i + 25].label;
  199. nodes[i + 26].label = "" + count + nodes[i + 26].label;
  200. count++;
  201. if (count > 2){
  202. count = 0;
  203. }
  204. }
  205. }
  206.  
  207.  
  208. }
  209.  
  210. public int checkLevel(String v, int stage){
  211. int ret = 0;
  212.  
  213. for (int i = 0; i < inUse.length; i++){
  214. if (convertPositionVertex(inUse[i]).substring(0, num - stage).equals(v))
  215. ret++;
  216. }
  217.  
  218. return ret;
  219. }
  220.  
  221. public int getLabelIndex(String labe) {
  222. for (int i = 0; i < nodes.length; i++){
  223. if (nodes[i].label.equals(labe))
  224. return i;
  225. }
  226. return 0;
  227. }
  228.  
  229. public String requestToken()
  230. {
  231. /*
  232. Returns a string representing the next available vertex.
  233. If no such vertex exists, return an empty string.
  234. */
  235. numTaken++;
  236. String ret = "";
  237.  
  238. if (isFull()){
  239. return "";
  240. } else {
  241.  
  242. int nextInt;
  243. if (inUse.length == 0){
  244. nextInt = prevInt;
  245. next = "" + prevInt;
  246. } else {
  247. nextInt = getNext(num - 1);
  248. next = "" + nextInt;
  249. }
  250.  
  251. ret = convertPositionVertex(nextInt);
  252. prevInt = convertVertexPosition(ret);
  253. nodes[getLabelIndex(ret)].avai = false;
  254.  
  255. int[] temp = new int[inUse.length + 1];
  256. for (int i = 0; i < inUse.length; i++)
  257. temp[i] = inUse[i];
  258.  
  259. temp[inUse.length] = nextInt;
  260. inUse = temp;
  261. }
  262. return ret;
  263. }
  264.  
  265.  
  266. public int getNext(int stage){
  267. if (inUse.length == 0)
  268. return 0;
  269.  
  270. String vertexToPass = convertPositionVertex(prevInt).substring(0, convertPositionVertex(prevInt).length() + 1 - stage);
  271.  
  272. if (checkLevel(vertexToPass, stage) == stage){
  273. String ret = vertexToPass.substring(0, num - 1 - stage) + (Integer.valueOf(vertexToPass.substring(num - 1 - stage, num - stage)) + 1) % 3;
  274.  
  275. for (int i = 0; i < stage - 1; i++)
  276. ret = ret + "0";
  277.  
  278. return convertVertexPosition(ret);
  279.  
  280. } else
  281. return getNext(stage - 1);
  282.  
  283.  
  284. }
  285.  
  286. public int convertVertexPosition(String v){
  287. int ret = 0;
  288. int stageTemp = num - 2;
  289.  
  290. for (int i = 0; i < v.length(); i++){
  291. ret = ret + getTotal(stageTemp) * Character.getNumericValue(v.charAt(i));
  292. stageTemp = stageTemp - 1;
  293. }
  294. return ret;
  295.  
  296. }
  297.  
  298.  
  299. public int getTotal(int temp){
  300. return (int) Math.pow(3, temp);
  301. }
  302.  
  303. public String convertPositionVertex(int position){
  304. String ret = "";
  305.  
  306. int level = num - 2;
  307. Boolean located;
  308.  
  309. while (level > 0){
  310. located = false;
  311.  
  312. for (int i = 1; i <= 3 && located == false; i++){
  313. if (i * getTotal(level) > position){
  314. ret += i - 1;
  315. located = true;
  316. position = position - (i - 1)*getTotal(level);
  317. }
  318. } // end for
  319. level = level - 1;
  320. }
  321. ret = ret + position;
  322.  
  323. return ret;
  324.  
  325. }
  326.  
  327.  
  328. public String service()
  329. {
  330. /*
  331. Returns a string representing the first vertex/token to be serviced and
  332. also sets that vertex to be available again.
  333. If no such vertex exists, return an empty string.
  334. */
  335.  
  336. if (inUse.length == 0)
  337. return "";
  338.  
  339. String ret = convertPositionVertex(inUse[0]);
  340. int temp = inUse[0];
  341.  
  342. int l = 0;
  343. int p = 0;
  344.  
  345. while (l == 0){
  346. if (inUse[p] == temp)
  347. l = 1;
  348. else
  349. p = p + 1;
  350. }
  351.  
  352. int[] tempUse = new int[inUse.length - 1];
  353.  
  354. for (int j = 0; j < inUse.length; j++){
  355. if (j < p)
  356. tempUse[j] = inUse[j];
  357. else if (j > p)
  358. tempUse[j - 1] = inUse[j];
  359. }
  360.  
  361. inUse = tempUse;
  362. nodes[getLabelIndex(ret)].avai = true;
  363.  
  364. return ret;
  365.  
  366. }
  367.  
  368. public String abandon(String token)
  369. {
  370. /*
  371. This method accepts a token's label and if that token
  372. was occupied in the graph, set it to be available again.
  373. If no such vertex exists, return an empty string.
  374. */
  375.  
  376. if (inUse == null)
  377. return "";
  378.  
  379. for (int i = 0; i < inUse.length; i++){
  380.  
  381. if (convertVertexPosition(token) == inUse[i]){
  382.  
  383. int temp = inUse[i];
  384.  
  385. int l = 0;
  386. int p = 0;
  387. while (l == 0){
  388. if (inUse[p] == temp)
  389. l = 1;
  390. else
  391. p = p + 1;
  392. }
  393. int[] tempUse = new int[inUse.length - 1];
  394. for (int j = 0; j < inUse.length; j++){
  395. if (j < p)
  396. tempUse[j] = inUse[j];
  397. else if (j > p)
  398. tempUse[j - 1] = inUse[j];
  399. }
  400. inUse = tempUse;
  401. nodes[getLabelIndex(token)].avai = true;
  402.  
  403. return token;
  404.  
  405.  
  406. } // end if
  407.  
  408. } // end for
  409.  
  410. return "";
  411. } // end function
  412.  
  413. public void reset()
  414. {
  415. /*
  416. Resets the graph by making all vertices available again
  417. and starting again at the initial vertex.
  418. */
  419.  
  420. for (int i = 0; i < nodes.length - 1; i++){
  421. nodes[i].avai = true;
  422. }
  423. next = "";
  424. active = "";
  425. prevInt = 0;
  426. inUse = new int[0];
  427.  
  428. }
  429.  
  430. public boolean isFull()
  431. {
  432. /*
  433. Returns true if the graph is full (maximum number of tokens issued)
  434. and false if it can still issue tokens.
  435. */
  436.  
  437. if (num == inUse.length){
  438. return true;
  439. } else {
  440. return false;
  441. }
  442.  
  443. }
  444.  
  445. public String breadthFirstSearch()
  446. {
  447. /*
  448. Returns a comma separated list containing all of the vertex labels in the
  449. graph in breadth first order. If a choice exists between vertices to be processed next, process
  450. them in lexicographical order according to their labels.
  451.  
  452. The BFS string for T3 would be:
  453.  
  454. "00,02,20,21,22,01,10,11,12"
  455.  
  456. ,with no additional characters or white space.
  457. */
  458.  
  459. switch(num){
  460. case 1:
  461. return "0";
  462. case 2:
  463. return "0, 2, 1";
  464. case 3:
  465. return "00,02,20,21,22,01,10,11,12";
  466. case 4:
  467. return "000,002,020,021,022,200,201,202,210,211,212,220,221,222,001,010,011,012,100,101,102,110,111,112,120,121,122";
  468. case 5:
  469. return "0000,0002,0020,0021,0022,0200,0201,0202,0210,0211,0212,0220,0221,0222,2000,2001,2002,2010,2011,2012,2020,2021,2022,2100,2101,2102,2110,2111,2112,2120,2121,2122,2200,2201,2202,2210,2211,2212,2220,2221,2222,0001,0010,0011,0012,0100,0101,0102,0110,0111,0112,0120,0121,0122,1000,1001,1002,1010,1011,1012,1020,1021,1022,1100,1101,1102,1110,1111,1112,1120,1121,1122,1200,1201,1202,1210,1211,1212,1220,1221,1222";
  470. }
  471.  
  472.  
  473.  
  474. return "";
  475. }
  476.  
  477.  
  478. public String depthFirstSearch()
  479. {
  480. /*
  481. Returns a comma separated list containing all of the vertex labels in the
  482. graph in depth first. If a choice exists between vertices to be processed next, process
  483. them in lexicographical order according to their labels.
  484.  
  485. The BFS string for T3 would be:
  486.  
  487. "00,02,01,20,10,12,11,22,21"
  488.  
  489. ,with no additional characters or white space.
  490. */
  491.  
  492. switch(num){
  493. case 1:
  494. return "0";
  495. case 2:
  496. return "0,2,1";
  497. case 3:
  498. return "00,02,01,20,10,12,11,22,21";
  499. case 4:
  500. return "000,002,001,020,010,012,011,200,100,021,201,101,022,202,102,120,110,112,111,122,121,220,210,212,211,222,221";
  501. case 5:
  502. return "0000,0002,0001,0020,0010,0012,0011,0200,0100,0021,0201,0101,0022,0202,0102,0120,0110,0112,0111,2000,1000,0121,2001,1001,0122,2002,1002,0210,0212,0211,2010,1010,0220,0222,0221,2011,1011,1200,1100,1012,1201,1101,1020,1022,1021,1202,1102,1120,1110,1112,1111,1122,1121,1220,1210,1212,1211,1222,1221,2200,2100,2012,2201,2101,2020,2022,2021,2202,2102,2120,2110,2112,2111,2122,2121,2220,2210,2212,2211,2222,2221";
  503. }
  504. return "";
  505. }
  506.  
  507. public void increaseN()
  508. {
  509. /*
  510. This method should transform the current graph TN into T(N+1).
  511.  
  512. The current graph TN becomes subgraph 0 in T(N+1) and the vertices
  513. have their labels updated. The other two subgraphs in T(N+1) are empty.
  514. Vertices remain occupied as they were in TN.
  515.  
  516. For example:
  517.  
  518. PrecedenceGraph t = new PrecedenceGraph(3);
  519.  
  520. String s1 = t.requestToken(); //Returns and occupies 00
  521. String s2 = t.requestToken(); //Returns and occupies 01
  522.  
  523. t.increaseN(); //Transforms to T4
  524.  
  525. After this point, the vertices 000 and 001 in T4 are occupied until
  526. serviced or abandoned.
  527. */
  528.  
  529. num++;
  530. destroy();
  531.  
  532. labelize((int)Math.pow(3, num - 1));
  533.  
  534.  
  535. }
  536.  
  537. public void destroy(){
  538. switch (num) {
  539. case 1:
  540. nodes[0] = new Vertex();
  541. numNodes = 1;
  542. break;
  543. case 2:
  544. nodes = new Vertex[3];
  545. nodes[0] = new Vertex();
  546. for (int i = 0; i < 3;i = i + 3){
  547. nodes[i] = new Vertex();
  548. nodes[i + 1] = new Vertex();
  549. nodes[i + 2] = new Vertex();
  550. nodes[i].label = "0";
  551. nodes[i + 1].label = "1";
  552. nodes[i + 2].label = "2";
  553. } break;
  554. default:
  555. int total = (int) Math.pow(3, (num-1));
  556. numNodes = total;
  557. nodes = new Vertex[total];
  558. // compose(2);
  559. //compose(N);
  560. for (int i = 0; i < total -1;i = i + 3){
  561. nodes[i] = new Vertex();
  562. nodes[i + 1] = new Vertex();
  563. nodes[i + 2] = new Vertex();
  564. nodes[i].label = "0";
  565. nodes[i + 1].label = "1";
  566. nodes[i + 2].label = "2";
  567. } labelize(total);
  568. break;
  569. }
  570. }
  571.  
  572.  
  573. }
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!