]>
Commit | Line | Data |
---|---|---|
a6f80f0e | 1 | #!/usr/bin/python |
3e8ee54f | 2 | # |
3 | # Copyright 2013. Cumulus Networks, Inc. | |
4 | # Author: Roopa Prabhu, roopa@cumulusnetworks.com | |
5 | # | |
6 | # graph -- | |
7 | # graph helper module for ifupdown | |
8 | # | |
a6f80f0e | 9 | |
10 | import logging | |
615234a1 | 11 | import copy |
a6f80f0e | 12 | from collections import deque |
739f665b | 13 | try: |
14 | from gvgen import * | |
15 | except ImportError, e: | |
16 | pass | |
a6f80f0e | 17 | |
18 | class graph(): | |
19 | ||
20 | def __init__(self): | |
21 | self.logger = logging.getLogger('ifupdown.' + | |
22 | self.__class__.__name__) | |
23 | ||
24 | @classmethod | |
615234a1 | 25 | def topological_sort_graphs_all(cls, dependency_graphs, indegrees_arg): |
a6f80f0e | 26 | S = [] |
27 | Q = deque() | |
28 | ||
615234a1 | 29 | indegrees = copy.deepcopy(indegrees_arg) |
a6f80f0e | 30 | for ifname,indegree in indegrees.items(): |
31 | if indegree == 0: | |
32 | Q.append(ifname) | |
33 | ||
fe0a57d3 | 34 | while len(Q): |
cca03c30 | 35 | # initialize queue |
36 | x = Q.popleft() | |
37 | ||
38 | # Get dependents of x | |
39 | dlist = dependency_graphs.get(x) | |
fe0a57d3 | 40 | if not dlist: |
cca03c30 | 41 | S.append(x) |
42 | continue | |
43 | ||
44 | for y in dlist: | |
45 | indegrees[y] = indegrees.get(y) - 1 | |
46 | if indegrees.get(y) == 0: | |
47 | Q.append(y) | |
48 | ||
49 | S.append(x) | |
50 | ||
51 | for ifname,indegree in indegrees.items(): | |
52 | if indegree != 0: | |
53 | raise Exception('cycle found involving iface %s' %ifname + | |
54 | ' (indegree %d)' %indegree) | |
55 | ||
56 | return S | |
57 | ||
739f665b | 58 | @classmethod |
59 | def generate_dots(cls, dependency_graph, indegrees): | |
83c1f241 | 60 | gvgraph = GvGen() |
61 | graphnodes = {} | |
62 | for v in dependency_graph.keys(): | |
63 | graphnodes[v] = gvgraph.newItem(v) | |
739f665b | 64 | |
83c1f241 | 65 | for i, v in graphnodes.items(): |
66 | dlist = dependency_graph.get(i, []) | |
67 | if not dlist: | |
68 | continue | |
69 | for d in dlist: | |
70 | gvgraph.newLink(v, graphnodes.get(d)) | |
71 | gvgraph.dot() |