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