]>
Commit | Line | Data |
---|---|---|
35681c06 | 1 | #!/usr/bin/env python3 |
3e8ee54f | 2 | # |
d486dd0d | 3 | # Copyright 2014-2017 Cumulus Networks, Inc. All rights reserved. |
3e8ee54f | 4 | # Author: Roopa Prabhu, roopa@cumulusnetworks.com |
5 | # | |
6 | # graph -- | |
7 | # graph helper module for ifupdown | |
8 | # | |
a6f80f0e | 9 | |
615234a1 | 10 | import copy |
d486dd0d JF |
11 | import logging |
12 | ||
a6f80f0e | 13 | from collections import deque |
d486dd0d | 14 | |
739f665b | 15 | try: |
16 | from gvgen import * | |
3b01ed76 | 17 | except ImportError as e: |
739f665b | 18 | pass |
a6f80f0e | 19 | |
d486dd0d | 20 | |
a6f80f0e | 21 | class graph(): |
2c0ad8b3 | 22 | """ graph functions to sort and print interface graph """ |
a6f80f0e | 23 | |
afe51251 | 24 | logger = logging.getLogger('ifupdown.graph') |
a6f80f0e | 25 | |
26 | @classmethod | |
615234a1 | 27 | def topological_sort_graphs_all(cls, dependency_graphs, indegrees_arg): |
2c0ad8b3 RP |
28 | """ runs topological sort on interface list passed as dependency graph |
29 | ||
30 | Args: | |
904908bc | 31 | **dependency_graphs** (dict): dependency graph with dependency |
d486dd0d | 32 | lists for interfaces |
904908bc RP |
33 | |
34 | **indegrees_arg** (dict): indegrees array for all interfaces | |
2c0ad8b3 | 35 | """ |
a6f80f0e | 36 | S = [] |
37 | Q = deque() | |
38 | ||
615234a1 | 39 | indegrees = copy.deepcopy(indegrees_arg) |
3b01ed76 | 40 | for ifname,indegree in list(indegrees.items()): |
a6f80f0e | 41 | if indegree == 0: |
42 | Q.append(ifname) | |
43 | ||
fe0a57d3 | 44 | while len(Q): |
cca03c30 | 45 | # initialize queue |
46 | x = Q.popleft() | |
47 | ||
48 | # Get dependents of x | |
49 | dlist = dependency_graphs.get(x) | |
fe0a57d3 | 50 | if not dlist: |
cca03c30 | 51 | S.append(x) |
52 | continue | |
53 | ||
54 | for y in dlist: | |
67cfaeb1 RP |
55 | try: |
56 | indegrees[y] = indegrees.get(y) - 1 | |
57 | except: | |
afe51251 | 58 | cls.logger.debug('topological_sort_graphs_all: did not find %s' %y) |
67cfaeb1 RP |
59 | indegrees[y] = 0 |
60 | pass | |
cca03c30 | 61 | if indegrees.get(y) == 0: |
62 | Q.append(y) | |
63 | ||
64 | S.append(x) | |
65 | ||
3b01ed76 | 66 | for ifname,indegree in list(indegrees.items()): |
cca03c30 | 67 | if indegree != 0: |
68 | raise Exception('cycle found involving iface %s' %ifname + | |
69 | ' (indegree %d)' %indegree) | |
70 | ||
71 | return S | |
72 | ||
739f665b | 73 | @classmethod |
74 | def generate_dots(cls, dependency_graph, indegrees): | |
2c0ad8b3 RP |
75 | """ spits out interface dependency graph in dot format |
76 | ||
77 | Args: | |
904908bc | 78 | **dependency_graphs** (dict): dependency graph with dependency |
d486dd0d | 79 | lists for interfaces |
904908bc RP |
80 | |
81 | **indegrees_arg** (dict): indegrees array for all interfaces | |
2c0ad8b3 RP |
82 | """ |
83 | ||
83c1f241 | 84 | gvgraph = GvGen() |
85 | graphnodes = {} | |
3b01ed76 | 86 | for v in list(dependency_graph.keys()): |
83c1f241 | 87 | graphnodes[v] = gvgraph.newItem(v) |
739f665b | 88 | |
3b01ed76 | 89 | for i, v in list(graphnodes.items()): |
83c1f241 | 90 | dlist = dependency_graph.get(i, []) |
91 | if not dlist: | |
92 | continue | |
93 | for d in dlist: | |
94 | gvgraph.newLink(v, graphnodes.get(d)) | |
95 | gvgraph.dot() |