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