1 """
2 EXPERIMENTAL: Base classes for trees and forests.
3
4 """
5 __author__ = """Aric Hagberg (hagberg@lanl.gov)"""
6
7
8
9
10
11
12
13
14 from networkx.graph import Graph
15 from networkx.digraph import DiGraph
16 from networkx.exception import NetworkXException, NetworkXError
17 import networkx.convert as convert
18 import networkx.component as component
19 import networkx.path as shortest_path
20
21
22
24 """ A free (unrooted) tree."""
40
42 if n in self:
43 return
44 elif len(self.adj)==0:
45 Graph.add_node(self,n)
46 else:
47 raise NetworkXError(\
48 "adding single node %s not allowed in non-empty tree"%(n))
49
53
55 try:
56 if len(self.adj[n])==1:
57 Graph.delete_node(self,n)
58 else:
59 raise NetworkXError(
60 "deleting interior node %s not allowed in tree"%(n))
61 except KeyError:
62 raise NetworkXError("node %s not in graph"%n)
63
67
69 if v is None: (u,v)=u
70 if self.has_edge(u,v): return
71 elif u in self and v in self:
72 raise NetworkXError("adding edge %s-%s not allowed in tree"%(u,v))
73 elif u in self or v in self:
74 Graph.add_edge(self,u,v)
75 return
76 elif len(self.adj)==0:
77 Graph.add_edge(self,u,v)
78 return
79 else:
80 raise NetworkXError("adding edge %s-%s not allowed in tree"%(u,v))
81
83 for e in ebunch:
84 self.add_edge(e)
85
87 if v is None: (u,v)=u
88 if self.degree(u)==1 or self.degree(v)==1:
89 Graph.delete_edge(self,u,v)
90 else:
91 raise NetworkXError(\
92 "deleting interior edge %s-%s not allowed in tree"%(u,v))
93 if self.degree(u)==0:
94 Graph.delete_node(self,u)
95 if self.degree(v)==0:
96 Graph.delete_node(self,v)
97
99 for e in ebunch:
100 self.delete_edge(e)
101
102
104 self.add_edge(u,v)
105
107 self.delete_edge(u,v)
108
110 for e in ebunch:
111 self.add_leaf(e)
112
114 for e in ebunch:
115 self.delete_leaf(e)
116
118 """Polymorphic helper method for Graph.union().
119
120 Required keywords: v_from and v_to, where v_from is the node
121 in self to which v_to should be attached as child."""
122 T = self.copy()
123 parent = kwds['v_from']
124 node = kwds['v_to']
125 T.add_edge(parent, node)
126 T.union_sub_tree_helper(T1, node)
127 return T
128
134
135
137 """ A rooted tree."""
138 - def __init__(self,root,data=None,**kwds):
139 Tree.__init__(self,data=data,**kwds)
140 self.root=root
141 self.par={}
142 if data is not None:
143
144 self.root_tree(root)
145
146
147
148
150 try:
151 if len(self.adj[n])==1:
152 Graph.delete_node(self,n)
153 del self.par[n]
154 else:
155 raise NetworkXError, \
156 "deleting interior node %s not allowed in tree"%(n)
157 except KeyError:
158 raise NetworkXError, "node %s not in graph"%n
159
160
162 if v is None:
163 (u,v)=u
164 if self.has_edge(u,v):
165 return
166 elif u in self and v in self:
167 raise NetworkXError, "adding edge %s-%s not allowed in tree"%(u,v)
168 elif u in self:
169 Graph.add_edge(self,u,v)
170 self.par[v]=u
171 return
172 elif v in self:
173 Graph.add_edge(self,u,v)
174 self.par[u]=v
175 return
176 elif len(self.adj)==0:
177 Graph.add_edge(self,u,v)
178 self.par[v]=u
179 return
180 else:
181 raise NetworkXError, "adding edge %s-%s not allowed in tree"%(u,v)
182
184 try:
185 return self.par[u]
186 except:
187 return None
188
189
193
194
196 preds=shortest_path.predecessor(self,root)
197 del preds[root]
198 for p in preds:
199 self.par[p]=preds[p][0]
200
201
203 """ A directed tree."""
205 DiGraph.__init__(self,**kwds)
206 if data is not None:
207
208 try:
209 D=DiGraph()
210 for (child,parent) in data.par.iteritems():
211 D.add_edge(parent,child)
212 except AttributeError:
213 D=DiGraph(data)
214 except:
215 raise NetworkXError, "Data %s is not a rooted tree:"%data
216
217 if D.order()==D.size()+1:
218 self.pred=D.pred.copy()
219 self.succ=D.succ.copy()
220 self.adj=self.succ
221 del D
222 else:
223 raise NetworkXError, "Data %s is not a rooted tree:"%data
224
226 try:
227 if len(self.succ[n])+len(self.pred[n])==1:
228 DiGraph.delete_node(self,n)
229 else:
230 raise NetworkXError( \
231 "deleting interior node %s not allowed in tree"%(n))
232 except KeyError:
233 raise NetworkXError, "node %s not in graph"%n
234
236 if v is None: (u,v)=u
237 if self.has_edge(u,v): return
238 elif u in self and v in self:
239 raise NetworkXError, "adding edge %s-%s not allowed in tree"%(u,v)
240 elif u in self or v in self:
241 DiGraph.add_edge(self,u,v)
242 return
243 elif len(self.adj)==0:
244 DiGraph.add_edge(self,u,v)
245 return
246 else:
247 raise NetworkXError("adding edge %s-%s not allowed in tree"%(u,v))
248
250 if v is None: (u,v)=u
251 if self.degree(u)==1 or self.degree(v)==1:
252 DiGraph.delete_edge(self,u,v)
253 else:
254 raise NetworkXError(
255 "deleting interior edge %s-%s not allowed in tree"%(u,v))
256 if self.degree(u)==0: DiGraph.delete_node(self,u)
257 if self.degree(v)==0: DiGraph.delete_node(self,v)
258
259
261 """ A forest."""
271
273 Graph.add_node(self,n)
274
275
276 self.comp[n]=self.nc
277 self.nc+=1
278
279
295
297 if v is None: (u,v)=u
298 if self.has_edge(u,v): return
299 if u in self:
300 if v in self:
301 if self.comp[u]==self.comp[v]:
302 raise NetworkXError, \
303 "adding edge %s-%s not allowed in forest"%(u,v)
304 else:
305 Graph.add_edge(self,u,v)
306 ucomp=self.comp[u]
307
308 for n in component.node_connected_component(self,v):
309 self.comp[n]=ucomp
310 else:
311 Graph.add_edge(self,u,v)
312 self.comp[v]=self.comp[u]
313 else:
314 Graph.add_edge(self,u,v)
315 self.comp[u]=self.nc
316 self.comp[v]=self.nc
317 self.nc+=1
318
320 if v is None: (u,v)=u
321 Graph.delete_edge(self,u,v)
322
323
324 vnodes=component.node_connected_component(self,v)
325 for n in vnodes:
326 self.comp[n]=self.nc
327 self.nc+=1
328
329 - def tree(self,n=None):
330 """Return tree containing node n.
331 If no node is specified return list of all trees in forest.
332 """
333 if n is not None:
334 ncomp=self.comp[n]
335 vnodes=[v for v in self if self.comp[v]==ncomp]
336 return Tree(self.subgraph(vnodes))
337 else:
338 trees=[]
339 uniqc={}
340
341 for c in self.comp.values():
342 uniqc[c]=True
343 for c in uniqc.keys():
344 vnodes=[v for v in self if self.comp[v]==c]
345 trees.append(Tree(self.subgraph(vnodes)))
346 return trees
347
349 """Return tree containing node n.
350 If no node is specified return list of all trees in forest.
351 """
352 if n is not None:
353 return self.tree(n).nodes()
354 else:
355 tlist=[]
356 for t in self.tree():
357 tlist.append(t.nodes())
358 return tlist
359
360
364
365
367 import doctest
368 suite = doctest.DocFileSuite('tests/tree.txt',
369 'tests/forest.txt',
370 package='networkx')
371 return suite
372
373
374 if __name__ == "__main__":
375 import os
376 import sys
377 import unittest
378 if sys.version_info[:2] < (2, 4):
379 print "Python version 2.4 or later required for tests (%d.%d detected)." % sys.version_info[:2]
380 sys.exit(-1)
381
382 nxbase=sys.path[0]+os.sep+os.pardir
383 sys.path.insert(0,nxbase)
384 unittest.TextTestRunner().run(_test_suite())
385