Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.HashMap;
- import java.util.ArrayList;
- import java.util.Scanner;
- import java.util.Comparator;
- import java.util.PriorityQueue;
- import java.util.Stack;
- import java.util.Set;
- import java.util.regex.Pattern;
- import java.util.regex.Matcher;
- import java.io.File;
- import java.io.FileNotFoundException;
- import java.io.IOException;
- class Oblig3 {
- private static String config = "config.txt";
- private static String data = "data.txt";
- private static Scanner sc;
- private static Graph graph;
- public static void main (String [] args) throws IOException {
- if (args != null) {
- if (args[0] != null) {
- config = args[0];
- if (args[1] != null) {
- data = args[1];
- } else {
- System.out.println("ERROR: Invalid user input.");
- }
- }
- }
- if (!config.equals("") && !data.equals("")) {
- sc = new Scanner(new File(config));
- graph = new Graph();
- // Network configuration from input file
- while (sc.hasNextLine()) {
- String [] line = sc.nextLine().split("[\t ]+");
- int [] attributes = new int[line.length];
- for (int i=0; i<line.length; i++) {
- attributes[i] = Integer.parseInt(line[i].trim());
- }
- graph.add(attributes);
- }
- sc = new Scanner(new File(data));
- HashMap<Integer, Graph.Vertex> g = graph.getGraph();
- // Data elements setup
- while (sc.hasNextLine()) {
- String [] line = sc.nextLine().split("[\t ]+");
- int [] data = new int[line.length];
- for (int i=0; i<line.length; i++) {
- data[i] = Integer.parseInt(line[i].trim());
- }
- // Nodene får riktige elementer: OK!
- // Set the vertex data capacity
- Graph.Vertex v = g.get(data[0]);
- v.setCapacity(data[1]);
- // Add data elements to the vertex
- for (int i=1; i<data.length; i++) {
- v.addElement(data[i]);
- }
- }
- }
- sc = new Scanner(System.in);
- // Run shell
- while (true) {
- // Search preference = T || C || B (pick shortest time || cost || both), Data ownership = O (original copy) || = A (any copy)
- System.out.println("Submit data element request on format <machine_id>:<search_preference>:<ownership_preference>: <list_of_data_elements> (press q to quit)");
- System.out.print("shell> ");
- String [] rqln = sc.nextLine().split("[: ]+");
- if (rqln.length < 4) {
- if (rqln[0].equals("q")) {
- System.out.println("Ending program");
- break;
- }
- System.out.println("Invalid command.");
- } else {
- ArrayList<Integer> elements = new ArrayList<Integer>();
- for (int i=0; i<rqln.length; i++) {
- System.out.println("index " + i + " has " + rqln[i]);
- }
- for (int i=3; i<rqln.length; i++) {
- elements.add(Integer.parseInt(rqln[i]));
- }
- System.out.println(elements.size() + " number of elements requested for.");
- graph.sendRequest(Integer.parseInt(rqln[0]), rqln[1], rqln[2], elements);
- }
- }
- }
- }
- class Graph {
- // Contains the graph data structure.
- protected HashMap<Integer, Vertex> graph;
- // Number of elements in the graph
- protected int size = 0;
- // Used for Dijkstra's algorithm
- protected ArrayList<Vertex> visited, unvisited;
- protected ArrayList<Vertex> tmpVisited, tmpUnvisited;
- // Default constructor
- public Graph() {
- graph = new HashMap<Integer, Vertex>();
- visited = new ArrayList<Vertex>();
- unvisited = new ArrayList<Vertex>();
- }
- /**
- * Adds a vertex to the graph with specified input data in integer array parameter
- * @param data array of data
- */
- public void add(int [] data) {
- if (data == null || data.length < 4)
- return;
- Vertex v1, v2;
- int edgetime;
- int costval;
- // Creates the first vertex in config file if it does not exist
- if (!graph.containsKey(data[0])) {
- v1 = new Vertex(data[0], data[1]);
- edgetime = data[2];
- costval = data[3];
- graph.put(data[0], v1);
- size++;
- }
- // Otherwise, add the edge to the vertex manually
- else {
- v1 = graph.get(data[0]);
- edgetime = data[2];
- costval = data[3];
- }
- // Creates the new biconnected vertex if it does not exist
- if (!graph.containsKey(data[1])) {
- v2 = new Vertex(data[1], data[0]);
- edgetime = data[2];
- costval = data[3];
- graph.put(data[1], v2);
- size++;
- }
- // Otherwise, get it from the hashmap.
- else {
- v2 = graph.get(data[1]);
- edgetime = data[2];
- costval = data[3];
- }
- v1.addEdge(v2, edgetime, costval);
- v2.addEdge(v1, edgetime, costval);
- }
- public HashMap<Integer, Vertex> getGraph() {
- return graph;
- }
- /**
- * Handles a request from one machine to another.
- * @param id id of requesting machine
- * @param spref search preference of request
- * @param typepref type preference of request
- * @param requests requested data elements
- */
- public void sendRequest(int id, String spref, String typepref, ArrayList<Integer> requests) {
- if (graph.get(id) == null)
- System.out.println("Network vertex " + id + " does not exist.");
- else if (requests.size() <= 0)
- System.out.println("No requests was specified.");
- else if (spref.equals("C")) {
- for (int i=0; i<requests.size(); i++) {
- printPath(transferFileOnCost(requests.get(i), typepref, id), requests.get(i));
- }
- }
- else if (spref.equals("T")) {
- }
- else if (spref.equals("B")) {
- }
- }
- public Stack<Vertex> transferFileOnCost(int request, String type, int source) {
- // Get the source node, and add it into path FIFO.
- Vertex src_node = graph.get(source);
- Stack<Vertex> path = new Stack<Vertex>();
- // Set distance to itself to 0.
- src_node.dist = 0;
- src_node.known = true;
- // Compute the path from one node to another node storing the correct element.
- return uniformCostSearch(src_node, request);
- }
- private Stack<Vertex> uniformCostSearch(Vertex src, int requestedElement) {
- Vertex current = src, previous = null;
- Heap heap = new Heap(size);
- ArrayList<Vertex> visited = new ArrayList<Vertex>();
- Stack<Vertex> path = new Stack<Vertex>();
- HeapItem item = new HeapItem(current, null, 0, 0);
- HeapItem currentItem = item, previousItem = null;
- heap.insert(item);
- visited.add(current);
- while (!heap.isEmpty()) {
- // Get highest priority element from heap.
- currentItem = heap.deleteMin();
- if (previousItem != null)
- currentItem.previousnode = previousItem.node;
- // If the data element was found in current node, return path.
- if (currentItem.node.hasElement(requestedElement)) {
- Vertex currentVertex = currentItem.node;
- path.push(currentVertex);
- currentVertex = currentVertex.previous;
- while (currentVertex != null) {
- path.push(currentVertex);
- currentVertex = currentVertex.previous;
- }
- return path;
- }
- if (visited.contains(currentItem.node)) {
- continue;
- }
- for (Edge e : currentItem.node.adjacencies) {
- HeapItem itm = null;
- Vertex v = e.v1;
- Vertex adjacency = e.v2;
- adjacency.costcount = e.cost + previousItem.costcount;
- if (!visited.contains(adjacency)) {
- if (!heap.contains(currentItem)) {
- itm = new HeapItem(adjacency, currentItem.node, adjacency.costcount, e.time);
- heap.insert(itm);
- itm.previousnode = previousItem.node;
- adjacency.previous = currentItem.node;
- }
- if ((previousItem.costcount + e.cost) > (v.costcount + e.cost)) {
- if (itm != null) {
- itm.previousnode = v;
- adjacency.previous = v;
- }
- else {
- //heap.remove(itm);
- itm = new HeapItem(adjacency, v, adjacency.costcount, e.time);
- heap.insert(itm);
- adjacency.previous = v;
- }
- itm = null;
- }
- } else {
- continue;
- }
- }
- previousItem = currentItem;
- }
- return null;
- }
- public void printPath(Stack<Vertex> queue, int element) {
- if (queue != null) {
- System.out.print("Element " + element + ":");
- while (!queue.empty()) {
- System.out.print(queue.pop().id + "->");
- }
- }
- else {
- System.out.println("Data element unreachable or non-existent.");
- }
- }
- class Heap {
- private int size;
- private HeapItem array [];
- private int numElements;
- // Default constructor
- public Heap (int size) {
- this.size = size;
- array = new HeapItem[size];
- numElements = 0;
- }
- /**
- * Inserts a HeapItem into the heap.
- * @param v the item to be inserted
- */
- public void insert(HeapItem v) {
- if (numElements == array.length-1)
- enlargeArray( array.length * 2 + 1 );
- int hole = ++numElements;
- for ( ; hole > 1 && v.compareTo(array[hole/2]) < 0; hole /= 2)
- array[hole] = array[hole/2];
- array[hole] = v;
- }
- /**
- * Returns and deletes the minimum (highest priority) vertex from the heap
- * @return minItem the vertex
- * @see findMin()
- * @see percolateDown()
- */
- public HeapItem deleteMin() {
- if (numElements == 0) {
- array = null;
- return null;
- } else {
- HeapItem minItem = findMin();
- array[1] = array[numElements--];
- percolateDown(1);
- return minItem;
- }
- }
- /**
- * Returns the minimum (high priority) from the heap at array position 1
- * @return array[1] if the array is not null
- * null if the heap is empty
- */
- public HeapItem findMin() {
- if(array != null) {
- return array[1];
- } else {
- return null;
- }
- }
- /**
- * Checks to see if the heap is empty.
- * @return true if empty
- * false if not empty
- */
- public boolean isEmpty() {
- return numElements == 0;
- }
- /**
- * Percolate-down function. Used for d
- * @param hole the hole where percolating should start (array index 1)
- */
- private void percolateDown(int hole) {
- int child;
- HeapItem tmp = array[hole];
- for ( ; hole * 2 <= numElements; hole = child) {
- child = hole * 2;
- if (child != numElements && array[child+1].compareTo(array[child]) < 0)
- child++;
- if (array[child].compareTo(tmp) < 0)
- array[hole] = array[child];
- else
- break;
- }
- array[hole] = tmp;
- }
- /**
- * Percolate-up method for óbject. Runs decreaseKey on target until replacable with parent, recursively until it reaches index one.
- * Ensures heap structure properties stays intact.
- * @param hole current index of node
- * @see deleteMin(), remove()
- */
- public void percolateUpDeletion(int hole) {
- HeapItem tmp = array[hole];
- HeapItem parent = array[hole/2];
- if (parent != null) {
- while (parent.compareTo(tmp) < 0) {
- tmp.decreaseKey();
- }
- HeapItem parTmp = parent;
- array[hole] = parTmp;
- array[hole/2] = tmp;
- hole /= 2;
- if (hole > 1) {
- percolateUpDeletion(hole);
- numElements--;
- return;
- } deleteMin();
- } return;
- }
- public void percolateUp(int hole) {
- HeapItem item = array[hole];
- HeapItem parent = array[hole/2];
- while (parent.compareTo(item) > 0) {
- HeapItem tmp = parent;
- array[hole] = tmp;
- array[hole/2] = item;
- hole /= 2;
- item = array[hole];
- parent = array[hole/2];
- }
- }
- /**
- * Increases the array size by parameter specification
- * @param newsize the new size of the array
- */
- public void enlargeArray(int newsize) {
- HeapItem [] tmp_array = new HeapItem[newsize];
- for (int i=0; i<array.length; i++) {
- tmp_array[i] = array[i];
- }
- array = tmp_array;
- }
- /**
- * Evaluates whether the vertex parameter is contained by the heap
- * @param v vertex to look for
- * @return true if present
- * false if not present
- */
- public boolean contains(HeapItem v) {
- return get(v) != null;
- }
- /**
- * Gets a vertex possibly contained by the heap
- * @param v vertex to look for
- * @return v if found
- * null if not found
- */
- public HeapItem get(HeapItem v) {
- for (int i=0; i<array.length; i++) {
- if (v == array[i])
- return array[i];
- }
- return null;
- }
- /**
- * Returns the array index of a vertex parameter
- * @param v vertex parameter
- * @return i index of vertex
- * 0 if none is found
- */
- public int getIndexOf(HeapItem v) {
- for (int i=0; i<array.length; i++) {
- if (v == array[i])
- return i;
- }
- return 0;
- }
- /**
- * Prompts percolateUp-deletion method. Finds index of the vertex.
- * @param v vertex to remove
- */
- public void remove(HeapItem v) {
- int index = getIndexOf(v);
- if (index != 1) {
- percolateUpDeletion(index);
- }
- }
- }
- class HeapItem {
- Vertex node;
- Vertex previousnode;
- int costcount, previouscost, time;
- HeapItem(Vertex v1, Vertex v2, int cost, int time) {
- this.costcount = cost;
- this.node = v1;
- this.previousnode = v2;
- this.time = time;
- }
- public int compareTo(HeapItem other) {
- if (costcount > other.costcount)
- return 1;
- else if (costcount < other.costcount)
- return -1;
- return 0;
- }
- public void decreaseKey() {
- costcount--;
- }
- public void decreaseKey(int goal) {
- if (goal > costcount)
- return;
- while (goal < costcount)
- costcount--;
- }
- }
- class Vertex {
- int id = 0;
- int capacity = 0;
- int cost = 0;
- int time = 0;
- // Used in dijkstra's algorithm.
- int dist = -1;
- boolean known = false;
- boolean timePriority = false;
- // Used for uniformal-cost search.
- Vertex previous = null;
- int previousnodeCost = 0;
- ArrayList<Edge> adjacencies;
- HashMap<Integer, DataElement> data;
- int costcount = 0, timecount = 0;
- public Vertex(int id, int edge) {
- data = new HashMap<Integer, DataElement>();
- adjacencies = new ArrayList<Edge>();
- this.id = id;
- unvisited.add(this);
- }
- public void setCapacity(int c) {
- capacity = c;
- }
- public void addEdge(Vertex v, int time, int cost) {
- adjacencies.add(new Edge(this, v, time, cost));
- }
- public void addElement(int e) {
- data.put(e, new DataElement(e));
- }
- public boolean hasElement(int key) {
- return data.get(key) != null;
- }
- public int compareTo(Vertex other) {
- if (costcount > other.costcount)
- return 1;
- else if (costcount < other.costcount)
- return -1;
- return 0;
- }
- public void decreaseKey() {
- costcount--;
- }
- class DataElement {
- int data;
- boolean original = true;
- DataElement(int data) {
- this.data = data;
- }
- }
- }
- class Edge {
- Vertex v1, v2;
- int cost = 0, time = 0;
- public Edge(Vertex v1, Vertex v2, int time, int cost) {
- this.v1 = v1;
- this.v2 = v2;
- this.time = time;
- this.cost = cost;
- }
- }
- }
Add Comment
Please, Sign In to add comment