ifupdown2/ifupdown/graph.py

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