"""
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 with respect to the dependency graph
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
'''
# array stores for each node its depth in the BFS-forest
earliest = [0 for v in range(al.node_size())]
roots = al.get_roots()
# start a BFS from each root
for root in roots:
q = queue.SimpleQueue()
q.put(root)
while not q.empty():
u = q.get()
for v in al.get_neighbors(u):
# children of u must be computed one time step later
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
>>> cycle2 = AdjacencyList(4)
>>> cycle2.add_edge(0,1)
>>> cycle2.add_edge(1,2)
>>> cycle2.add_edge(2,1)
>>> cycle2.add_edge(2,3)
>>> color = ['white' for v in range(4)]
>>> dfs_visit(cycle2, 0, color, [])
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')