as

# 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
#-------------------------------------------------------------------