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