shinken/graph.py

   1 #!/usr/bin/env python
   2 #Copyright (C) 2009-2010 :
   3 #    Gabes Jean, naparuba@gmail.com
   4 #    Gerhard Lausser, Gerhard.Lausser@consol.de
   5 #
   6 #This file is part of Shinken.
   7 #
   8 #Shinken is free software: you can redistribute it and/or modify
   9 #it under the terms of the GNU Affero General Public License as published by
  10 #the Free Software Foundation, either version 3 of the License, or
  11 #(at your option) any later version.
  12 #
  13 #Shinken is distributed in the hope that it will be useful,
  14 #but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 #MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 #GNU Affero General Public License for more details.
  17 #
  18 #You should have received a copy of the GNU Affero General Public License
  19 #along with Shinken.  If not, see <http://www.gnu.org/licenses/>.
  20
  21
  22 #Graph is a class to make graph things like DFS checks or accessibility
  23 #Why use an atomic bomb when a little hammer is enought?
  24
  25
  26 class Graph:
  27     def __init__(self):
  28         self.nodes = {}
  29
  30
  31     #Do not call twice...
  32     def add_node(self, node):
  33         self.nodes[node] = []
  34
  35
  36     #Just loop over nodes
  37     def add_nodes(self, nodes):
  38         for node in nodes:
  39             self.add_node(node)
  40
  41     #Add an edge to the graph from->to
  42     def add_edge(self, from_node, to_node):
  43         #Maybe to_node is unknown
  44         if to_node not in self.nodes:
  45             self.add_node(to_node)
  46
  47         try:
  48             self.nodes[from_node].append(to_node)
  49         #If from_node do not exist, add it with it's son
  50         except KeyError:
  51             self.nodes[from_node] = [to_node]
  52
  53
  54     #Return all nodes that are in a loop. So if return [], no loop
  55     def loop_check(self):
  56         in_loop = []
  57         #Add the tag for dfs check
  58         for node in self.nodes:
  59             node.dfs_loop_status = 'DFS_UNCHECKED'
  60
  61         #Now do the job
  62         for node in self.nodes:
  63             #Run the dfs only if the node is not already done */
  64             if node.dfs_loop_status == 'DFS_UNCHECKED':
  65                 self.dfs_loop_search(node)
  66             #If LOOP_INSIDE, must be returned
  67             if node.dfs_loop_status == 'DFS_LOOP_INSIDE':
  68                 in_loop.append(node)
  69
  70         #Remove the tag
  71         for node in self.nodes:
  72             del node.dfs_loop_status
  73
  74         return in_loop
  75
  76
  77     #DFS_UNCHECKED default value
  78     #DFS_TEMPORARY_CHECKED check just one time
  79     #DFS_OK no problem for node and it's childs
  80     #DFS_NEAR_LOOP has trouble sons
  81     #DFS_LOOP_INSIDE is a part of a loop!
  82     def dfs_loop_search(self, root):
  83         #Make the root temporary checkded
  84         root.dfs_loop_status = 'DFS_TEMPORARY_CHECKED'
  85
  86         #We are scanning the sons
  87         for child in self.nodes[root]:
  88             child_status = child.dfs_loop_status
  89             #If a child is not checked, check it
  90             if child_status == 'DFS_UNCHECKED':
  91                 self.dfs_loop_search(child)
  92                 child_status = child.dfs_loop_status
  93
  94             #If a child already temporary checked, its a problem,
  95             #loop inside, and its a acked status
  96             if child_status == 'DFS_TEMPORARY_CHECKED':
  97                 child.dfs_loop_status = 'DFS_LOOP_INSIDE'
  98                 root.dfs_loop_status = 'DFS_LOOP_INSIDE'
  99
 100             #If a child already temporary checked, its a problem, loop inside
 101             if child_status in ('DFS_NEAR_LOOP', 'DFS_LOOP_INSIDE'):
 102                 #if a node is know to be part of a loop, do not let it be less
 103                 if root.dfs_loop_status != 'DFS_LOOP_INSIDE':
 104                     root.dfs_loop_status = 'DFS_NEAR_LOOP'
 105                 #We already saw this child, it's a problem
 106                 child.dfs_loop_status = 'DFS_LOOP_INSIDE'
 107
 108         #If root have been modified, do not set it OK
 109         #A node is OK if and only if all of his childs are OK
 110         #if it does not have child, goes ok
 111         if root.dfs_loop_status == 'DFS_TEMPORARY_CHECKED':
 112             root.dfs_loop_status = 'DFS_OK'
 113
 114
 115     #Get accessibility packs of the graph : in one pack,
 116     #element are related in a way. Between packs, there is no relation
 117     #at all.
 118     #TODO : Get it work for directionnal graph too
 119     #Because for now, edge must be father->son AND son->father
 120     def get_accessibility_packs(self):
 121         packs = []
 122         #Add the tag for dfs check
 123         for node in self.nodes:
 124             node.dfs_loop_status = 'DFS_UNCHECKED'
 125
 126         for node in self.nodes:
 127             #Run the dfs only if the node is not already done */
 128             if node.dfs_loop_status == 'DFS_UNCHECKED':
 129                 packs.append(self.dfs_get_all_childs(node))
 130
 131         #Remove the tag
 132         for node in self.nodes:
 133             del node.dfs_loop_status
 134
 135         return packs
 136
 137
 138     #Return all mychilds, and all childs of my childs
 139     def dfs_get_all_childs(self, root):
 140         root.dfs_loop_status = 'DFS_CHECKED'
 141
 142         ret = set()
 143         #Me
 144         ret.add(root)
 145         #And my sons
 146         ret.update(self.nodes[root])
 147
 148         for child in self.nodes[root]:
 149             #I just don't care about already check childs
 150             if child.dfs_loop_status == 'DFS_UNCHECKED':
 151                 ret.update(self.dfs_get_all_childs(child))
 152
 153         return list(ret)