1from __future__ import print_function 2################################################################################ 3# 4# graph.py 5# 6# 7# Copyright (c) 10/9/2009 Leo Goodstadt 8# 9# Permission is hereby granted, free of charge, to any person obtaining a copy 10# of this software and associated documentation files (the "Software"), to deal 11# in the Software without restriction, including without limitation the rights 12# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 13# copies of the Software, and to permit persons to whom the Software is 14# furnished to do so, subject to the following conditions: 15# 16# The above copyright notice and this permission notice shall be included in 17# all copies or substantial portions of the Software. 18# 19# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 20# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 21# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 22# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 23# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 24# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN 25# THE SOFTWARE. 26################################################################################# 27""" 28 graph.py 29 30 provides support for diacyclic graph 31 with topological_sort 32 33""" 34import sys 35import re 36import os 37 38# use simplejson in place of json for python < 2.6 39try: 40 import json 41except ImportError: 42 import simplejson 43 json = simplejson 44 45from collections import defaultdict 46from .print_dependencies import * 47import tempfile 48import subprocess 49# 88888888888888888888888888888888888888888888888888888888888888888888888888888888888888888 50 51# class node 52 53# 88888888888888888888888888888888888888888888888888888888888888888888888888888888888888888 54 55 56class graph_error(Exception): 57 def __init__(self, message): 58 self.message = message 59 60 def __str__(self): 61 return self.message 62 63 64class error_duplicate_node_name(graph_error): 65 pass 66 67 68class node (object): 69 """ 70 node 71 designed for diacyclic graphs but can hold anything 72 contains lists of nodes and 73 dictionary to look up node name from node 74 """ 75 76 _all_nodes = list() 77 _name_to_node = dict() 78 _index_to_node = dict() 79 _global_node_index = 0 80 81 _one_to_one = 0 82 _many_to_many = 1 83 _one_to_many = 2 84 _many_to_one = 3 85 86 @staticmethod 87 def _get_leaves(): 88 for n in node._all_nodes: 89 if len(n._inward) == 0: 90 yield n 91 92 @staticmethod 93 def _get_roots(): 94 for n in node._all_nodes: 95 if len(n._outward) == 0: 96 yield n 97 98 @staticmethod 99 def _count_nodes(): 100 return len(_all_nodes) 101 102 @staticmethod 103 def _dump_tree_as_str(): 104 """ 105 dumps entire tree 106 """ 107 return ("%d nodes " % node._count_nodes()) + "\n" + \ 108 "\n".join([x._fullstr() for x in node._all_nodes]) 109 110 @staticmethod 111 def _lookup_node_from_name(name): 112 return node._name_to_node[name] 113 114 @staticmethod 115 def _lookup_node_from_index(index): 116 return node._index_to_node[index] 117 118 @staticmethod 119 def _is_node(name): 120 return name in node._name_to_node 121 122 # _____________________________________________________________________________________ 123 124 # init 125 126 # _____________________________________________________________________________________ 127 128 def __init__(self, name, **args): 129 """ 130 each node has 131 _name 132 _inward : lists of incoming edges 133 _outward: lists of outgoing edges 134 """ 135 # 136 # make sure node name is unique 137 # 138 # if name in node._name_to_node: 139 # raise error_duplicate_node_name("[%s] has already been added" % name) 140 141 self.__dict__.update(args) 142 self._inward = list() 143 self._outward = list() 144 self.args = args 145 self._name = name 146 self._signal = False 147 self._node_index = node._global_node_index 148 node._global_node_index += 1 149 150 # 151 # for looking up node for name 152 # 153 node._all_nodes.append(self) 154 node._name_to_node[self._name] = self 155 node._index_to_node[self._node_index] = self 156 157 # _____________________________________________________________________________________ 158 159 # _add_child 160 161 # _____________________________________________________________________________________ 162 def _add_child(self, child): 163 """ 164 connect edges 165 """ 166 # do not add duplicates 167 if child in self._outward: 168 return child 169 170 self._outward.append(child) 171 child._inward.append(self) 172 return child 173 174 # _____________________________________________________________________________________ 175 176 # _remove_child 177 178 # _____________________________________________________________________________________ 179 def _remove_child(self, child): 180 """ 181 disconnect edges 182 """ 183 184 if child in self._outward: 185 self._outward.remove(child) 186 if self in child._inward: 187 child._inward.remove(self) 188 return child 189 # _____________________________________________________________________________________ 190 191 # _add_parent 192 193 # _____________________________________________________________________________________ 194 def _add_parent(self, parent): 195 """ 196 connect edges 197 """ 198 # do not add duplicates 199 if parent in self._inward: 200 return parent 201 202 self._inward.append(parent) 203 parent._outward.append(self) 204 return parent 205 206 # _____________________________________________________________________________________ 207 208 # _remove_all_parents 209 210 # _____________________________________________________________________________________ 211 def _remove_all_parents(self): 212 """ 213 disconnect edges 214 """ 215 216 # remove self from parent 217 for parent in self._inward: 218 if self in parent._outward: 219 parent._outward.remove(self) 220 221 # clear self 222 self._inward = [] 223 224 return self 225 226 # _____________________________________________________________________________________ 227 228 # _remove_parent 229 230 # _____________________________________________________________________________________ 231 def _remove_parent(self, parent): 232 """ 233 disconnect edges 234 """ 235 236 if parent in self._inward: 237 self._inward.remove(parent) 238 if self in parent._outward: 239 parent._outward.remove(self) 240 return parent 241 # _____________________________________________________________________________________ 242 243 # _get_inward/_get_outward 244 245 # _____________________________________________________________________________________ 246 def _get_outward(self): 247 """ 248 just in case we need to return inward when we mean outward! 249 (for reversed graphs) 250 """ 251 return self._outward 252 253 def _get_inward(self): 254 """ 255 just in case we need to return inward when we mean outward! 256 (for reversed graphs) 257 """ 258 return self._inward 259 260 # _____________________________________________________________________________________ 261 262 # _fullstr 263 264 # _____________________________________________________________________________________ 265 266 def _fullstr(self): 267 """ 268 Full dump. Normally edges are not printed out 269 Everything is indented except name 270 """ 271 self_desc = list() 272 for k, v in sorted(iter(self.__dict__.items()), key=lambda x_v: (0, x_v[0], x_v[1]) if x_v[0] == "_name" else (1, x_v[0], x_v[1])): 273 indent = " " if k != "_name" else "" 274 if k in ("_inward", "_outward"): 275 v = ",".join([x._name for x in v]) 276 self_desc.append(indent + str(k) + "=" + str(v)) 277 else: 278 self_desc.append(indent + str(k) + "=" + str(v)) 279 return "\n".join(self_desc) 280 281 # _____________________________________________________________________________________ 282 283 # __str__ 284 285 # _____________________________________________________________________________________ 286 def __str__(self): 287 """ 288 Print everything except lists of edges 289 Useful for debugging 290 """ 291 self_desc = list() 292 for k, v in sorted(self.__dict__.items(), reverse=True): 293 indent = " " if k != "_name" else "" 294 if k[0] == '_': 295 continue 296 else: 297 self_desc.append(indent + str(k) + "=" + str(v)) 298 return " Task = " + "\n".join(self_desc) 299 300 # _____________________________________________________________________________________ 301 302 # _signalled 303 # 304 # _____________________________________________________________________________________ 305 306 def _signalled(self, extra_data_for_signal=None): 307 """ 308 Signals whether depth first search ends without this node 309 """ 310 return self._signal 311 312 313# _____________________________________________________________________________________ 314 315# node_to_json 316# 317# 318# _____________________________________________________________________________________ 319class node_to_json(json.JSONEncoder): 320 """ 321 output node using json 322 """ 323 324 def default(self, obj): 325 print(str(obj)) 326 if isinstance(obj, node): 327 return obj._name, { 328 "index": obj._node_index, 329 "_signal": obj._signal, 330 "_get_inward": [n._name for n in obj._inward], 331 "_get_outward": [n._name for n in obj._outward], 332 } 333 return json.JSONEncoder.default(self, obj) 334 335 336# 88888888888888888888888888888888888888888888888888888888888888888888888888888888888888888 337 338# topological_sort_visitor 339 340# 88888888888888888888888888888888888888888888888888888888888888888888888888888888888888888 341 342 343def default_signalled(node, extra_data): 344 """ 345 Depth first search stops when node._signalled return True 346 """ 347 return node._signalled(extra_data) 348 349 350class topological_sort_visitor (object): 351 """ 352 topological sort 353 used with DFS to find all nodes in topologically sorted order 354 All finds all DAG breaking cycles 355 356 """ 357 358 IGNORE_NODE_SIGNAL = 0 359 NOTE_NODE_SIGNAL = 1 360 END_ON_SIGNAL = 2 361 362 # _____________________________________________________________________________________ 363 364 # init 365 366 # _____________________________________________________________________________________ 367 def __init__(self, forced_dfs_nodes, 368 node_termination=END_ON_SIGNAL, 369 extra_data_for_signal=None, 370 signal_callback=None): 371 """ 372 list of saved results 373 """ 374 self._forced_dfs_nodes = set(forced_dfs_nodes) 375 self._node_termination = node_termination 376 377 self._start_nodes = set() 378 self._back_edges = set() 379 self._back_nodes = set() 380 self._signalling_nodes = set() 381 382 self.signal_callback = signal_callback 383 384 # keep order for tree traversal later 385 self._examined_edges = list() 386 # keep order for topological sorted results 387 self._finished_nodes = list() 388 389 self._extra_data_for_signal = extra_data_for_signal 390 391 def combine_with(self, other): 392 """ 393 combine the results of two visitors 394 (add other to self) 395 """ 396 self._back_edges .update(other._back_edges) 397 self._back_nodes .update(other._back_nodes) 398 extra_finished_nodes = set( 399 other._finished_nodes) - set(self._finished_nodes) 400 self._finished_nodes .extend(extra_finished_nodes) 401 402 # _____________________________________________________________________________________ 403 404 # __str__ 405 406 # _____________________________________________________________________________________ 407 408 def __str__(self): 409 """ 410 for diagnostics 411 """ 412 signalling_str = get_nodes_str("Signalling", self._signalling_nodes) 413 finished_str = get_nodes_str("Finished", self._finished_nodes) 414 forced_str = get_nodes_str("Forced to run", self._forced_dfs_nodes) 415 start_str = get_nodes_str("Start", self._start_nodes) 416 back_edges_str = get_edges_str("back", self._back_edges) 417 return ("" 418 + finished_str 419 + start_str 420 + back_edges_str 421 + signalling_str 422 + finished_str 423 ) 424 425 # _____________________________________________________________________________________ 426 427 # not_dag 428 429 # _____________________________________________________________________________________ 430 def not_dag(self): 431 """ 432 back edges add circularity 433 """ 434 return len(self._back_edges) 435 436 # _____________________________________________________________________________________ 437 438 # dag_violating_edges 439 440 # _____________________________________________________________________________________ 441 def dag_violating_edges(self): 442 """ 443 back edges add circularity 444 """ 445 return self._back_edges 446 447 # _____________________________________________________________________________________ 448 449 # dag_violating_nodes 450 451 # _____________________________________________________________________________________ 452 453 def dag_violating_nodes(self): 454 """ 455 all nodes involved in cycless 456 """ 457 return self._back_nodes 458 459 # _____________________________________________________________________________________ 460 461 # identify_dag_violating_nodes_and_edges 462 # 463 # _____________________________________________________________________________________ 464 def identify_dag_violating_nodes_and_edges(self): 465 """ 466 find all nodes and edges in any cycles 467 468 All dag violating cycles are defined by the back edge identified in DFS. 469 All paths which go the other way: start at the to_node and end up at the from_node 470 are therefore also part of the cycle 471 472 """ 473 if not len(self._back_edges): 474 return 475 cnt_examined_edges = len(self._examined_edges) 476 477 # add this to _back_edges at the end 478 cycle_edges = set() 479 480 # 481 # each cycle 482 # starts from the to_node of each back_edge and 483 # ends with the from_node of each back_edge 484 # 485 for cycle_to_node, cycle_from_node in self._back_edges: 486 start_search_from = 0 487 while 1: 488 # 489 # find start of cycle 490 for i, (f, t, n) in enumerate(self._examined_edges[start_search_from:]): 491 if f == cycle_from_node: 492 break 493 494 # no more cycles for this cycle_from_node/cycle_to_node pair 495 else: 496 break 497 498 # 499 # cycle end might be within the same pair 500 # if so, don't search the current (not the next) edge for the cycle end 501 # 502 # Otherwise incrementing search position avoids infinite loop 503 # 504 start_search_from = cycle_start = start_search_from + i 505 if self._examined_edges[cycle_start][1] != cycle_to_node: 506 start_search_from += 1 507 508 for i, (f, t, n) in enumerate(self._examined_edges[start_search_from:]): 509 510 # 511 # found end of cycle 512 # 513 if t == cycle_to_node: 514 cycle_end = start_search_from + i + 1 515 # 516 # ignore backtracked nodes which will not be part of the cycle 517 # we are essentially doing tree traversal here 518 # 519 backtracked_nodes = set() 520 for f, t, n in self._examined_edges[cycle_start:cycle_end]: 521 if t is None: 522 backtracked_nodes.add(n) 523 for f, t, n in self._examined_edges[cycle_start:cycle_end]: 524 if f is None or f in backtracked_nodes or t in backtracked_nodes: 525 continue 526 cycle_edges.add((f, t)) 527 self._back_nodes.add(f) 528 self._back_nodes.add(t) 529 start_search_from = cycle_end 530 break 531 532 # if cycle_from_node comes around again, this is not a cycle 533 if cycle_from_node == f: 534 if not i: 535 i += 1 536 start_search_from = start_search_from + i 537 break 538 539 continue 540 541 # no more cycles for this cycle_from_node/cycle_to_node pair 542 else: 543 break 544 545 self._back_edges.update(cycle_edges) 546 547 # _____________________________________________________________________________________ 548 549 # not_dag 550 551 # _____________________________________________________________________________________ 552 553 def topological_sorted(self): 554 """ 555 _finished_nodes 556 """ 557 return self._finished_nodes 558 559 # _____________________________________________________________________________________ 560 561 # terminate_before 562 563 # _____________________________________________________________________________________ 564 565 def terminate_before(self, node): 566 """ 567 Allow node to terminate this path in DFS without including itself 568 (see terminate_at) 569 570 If node in _forced_dfs_nodes that overrides what the node wants 571 """ 572 573 # 574 # If _node_termination = IGNORE_NODE_TERMINATION 575 # always go through whole tree 576 # 577 if self._node_termination == self.IGNORE_NODE_SIGNAL: 578 return False 579 580 # 581 # If _node_termination = NOTE_NODE_TERMINATION 582 # always go through whole tree but remember 583 # which nodes want to terminate 584 # 585 # Note that _forced_dfs_nodes is ignored 586 # 587 if self._node_termination == self.NOTE_NODE_SIGNAL: 588 if self.signal_callback(node, self._extra_data_for_signal): 589 self._signalling_nodes.add(node) 590 return False 591 592 # 593 # _forced_dfs_nodes always overrides node preferences 594 # but let us save what the node says anyway for posterity 595 # 596 if node in self._forced_dfs_nodes: 597 # Commented out code lets us save self_terminating_nodes even when 598 # they have been overridden by _forced_dfs_nodes 599 # if self.signal_callback(node, self._extra_data_for_signal): 600 # self._signalling_nodes.add(node) 601 return False 602 603 # 604 # OK. Go by what the node wants then 605 # 606 if self.signal_callback(node, self._extra_data_for_signal): 607 self._signalling_nodes.add(node) 608 return True 609 return False 610 611 # _____________________________________________________________________________________ 612 613 # call_backs 614 615 # _____________________________________________________________________________________ 616 617 def discover_vertex(self, node): 618 pass 619 620 def start_vertex(self, node): 621 self._start_nodes.add(node) 622 623 def finish_vertex(self, node): 624 """ 625 Save 626 1) topologically sorted nodes 627 2) as "None" (back) edges which allows _examined_edges to be traversed 628 like a tree 629 630 """ 631 self._examined_edges.append((None, None, node)) 632 self._finished_nodes.append(node) 633 634 def examine_edge(self, node_from, node_to): 635 """ 636 Save edges as we encounter then so we can look for loops 637 638 """ 639 self._examined_edges.append((node_from, node_to, None)) 640 641 def back_edge(self, node_from, node_to): 642 self._back_edges.add((node_from, node_to)) 643 644 def tree_edge(self, node_from, node_to): 645 pass 646 647 def forward_or_cross_edge(self, node_from, node_to): 648 pass 649 650 def terminate_at(self, node): 651 """ 652 Terminate this line of DFS but include myself 653 """ 654 return False 655 656# 657# _________________________________________________________________________________________ 658 659# debug_print_visitor 660 661# _________________________________________________________________________________________ 662 663 664class debug_print_visitor (object): 665 """ 666 log progress through DFS: for debugging 667 668 """ 669 670 def terminate_before(self, node): 671 return False 672 673 def terminate_at(self, node): 674 return False 675 676 def start_vertex(self, node): 677 print("s start vertex %s" % (node._name)) 678 679 def finish_vertex(self, node): 680 print(" v finish vertex %s" % (node._name)) 681 682 def discover_vertex(self, node): 683 print(" | discover vertex %s" % (node._name)) 684 685 def examine_edge(self, node_from, node_to): 686 print(" -- examine edge %s -> %s" % (node_from._name, node_to._name)) 687 688 def back_edge(self, node_from, node_to): 689 print(" back edge %s -> %s" % (node_from._name, node_to._name)) 690 691 def tree_edge(self, node_from, node_to): 692 print(" - tree edge %s -> %s" % (node_from._name, node_to._name)) 693 694 def forward_or_cross_edge(self, node_from, node_to): 695 print(" - forward/cross edge %s -> %s" % 696 (node_from._name, node_to._name)) 697 698 699# 88888888888888888888888888888888888888888888888888888888888888888888888888888888888888888 700# Functions 701# 88888888888888888888888888888888888888888888888888888888888888888888888888888888888888888 702# _________________________________________________________________________________________ 703# depth first search 704# _________________________________________________________________________________________ 705# 706# 707# 708WHITE = 0 # virgin 709GRAY = 1 # processing 710BLACK = 2 # finished 711 712 713def depth_first_visit(u, visitor, colours, outedges_func): 714 """ 715 depth_first_visit 716 unused callbacks are commented out 717 """ 718 # start processing this node: so gray 719 colours[u] = GRAY 720 721 stack = list() 722 723 # 724 # unused callback 725 # 726 # visitor.discover_vertex(u) 727 728 curr_edges = outedges_func(u) 729 730 if visitor.terminate_before(u): 731 colours[u] = BLACK 732 return 733 # If this vertex terminates the search, we push empty range 734 if visitor.terminate_at(u): 735 stack.append((u, curr_edges, len(curr_edges))) 736 else: 737 stack.append((u, curr_edges, 0)) 738 739 while len(stack): 740 u, curr_edges, curr_edge_pos = stack.pop() 741 while curr_edge_pos < len(curr_edges): 742 v = curr_edges[curr_edge_pos] 743 visitor.examine_edge(u, v) 744 v_colour = colours[v] 745 746 if visitor.terminate_before(v): 747 colours[v] = BLACK 748 curr_edge_pos += 1 749 continue 750 751 if v_colour == WHITE: 752 # 753 # unused callback 754 # 755 #visitor.tree_edge(u, v) 756 curr_edge_pos += 1 757 stack.append((u, curr_edges, curr_edge_pos)) 758 u = v 759 colours[u] = GRAY 760 # 761 # unused callback 762 # 763 # visitor.discover_vertex(u) 764 curr_edges = outedges_func(u) 765 curr_edge_pos = 0 766 767 if visitor.terminate_at(u): 768 break 769 elif v_colour == GRAY: 770 visitor.back_edge(u, v) 771 curr_edge_pos += 1 772 else: 773 # 774 # unused callback 775 # 776 #visitor.forward_or_cross_edge(u, v) 777 curr_edge_pos += 1 778 colours[u] = BLACK 779 visitor.finish_vertex(u) 780 781 782def depth_first_search(starting_nodes, visitor, outedges_func=node._get_inward): 783 """ 784 depth_first_search 785 go through all starting points and DFV on each of them 786 if they haven't been seen before 787 """ 788 colours = defaultdict(int) # defaults to WHITE 789 if len(starting_nodes): 790 for start in starting_nodes: 791 if colours[start] == WHITE: 792 visitor.start_vertex(start) 793 depth_first_visit(start, visitor, colours, outedges_func) 794 else: 795 796 # 797 # go through all nodes, maintaining order 798 # 799 for start in node._all_nodes: 800 if colours[start] == WHITE: 801 visitor.start_vertex(start) 802 depth_first_visit(start, visitor, colours, outedges_func) 803 804 805def topologically_sorted_nodes(to_leaves, 806 force_start_from=[], 807 gather_all_non_signalled=True, 808 test_all_signals=False, 809 extra_data_for_signal=None, 810 signal_callback=None): 811 """ 812 Get all nodes which are children of to_leaves 813 in topological sorted order 814 815 Defaults to including all nodes which are non-signalled and their dependents (via include_any_children()) 816 i.e. includes the *last* non-signalling node on each branch and all the way up the tree 817 818 819 Otherwise stops at each branch just before signalling node 820 i.e. includes the last non-signalling *run* on each branch 821 822 823 force_start_from 824 Optionally specify all the child nodes which *have* to 825 be included in the list at least 826 This will override any node signals 827 828 force_start_from = True to get the whole tree irrespective of signalling 829 830 831 Rewritten to minimise calls to node._signalled() 832 833 """ 834 835 # 836 # got through entire tree, looking for signalling nodes, 837 # usually for debugging or for printing 838 # 839 if test_all_signals: 840 v = topological_sort_visitor([], 841 topological_sort_visitor.NOTE_NODE_SIGNAL, 842 extra_data_for_signal, 843 signal_callback) 844 depth_first_search(to_leaves, v, node._get_inward) 845 signalling_nodes = v._signalling_nodes 846 else: 847 signalling_nodes = set() 848 849 if gather_all_non_signalled: 850 # 851 # get whole tree, ignoring signalling 852 # 853 v = topological_sort_visitor( 854 [], topological_sort_visitor.IGNORE_NODE_SIGNAL) 855 depth_first_search(to_leaves, v, node._get_inward) 856 857 # 858 # not dag: no further processing 859 # 860 if v.not_dag(): 861 v.identify_dag_violating_nodes_and_edges() 862 return (v.topological_sorted(), v._signalling_nodes, v.dag_violating_edges(), 863 v.dag_violating_nodes()) 864 865 # 866 # if force_start_from == True 867 # 868 # return entire tree 869 # 870 if force_start_from == True: 871 return (v.topological_sorted(), v._signalling_nodes, v.dag_violating_edges(), 872 v.dag_violating_nodes()) 873 874 # 875 # Set of all nodes we are going to return 876 # We will use v.topological_sorted to return them in the right (sorted) order 877 # 878 nodes_to_include = set() 879 880 # 881 # If force start from is a list of nodes, 882 # include these and all of its dependents (via include_any_children) 883 # 884 # We don't need to bother to check if they signal (_signalled) 885 # This saves calling the expensive _signalled 886 # 887 if len(force_start_from): 888 nodes_to_include.update(include_any_children(force_start_from)) 889 # This should not be necessary because include_any_children also returns self. 890 # for n in force_start_from: 891 # if n in nodes_to_include: 892 # continue 893 # nodes_to_include.add(n) 894 # nodes_to_include.update(include_any_children([n])) 895 896 # 897 # Now select all nodes from ancestor -> descendant which do not signal (signal_callback() == false) 898 # and select their descendants (via include_any_children()) 899 # 900 # Nodes which signal are added to signalling_nodes 901 # 902 reversed_nodes = v.topological_sorted() 903 for n in reversed_nodes: 904 if n in nodes_to_include: 905 continue 906 907 if not signal_callback(n, extra_data_for_signal): 908 # nodes_to_include.add(n) 909 nodes_to_include.update(include_any_children([n])) 910 else: 911 signalling_nodes.add(n) 912 #sys.stderr.write(json.dumps(n, cls=node_to_json, sort_keys=1) + "\n") 913 914 return ([n for n in v.topological_sorted() if n in nodes_to_include], 915 signalling_nodes, 916 [], []) 917 918 # 919 # gather_all_non_signalled = False 920 # stop at first signalled 921 # 922 else: 923 924 if force_start_from == True: 925 # 926 # get whole tree, ignoring signalling 927 # 928 v = topological_sort_visitor([], 929 topological_sort_visitor.IGNORE_NODE_SIGNAL) 930 else: 931 # 932 # End at each branch without including signalling node 933 # but ignore signalling for forced_nodes_and_dependencies 934 # 935 936 # Get forced nodes and all descendants via include_any_children 937 # 938 forced_nodes_and_dependencies = [] 939 if len(force_start_from): 940 forced_nodes_and_dependencies = include_any_children( 941 force_start_from) 942 943 v = topological_sort_visitor(forced_nodes_and_dependencies, 944 topological_sort_visitor.END_ON_SIGNAL, 945 extra_data_for_signal, 946 signal_callback) 947 948 # 949 # Forward graph iteration 950 # 951 depth_first_search(to_leaves, v, node._get_inward) 952 953 if v.not_dag(): 954 v.identify_dag_violating_nodes_and_edges() 955 956 signalling_nodes.update(v._signalling_nodes) 957 return (v.topological_sorted(), signalling_nodes, v.dag_violating_edges(), v.dag_violating_nodes()) 958 959 960# 961def debug_print_nodes(to_leaves): 962 v = debug_print_visitor() 963 depth_first_search(to_leaves, v, node._get_inward) 964 965 966# _________________________________________________________________________________________ 967 968# graph_printout 969 970# _________________________________________________________________________________________ 971def graph_colour_demo_printout(stream, 972 output_format, 973 size='11,8', 974 dpi='120'): 975 """ 976 Demo of the different colour schemes 977 """ 978 979 if output_format == 'dot': 980 write_colour_scheme_demo_in_dot_format(stream) 981 return 982 983 # print to dot file 984 #temp_dot_file = tempfile.NamedTemporaryFile(suffix='.dot', delete=False) 985 fh, temp_dot_file_name = tempfile.mkstemp(suffix='.dot') 986 temp_dot_file = os.fdopen(fh, "w") 987 988 write_colour_scheme_demo_in_dot_format(temp_dot_file) 989 temp_dot_file.close() 990 991 print_dpi = ("-Gdpi='%s'" % dpi) if output_format != "svg" else "" 992 run_dot = os.popen("dot -Gsize='%s' %s -T%s < %s" % 993 (size, print_dpi, output_format, temp_dot_file_name)) 994 995 # 996 # wierd bug fix for firefox and svg 997 # 998 result_str = run_dot.read() 999 err = run_dot.close() 1000 if err: 1001 raise RuntimeError("dot failed to run with exit code %d" % err) 1002 if output_format == "svg": 1003 result_str = result_str.replace("0.12", "0.0px") 1004 stream.write(result_str) 1005# _________________________________________________________________________________________ 1006 1007# graph_printout_in_dot_format 1008 1009# _________________________________________________________________________________________ 1010 1011 1012def graph_printout_in_dot_format(stream, 1013 to_leaves, 1014 force_start_from=[], 1015 draw_vertically=True, 1016 ignore_upstream_of_target=False, 1017 skip_signalling_nodes=False, 1018 gather_all_non_signalled=True, 1019 test_all_signals=True, 1020 no_key_legend=False, 1021 minimal_key_legend=True, 1022 user_colour_scheme=None, 1023 pipeline_name="Pipeline:", 1024 extra_data_for_signal=None, 1025 signal_callback=None): 1026 """ 1027 print out pipeline dependencies in dot formatting 1028 """ 1029 1030 (topological_sorted, # tasks_to_run 1031 signalling_nodes, # up to date 1032 dag_violating_edges, 1033 dag_violating_nodes) = topologically_sorted_nodes(to_leaves, force_start_from, 1034 gather_all_non_signalled, 1035 test_all_signals, 1036 extra_data_for_signal, 1037 signal_callback) 1038 1039 # 1040 # N.B. For graph: 1041 # upstream = parent 1042 # dependents/downstream 1043 # = children 1044 # 1045 # 1046 nodes_to_display = get_reachable_nodes( 1047 to_leaves, not ignore_upstream_of_target) 1048 1049 # 1050 # print out dependencies in dot format 1051 # 1052 write_flowchart_in_dot_format(topological_sorted, # tasks_to_run 1053 signalling_nodes, # up to date 1054 dag_violating_edges, 1055 dag_violating_nodes, 1056 stream, 1057 to_leaves, 1058 force_start_from, 1059 nodes_to_display, 1060 draw_vertically, 1061 skip_signalling_nodes, 1062 no_key_legend, 1063 minimal_key_legend, 1064 user_colour_scheme, 1065 pipeline_name) 1066 1067# _________________________________________________________________________________________ 1068 1069# graph_printout 1070 1071# _________________________________________________________________________________________ 1072 1073 1074def graph_printout(stream, 1075 output_format, 1076 to_leaves, 1077 force_start_from=[], 1078 draw_vertically=True, 1079 ignore_upstream_of_target=False, 1080 skip_signalling_nodes=False, 1081 gather_all_non_signalled=True, 1082 test_all_signals=True, 1083 no_key_legend=False, 1084 minimal_key_legend=True, 1085 user_colour_scheme=None, 1086 pipeline_name="Pipeline:", 1087 size=(11, 8), 1088 dpi=120, 1089 extra_data_for_signal=None, 1090 signal_callback=None): 1091 """ 1092 print out pipeline dependencies in a variety of formats, using the programme "dot" 1093 an intermediary 1094 """ 1095 1096 if output_format == 'dot': 1097 graph_printout_in_dot_format(stream, 1098 to_leaves, 1099 force_start_from, 1100 draw_vertically, 1101 ignore_upstream_of_target, 1102 skip_signalling_nodes, 1103 gather_all_non_signalled, 1104 test_all_signals, 1105 no_key_legend, 1106 minimal_key_legend, 1107 user_colour_scheme, 1108 pipeline_name, 1109 extra_data_for_signal, 1110 signal_callback) 1111 return 1112 1113 # print to dot file 1114 #temp_dot_file = tempfile.NamedTemporaryFile(suffix='.dot', delete=False) 1115 fh, temp_dot_file_name = tempfile.mkstemp(suffix='.dot') 1116 temp_dot_file = os.fdopen(fh, "wb") 1117 1118 graph_printout_in_dot_format(temp_dot_file, 1119 to_leaves, 1120 force_start_from, 1121 draw_vertically, 1122 ignore_upstream_of_target, 1123 skip_signalling_nodes, 1124 gather_all_non_signalled, 1125 test_all_signals, 1126 no_key_legend, 1127 minimal_key_legend, 1128 user_colour_scheme, 1129 pipeline_name, 1130 extra_data_for_signal, 1131 signal_callback) 1132 temp_dot_file.close() 1133 1134 if isinstance(size, tuple): 1135 print_size = "(%d,%d)" % size 1136 elif isinstance(size, (str)): 1137 print_size = size 1138 else: 1139 raise Exception( 1140 "Flowchart print size [%s] should be specified as a tuple of X,Y in inches" % str(size)) 1141 1142 # 1143 # N.B. Resolution doesn't seem to play nice with SVG and is ignored 1144 # 1145 print_dpi = ("-Gdpi='%s'" % dpi) if output_format != "svg" else "" 1146 cmd = "dot -Gsize='%s' %s -T%s < %s" % (print_size, 1147 print_dpi, output_format, temp_dot_file_name) 1148 1149 proc = subprocess.Popen( 1150 cmd, shell=True, stdout=subprocess.PIPE, stderr=subprocess.PIPE) 1151 result_str, error_str = proc.communicate() 1152 retcode = proc.returncode 1153 if retcode: 1154 raise subprocess.CalledProcessError( 1155 retcode, cmd + "\n" + "\n".join([str(result_str), str(error_str)])) 1156 1157 #run_dot = os.popen(cmd) 1158 #result_str = run_dot.read() 1159 #err = run_dot.close() 1160 # 1161 # if err: 1162 # raise RuntimeError("dot failed to run with exit code %d" % err) 1163 1164 # 1165 # wierd workaround for bug / bad interaction between firefox and svg: 1166 # Font sizes have "px" appended. 1167 # 1168 1169 if output_format == "svg": 1170 # result str is a binary string. I.e. could be .jpg 1171 # must turn it into string before we can replace, and then turn it back into binary 1172 result_str = result_str.decode() 1173 result_str = result_str.replace("0.12", "0.0px") 1174 result_str = result_str.encode() 1175 stream.write(result_str) 1176 1177 1178# _________________________________________________________________________________________ 1179 1180# include_any_children 1181 1182# _________________________________________________________________________________________ 1183def include_any_children(nodes): 1184 """ 1185 Get all children nodes by DFS in the inward direction, 1186 Ignores signals 1187 Also includes original nodes in the results 1188 """ 1189 children_visitor = topological_sort_visitor( 1190 [], topological_sort_visitor.IGNORE_NODE_SIGNAL) 1191 depth_first_search(nodes, children_visitor, node._get_outward) 1192 return children_visitor.topological_sorted() 1193 1194 1195# _________________________________________________________________________________________ 1196 1197# get_reachable_nodes 1198 1199# _________________________________________________________________________________________ 1200def get_reachable_nodes(nodes, children_as_well=True): 1201 """ 1202 Get all nodes which are parents and children of nodes 1203 recursing through the entire tree 1204 1205 i.e. go up *and* down tree starting from node 1206 1207 1) specify parents_as_well = False 1208 to only get children and not parents of nodes 1209 """ 1210 1211 # look for parents of nodes and start there instead 1212 if children_as_well: 1213 nodes = include_any_children(nodes) 1214 1215 parent_visitor = topological_sort_visitor( 1216 [], topological_sort_visitor.IGNORE_NODE_SIGNAL) 1217 depth_first_search(nodes, parent_visitor, node._get_inward) 1218 return parent_visitor.topological_sorted() 1219 1220 1221# _________________________________________________________________________________________ 1222 1223# Helper functions to dump edges and nodes 1224 1225# _________________________________________________________________________________________ 1226def get_edges_str(name, edges): 1227 """ 1228 helper function to dump edges as a list of names 1229 """ 1230 edges_str = " %d %s edges\n" % (len(edges), name) 1231 edges_str += " " + \ 1232 ", ".join([x_y[0]._name + "->" + x_y[1]._name for x_y in edges]) + "\n" 1233 return edges_str 1234 1235 1236def get_nodes_str(name, nodes): 1237 """ 1238 helper function to dump nodes as a list of names 1239 """ 1240 nodes_str = " %s nodes = %d\n" % (name, len(nodes)) 1241 nodes_str += " " + ", ".join([x._name for x in nodes]) + "\n" 1242 return nodes_str 1243