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