1 """
2 Hybrid
3
4 """
5 __author__ = """Aric Hagberg (hagberg@lanl.gov)\nDan Schult (dschult@colgate.edu)"""
6 __date__ = "$Date: 2005-03-30 16:56:28 -0700 (Wed, 30 Mar 2005) $"
7 __credits__ = """"""
8 __revision__ = "$Revision: 911 $"
9
10
11
12
13
14
15 import copy
16 import sets
17 from networkx.path import shortest_path
18
20 """ Returns the maximum locally (k,l) connected subgraph of G.
21
22 (k,l)-connected subgraphs are presented by Fan Chung and Li
23 in "The Small World Phenomenon in hybrid power law graphs"
24 to appear in "Complex Networks" (Ed. E. Ben-Naim) Lecture
25 Notes in Physics, Springer (2004)
26
27 low_memory=True then use a slightly slower, but lower memory version
28 same_as_graph=True then return a tuple with subgraph and
29 pflag for if G is kl-connected
30 """
31 H=copy.deepcopy(G)
32
33 graphOK=True
34 deleted_some=True
35 while deleted_some:
36 deleted_some=False
37 for edge in H.edges():
38 (u,v)=edge
39
40 if low_memory:
41 verts=sets.Set([u,v])
42 for i in range(k):
43 [verts.update(G.neighbors(w)) for w in verts.copy()]
44 G2=G.subgraph(list(verts))
45 else:
46 G2=copy.deepcopy(G)
47
48 path=[u,v]
49 cnt=0
50 accept=0
51 while path:
52 cnt += 1
53 if cnt>=l:
54 accept=1
55 break
56
57 prev=u
58 for w in path:
59 G2.delete_edge(prev,w)
60 prev=w
61
62 path=shortest_path(G2,u,v)
63
64 if accept==0:
65 H.delete_edge(u,v)
66 deleted_some=True
67 if graphOK: graphOK=False
68
69
70 if same_as_graph:
71 return (H,graphOK)
72 return H
73
75 """Returns True if G is kl connected """
76 graphOK=True
77 for edge in G.edges():
78 (u,v)=edge
79
80 if low_memory:
81 verts=sets.Set([u,v])
82 for i in range(k):
83 [verts.update(G.neighbors(w)) for w in verts.copy()]
84 G2=G.subgraph(list(verts))
85 else:
86 G2=copy.deepcopy(G)
87
88 path=[u,v]
89 cnt=0
90 accept=0
91 while path:
92 cnt += 1
93 if cnt>=l:
94 accept=1
95 break
96
97 prev=u
98 for w in path:
99 G2.delete_edge(prev,w)
100 prev=w
101
102 path=shortest_path(G2,u,v)
103
104 if accept==0:
105 graphOK=False
106 break
107
108 return graphOK
109
110
112 import doctest
113 suite = doctest.DocFileSuite('tests/hybrid.txt',package='networkx')
114 return suite
115
116
117 if __name__ == "__main__":
118 import os
119 import sys
120 import unittest
121 if sys.version_info[:2] < (2, 4):
122 print "Python version 2.4 or later required for tests (%d.%d detected)." % sys.version_info[:2]
123 sys.exit(-1)
124
125 nxbase=sys.path[0]+os.sep+os.pardir
126 sys.path.insert(0,nxbase)
127 unittest.TextTestRunner().run(_test_suite())
128