Guest User

Untitled

a guest
Mar 13th, 2018
87
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 14.74 KB | None | 0 0
  1. import java.util.HashMap;
  2. import java.util.ArrayList;
  3. import java.util.Scanner;
  4. import java.util.Comparator;
  5. import java.util.PriorityQueue;
  6. import java.util.Stack;
  7. import java.util.Set;
  8.  
  9.  
  10. import java.util.regex.Pattern;
  11. import java.util.regex.Matcher;
  12.  
  13.  
  14. import java.io.File;
  15. import java.io.FileNotFoundException;
  16. import java.io.IOException;
  17.  
  18.  
  19. class Oblig3 {
  20.  
  21.        
  22.  
  23.     private static String   config = "config.txt";
  24.     private static String   data = "data.txt";
  25.    
  26.     private static Scanner  sc;
  27.     private static Graph    graph;
  28.    
  29.  
  30.     public static void main (String [] args) throws IOException {
  31.         if (args != null) {
  32.             if (args[0] != null) {    
  33.                 config = args[0];
  34.                 if (args[1] != null) {
  35.                     data = args[1];
  36.                 } else {
  37.                     System.out.println("ERROR: Invalid user input.");
  38.                 }  
  39.             }
  40.         }
  41.        
  42.         if (!config.equals("") && !data.equals("")) {
  43.             sc = new Scanner(new File(config));
  44.             graph = new Graph();
  45.            
  46.             // Network configuration from input file
  47.             while (sc.hasNextLine()) {
  48.                 String [] line = sc.nextLine().split("[\t ]+");
  49.                 int [] attributes = new int[line.length];
  50.        
  51.                 for (int i=0; i<line.length; i++) {
  52.                     attributes[i] = Integer.parseInt(line[i].trim());
  53.                 }
  54.                
  55.                 graph.add(attributes);
  56.             }
  57.            
  58.             sc = new Scanner(new File(data));
  59.             HashMap<Integer, Graph.Vertex> g = graph.getGraph();
  60.            
  61.             // Data elements setup
  62.             while (sc.hasNextLine()) {
  63.                 String [] line = sc.nextLine().split("[\t ]+");
  64.                 int [] data = new int[line.length];
  65.                
  66.                 for (int i=0; i<line.length; i++) {
  67.                     data[i] = Integer.parseInt(line[i].trim());
  68.                 }
  69.            
  70.                 // Nodene får riktige elementer: OK!
  71.                
  72.                 // Set the vertex data capacity
  73.                 Graph.Vertex v = g.get(data[0]);
  74.                 v.setCapacity(data[1]);
  75.                
  76.                 // Add data elements to the vertex
  77.                 for (int i=1; i<data.length; i++) {
  78.                     v.addElement(data[i]);
  79.                 }
  80.             }
  81.         }
  82.  
  83.         sc = new Scanner(System.in);
  84.        
  85.         // Run shell
  86.         while (true) {
  87.             // Search preference = T || C || B (pick shortest time || cost || both), Data ownership = O (original copy) || = A (any copy)
  88.             System.out.println("Submit data element request on format <machine_id>:<search_preference>:<ownership_preference>: <list_of_data_elements> (press q to quit)");
  89.             System.out.print("shell> ");
  90.            
  91.             String [] rqln = sc.nextLine().split("[: ]+");
  92.            
  93.             if (rqln.length < 4) {
  94.                 if (rqln[0].equals("q")) {
  95.                     System.out.println("Ending program");
  96.                     break;
  97.                 }
  98.                 System.out.println("Invalid command.");
  99.             } else {
  100.                 ArrayList<Integer> elements = new ArrayList<Integer>();
  101.                 for (int i=0; i<rqln.length; i++) {
  102.                     System.out.println("index " + i + " has " + rqln[i]);
  103.                 }
  104.                 for (int i=3; i<rqln.length; i++) {
  105.                     elements.add(Integer.parseInt(rqln[i]));
  106.                 }
  107.                
  108.                 System.out.println(elements.size() + " number of elements requested for.");
  109.                 graph.sendRequest(Integer.parseInt(rqln[0]), rqln[1], rqln[2], elements);
  110.             }
  111.         }
  112.     }
  113. }
  114.  
  115.  
  116. class Graph {
  117.  
  118.     // Contains the graph data structure.
  119.     protected HashMap<Integer, Vertex> graph;
  120.  
  121.     // Number of elements in the graph
  122.     protected int size = 0;
  123.  
  124.     // Used for Dijkstra's algorithm
  125.     protected ArrayList<Vertex> visited, unvisited;
  126.     protected ArrayList<Vertex> tmpVisited, tmpUnvisited;
  127.  
  128.     // Default constructor
  129.     public Graph() {
  130.         graph = new HashMap<Integer, Vertex>();
  131.         visited = new ArrayList<Vertex>();
  132.         unvisited = new ArrayList<Vertex>();
  133.     }
  134.    
  135.    
  136.     /**
  137.      * Adds a vertex to the graph with specified input data in integer array parameter
  138.      * @param data  array of data
  139.      */
  140.     public void add(int [] data) {
  141.         if (data == null || data.length < 4)
  142.             return;
  143.        
  144.         Vertex v1, v2;
  145.         int edgetime;
  146.         int costval;
  147.        
  148.         // Creates the first vertex in config file if it does not exist
  149.         if (!graph.containsKey(data[0])) {
  150.             v1 = new Vertex(data[0], data[1]);
  151.             edgetime = data[2];
  152.             costval = data[3];
  153.             graph.put(data[0], v1);
  154.             size++;
  155.         }
  156.         // Otherwise, add the edge to the vertex manually
  157.         else {
  158.             v1 = graph.get(data[0]);
  159.             edgetime = data[2];
  160.             costval = data[3];
  161.         }
  162.         // Creates the new biconnected vertex if it does not exist
  163.         if (!graph.containsKey(data[1])) {
  164.             v2 = new Vertex(data[1], data[0]);
  165.             edgetime = data[2];
  166.             costval = data[3];
  167.             graph.put(data[1], v2);
  168.             size++;
  169.         }
  170.         // Otherwise, get it from the hashmap.
  171.         else {
  172.             v2 = graph.get(data[1]);
  173.             edgetime = data[2];
  174.             costval = data[3];
  175.         }
  176.        
  177.         v1.addEdge(v2, edgetime, costval);
  178.         v2.addEdge(v1, edgetime, costval);
  179.     }
  180.    
  181.     public HashMap<Integer, Vertex> getGraph() {
  182.         return graph;
  183.     }
  184.    
  185.     /**
  186.      * Handles a request from one machine to another.
  187.      * @param id        id of requesting machine
  188.      * @param spref     search preference of request
  189.      * @param typepref  type preference of request
  190.      * @param requests  requested data elements
  191.      */
  192.     public void sendRequest(int id, String spref, String typepref, ArrayList<Integer> requests) {
  193.         if (graph.get(id) == null)
  194.             System.out.println("Network vertex " + id + " does not exist.");
  195.         else if (requests.size() <= 0)
  196.             System.out.println("No requests was specified.");
  197.         else if (spref.equals("C")) {
  198.             for (int i=0; i<requests.size(); i++) {
  199.                 printPath(transferFileOnCost(requests.get(i), typepref, id), requests.get(i));
  200.             }
  201.         }
  202.         else if (spref.equals("T")) {
  203.            
  204.         }
  205.         else if (spref.equals("B")) {
  206.            
  207.         }
  208.     }
  209.    
  210.     public Stack<Vertex> transferFileOnCost(int request, String type, int source) {
  211.         // Get the source node, and add it into path FIFO.
  212.         Vertex src_node = graph.get(source);
  213.         Stack<Vertex> path = new Stack<Vertex>();
  214.        
  215.         // Set distance to itself to 0.
  216.         src_node.dist = 0;
  217.         src_node.known = true;
  218.        
  219.         // Compute the path from one node to another node storing the correct element.
  220.         return uniformCostSearch(src_node, request);
  221.     }
  222.  
  223.    
  224.    
  225.      private Stack<Vertex> uniformCostSearch(Vertex src, int requestedElement) {
  226.         Vertex current = src, previous = null;
  227.         Heap heap = new Heap(size);
  228.         ArrayList<Vertex> visited = new ArrayList<Vertex>();
  229.         Stack<Vertex> path = new Stack<Vertex>();
  230.        
  231.         HeapItem item = new HeapItem(current, null, 0, 0);
  232.         HeapItem currentItem = item, previousItem = null;
  233.         heap.insert(item);
  234.         visited.add(current);
  235.    
  236.         while (!heap.isEmpty()) {
  237.             // Get highest priority element from heap.
  238.             currentItem = heap.deleteMin();
  239.             if (previousItem != null)
  240.                 currentItem.previousnode = previousItem.node;
  241.            
  242.             // If the data element was found in current node, return path.
  243.             if (currentItem.node.hasElement(requestedElement)) {
  244.                 Vertex currentVertex = currentItem.node;
  245.                 path.push(currentVertex);
  246.                 currentVertex = currentVertex.previous;
  247.            
  248.                 while (currentVertex != null) {
  249.                     path.push(currentVertex);
  250.                     currentVertex = currentVertex.previous;
  251.                 }
  252.                
  253.                 return path;
  254.             }
  255.            
  256.             if (visited.contains(currentItem.node)) {
  257.                 continue;
  258.             }
  259.            
  260.             for (Edge e : currentItem.node.adjacencies) {
  261.                 HeapItem itm = null;
  262.                 Vertex v = e.v1;
  263.                 Vertex adjacency = e.v2;
  264.                 adjacency.costcount = e.cost + previousItem.costcount;
  265.                
  266.                 if (!visited.contains(adjacency)) {
  267.                     if (!heap.contains(currentItem)) {
  268.                         itm = new HeapItem(adjacency, currentItem.node, adjacency.costcount, e.time);
  269.                         heap.insert(itm);
  270.                         itm.previousnode = previousItem.node;
  271.                         adjacency.previous = currentItem.node;
  272.                     }
  273.                     if ((previousItem.costcount + e.cost) > (v.costcount + e.cost)) {
  274.                         if (itm != null) {
  275.                             itm.previousnode = v;
  276.                             adjacency.previous = v;
  277.                         }
  278.                         else {
  279.                             //heap.remove(itm);
  280.                             itm = new HeapItem(adjacency, v, adjacency.costcount, e.time);
  281.                             heap.insert(itm);
  282.                             adjacency.previous = v;
  283.                         }
  284.                         itm = null;
  285.                     }
  286.                 } else {
  287.                     continue;
  288.                 }
  289.             }
  290.             previousItem = currentItem;
  291.         }
  292.        
  293.         return null;
  294.     }
  295.    
  296.    
  297.     public void printPath(Stack<Vertex> queue, int element) {
  298.         if (queue != null) {
  299.             System.out.print("Element " + element + ":");
  300.             while (!queue.empty()) {
  301.                 System.out.print(queue.pop().id + "->");
  302.             }
  303.         }
  304.        
  305.         else {
  306.             System.out.println("Data element unreachable or non-existent.");
  307.         }
  308.     }
  309.    
  310.    
  311.    
  312.     class Heap {
  313.  
  314.         private int size;
  315.         private HeapItem array [];
  316.         private int numElements;
  317.  
  318.  
  319.         // Default constructor
  320.         public Heap (int size) {
  321.             this.size = size;
  322.             array = new HeapItem[size];
  323.             numElements = 0;
  324.         }
  325.  
  326.         /**
  327.          * Inserts a HeapItem into the heap.
  328.          * @param v     the item to be inserted
  329.          */
  330.         public void insert(HeapItem v) {
  331.             if (numElements == array.length-1)
  332.                 enlargeArray( array.length * 2 + 1 );
  333.  
  334.             int hole = ++numElements;
  335.  
  336.             for ( ; hole > 1 && v.compareTo(array[hole/2]) < 0; hole /= 2)
  337.                 array[hole] = array[hole/2];
  338.  
  339.             array[hole] = v;
  340.         }
  341.  
  342.         /**
  343.          * Returns and deletes the minimum (highest priority) vertex from the heap
  344.          * @return minItem  the vertex
  345.          * @see findMin()
  346.          * @see percolateDown()
  347.          */
  348.         public HeapItem deleteMin() {
  349.             if (numElements == 0) {
  350.                 array = null;
  351.                 return null;
  352.             } else {
  353.                 HeapItem minItem = findMin();
  354.                 array[1] = array[numElements--];
  355.                 percolateDown(1);
  356.  
  357.                 return minItem;
  358.             }
  359.         }
  360.  
  361.         /**
  362.          * Returns the minimum (high priority) from the heap at array position 1
  363.          * @return  array[1]    if the array is not null
  364.          *          null        if the heap is empty
  365.          */
  366.         public HeapItem findMin() {
  367.             if(array != null) {
  368.                 return array[1];
  369.             } else {
  370.                 return null;
  371.             }
  372.         }
  373.  
  374.         /**
  375.          * Checks to see if the heap is empty.
  376.          * @return  true if empty
  377.          *          false if not empty
  378.          */
  379.         public boolean isEmpty() {
  380.             return numElements == 0;
  381.         }
  382.  
  383.  
  384.         /**
  385.          * Percolate-down function. Used for d
  386.          * @param hole  the hole where percolating should start (array index 1)
  387.          */
  388.         private void percolateDown(int hole) {
  389.             int child;
  390.             HeapItem tmp = array[hole];
  391.  
  392.             for ( ; hole * 2 <= numElements; hole = child) {
  393.                 child = hole * 2;
  394.                 if (child != numElements && array[child+1].compareTo(array[child]) < 0)
  395.                     child++;
  396.                 if (array[child].compareTo(tmp) < 0)
  397.                     array[hole] = array[child];
  398.                 else
  399.                     break;
  400.             }
  401.             array[hole] = tmp;
  402.         }
  403.  
  404.  
  405.         /**
  406.          * Percolate-up method for óbject. Runs decreaseKey on target until replacable with parent, recursively until it reaches index one.
  407.          * Ensures heap structure properties stays intact.
  408.          * @param hole  current index of node
  409.          * @see deleteMin(), remove()
  410.          */
  411.         public void percolateUpDeletion(int hole) {
  412.             HeapItem tmp = array[hole];
  413.             HeapItem parent = array[hole/2];
  414.            
  415.             if (parent != null) {
  416.                 while (parent.compareTo(tmp) < 0) {
  417.                     tmp.decreaseKey();
  418.                 }
  419.        
  420.             HeapItem parTmp = parent;
  421.             array[hole] = parTmp;
  422.             array[hole/2] = tmp;
  423.             hole /= 2;
  424.             if (hole > 1) {
  425.                 percolateUpDeletion(hole);
  426.                 numElements--; 
  427.                 return;
  428.             } deleteMin();
  429.             } return;
  430.         }
  431.        
  432.        
  433.         public void percolateUp(int hole) {
  434.             HeapItem item = array[hole];
  435.             HeapItem parent = array[hole/2];
  436.            
  437.             while (parent.compareTo(item) > 0) {
  438.                 HeapItem tmp = parent;
  439.                 array[hole] = tmp;
  440.                 array[hole/2] = item;
  441.                 hole /= 2;
  442.                 item = array[hole];
  443.                 parent = array[hole/2];
  444.             }
  445.         }
  446.  
  447.         /**
  448.          * Increases the array size by parameter specification
  449.          * @param newsize   the new size of the array
  450.          */
  451.         public void enlargeArray(int newsize) {
  452.             HeapItem [] tmp_array = new HeapItem[newsize];
  453.  
  454.             for (int i=0; i<array.length; i++) {
  455.                 tmp_array[i] = array[i];
  456.             }
  457.  
  458.             array = tmp_array;
  459.         }
  460.        
  461.        
  462.         /**
  463.          * Evaluates whether the vertex parameter is contained by the heap
  464.          * @param   v   vertex to look for
  465.          * @return  true    if present
  466.          *          false   if not present
  467.          */
  468.         public boolean contains(HeapItem v) {
  469.             return get(v) != null;
  470.         }
  471.        
  472.         /**
  473.          * Gets a vertex possibly contained by the heap
  474.          * @param v     vertex to look for
  475.          * @return  v if found
  476.          *          null if not found
  477.          */
  478.         public HeapItem get(HeapItem v) {
  479.             for (int i=0; i<array.length; i++) {
  480.                 if (v == array[i])
  481.                     return array[i];
  482.             }
  483.             return null;
  484.         }
  485.        
  486.         /**
  487.          * Returns the array index of a vertex parameter
  488.          * @param   v   vertex parameter
  489.          * @return  i   index of vertex
  490.          *          0   if none is found
  491.          */
  492.         public int getIndexOf(HeapItem v) {
  493.             for (int i=0; i<array.length; i++) {
  494.                 if (v == array[i])
  495.                     return i;
  496.             }
  497.            
  498.             return 0;
  499.         }
  500.        
  501.         /**
  502.          * Prompts percolateUp-deletion method. Finds index of the vertex.
  503.          * @param v     vertex to remove
  504.          */
  505.         public void remove(HeapItem v) {
  506.             int index = getIndexOf(v); 
  507.             if (index != 1) {  
  508.                 percolateUpDeletion(index);
  509.             }
  510.         }
  511.     }
  512.    
  513.    
  514.     class HeapItem {
  515.        
  516.         Vertex node;
  517.         Vertex previousnode;
  518.         int costcount, previouscost, time;
  519.        
  520.        
  521.         HeapItem(Vertex v1, Vertex v2, int cost, int time) {
  522.             this.costcount = cost;
  523.             this.node = v1;
  524.             this.previousnode = v2;
  525.             this.time = time;
  526.            
  527.         }
  528.        
  529.         public int compareTo(HeapItem other) {
  530.             if (costcount > other.costcount)
  531.                 return 1;
  532.             else if (costcount < other.costcount)
  533.                 return -1;
  534.             return 0;
  535.         }
  536.        
  537.         public void decreaseKey() {
  538.             costcount--;
  539.         }
  540.        
  541.         public void decreaseKey(int goal) {
  542.             if (goal > costcount)
  543.                 return;
  544.             while (goal < costcount)
  545.                 costcount--;
  546.         }
  547.     }
  548.    
  549.    
  550.     class Vertex  {
  551.        
  552.         int id = 0;
  553.         int capacity = 0;
  554.         int cost = 0;
  555.         int time = 0;
  556.        
  557.         // Used in dijkstra's algorithm.
  558.         int dist = -1;
  559.         boolean known = false;
  560.        
  561.         boolean timePriority = false;
  562.        
  563.        
  564.         // Used for uniformal-cost search.
  565.         Vertex previous = null;
  566.         int previousnodeCost = 0;
  567.        
  568.         ArrayList<Edge> adjacencies;
  569.         HashMap<Integer, DataElement> data;
  570.        
  571.         int costcount = 0, timecount = 0;
  572.        
  573.         public Vertex(int id, int edge) {
  574.             data = new HashMap<Integer, DataElement>();
  575.             adjacencies = new ArrayList<Edge>();
  576.             this.id = id;
  577.             unvisited.add(this);
  578.         }
  579.        
  580.        
  581.         public void setCapacity(int c) {
  582.             capacity = c;
  583.         }
  584.        
  585.         public void addEdge(Vertex v, int time, int cost) {
  586.             adjacencies.add(new Edge(this, v, time, cost));
  587.         }
  588.        
  589.         public void addElement(int e) {
  590.             data.put(e, new DataElement(e));
  591.         }
  592.        
  593.         public boolean hasElement(int key) {
  594.             return data.get(key) != null;
  595.         }
  596.  
  597.         public int compareTo(Vertex other) {
  598.             if (costcount > other.costcount)
  599.                 return 1;
  600.             else if (costcount < other.costcount)
  601.                 return -1;
  602.             return 0;
  603.         }
  604.  
  605.         public void decreaseKey() {
  606.             costcount--;
  607.         }
  608.        
  609.         class DataElement {
  610.             int data;
  611.             boolean original = true;   
  612.            
  613.             DataElement(int data) {
  614.                 this.data = data;
  615.             }
  616.         }
  617.     }
  618.    
  619.     class Edge {
  620.         Vertex v1, v2;
  621.         int cost = 0, time = 0;
  622.        
  623.        
  624.         public Edge(Vertex v1, Vertex v2, int time, int cost) {
  625.             this.v1 = v1;
  626.             this.v2 = v2;
  627.             this.time = time;
  628.             this.cost = cost;
  629.         }
  630.     }
  631. }
Add Comment
Please, Sign In to add comment