'''critical path using topologically ordering
(which in this case comes from a DFS).
In many later problems, the topological order will be clear without a DFS.
'''
from DFS import vertexStr, fromStr, toStr, charToNum
from topoorder import DFSTopoOrder
def critPathTopo(g, duration, verbose=True):
'''g is a list structure for a DAG.
g is interpreted as a dependency graph with tasks as vertices and
tast -> prerequisite task.
duration is a list with duration[v] the duration of task v.
Return (eft, critDep, lastVert), where eft and critDep are lists
indexed by vertices for expected finishing time and a critical dependency,
and worstVert is a vertex with the worst eft.
In all lists indexed by vertex, entry 0 is ignored,
optionally including duration.
If there is a cycle (graph not actually a DAG), None is returned.
A single source vertex is assumed.
'''
revTopo = DFSTopoOrder(g, verbose=False)
if revTopo is None:
print('Graph not DAG')
return
lim = len(g)
eft = [0]*lim # create list with index 0 .. n
critDep = [None]*lim
for v in revTopo:
est = 0
for w in g[v]:
if eft[w] > est:
est = eft[w]
critDep[v] = w
eft[v] = est + duration[v]
w = revTopo[-1]
if verbose:
displayCrit(eft, critDep, w, g)
return (eft, critDep, w)
def displayCrit(eft, critDep, w, g):
if isinstance(eft, list):
big = eft[w]
else: # for use in other version
big = eft
print('Longest time:', big)
critPath = []
v = w
while v is not None: # follow critical path
critPath.append(v)
v = critDep[v]
critPath.reverse() # now in time order
print('A critical sequence in time order:', vertexStr(critPath, g))
### string manipulation/testing routines follow
def parseVertexWtStr(vStr):
'''vStr is in the format for DFS.fromStr except that each vertex token
starts with an integer associated with the following vertex as in:
'2A>BE 7B>I 4C> 6D>FI 5E>CI 1F> 3G>AD 9H>DJ 3I> 5J>'
return (g, numbers) where the numbers list is stripped from vStr
preceded by None, and g is the resulting graph list structure.
If there is more than one source, a new source labeled '!' connects
to the original sources, so there is now a single source.
If the string is bad, (None, None) is returned.
'''
verts = vStr.split()
vWt = [None] + [int(s.split('>')[0][:-1]) for s in verts]
verts = [s[s.index('>')-1:] for s in verts]
graphStr = ' '.join(verts)
g = fromStr(graphStr)
if g is None:
print('Bad string')
return (None, None)
lim = len(g)
source = [True]*lim
for v in range(1, lim):
for w in g[v]:
source[w] = False
sources = [i for i in range(1, lim) if source[i]]
if len(sources) > 1:
g.append(sources)
g[0] += '!'
vWt.append(0)
return (g, vWt)
def doVWtStr(f, vStr):
'''parse string with int weights before vertices.
Return (vWt, g) where vWt is the list of vertex weights,
starting from index'''
print(vStr)
(g, vWt) = parseVertexWtStr(vStr)
if g is None: return
if '!' in g[0]:
print('With single source !:\n', toStr(g))
return f(g, vWt)
if __name__ == '__main__':
doVWtStr(critPathTopo,
'2A>BE 7B>I 4C> 6D>FI 5E>CI 1F> 3G>AD 9H>DJ 3I> 5J>')