1# Copyright 2013-present Barefoot Networks, Inc. 2# 3# Licensed under the Apache License, Version 2.0 (the "License"); 4# you may not use this file except in compliance with the License. 5# You may obtain a copy of the License at 6# 7# http://www.apache.org/licenses/LICENSE-2.0 8# 9# Unless required by applicable law or agreed to in writing, software 10# distributed under the License is distributed on an "AS IS" BASIS, 11# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12# See the License for the specific language governing permissions and 13# limitations under the License. 14# 15 16# 17# Antonin Bas (antonin@barefootnetworks.com) 18# 19# 20 21# -*- coding: utf-8 -*- 22 23from __future__ import print_function 24 25class Node(object): 26 def __init__(self, n): 27 self.n = n 28 self.edges = set() 29 30 def add_edge_to(self, other): 31 assert(isinstance(other, Node)) 32 self.edges.add(other) 33 34 def __str__(self): 35 return str(self.n) 36 37 38class Graph(object): 39 def __init__(self): 40 self.nodes = {} 41 self.root = None 42 43 def add_node(self, node): 44 assert(node not in self.nodes) 45 self.nodes[node] = Node(node) 46 47 def __contains__(self, node): 48 return node in self.nodes 49 50 def get_node(self, node): 51 return self.nodes[node] 52 53 def produce_topo_sorting(self): 54 def visit(node, topo_sorting, sequence=None): 55 if sequence is not None: 56 sequence += [str(node)] 57 if node._behavioral_topo_sorting_mark == 1: 58 if sequence is not None: 59 print("cycle", sequence) 60 return False 61 if node._behavioral_topo_sorting_mark != 2: 62 node._behavioral_topo_sorting_mark = 1 63 for next_node in node.edges: 64 res = visit(next_node, topo_sorting, sequence) 65 if not res: 66 return False 67 node._behavioral_topo_sorting_mark = 2 68 topo_sorting.insert(0, node.n) 69 return True 70 71 has_cycle = False 72 topo_sorting = [] 73 74 for node in self.nodes.values(): 75 # 0 is unmarked, 1 is temp, 2 is permanent 76 node._behavioral_topo_sorting_mark = 0 77 for node in self.nodes.values(): 78 if node._behavioral_topo_sorting_mark == 0: 79 if not visit(node, topo_sorting, sequence=[]): 80 has_cycle = True 81 break 82 # removing mark 83 for node in self.nodes.values(): 84 del node._behavioral_topo_sorting_mark 85 86 if has_cycle: 87 return None 88 89 return topo_sorting 90