ifupdown2/ifupdown/graph.py

   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()