Program To Create a Connection Using Graphs in Java Assignment Solution

Instructions

Objective

Write a java assignment program to create a connection using graphs.

Requirements and Specifications

Source Code

EXTENDED LETTER import java.util.Objects; public class ExtendedLetter extends Letter { private static final int SINGLETON = -1; private String content; private int family; private boolean related; public ExtendedLetter(String s) { this(s, SINGLETON); } public ExtendedLetter(String s, int fam) { super('a'); content = s; related = false; family = fam; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; ExtendedLetter that = (ExtendedLetter) o; if (that.family == family) { related = true; } return content.equals(that.content); } @Override public String toString() { if (isUnused() && related) { return "." + content + "."; } return decorator() + content + decorator(); } public static Letter[] fromStrings(String[] content, int[] codes) { Letter[] result = new Letter[content.length]; for (int i = 0; i if (codes == null) { result[i] = new ExtendedLetter(content[i]); } else { result[i] = new ExtendedLetter(content[i], codes[i]); } } return result; } } LETTER import java.util.Objects; public class Letter { private static final int UNSET = 0; private static final int UNUSED = 1; private static final int USED = 2; private static final int CORRECT = 3; private char letter; private int label; public Letter(char c) { letter = c; label = UNSET; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Letter letter1 = (Letter) o; return letter == letter1.letter; } public String decorator() { switch (label) { case UNSET: return " "; case UNUSED: return "-"; case USED: return "+"; case CORRECT: return "!"; default: throw new IllegalStateException(); } } @Override public String toString() { return decorator() + letter + decorator(); } public void setUnused() { label = UNUSED; } public void setUsed() { label = USED; } public void setCorrect() { label = CORRECT; } public boolean isUnused() { return label == UNUSED; } public static Letter[] fromString(String s) { Letter[] result = new Letter[s.length()]; for (int i = 0; i result[i] = new Letter(s.charAt(i)); } return result; } } WORD public class Word { private LinearNode firstNode; public Word(Letter[] letters) { for (int i = letters.length - 1; i>=0; i--) { LinearNode newNode = new LinearNode<>(letters[i]); newNode.setNext(firstNode); firstNode = newNode; } } @Override public String toString() { StringBuilder builder = new StringBuilder("Word: "); LinearNode current = firstNode; while(current != null) { builder.append(current.getElement().toString()).append(" "); current = current.getNext(); } return builder.toString(); } // this is the only method, which is not described strictly in the paper, // so it is the only one, which must be commented in details. public boolean labelWord(Word mystery) { // firstly we set used/unused for all letters in this word // iterating through all letters in this word LinearNode current = firstNode; while(current != null) { Letter l = current.getElement(); // trying to find current letter 'l' in this word LinearNode mysteryCurr = mystery.firstNode; // trying to find letter 'l' in word mystery while (mysteryCurr != null) { Letter mysteryL = mysteryCurr.getElement(); if (l.equals(mysteryL)) { // letter 'l' was found in mystery, setting letter l as used l.setUsed(); break; } mysteryCurr = mysteryCurr.getNext(); } // if we walked through all the letters in mystery and did not find letter l, setting it as unused if (mysteryCurr == null) { l.setUnused(); } // going to next letter of this word. // maybe some letters in this word are the same, but we don't care - just making the same current = current.getNext(); } // now we need to set letters as 'correct' if they are in a correct place // we start parallel iterations over both words current = firstNode; LinearNode mysteryCurr = mystery.firstNode; // if there will be no matches, this variable will remain true boolean equals = true; // we will iterate until both words are not over while(current != null && mysteryCurr != null) { Letter l = current.getElement(); Letter mysteryL = mysteryCurr.getElement(); // comparing current letters for both words. If they match, setting 'correct' if (l.equals(mysteryL)) { l.setCorrect(); } else { equals = false; } // shifting to next letter current = current.getNext(); mysteryCurr = mysteryCurr.getNext(); } // if words had different length, setting equals var to false if (current != null || mysteryCurr != null) { equals = false; } return equals; } } WORD LL public class WordLL { private Word mysteryWord; private LinearNode history; public WordLL(Word mystery) { mysteryWord = mystery; history = null; } public boolean tryWord(Word guess) { // checking if word matches boolean equals = guess.labelWord(mysteryWord); // appending new guess to history LinearNode newWord = new LinearNode<>(guess); newWord.setNext(history); history = newWord; // returning comparing result return equals; } @Override public String toString() { LinearNode current = history; StringBuilder builder = new StringBuilder(); while(current != null) { builder.append(current.getElement().toString()).append(System.lineSeparator()); current = current.getNext(); } return builder.toString(); } }Source Code DJ SET import java.util.*; public class djset { final public static int N = 10; public int[] parent; // this array will store set sizes: sizes[find(v)] is the size of set, contatining v public int[] sizes; // Creates a disjoint set of size n (0, 1, ..., n-1) public djset(int n) { parent = new int[n]; sizes = new int[n]; for (int i = 0; i < n; i++) { parent[i] = i; sizes[i] = 1; } } public int find(int v) { // I am the club president!!! (root of the tree) if (parent[v] == v) return v; // Find my parent's root. int res = find(parent[v]); // Attach me directly to the root of my tree. parent[v] = res; return res; } public boolean union(int v1, int v2) { // Find respective roots. int rootv1 = find(v1); int rootv2 = find(v2); // No union done, v1, v2 already together. if (rootv1 == rootv2) return false; // Attach tree of v2 to tree of v1. parent[rootv2] = rootv1; // merging sizes of sets togethers sizes[rootv1] += sizes[rootv2]; // clearing size of the second set sizes[rootv2] = 0; return true; } // method for calculating connectivity, according to task rules public long connectivity() { // we just beed to make sum of all squares long sum = 0; for (int i : sizes) { long l = i; sum += l*l; } return sum; } // For testing. public void print() { for (int i = 0; i < parent.length; i++) System.out.print(parent[i] + " "); System.out.println(); } // Run a little test. public static void main(String[] args) { djset set = new djset(N); Random r = new Random(); int numUnion = 0; // Union N-1 times. while (numUnion < N - 1) { // Make v1 and v2 two distinct values. int v1 = r.nextInt(N); int v2 = v1; while (v2 == v1) v2 = r.nextInt(N); System.out.println("Union of " + v1 + " and " + v2); boolean res = set.union(v1, v2); // Already in the same tree/set. if (!res) System.out.println("Already together"); // Merge them. else { System.out.println("Merged the two trees."); numUnion++; } // Let's look at the set. set.print(); } } } DESTROY import java.io.File; import java.io.IOException; import java.util.*; import java.util.stream.Collectors; public class destroy { public static void main(String[] args) throws IOException { // reading input from console try (Scanner scanner = new Scanner(new File("input.txt"))) { // reading first line String[] nmd = scanner.nextLine().split("\\s+"); // parsing n, m and d int n = Integer.parseInt(nmd[0]); int m = Integer.parseInt(nmd[1]); int d = Integer.parseInt(nmd[2]); // creating empty graph adjacency matrix djset djset = new djset(n); // creating an array of edges int[][] edges = new int[m][2]; for (int i = 0; i < m; i++) { // reading each edge from input String[] parts = scanner.nextLine().split("\\s+"); int a = Integer.parseInt(parts[0]) - 1; int b = Integer.parseInt(parts[1]) - 1; // adding edge to edge array edges[i][0] = a; edges[i][1] = b; } // this linked list will contain all edges, which must be deleted in reversed order LinkedList edgesToDelete = new LinkedList<>(); for (int i = 0; i < d; i++) { // parsing index of edge destructed int dest = Integer.parseInt(scanner.nextLine().trim()) - 1; // adding next one to the beginning, to make list reversed edgesToDelete.addFirst(dest); } // first of all, we create djset for graph without all edges for deletion LinkedList result = new LinkedList<>(); for (int i = 0; i < m; i++) { if (edgesToDelete.contains(i)) { continue; } djset.union(edges[i][0], edges[i][1]); } // obtained set will have connectivity, which must be outputted last // here we also reverse the list by adding next value to the beginning result.addFirst(djset.connectivity()); // iterating over all edges to delete: we add last edge to delete to get previous configuration for (int i : edgesToDelete) { // linking connected sets djset.union(edges[i][0], edges[i][1]); // recalculating connectivity and pushing it result.addFirst(djset.connectivity()); } // outputting result list content, separated by new line character System.out.println(result.stream().map(l -> Long.toString(l)).collect(Collectors.joining(System.lineSeparator()))); } } }