Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / doc / tutorial.rst @ 5cef0f13

History | View | Annotate | Download (16.7 KB)

1 5cef0f13 tiamilani
..  -*- coding: utf-8 -*-
2
3
Tutorial
4
========
5
6
.. currentmodule:: networkx
7
8
This guide can help you start working with NetworkX.
9
10
Creating a graph
11
----------------
12
13
Create an empty graph with no nodes and no edges.
14
15
.. nbplot::
16
17
    >>> import networkx as nx
18
    >>> G = nx.Graph()
19
20
By definition, a :class:`Graph` is a collection of nodes (vertices) along with
21
identified pairs of nodes (called edges, links, etc).  In NetworkX, nodes can
22
be any hashable object e.g., a text string, an image, an XML object, another
23
Graph, a customized node object, etc.
24
25
.. note:: Python's ``None`` object should not be used as a node as it determines
26
   whether optional function arguments have been assigned in many functions.
27
28
Nodes
29
-----
30
31
The graph ``G`` can be grown in several ways.  NetworkX includes many graph
32
generator functions and facilities to read and write graphs in many formats.
33
To get started though we'll look at simple manipulations.  You can add one node
34
at a time,
35
36
.. nbplot::
37
38
    >>> G.add_node(1)
39
40
add a list of nodes,
41
42
.. nbplot::
43
44
    >>> G.add_nodes_from([2, 3])
45
46
or add any iterable container of nodes. You can also add nodes along with node
47
attributes if your container yields 2-tuples (node, node_attribute_dict).
48
Node attributes are discussed further below.
49
50
.. nbplot::
51
52
    >>> H = nx.path_graph(10)
53
    >>> G.add_nodes_from(H)
54
55
Note that ``G`` now contains the nodes of ``H`` as nodes of ``G``.
56
In contrast, you could use the graph ``H`` as a node in ``G``.
57
58
.. nbplot::
59
60
    >>> G.add_node(H)
61
62
The graph ``G`` now contains ``H`` as a node.  This flexibility is very powerful as
63
it allows graphs of graphs, graphs of files, graphs of functions and much more.
64
It is worth thinking about how to structure your application so that the nodes
65
are useful entities.  Of course you can always use a unique identifier in ``G``
66
and have a separate dictionary keyed by identifier to the node information if
67
you prefer.
68
69
.. note:: You should not change the node object if the hash depends
70
   on its contents.
71
72
Edges
73
-----
74
75
``G`` can also be grown by adding one edge at a time,
76
77
.. nbplot::
78
79
    >>> G.add_edge(1, 2)
80
    >>> e = (2, 3)
81
    >>> G.add_edge(*e)  # unpack edge tuple*
82
83
by adding a list of edges,
84
85
.. nbplot::
86
87
    >>> G.add_edges_from([(1, 2), (1, 3)])
88
89
or by adding any :term:`ebunch` of edges.  An *ebunch* is any iterable
90
container of edge-tuples.  An edge-tuple can be a 2-tuple of nodes or a 3-tuple
91
with 2 nodes followed by an edge attribute dictionary, e.g.,
92
``(2, 3, {'weight': 3.1415})``.  Edge attributes are discussed further below
93
94
.. nbplot::
95
96
    >>> G.add_edges_from(H.edges)
97
98
There are no complaints when adding existing nodes or edges. For example,
99
after removing all nodes and edges,
100
101
.. nbplot::
102
103
    >>> G.clear()
104
105
we add new nodes/edges and NetworkX quietly ignores any that are
106
already present.
107
108
.. nbplot::
109
110
    >>> G.add_edges_from([(1, 2), (1, 3)])
111
    >>> G.add_node(1)
112
    >>> G.add_edge(1, 2)
113
    >>> G.add_node("spam")        # adds node "spam"
114
    >>> G.add_nodes_from("spam")  # adds 4 nodes: 's', 'p', 'a', 'm'
115
    >>> G.add_edge(3, 'm')
116
117
At this stage the graph ``G`` consists of 8 nodes and 3 edges, as can be seen by:
118
119
.. nbplot::
120
121
    >>> G.number_of_nodes()
122
    8
123
    >>> G.number_of_edges()
124
    3
125
126
We can examine the nodes and edges. Four basic graph properties facilitate
127
reporting: ``G.nodes``, ``G.edges``, ``G.adj`` and ``G.degree``.  These
128
are set-like views of the nodes, edges, neighbors (adjacencies), and degrees
129
of nodes in a graph. They offer a continually updated read-only view into
130
the graph structure. They are also dict-like in that you can look up node
131
and edge data attributes via the views and iterate with data attributes
132
using methods ``.items()``, ``.data('span')``.
133
If you want a specific container type instead of a view, you can specify one.
134
Here we use lists, though sets, dicts, tuples and other containers may be
135
better in other contexts.
136
137
.. nbplot::
138
139
    >>> list(G.nodes)
140
    [1, 2, 3, 'spam', 's', 'p', 'a', 'm']
141
    >>> list(G.edges)
142
    [(1, 2), (1, 3), (3, 'm')]
143
    >>> list(G.adj[1])  # or list(G.neighbors(1))
144
    [2, 3]
145
    >>> G.degree[1]  # the number of edges incident to 1
146
    2
147
148
One can specify to report the edges and degree from a subset of all nodes
149
using an *nbunch*. An *nbunch* is any of: None (meaning all nodes), a node,
150
or an iterable container of nodes that is not itself a node in the graph.
151
152
.. nbplot::
153
154
    >>> G.edges([2, 'm'])
155
    EdgeDataView([(2, 1), ('m', 3)])
156
    >>> G.degree([2, 3])
157
    DegreeView({2: 1, 3: 2})
158
159
One can remove nodes and edges from the graph in a similar fashion to adding.
160
Use methods
161
:meth:`Graph.remove_node`,
162
:meth:`Graph.remove_nodes_from`,
163
:meth:`Graph.remove_edge`
164
and
165
:meth:`Graph.remove_edges_from`, e.g.
166
167
.. nbplot::
168
169
    >>> G.remove_node(2)
170
    >>> G.remove_nodes_from("spam")
171
    >>> list(G.nodes)
172
    [1, 3, 'spam']
173
    >>> G.remove_edge(1, 3)
174
175
When creating a graph structure by instantiating one of the graph
176
classes you can specify data in several formats.
177
178
.. nbplot::
179
180
    >>> G.add_edge(1, 2)
181
    >>> H = nx.DiGraph(G)   # create a DiGraph using the connections from G
182
    >>> list(H.edges())
183
    [(1, 2), (2, 1)]
184
    >>> edgelist = [(0, 1), (1, 2), (2, 3)]
185
    >>> H = nx.Graph(edgelist)
186
187
What to use as nodes and edges
188
------------------------------
189
190
You might notice that nodes and edges are not specified as NetworkX
191
objects.  This leaves you free to use meaningful items as nodes and
192
edges. The most common choices are numbers or strings, but a node can
193
be any hashable object (except ``None``), and an edge can be associated
194
with any object ``x`` using ``G.add_edge(n1, n2, object=x)``.
195
196
As an example, ``n1`` and ``n2`` could be protein objects from the RCSB Protein
197
Data Bank, and ``x`` could refer to an XML record of publications detailing
198
experimental observations of their interaction.
199
200
We have found this power quite useful, but its abuse
201
can lead to unexpected surprises unless one is familiar with Python.
202
If in doubt, consider using :func:`~relabel.convert_node_labels_to_integers` to obtain
203
a more traditional graph with integer labels.
204
205
Accessing edges and neighbors
206
-----------------------------
207
208
In addition to the views :meth:`Graph.edges`, and :meth:`Graph.adj`,
209
access to edges and neighbors is possible using subscript notation.
210
211
.. nbplot::
212
213
    >>> G[1]  # same as G.adj[1]
214
    AtlasView({2: {}})
215
    >>> G[1][2]
216
    {}
217
    >>> G.edges[1, 2]
218
    {}
219
220
You can get/set the attributes of an edge using subscript notation
221
if the edge already exists.
222
223
.. nbplot::
224
225
    >>> G.add_edge(1, 3)
226
    >>> G[1][3]['color'] = "blue"
227
    >>> G.edges[1, 2]['color'] = "red"
228
229
Fast examination of all (node, adjacency) pairs is achieved using
230
``G.adjacency()``, or ``G.adj.items()``.
231
Note that for undirected graphs, adjacency iteration sees each edge twice.
232
233
.. nbplot::
234
235
    >>> FG = nx.Graph()
236
    >>> FG.add_weighted_edges_from([(1, 2, 0.125), (1, 3, 0.75), (2, 4, 1.2), (3, 4, 0.375)])
237
    >>> for n, nbrs in FG.adj.items():
238
    ...    for nbr, eattr in nbrs.items():
239
    ...        wt = eattr['weight']
240
    ...        if wt < 0.5: print('(%d, %d, %.3f)' % (n, nbr, wt))
241
    (1, 2, 0.125)
242
    (2, 1, 0.125)
243
    (3, 4, 0.375)
244
    (4, 3, 0.375)
245
246
Convenient access to all edges is achieved with the edges property.
247
248
.. nbplot::
249
250
    >>> for (u, v, wt) in FG.edges.data('weight'):
251
    ...     if wt < 0.5: print('(%d, %d, %.3f)' % (u, v, wt))
252
    (1, 2, 0.125)
253
    (3, 4, 0.375)
254
255
Adding attributes to graphs, nodes, and edges
256
---------------------------------------------
257
258
Attributes such as weights, labels, colors, or whatever Python object you like,
259
can be attached to graphs, nodes, or edges.
260
261
Each graph, node, and edge can hold key/value attribute pairs in an associated
262
attribute dictionary (the keys must be hashable).  By default these are empty,
263
but attributes can be added or changed using ``add_edge``, ``add_node`` or direct
264
manipulation of the attribute dictionaries named ``G.graph``, ``G.nodes``, and
265
``G.edges`` for a graph ``G``.
266
267
Graph attributes
268
~~~~~~~~~~~~~~~~
269
270
Assign graph attributes when creating a new graph
271
272
.. nbplot::
273
274
    >>> G = nx.Graph(day="Friday")
275
    >>> G.graph
276
    {'day': 'Friday'}
277
278
Or you can modify attributes later
279
280
.. nbplot::
281
282
    >>> G.graph['day'] = "Monday"
283
    >>> G.graph
284
    {'day': 'Monday'}
285
286
Node attributes
287
~~~~~~~~~~~~~~~
288
289
Add node attributes using ``add_node()``, ``add_nodes_from()``, or ``G.nodes``
290
291
.. nbplot::
292
293
    >>> G.add_node(1, time='5pm')
294
    >>> G.add_nodes_from([3], time='2pm')
295
    >>> G.nodes[1]
296
    {'time': '5pm'}
297
    >>> G.nodes[1]['room'] = 714
298
    >>> G.nodes.data()
299
    NodeDataView({1: {'time': '5pm', 'room': 714}, 3: {'time': '2pm'}})
300
301
Note that adding a node to ``G.nodes`` does not add it to the graph, use
302
``G.add_node()`` to add new nodes. Similarly for edges.
303
304
Edge Attributes
305
~~~~~~~~~~~~~~~
306
307
Add/change edge attributes using ``add_edge()``, ``add_edges_from()``,
308
or subscript notation.
309
310
.. nbplot::
311
312
    >>> G.add_edge(1, 2, weight=4.7 )
313
    >>> G.add_edges_from([(3, 4), (4, 5)], color='red')
314
    >>> G.add_edges_from([(1, 2, {'color': 'blue'}), (2, 3, {'weight': 8})])
315
    >>> G[1][2]['weight'] = 4.7
316
    >>> G.edges[3, 4]['weight'] = 4.2
317
318
The special attribute ``weight`` should be numeric as it is used by
319
algorithms requiring weighted edges.
320
321
Directed graphs
322
---------------
323
324
The :class:`DiGraph` class provides additional properties specific to
325
directed edges, e.g.,
326
:meth:`DiGraph.out_edges`, :meth:`DiGraph.in_degree`,
327
:meth:`DiGraph.predecessors`, :meth:`DiGraph.successors` etc.
328
To allow algorithms to work with both classes easily, the directed versions of
329
``neighbors()`` is equivalent to ``successors()`` while ``degree`` reports
330
the sum of ``in_degree`` and ``out_degree`` even though that may feel
331
inconsistent at times.
332
333
.. nbplot::
334
335
    >>> DG = nx.DiGraph()
336
    >>> DG.add_weighted_edges_from([(1, 2, 0.5), (3, 1, 0.75)])
337
    >>> DG.out_degree(1, weight='weight')
338
    0.5
339
    >>> DG.degree(1, weight='weight')
340
    1.25
341
    >>> list(DG.successors(1))
342
    [2]
343
    >>> list(DG.neighbors(1))
344
    [2]
345
346
Some algorithms work only for directed graphs and others are not well
347
defined for directed graphs.  Indeed the tendency to lump directed
348
and undirected graphs together is dangerous.  If you want to treat
349
a directed graph as undirected for some measurement you should probably
350
convert it using :meth:`Graph.to_undirected` or with
351
352
.. nbplot::
353
354
    >>> H = nx.Graph(G)  # convert G to undirected graph
355
356
Multigraphs
357
-----------
358
359
NetworkX provides classes for graphs which allow multiple edges
360
between any pair of nodes.  The :class:`MultiGraph` and
361
:class:`MultiDiGraph`
362
classes allow you to add the same edge twice, possibly with different
363
edge data.  This can be powerful for some applications, but many
364
algorithms are not well defined on such graphs.
365
Where results are well defined,
366
e.g., :meth:`MultiGraph.degree` we provide the function.  Otherwise you
367
should convert to a standard graph in a way that makes the measurement
368
well defined.
369
370
.. nbplot::
371
372
    >>> MG = nx.MultiGraph()
373
    >>> MG.add_weighted_edges_from([(1, 2, 0.5), (1, 2, 0.75), (2, 3, 0.5)])
374
    >>> dict(MG.degree(weight='weight'))
375
    {1: 1.25, 2: 1.75, 3: 0.5}
376
    >>> GG = nx.Graph()
377
    >>> for n, nbrs in MG.adjacency():
378
    ...    for nbr, edict in nbrs.items():
379
    ...        minvalue = min([d['weight'] for d in edict.values()])
380
    ...        GG.add_edge(n, nbr, weight = minvalue)
381
    ...
382
    >>> nx.shortest_path(GG, 1, 3)
383
    [1, 2, 3]
384
385
Graph generators and graph operations
386
-------------------------------------
387
388
In addition to constructing graphs node-by-node or edge-by-edge, they
389
can also be generated by
390
391
1. Applying classic graph operations, such as::
392
393
    subgraph(G, nbunch)      - induced subgraph view of G on nodes in nbunch
394
    union(G1,G2)             - graph union
395
    disjoint_union(G1,G2)    - graph union assuming all nodes are different
396
    cartesian_product(G1,G2) - return Cartesian product graph
397
    compose(G1,G2)           - combine graphs identifying nodes common to both
398
    complement(G)            - graph complement
399
    create_empty_copy(G)     - return an empty copy of the same graph class
400
    to_undirected(G) - return an undirected representation of G
401
    to_directed(G)   - return a directed representation of G
402
403
2. Using a call to one of the classic small graphs, e.g.,
404
405
.. nbplot::
406
407
    >>> petersen = nx.petersen_graph()
408
    >>> tutte = nx.tutte_graph()
409
    >>> maze = nx.sedgewick_maze_graph()
410
    >>> tet = nx.tetrahedral_graph()
411
412
3. Using a (constructive) generator for a classic graph, e.g.,
413
414
.. nbplot::
415
416
    >>> K_5 = nx.complete_graph(5)
417
    >>> K_3_5 = nx.complete_bipartite_graph(3, 5)
418
    >>> barbell = nx.barbell_graph(10, 10)
419
    >>> lollipop = nx.lollipop_graph(10, 20)
420
421
4. Using a stochastic graph generator, e.g.,
422
423
.. nbplot::
424
425
    >>> er = nx.erdos_renyi_graph(100, 0.15)
426
    >>> ws = nx.watts_strogatz_graph(30, 3, 0.1)
427
    >>> ba = nx.barabasi_albert_graph(100, 5)
428
    >>> red = nx.random_lobster(100, 0.9, 0.9)
429
430
5. Reading a graph stored in a file using common graph formats,
431
   such as edge lists, adjacency lists, GML, GraphML, pickle, LEDA and others.
432
433
.. nbplot::
434
435
    >>> nx.write_gml(red, "path.to.file")
436
    >>> mygraph = nx.read_gml("path.to.file")
437
438
For details on graph formats see :doc:`/reference/readwrite/index`
439
and for graph generator functions see :doc:`/reference/generators`
440
441
Analyzing graphs
442
----------------
443
444
The structure of ``G`` can be analyzed using various graph-theoretic
445
functions such as:
446
447
.. nbplot::
448
449
    >>> G = nx.Graph()
450
    >>> G.add_edges_from([(1, 2), (1, 3)])
451
    >>> G.add_node("spam")       # adds node "spam"
452
    >>> list(nx.connected_components(G))
453
    [{1, 2, 3}, {'spam'}]
454
    >>> sorted(d for n, d in G.degree())
455
    [0, 1, 1, 2]
456
    >>> nx.clustering(G)
457
    {1: 0, 2: 0, 3: 0, 'spam': 0}
458
459
Some functions with large output iterate over (node, value) 2-tuples.
460
These are easily stored in a `dict` structure if you desire.
461
462
.. nbplot::
463
464
    >>> sp = dict(nx.all_pairs_shortest_path(G))
465
    >>> sp[3]
466
    {3: [3], 1: [3, 1], 2: [3, 1, 2]}
467
468
See :doc:`/reference/algorithms/index` for details on graph algorithms
469
supported.
470
471
Drawing graphs
472
--------------
473
474
NetworkX is not primarily a graph drawing package but basic drawing with
475
Matplotlib as well as an interface to use the open source Graphviz software
476
package are included.  These are part of the ``networkx.drawing`` module and will
477
be imported if possible.
478
479
First import Matplotlib's plot interface (pylab works too)
480
481
.. nbplot::
482
483
    >>> import matplotlib.pyplot as plt
484
485
You may find it useful to interactively test code using ``ipython -pylab``,
486
which combines the power of ipython and matplotlib and provides a convenient
487
interactive mode.
488
489
To test if the import of ``networkx.drawing`` was successful draw ``G`` using one of
490
491
.. nbplot::
492
493
    >>> G = nx.petersen_graph()
494
    >>> plt.subplot(121)
495
    <matplotlib.axes._subplots.AxesSubplot object at ...>
496
    >>> nx.draw(G, with_labels=True, font_weight='bold')
497
    >>> plt.subplot(122)
498
    <matplotlib.axes._subplots.AxesSubplot object at ...>
499
    >>> nx.draw_shell(G, nlist=[range(5, 10), range(5)], with_labels=True, font_weight='bold')
500
501
when drawing to an interactive display.  Note that you may need to issue a
502
Matplotlib
503
504
>>> plt.show()
505
506
command if you are not using matplotlib in interactive mode (see
507
`Matplotlib FAQ <http://matplotlib.org/faq/installing_faq.html#matplotlib-compiled-fine-but-nothing-shows-up-when-i-use-it>`_
508
).
509
510
.. nbplot::
511
512
    >>> options = {
513
    ...     'node_color': 'black',
514
    ...     'node_size': 100,
515
    ...     'width': 3,
516
    ... }
517
    >>> plt.subplot(221)
518
    <matplotlib.axes._subplots.AxesSubplot object at ...>
519
    >>> nx.draw_random(G, **options)
520
    >>> plt.subplot(222)
521
    <matplotlib.axes._subplots.AxesSubplot object at ...>
522
    >>> nx.draw_circular(G, **options)
523
    >>> plt.subplot(223)
524
    <matplotlib.axes._subplots.AxesSubplot object at ...>
525
    >>> nx.draw_spectral(G, **options)
526
    >>> plt.subplot(224)
527
    <matplotlib.axes._subplots.AxesSubplot object at ...>
528
    >>> nx.draw_shell(G, nlist=[range(5,10), range(5)], **options)
529
530
You can find additional options via :func:`~drawing.nx_pylab.draw_networkx` and
531
layouts via :mod:`layout <networkx.drawing.layout>`.
532
You can use multiple shells with :func:`~drawing.nx_pylab.draw_shell`.
533
534
.. nbplot::
535
536
    >>> G = nx.dodecahedral_graph()
537
    >>> shells = [[2, 3, 4, 5, 6], [8, 1, 0, 19, 18, 17, 16, 15, 14, 7], [9, 10, 11, 12, 13]]
538
    >>> nx.draw_shell(G, nlist=shells, **options)
539
540
To save drawings to a file, use, for example
541
542
>>> nx.draw(G)
543
>>> plt.savefig("path.png")
544
545
writes to the file ``path.png`` in the local directory. If Graphviz and
546
PyGraphviz or pydot, are available on your system, you can also use
547
``nx_agraph.graphviz_layout(G)`` or ``nx_pydot.graphviz_layout(G)`` to get the
548
node positions, or write the graph in dot format for further processing.
549
550
>>> from networkx.drawing.nx_pydot import write_dot
551
>>> pos = nx.nx_agraph.graphviz_layout(G)
552
>>> nx.draw(G, pos=pos)
553
>>> write_dot(G, 'file.dot')
554
555
See :doc:`/reference/drawing` for additional details.
556
557
.. code-links::