Title / Description
Code # assignment2.rb (v1.0) # Fill this up: # Section : G??? (Mon/Tue/Wed/Thu/Fri) (please specify correct day) # Faculty : Cheng Shih-fen / Lau Hoong Chuin (please delete one) # Team ID : # Name of Team member 1: # Name of Team member 2: # Name of Team member 3 (if any): #------------------------------------------------------------------- # Q3(a) def get_shortest_link_between_actors (g, x, y) # first swap the values so that later when we reconstruct the path, we dont need to reverse the path later # so right now we are finding the path from y to x x,y = y,x # initialise some data structures to keep track of stuff visits = Queue.new # keep track of order of visitation dist = Hash.new # maps the actors to the distance between actorX and that actor parent = Hash.new # keeps track of the node visited before the current node # get the relevant actors actorX = g.get_vertex(x) actorY = g.get_vertex(y) # ensure that the actors exist in the graph if actorX == nil or actorY == nil return nil end # set the distance from source ActorX to ActorX to be 0 dist[x] = 0 # start visitation from the source visits.enqueue(x) # implementation of BFS - keep looping until there are no more connected components while not visits.is_empty? # take out the front most vertex current_actor = g.get_vertex(visits.dequeue) # get neighbours for the current actor neighbours = current_actor.adjList # loop through the list of neighbours neighbours.each { |neighbour| # if it has not been visited, record the distance to it if !dist.has_key?(neighbour.value) # distance to the neighbour is distance to current actor + 1 dist[neighbour.value] = dist[current_actor.value] + 1 # keep track of who this neighbour's parent is parent[neighbour.value] = current_actor.value # enqueue the neighbour to be visited later visits.enqueue(neighbour.value) end } end # get the path to the desired actor path = [] current_actor = y while parent.has_key?(current_actor) # insert the parent into our path path << current_actor # update the current actor current_actor = parent[current_actor] end # insert the last actor into the path path << current_actor # ensure that the current actor is x, this means there is a path joining x and y if current_actor != x return nil end # puts path # check whats in our hash # dist.each do |key, value| # puts key.to_s + ' : ' + value.to_s # end # TODO: fill up this method # do stuff with $g here return path end #------------------------------------------------------------------- # Q3(b) def get_closest_link_between_actors (g, x, y) # swap the values so we dont have to reverse the path later x,y = y,x # get the source node source = g.get_vertex(x) destination = g.get_vertex(y) # ensure that the actors exist in the graph if source == nil or destination == nil return nil end # create a pseudo priority queue to keep track of the order of visitation # this is a pseudo priority queue in that we always want to remove the one with the smallest # distance, but the data in this array is not actually sorted pseudo_pq = Array.new{Array.new(2)} # stores pairs: (distance from source, vertex) # initialise a hash to store the shortest distance from source to each vertex # key: vertex value, value: distance from source to vertex dist = Hash.new parent = Hash.new # keeps track of the node visited before the current node # push the first value dist[x] = 0# set the distance from source ActorX to ActorX to be 0 # start by 'queuing' the source node pseudo_pq << [0, source] # the search starts. we keep visiting until the whole graph has been visited while not pseudo_pq.empty? # find index of the minimum distance vertex minimum_index = (2**(0.size * 8 -2) -1) # initialise the min to maximum ruby value http://stackoverflow.com/questions/535721/ruby-max-integer # loop through all the nodes to be visited for i in 0...pseudo_pq.length # pseudo_pq[i] returns the pair of (dist, vertex) if pseudo_pq[i][0] < minimum_index minimum_index = i end end # retrieve the minimum dist element from pseudo pq front = pseudo_pq[minimum_index] vertex_dist = front[0] vertex = front[1] pseudo_pq.delete_at(minimum_index) # remove it from the queue # get neighbours and corresponding distance for the current vertex neighbours = vertex.adjList if vertex_dist == dist[vertex.value] # perform this check because one vertex may appear in the queue more than once # loop through the list of neighbours for i in 0...neighbours.length # get the neighbour neighbour = neighbours[i] # first check if the distance to this node has been established if dist.has_key?(neighbour.value) # perform relaxation # the following line checks the distance to current vertex added to the distance between the current vertex and the neighbour if dist[vertex.value] + g.get_edge_weight(vertex, neighbour) < dist[neighbour.value] dist[neighbour.value] = dist[vertex.value] + g.get_edge_weight(vertex, neighbour) # now we can enqueue it without first checking to see if the vertex already exists in the queue pseudo_pq << [dist[neighbour.value], neighbour] # keep track of who this neighbour's parent is parent[neighbour.value] = vertex.value end else # we set the initial distance to this node dist[neighbour.value] = dist[vertex.value] + g.get_edge_weight(vertex, neighbour) pseudo_pq << [dist[neighbour.value], neighbour] # keep track of who this neighbour's parent is parent[neighbour.value] = vertex.value end end end end # get the path to the desired actor path = [] current_actor = y while parent.has_key?(current_actor) # insert the parent into our path path << current_actor # update the current actor current_actor = parent[current_actor] end # insert the last actor into the path path << current_actor # ensure that the current actor is x, this means there is a path joining x and y if current_actor != x return nil end # # check whats in our hash # dist.each do |key, value| # puts key.to_s + ' : ' + value.to_s # end # TODO: fill up this method # do stuff with $g here return path end #------------------------------------------------------------------- # Q4 - this method will only be invoked AFTER Q3(a) and Q3(b) have been tested on the submission server def get_largest_set_of_independent_actors (g) # first ensure that the graph has vertices if g.is_empty? return nil end # create data structures to track the set i_set = [] #stores the independent set in_i_set = Hash.new # a hash of (vertex -> Boolean) that tracks if an actor has been added # obtain the list of vertices in the graph vertices = g.vertices # sort the list of vertices sorted_vertices = [] # create a hash to store the number of neighbours for each vertex num_neighbours = Hash.new # maps vertex -> number of neighbours for this vertex # populate the hash with the number of neighbours for each node vertices.each{ |vertex| num_neighbours[vertex.value] = vertex.adjList.length } # now sort the hash for iterating through later num_neighbours = num_neighbours.sort_by{|vertex, number| number} # obtain the list of vertices, but now sorted # at the same time, initialise the in_i_set hash to false num_neighbours.each{ |vertex, num| sorted_vertices << g.get_vertex(vertex) in_i_set[vertex] = false } # loop through the vertices and remove them until there are none left while !sorted_vertices.empty? # get the vertex with the least neighbours current_vertex = sorted_vertices.shift current_vertex_value = current_vertex.value if !in_i_set[current_vertex_value] # insert it into the independent set i_set << current_vertex_value # update the boolean flag to indicate insertion into the set in_i_set[current_vertex_value] = true # now that it is in the independent set, its neighbours must be removed from the candidate set neighbours = current_vertex.adjList neighbours.each{ |neighbour| sorted_vertices.delete(neighbour) } end end return i_set end #-------------------------------------------------------------------
Author
Highlight as C C++ CSS Clojure Delphi ERb Groovy (beta) HAML HTML JSON Java JavaScript PHP Plain text Python Ruby SQL XML YAML diff code
1.1.2
1.1.2