graph.py
Go to the documentation of this file.
00001 #! /usr/bin/env python
00002 # -*- coding: latin-1 -*-
00003 
00004 class Graph:
00005   def __init__(self, nodes):
00006     self.nodes = nodes
00007     self.neighbours = dict((u, set()) for u in nodes)
00008   def connect(self, u, v):
00009     self.neighbours[u].add(v)
00010     self.neighbours[v].add(u)
00011   def connected_components(self):
00012     remaining_nodes = set(self.nodes)
00013     result = []
00014     def dfs(node):
00015       result[-1].append(node)
00016       remaining_nodes.remove(node)
00017       for neighbour in self.neighbours[node]:
00018         if neighbour in remaining_nodes:
00019           dfs(neighbour)
00020     while remaining_nodes:
00021       node = iter(remaining_nodes).next()
00022       result.append([])
00023       dfs(node)
00024     return result
00025 
00026 
00027 def transitive_closure(pairs):
00028   # Warshall's algorithm.
00029   result = set(pairs)
00030   nodes = set(u for (u, v) in pairs) | set(v for (u, v) in pairs)
00031   for k in nodes:
00032     for i in nodes:
00033       for j in nodes:
00034         if (i, j) not in result and (i, k) in result and (k, j) in result:
00035           result.add((i, j))
00036   return sorted(result)
00037 
00038 
00039 if __name__ == "__main__":
00040   g = Graph([1, 2, 3, 4, 5, 6])
00041   g.connect(1, 2)
00042   g.connect(1, 3)
00043   g.connect(4, 5)
00044   print g.connected_components()


tfd_modules
Author(s): Maintained by Christian Dornhege (see AUTHORS file).
autogenerated on Mon Oct 6 2014 07:52:06