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