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