"""
Functions for scheduling jobs on machines
Copyright 2020, University of Freiburg
Philipp Schneider
"""
import queue
from AdjacencyList import AdjacencyList
import networkx as nx
def dispatch_sequence(al):
'''
computes a valid sequence in which jobs can be
dispatched to a single machine without violating
the depency graph given as parameter
Parameter:
al - depency graph as instance of AdjacencyList
Returns:
a list representing a valid sequence of IDs for
computing the respective jobs on a single machine
or None if such a sequence does not exist
Unit Tests:
>>> cycle = AdjacencyList(6)
>>> cycle.add_edge(0,1); cycle.add_edge(1,2)
>>> cycle.add_edge(2,3); cycle.add_edge(3,0)
>>> cycle.add_edge(4,5);
>>> dispatch_sequence(cycle) is None
True
>>> isolated_nodes = AdjacencyList(50)
>>> sequence = [v for v in range(50)]
>>> sequence.reverse()
>>> dispatch_sequence(isolated_nodes) == sequence
True
>>> linear_graph = AdjacencyList(50)
>>> for i in range(49):
... linear_graph.add_edge(i, i + 1)
>>> sequence = [v for v in range(50)]
>>> dispatch_sequence(linear_graph) == sequence
True
'''
sequence = []
n = al.node_size()
color = ['white' for v in range(n)]
loop = False
# start a DFS from each node that is still white
for v in range(n):
if color[v] == 'white':
# starts a dfs and remembers if there have been loops
loop = dfs_visit(al, v, color, sequence)
# if a loop was found return None
if loop:
return None
# topological ordering is the black coloring order in reverse
sequence.reverse()
return sequence
def earliest_computation(al):
'''
for each job, gives the earliest point in time it can
be completed, which is when at least one parent in the
depency graph has been computed or it has indegree 0.
Parameter:
al - depency graph as instance of AdjacencyList
Returns:
a list of size n containing at position i the
earliest point in time it can be computed
Unit Tests:
>>> isolated_nodes = AdjacencyList(50)
>>> sequence = [0 for i in range(50)]
>>> earliest_computation(isolated_nodes) == sequence
True
>>> linear_graph = AdjacencyList(50)
>>> for i in range(49):
... linear_graph.add_edge(i, i + 1)
>>> sequence = [i for i in range(50)]
>>> earliest_computation(linear_graph) == sequence
True
>>> star = AdjacencyList(50)
>>> for i in range(1, 50):
... star.add_edge(0, i)
>>> sequence = [0] + [1 for i in range(49)]
>>> earliest_computation(star) == sequence
True
'''
# array stores depth of nodes, initally large, later updated
earliest = [al.node_size() + 1 for v in range(al.node_size())]
roots = al.get_roots()
# BFS starts from each root "simultaneously"
for root in roots:
earliest[root] = 0
q = queue.SimpleQueue()
q.put(root)
# start a BFS with roots in queue
while not q.empty():
u = q.get()
for v in al.get_neighbors(u):
# check if node was not yet visited
if earliest[v] == al.node_size() + 1:
# set earliest time to compute for child nodes
if earliest[v] > earliest[u] + 1:
earliest[v] = earliest[u] + 1
q.put(v)
return earliest
def dfs_visit(al, u, color, sequence):
'''
implements the dfs-visit function given in the lecture
each node writes its ID into a list when it is colored black
Parameter:
al - adjacency list representing the graph
u - a node from which dfs visit is to be started
color - array of strings giving the color of each node
sequence - array into which nodes write their IDs
Returns:
True when a backward edge is found -> graph has a cycle
Unit-Tests:
>>> cycle = AdjacencyList(6)
>>> cycle.add_edge(0,1); cycle.add_edge(1,2)
>>> cycle.add_edge(2,3); cycle.add_edge(3,0)
>>> cycle.add_edge(4,5);
>>> color = ['white' for v in range(6)]
>>> dfs_visit(cycle, 0, color, [])
True
>>> linear_graph = AdjacencyList(50)
>>> for i in range(49):
... linear_graph.add_edge(i, i + 1)
>>> sequence = [i for i in range(50)]
>>> sequence.reverse()
>>> color = ['white' for v in range(50)]
>>> black_order = []
>>> dfs_visit(linear_graph, 0, color, black_order)
False
>>> black_order == sequence
True
'''
loop = False
color[u] = 'gray'
for v in al.get_neighbors(u):
# backward edge found
if color[v] == 'gray':
return True
# node unvisited -> recurse & memorize if loops are found
if color[v] == 'white':
loop = loop or dfs_visit(al, v, color, sequence)
color[u] = 'black'
sequence.append(u)
return loop
def read_graph_from_file(filename):
'''
reads a depency graph from a file (that must be loated
in same folder) and creates an adjacency list from it
Parameter:
filename - name of file
Returns:
instance of AdjacencyList representing the file
'''
with open(filename) as input:
lines = input.read().splitlines()
# first line contains the number of nodes
al = AdjacencyList(int(lines[0]))
# other lines contain edges seperated by a whitespace
for i in range(1, len(lines)):
source = int(lines[i].split(' ')[0])
target = int(lines[i].split(' ')[1])
al.add_edge(source, target)
return al
def draw_graph_from_file(filename):
'''
draws a graph from a file that is in the required format
Parameter:
filename - name of file
'''
g = nx.DiGraph()
with open(filename) as input:
lines = input.read().splitlines()
# first line contains the number of nodes
n = int(lines[0])
nodes = [v for v in range(n)]
g.add_nodes_from(nodes)
# other lines contain edges seperated by a whitespace
for i in range(1, len(lines)):
source = int(lines[i].split(' ')[0])
target = int(lines[i].split(' ')[1])
g.add_edge(source, target)
a = nx.nx_agraph.to_agraph(g)
a.layout('dot', args='-Nfontsize=40')
a.draw('drawing_' + filename + '.png')