Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (16.7 KB)

1
..  -*- 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::