Package networkx :: Module info
[hide private]
[frames] | no frames]

Source Code for Module networkx.info

  1  """ 
  2  Graph classes 
  3  ============= 
  4   
  5  Graph 
  6   
  7     A simple graph that has no self-loops or multiple (parallel) edges. 
  8   
  9     An empty graph is created with 
 10   
 11     >>> G=Graph() 
 12      
 13  DiGraph 
 14   
 15     A directed graph that has no self-loops or multiple (parallel) edges. 
 16     Subclass of Graph. 
 17   
 18     An empty digraph is created with 
 19   
 20     >>> G=DiGraph() 
 21   
 22  XGraph 
 23   
 24     A graph that has (optional) self-loops or multiple (parallel) edges 
 25     and arbitrary data on the edges. 
 26     Subclass of Graph. 
 27   
 28     An empty graph is created with 
 29   
 30     >>> G=XGraph() 
 31      
 32  XDiGraph 
 33   
 34     A directed graph that has (optional) self-loops or multiple (parallel) 
 35     edges and arbitrary data on the edges. 
 36   
 37     A simple digraph that has no self-loops or multiple (parallel) edges. 
 38     Subclass of DiGraph which is a subclass of Graph. 
 39   
 40     An empty digraph is created with 
 41   
 42     >>> G=DiGraph() 
 43   
 44   
 45  The XGraph and XDiGraph classes extend the Graph and DiGraph classes 
 46  by allowing (optional) self loops, multiedges and by decorating 
 47  each edge with an object x.   
 48   
 49  Each XDiGraph or XGraph edge is a 3-tuple e=(n1,n2,x),  
 50  representing an edge between nodes n1 and n2 that  
 51  is decorated with the object x. Here n1 and n2 are (hashable)  
 52  node objects and x is a (not necessarily hashable) edge object.  
 53  If multiedges are allowed, G.get_edge(n1,n2) returns a  
 54  list of edge objects. 
 55   
 56  Whether an XGraph or XDiGraph allow self-loops or multiple edges is 
 57  determined initially via parameters selfloops=True/False and  
 58  multiedges=True/False.  
 59  For example, the example empty XGraph created above is equivalent to 
 60   
 61  >>> G=XGraph(selfloops=False, multiedges=False) 
 62   
 63  Similar defaults hold for XDiGraph.  The command 
 64   
 65  >>> G=XDiGraph(multiedges=True) 
 66   
 67  creates an empty digraph G that does not allow selfloops  
 68  but does allow for multiple (parallel) edges.  Methods exist  
 69  for allowing or disallowing each feature after instatiation as well. 
 70   
 71  Note that if G is an XGraph then G.add_edge(n1,n2) will add  
 72  the edge (n1,n2,None), and G.delete_edge(n1,n2) will attempt  
 73  to delete the edge (n1,n2,None). 
 74  In the case of multiple edges between nodes n1 and n2, one can use 
 75  G.delete_multiedge(n1,n2) to delete all edges between n1 and n2. 
 76   
 77   
 78  Notation 
 79  ======== 
 80   
 81  The following shorthand is used throughout NetworkX documentation and code: 
 82  (we use mathematical notation n,v,w,... to indicate a node, v=vertex=node). 
 83    
 84  G,G1,G2,H,etc: 
 85     Graphs 
 86   
 87  n,n1,n2,u,v,v1,v2: 
 88     nodes (vertices) 
 89   
 90  nlist: 
 91     a list of nodes (vertices) 
 92   
 93  nbunch: 
 94     a "bunch" of nodes (vertices). 
 95     An nbunch is either a single node of the graph or 
 96     any iterable container/iterator of nodes.  The distinction 
 97     is determined by checking if nbunch is in the graph. 
 98     If you use iterable containers as nodes you should be  
 99     careful when using nbunch. 
100   
101  e=(n1,n2): 
102     an edge (a python "2-tuple"), also written n1-n2 (if undirected) 
103     and n1->n2 (if directed).  
104      
105  e=(n1,n2,x): 
106     an edge triple ("3-tuple") containing the two nodes connected and the  
107     edge data/label/object stored associated with the edge. The object x, 
108     or a list of objects (if multiedges=True), can be obtained using 
109     G.get_edge(n1,n2) 
110   
111  elist: 
112     a list of edges (as 2- or 3-tuples) 
113   
114  ebunch: 
115     a bunch of edges (as 2- or 3-tuples). 
116     An ebunch is any iterable (non-string) container 
117     of edge-tuples (either 2-tuples, 3-tuples or a mixture). 
118   
119  Warning: 
120    - The ordering of objects within an arbitrary nbunch/ebunch can be 
121      machine-dependent. 
122    - Algorithms should treat an arbitrary nbunch/ebunch as 
123      once-through-and-exhausted iterable containers. 
124    - len(nbunch) and len(ebunch) need not be defined. 
125       
126   
127  Methods 
128  ======= 
129   
130  Each class provides basic graph methods. 
131   
132  Mutating Graph methods 
133  ---------------------- 
134      
135      - G.add_node(n), G.add_nodes_from(nlist) 
136      - G.delete_node(n), G.delete_nodes_from(nlist) 
137      - G.add_edge(n1,n2), G.add_edge(e), where e=(u,v) 
138      - G.add_edges_from(ebunch) 
139      - G.delete_edge(n1,n2), G.delete_edge(e), where e=(u,v) 
140      - G.delete_edges_from(ebunch) 
141      - G.add_path(nlist) 
142      - G.add_cycle(nlist) 
143      - G.clear() 
144      - G.subgraph(nbunch,inplace=True) 
145   
146  Non-mutating Graph methods 
147  -------------------------- 
148   
149      - len(G) 
150      - G.has_node(n) 
151      - n in G (equivalent to G.has_node(n)) 
152      - for n in G: (iterate through the nodes of G) 
153      - G.nodes() 
154      - G.nodes_iter() 
155      - G.has_edge(n1,n2), G.has_neighbor(n1,n2), G.get_edge(n1,n2) 
156      - G.edges(), G.edges(n), G.edges(nbunch)       
157      - G.edges_iter(), G.edges_iter(n), G.edges_iter(nbunch) 
158      - G.neighbors(n) 
159      - G[n]  (equivalent to G.neighbors(n)) 
160      - G.neighbors_iter(n) # iterator over neighbors 
161      - G.number_of_nodes(), G.order() 
162      - G.number_of_edges(), G.size() 
163      - G.edge_boundary(nbunch1), G.node_boundary(nbunch1) 
164      - G.degree(n), G.degree(nbunch) 
165      - G.degree_iter(n), G.degree_iter(nbunch) 
166      - G.is_directed() 
167      - G.info()  # print variaous info about a graph 
168      - G.prepare_nbunch(nbunch)  # return list of nodes in G and nbunch 
169   
170  Methods returning a new graph 
171  ----------------------------- 
172   
173      - G.subgraph(nbunch) 
174      - G.subgraph(nbunch,create_using=H) 
175      - G.copy() 
176      - G.to_undirected() 
177      - G.to_directed() 
178       
179   
180   
181   
182  Implementation Notes 
183  ==================== 
184   
185  The graph classes implement graphs using data structures 
186  based on an adjacency list implemented as a node-centric dictionary of 
187  dictionaries. The dictionary contains keys corresponding to the nodes 
188  and the values are dictionaries of neighboring node keys with the 
189  value None (the Python None type) for Graph and DiGraph or 
190  user specified (default is None) for XGraph and XDiGraph. 
191  The dictionary of dictionary structure  allows fast addition, 
192  deletion and lookup of nodes and neighbors in large graphs.   
193   
194  Similarities between XGraph and Graph 
195  ------------------------------------- 
196   
197  XGraph and Graph differ in the way edge data is handled. 
198  XGraph edges are 3-tuples (n1,n2,x) and Graph edges are 2-tuples (n1,n2). 
199  XGraph inherits from the Graph class, and XDiGraph from the DiGraph class. 
200   
201  Graph and XGraph are similar in the following ways: 
202   
203  1. Edgeless graphs are the same in XGraph and Graph. 
204     For an edgeless graph, represented by G (member of the Graph class) 
205     and XG (member of XGraph class), there is no difference between 
206     the datastructures G.adj and XG.adj, other than possibly 
207     in the ordering of the keys in the adj dict. 
208   
209   
210  2. Basic graph construction code for G=Graph() will also work for 
211     G=XGraph().  In the Graph class, the simplest graph construction 
212     consists of a graph creation command G=Graph() followed by a list 
213     of graph construction commands, consisting of successive calls to 
214     the methods: 
215   
216     G.add_node, G.add_nodes_from, G.add_edge, G.add_edges, G.add_path, 
217     G.add_cycle G.delete_node, G.delete_nodes_from, G.delete_edge, 
218     G.delete_edges_from 
219   
220     with all edges specified as 2-tuples,   
221   
222     If one replaces the graph creation command with G=XGraph(), and then 
223     apply the identical list of construction commands, the resulting XGraph 
224     object will be a simple graph G with identical datastructure G.adj.  
225     This property ensures reuse of code developed for graph generation  
226     in the Graph class. 
227   
228   
229  """ 
230