Topological sort/Extracted top item: Difference between revisions
m (J: added top level) |
(J: simplify) |
||
Line 48: | Line 48: | ||
depends=. (> =@i.@#) names e.S:1 (#names){.parsed |
depends=. (> =@i.@#) names e.S:1 (#names){.parsed |
||
depends=. (+. +./ .*.~)^:_ depends |
depends=. (+. +./ .*.~)^:_ depends |
||
b=. +./depends (] , #~) names e. targets |
|||
⚫ | |||
r=.0 0$'' |
|||
(b#names) (</.~ /: ~.@]) +/ }.+./ .*.~&(b#"1 b#depends)^:a: 1 |
|||
while.#names=. keep#names do. |
|||
⚫ | |||
keep=. 0<+/"1 depends |
|||
r=.r,;:inv (-.keep)#names |
|||
end. |
|||
) |
) |
||
Line 60: | Line 56: | ||
</lang> |
</lang> |
||
The changes |
The changes include: |
||
# Added an argument for the target(s) we wish to find dependencies for |
# Added an argument for the target(s) we wish to find dependencies for |
||
Line 68: | Line 64: | ||
# When ordering names by dependencies: |
# When ordering names by dependencies: |
||
## only consider names and dependencies we want to keep |
## only consider names and dependencies we want to keep |
||
## |
## extract names grouped by their dependency chain length |
||
Example: |
Example: |
||
Line 86: | Line 82: | ||
top2 |
top2 |
||
'top1' compileOrder dependencies |
;:inv@> 'top1' compileOrder dependencies |
||
extra1 ip1a ipcommon ip2a ip2b ip2c des1b des1a1 des1a2 des1c1 |
extra1 ip1a ipcommon ip2a ip2b ip2c des1b des1a1 des1a2 des1c1 |
||
ip1 ip2 des1a des1c |
ip1 ip2 des1a des1c |
||
Line 92: | Line 88: | ||
top1 |
top1 |
||
'top2' compileOrder dependencies |
;:inv@> 'top2' compileOrder dependencies |
||
ip3 extra1 ipcommon ip2a ip2b ip2c des1b des1a1 des1a2 des1c1 |
ip3 extra1 ipcommon ip2a ip2b ip2c des1b des1a1 des1a2 des1c1 |
||
ip2 des1a des1c |
ip2 des1a des1c |
||
Line 98: | Line 94: | ||
top2 |
top2 |
||
'top1 top2' compileOrder dependencies |
;:inv@> 'top1 top2' compileOrder dependencies |
||
ip3 extra1 ip1a ipcommon ip2a ip2b ip2c des1b des1a1 des1a2 des1c1 |
ip3 extra1 ip1a ipcommon ip2a ip2b ip2c des1b des1a1 des1a2 des1c1 |
||
ip1 ip2 des1a des1c |
ip1 ip2 des1a des1c |
Revision as of 20:56, 15 October 2010
Given a mapping between items, and items they depend on, a topological sort orders items so that no item precedes an item it depends upon.
The compiling of a design in the VHDL language has the constraint that a file must be compiled after any file containing definitions it depends on. A tool exists that extracts file dependencies.
- Assume the file names are single words, given without their file extensions.
- Files mentioned as only dependants, have no dependants of their own, but their order of compiling must be given.
- Any self dependencies should be ignored.
A top level file is defined as a file that:
- Has dependents.
- Is not itself the dependent of another file
Task Description
Given the following file dependencies as an example:
FILE FILE DEPENDENCIES ==== ================= top1 des1 ip1 ip2 top2 des1 ip2 ip3 ip1 extra1 ip1a ipcommon ip2 ip2a ip2b ip2c ipcommon des1 des1a des1b des1c des1a des1a1 des1a2 des1c des1c1 extra1
The task is to create a program that given a graph of the dependency:
- Determines the top levels from the dependencies and show them.
- Extracts a compile order of files to compile any given (usually top level) file.
- Give a compile order for file top1.
- Give a compile order for file top2.
You may show how to compile multiple top levels as a stretch goal
Note: this task differs from task Topological sort in that the order for compiling any file might not include all files; and that checks for dependency cycles are not mandated.
C.f. Topological sort
J
Derived from the topological sort implementation:
<lang j>compileOrder=: dyad define
targets=. ;: x parsed=. <@;:;._2 y names=. ~.({.&>parsed),targets,;parsed depends=. (> =@i.@#) names e.S:1 (#names){.parsed depends=. (+. +./ .*.~)^:_ depends b=. +./depends (] , #~) names e. targets names (</.~ \: ~.@])&(keep&#) +/"1 depends (b#names) (</.~ /: ~.@]) +/ }.+./ .*.~&(b#"1 b#depends)^:a: 1
)
topLevel=: [: ({.&> -. [:;}.&.>) <@;:;._2 </lang>
The changes include:
- Added an argument for the target(s) we wish to find dependencies for
- Make sure that these targets are included in our dependency structures
- Make sure that things we can depend on are included in our dependency structures
- Select these targets, and the things they depend on, once we know what depends on what
- When ordering names by dependencies:
- only consider names and dependencies we want to keep
- extract names grouped by their dependency chain length
Example:
<lang j>dependencies=: noun define
top1 des1 ip1 ip2 top2 des1 ip2 ip3 ip1 extra1 ip1a ipcommon ip2 ip2a ip2b ip2c ipcommon des1 des1a des1b des1c des1a des1a1 des1a2 des1c des1c1 extra1
)
>topLevel dependencies
top1 top2
;:inv@> 'top1' compileOrder dependencies
extra1 ip1a ipcommon ip2a ip2b ip2c des1b des1a1 des1a2 des1c1 ip1 ip2 des1a des1c des1 top1
;:inv@> 'top2' compileOrder dependencies
ip3 extra1 ipcommon ip2a ip2b ip2c des1b des1a1 des1a2 des1c1 ip2 des1a des1c des1 top2
;:inv@> 'top1 top2' compileOrder dependencies
ip3 extra1 ip1a ipcommon ip2a ip2b ip2c des1b des1a1 des1a2 des1c1 ip1 ip2 des1a des1c des1 top1 top2 </lang>
Python
Where the compile order between a subset of files is arbitraary, they are shown on the same line. <lang python>try:
from functools import reduce
except: pass
- Python 3.x: def topx(data:'dict', tops:'set'=None) -> 'list':
def topx(data, tops=None):
'Extract the set of top-level(s) in topological order' for k, v in data.items(): v.discard(k) # Ignore self dependencies if tops is None: tops = toplevels(data) return _topx(data, tops, [], set())
def _topx(data, tops, _sofar, _sofar_set):
'Recursive topological extractor' _sofar += [tops] # Accumulates order in reverse _sofar_set.union(tops) depends = reduce(set.union, (data.get(top, set()) for top in tops)) if depends: _topx(data, depends, _sofar, _sofar_set) ordered, accum = [], set() for s in _sofar[::-1]: ordered += [sorted(s - accum)] accum |= s return ordered
def printorder(order):
'Prettyprint topological ordering' if order: print("First: " + ', '.join(str(s) for s in order[0])) for o in order[1:]: print(" Then: " + ', '.join(str(s) for s in o))
def toplevels(data):
\ Extract all top levels from dependency data Top levels are never dependents for k, v in data.items(): v.discard(k) # Ignore self dependencies dependents = reduce(set.union, data.values()) return set(data.keys()) - dependents
if __name__ == '__main__':
data = dict( top1 = set('ip1 des1 ip2'.split()), top2 = set('ip2 des1 ip3'.split()), des1 = set('des1a des1b des1c'.split()), des1a = set('des1a1 des1a2'.split()), des1c = set('des1c1 extra1'.split()), ip2 = set('ip2a ip2b ip2c ipcommon'.split()), ip1 = set('ip1a ipcommon extra1'.split()), )
tops = toplevels(data) print("The top levels of the dependency graph are: " + ' '.join(tops))
for t in sorted(tops): print("\nThe compile order for top level: %s is..." % t) printorder(topx(data, set([t]))) if len(tops) > 1: print("\nThe compile order for top levels: %s is..." % ' and '.join(str(s) for s in sorted(tops)) ) printorder(topx(data, tops))</lang>
Sample Output
The top levels of the dependency graph are: top2 top1 The compile order for top level: top1 is... First: des1a1, des1a2, des1c1, extra1 Then: des1a, des1b, des1c, ip1a, ip2a, ip2b, ip2c, ipcommon Then: des1, ip1, ip2 Then: top1 The compile order for top level: top2 is... First: des1a1, des1a2, des1c1, extra1 Then: des1a, des1b, des1c, ip2a, ip2b, ip2c, ipcommon Then: des1, ip2, ip3 Then: top2 The compile order for top levels: top1 and top2 is... First: des1a1, des1a2, des1c1, extra1 Then: des1a, des1b, des1c, ip1a, ip2a, ip2b, ip2c, ipcommon Then: des1, ip1, ip2, ip3 Then: top1, top2