Mercurial > repos > shellac > guppy_basecaller

comparison env/lib/python3.7/site-packages/networkx/classes/function.py @ 5:9b1c78e6ba9c draft default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
"planemo upload commit 6c0a8142489327ece472c84e558c47da711a9142"
author shellac
date Mon, 01 Jun 2020 08:59:25 -0400
parents 79f47841a781
children
comparison
equal deleted inserted replaced
4:79f47841a781 5:9b1c78e6ba9c
1 # Copyright (C) 2004-2019 by
2 # Aric Hagberg <hagberg@lanl.gov>
3 # Dan Schult <dschult@colgate.edu>
4 # Pieter Swart <swart@lanl.gov>
5 # All rights reserved.
6 # BSD license.
7 #
8 # Authors: Aric Hagberg <hagberg@lanl.gov>
9 # Pieter Swart <swart@lanl.gov>
10 # Dan Schult <dschult@colgate.edu>
11 """Functional interface to graph methods and assorted utilities.
12 """
13
14 from collections import Counter
15 from itertools import chain
16 try:
17 from itertools import zip_longest
18 except ImportError:
19 from itertools import izip_longest as zip_longest
20
21 import networkx as nx
22 from networkx.utils import pairwise, not_implemented_for
23
24 from networkx.classes.graphviews import subgraph_view, reverse_view
25
26 __all__ = ['nodes', 'edges', 'degree', 'degree_histogram', 'neighbors',
27 'number_of_nodes', 'number_of_edges', 'density',
28 'is_directed', 'info', 'freeze', 'is_frozen',
29 'subgraph', 'subgraph_view', 'induced_subgraph', 'reverse_view',
30 'edge_subgraph', 'restricted_view',
31 'to_directed', 'to_undirected',
32 'add_star', 'add_path', 'add_cycle',
33 'create_empty_copy', 'set_node_attributes',
34 'get_node_attributes', 'set_edge_attributes',
35 'get_edge_attributes', 'all_neighbors', 'non_neighbors',
36 'non_edges', 'common_neighbors', 'is_weighted',
37 'is_negatively_weighted', 'is_empty',
38 'selfloop_edges', 'nodes_with_selfloops', 'number_of_selfloops',
39 ]
40
41
42 def nodes(G):
43 """Returns an iterator over the graph nodes."""
44 return G.nodes()
45
46
47 def edges(G, nbunch=None):
48 """Returns an edge view of edges incident to nodes in nbunch.
49
50 Return all edges if nbunch is unspecified or nbunch=None.
51
52 For digraphs, edges=out_edges
53 """
54 return G.edges(nbunch)
55
56
57 def degree(G, nbunch=None, weight=None):
58 """Returns a degree view of single node or of nbunch of nodes.
59 If nbunch is omitted, then return degrees of *all* nodes.
60 """
61 return G.degree(nbunch, weight)
62
63
64 def neighbors(G, n):
65 """Returns a list of nodes connected to node n. """
66 return G.neighbors(n)
67
68
69 def number_of_nodes(G):
70 """Returns the number of nodes in the graph."""
71 return G.number_of_nodes()
72
73
74 def number_of_edges(G):
75 """Returns the number of edges in the graph. """
76 return G.number_of_edges()
77
78
79 def density(G):
80 r"""Returns the density of a graph.
81
82 The density for undirected graphs is
83
84 .. math::
85
86 d = \frac{2m}{n(n-1)},
87
88 and for directed graphs is
89
90 .. math::
91
92 d = \frac{m}{n(n-1)},
93
94 where `n` is the number of nodes and `m` is the number of edges in `G`.
95
96 Notes
97 -----
98 The density is 0 for a graph without edges and 1 for a complete graph.
99 The density of multigraphs can be higher than 1.
100
101 Self loops are counted in the total number of edges so graphs with self
102 loops can have density higher than 1.
103 """
104 n = number_of_nodes(G)
105 m = number_of_edges(G)
106 if m == 0 or n <= 1:
107 return 0
108 d = m / (n * (n - 1))
109 if not G.is_directed():
110 d *= 2
111 return d
112
113
114 def degree_histogram(G):
115 """Returns a list of the frequency of each degree value.
116
117 Parameters
118 ----------
119 G : Networkx graph
120 A graph
121
122 Returns
123 -------
124 hist : list
125 A list of frequencies of degrees.
126 The degree values are the index in the list.
127
128 Notes
129 -----
130 Note: the bins are width one, hence len(list) can be large
131 (Order(number_of_edges))
132 """
133 counts = Counter(d for n, d in G.degree())
134 return [counts.get(i, 0) for i in range(max(counts) + 1)]
135
136
137 def is_directed(G):
138 """ Return True if graph is directed."""
139 return G.is_directed()
140
141
142 def frozen(*args, **kwargs):
143 """Dummy method for raising errors when trying to modify frozen graphs"""
144 raise nx.NetworkXError("Frozen graph can't be modified")
145
146
147 def freeze(G):
148 """Modify graph to prevent further change by adding or removing
149 nodes or edges.
150
151 Node and edge data can still be modified.
152
153 Parameters
154 ----------
155 G : graph
156 A NetworkX graph
157
158 Examples
159 --------
160 >>> G = nx.path_graph(4)
161 >>> G = nx.freeze(G)
162 >>> try:
163 ... G.add_edge(4, 5)
164 ... except nx.NetworkXError as e:
165 ... print(str(e))
166 Frozen graph can't be modified
167
168 Notes
169 -----
170 To "unfreeze" a graph you must make a copy by creating a new graph object:
171
172 >>> graph = nx.path_graph(4)
173 >>> frozen_graph = nx.freeze(graph)
174 >>> unfrozen_graph = nx.Graph(frozen_graph)
175 >>> nx.is_frozen(unfrozen_graph)
176 False
177
178 See Also
179 --------
180 is_frozen
181 """
182 G.add_node = frozen
183 G.add_nodes_from = frozen
184 G.remove_node = frozen
185 G.remove_nodes_from = frozen
186 G.add_edge = frozen
187 G.add_edges_from = frozen
188 G.add_weighted_edges_from = frozen
189 G.remove_edge = frozen
190 G.remove_edges_from = frozen
191 G.clear = frozen
192 G.frozen = True
193 return G
194
195
196 def is_frozen(G):
197 """Returns True if graph is frozen.
198
199 Parameters
200 ----------
201 G : graph
202 A NetworkX graph
203
204 See Also
205 --------
206 freeze
207 """
208 try:
209 return G.frozen
210 except AttributeError:
211 return False
212
213
214 def add_star(G_to_add_to, nodes_for_star, **attr):
215 """Add a star to Graph G_to_add_to.
216
217 The first node in `nodes_for_star` is the middle of the star.
218 It is connected to all other nodes.
219
220 Parameters
221 ----------
222 G_to_add_to : graph
223 A NetworkX graph
224 nodes_for_star : iterable container
225 A container of nodes.
226 attr : keyword arguments, optional (default= no attributes)
227 Attributes to add to every edge in star.
228
229 See Also
230 --------
231 add_path, add_cycle
232
233 Examples
234 --------
235 >>> G = nx.Graph()
236 >>> nx.add_star(G, [0, 1, 2, 3])
237 >>> nx.add_star(G, [10, 11, 12], weight=2)
238 """
239 nlist = iter(nodes_for_star)
240 try:
241 v = next(nlist)
242 except StopIteration:
243 return
244 G_to_add_to.add_node(v)
245 edges = ((v, n) for n in nlist)
246 G_to_add_to.add_edges_from(edges, **attr)
247
248
249 def add_path(G_to_add_to, nodes_for_path, **attr):
250 """Add a path to the Graph G_to_add_to.
251
252 Parameters
253 ----------
254 G_to_add_to : graph
255 A NetworkX graph
256 nodes_for_path : iterable container
257 A container of nodes. A path will be constructed from
258 the nodes (in order) and added to the graph.
259 attr : keyword arguments, optional (default= no attributes)
260 Attributes to add to every edge in path.
261
262 See Also
263 --------
264 add_star, add_cycle
265
266 Examples
267 --------
268 >>> G = nx.Graph()
269 >>> nx.add_path(G, [0, 1, 2, 3])
270 >>> nx.add_path(G, [10, 11, 12], weight=7)
271 """
272 nlist = iter(nodes_for_path)
273 try:
274 first_node = next(nlist)
275 except StopIteration:
276 return
277 G_to_add_to.add_node(first_node)
278 G_to_add_to.add_edges_from(pairwise(chain((first_node,), nlist)), **attr)
279
280
281 def add_cycle(G_to_add_to, nodes_for_cycle, **attr):
282 """Add a cycle to the Graph G_to_add_to.
283
284 Parameters
285 ----------
286 G_to_add_to : graph
287 A NetworkX graph
288 nodes_for_cycle: iterable container
289 A container of nodes. A cycle will be constructed from
290 the nodes (in order) and added to the graph.
291 attr : keyword arguments, optional (default= no attributes)
292 Attributes to add to every edge in cycle.
293
294 See Also
295 --------
296 add_path, add_star
297
298 Examples
299 --------
300 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc
301 >>> nx.add_cycle(G, [0, 1, 2, 3])
302 >>> nx.add_cycle(G, [10, 11, 12], weight=7)
303 """
304 nlist = iter(nodes_for_cycle)
305 try:
306 first_node = next(nlist)
307 except StopIteration:
308 return
309 G_to_add_to.add_node(first_node)
310 G_to_add_to.add_edges_from(pairwise(chain((first_node,), nlist), cyclic=True), **attr)
311
312
313 def subgraph(G, nbunch):
314 """Returns the subgraph induced on nodes in nbunch.
315
316 Parameters
317 ----------
318 G : graph
319 A NetworkX graph
320
321 nbunch : list, iterable
322 A container of nodes that will be iterated through once (thus
323 it should be an iterator or be iterable). Each element of the
324 container should be a valid node type: any hashable type except
325 None. If nbunch is None, return all edges data in the graph.
326 Nodes in nbunch that are not in the graph will be (quietly)
327 ignored.
328
329 Notes
330 -----
331 subgraph(G) calls G.subgraph()
332 """
333 return G.subgraph(nbunch)
334
335
336 def induced_subgraph(G, nbunch):
337 """Returns a SubGraph view of `G` showing only nodes in nbunch.
338
339 The induced subgraph of a graph on a set of nodes N is the
340 graph with nodes N and edges from G which have both ends in N.
341
342 Parameters
343 ----------
344 G : NetworkX Graph
345 nbunch : node, container of nodes or None (for all nodes)
346
347 Returns
348 -------
349 subgraph : SubGraph View
350 A read-only view of the subgraph in `G` induced by the nodes.
351 Changes to the graph `G` will be reflected in the view.
352
353 Notes
354 -----
355 To create a mutable subgraph with its own copies of nodes
356 edges and attributes use `subgraph.copy()` or `Graph(subgraph)`
357
358 For an inplace reduction of a graph to a subgraph you can remove nodes:
359 `G.remove_nodes_from(n in G if n not in set(nbunch))`
360
361 If you are going to compute subgraphs of your subgraphs you could
362 end up with a chain of views that can be very slow once the chain
363 has about 15 views in it. If they are all induced subgraphs, you
364 can short-cut the chain by making them all subgraphs of the original
365 graph. The graph class method `G.subgraph` does this when `G` is
366 a subgraph. In contrast, this function allows you to choose to build
367 chains or not, as you wish. The returned subgraph is a view on `G`.
368
369 Examples
370 --------
371 >>> import networkx as nx
372 >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
373 >>> H = G.subgraph([0, 1, 2])
374 >>> list(H.edges)
375 [(0, 1), (1, 2)]
376 """
377 induced_nodes = nx.filters.show_nodes(G.nbunch_iter(nbunch))
378 return nx.graphviews.subgraph_view(G, induced_nodes)
379
380
381 def edge_subgraph(G, edges):
382 """Returns a view of the subgraph induced by the specified edges.
383
384 The induced subgraph contains each edge in `edges` and each
385 node incident to any of those edges.
386
387 Parameters
388 ----------
389 G : NetworkX Graph
390 edges : iterable
391 An iterable of edges. Edges not present in `G` are ignored.
392
393 Returns
394 -------
395 subgraph : SubGraph View
396 A read-only edge-induced subgraph of `G`.
397 Changes to `G` are reflected in the view.
398
399 Notes
400 -----
401 To create a mutable subgraph with its own copies of nodes
402 edges and attributes use `subgraph.copy()` or `Graph(subgraph)`
403
404 If you create a subgraph of a subgraph recursively you can end up
405 with a chain of subgraphs that becomes very slow with about 15
406 nested subgraph views. Luckily the edge_subgraph filter nests
407 nicely so you can use the original graph as G in this function
408 to avoid chains. We do not rule out chains programmatically so
409 that odd cases like an `edge_subgraph` of a `restricted_view`
410 can be created.
411
412 Examples
413 --------
414 >>> import networkx as nx
415 >>> G = nx.path_graph(5)
416 >>> H = G.edge_subgraph([(0, 1), (3, 4)])
417 >>> list(H.nodes)
418 [0, 1, 3, 4]
419 >>> list(H.edges)
420 [(0, 1), (3, 4)]
421 """
422 nxf = nx.filters
423 edges = set(edges)
424 nodes = set()
425 for e in edges:
426 nodes.update(e[:2])
427 induced_nodes = nxf.show_nodes(nodes)
428 if G.is_multigraph():
429 if G.is_directed():
430 induced_edges = nxf.show_multidiedges(edges)
431 else:
432 induced_edges = nxf.show_multiedges(edges)
433 else:
434 if G.is_directed():
435 induced_edges = nxf.show_diedges(edges)
436 else:
437 induced_edges = nxf.show_edges(edges)
438 return nx.graphviews.subgraph_view(G, induced_nodes, induced_edges)
439
440
441 def restricted_view(G, nodes, edges):
442 """Returns a view of `G` with hidden nodes and edges.
443
444 The resulting subgraph filters out node `nodes` and edges `edges`.
445 Filtered out nodes also filter out any of their edges.
446
447 Parameters
448 ----------
449 G : NetworkX Graph
450 nodes : iterable
451 An iterable of nodes. Nodes not present in `G` are ignored.
452 edges : iterable
453 An iterable of edges. Edges not present in `G` are ignored.
454
455 Returns
456 -------
457 subgraph : SubGraph View
458 A read-only restricted view of `G` filtering out nodes and edges.
459 Changes to `G` are reflected in the view.
460
461 Notes
462 -----
463 To create a mutable subgraph with its own copies of nodes
464 edges and attributes use `subgraph.copy()` or `Graph(subgraph)`
465
466 If you create a subgraph of a subgraph recursively you may end up
467 with a chain of subgraph views. Such chains can get quite slow
468 for lengths near 15. To avoid long chains, try to make your subgraph
469 based on the original graph. We do not rule out chains programmatically
470 so that odd cases like an `edge_subgraph` of a `restricted_view`
471 can be created.
472
473 Examples
474 --------
475 >>> import networkx as nx
476 >>> G = nx.path_graph(5)
477 >>> H = nx.restricted_view(G, [0], [(1, 2), (3, 4)])
478 >>> list(H.nodes)
479 [1, 2, 3, 4]
480 >>> list(H.edges)
481 [(2, 3)]
482 """
483 nxf = nx.filters
484 hide_nodes = nxf.hide_nodes(nodes)
485 if G.is_multigraph():
486 if G.is_directed():
487 hide_edges = nxf.hide_multidiedges(edges)
488 else:
489 hide_edges = nxf.hide_multiedges(edges)
490 else:
491 if G.is_directed():
492 hide_edges = nxf.hide_diedges(edges)
493 else:
494 hide_edges = nxf.hide_edges(edges)
495 return nx.graphviews.subgraph_view(G, hide_nodes, hide_edges)
496
497
498 def to_directed(graph):
499 """Returns a directed view of the graph `graph`.
500
501 Identical to graph.to_directed(as_view=True)
502 Note that graph.to_directed defaults to `as_view=False`
503 while this function always provides a view.
504 """
505 return graph.to_directed(as_view=True)
506
507
508 def to_undirected(graph):
509 """Returns an undirected view of the graph `graph`.
510
511 Identical to graph.to_undirected(as_view=True)
512 Note that graph.to_undirected defaults to `as_view=False`
513 while this function always provides a view.
514 """
515 return graph.to_undirected(as_view=True)
516
517
518 def create_empty_copy(G, with_data=True):
519 """Returns a copy of the graph G with all of the edges removed.
520
521 Parameters
522 ----------
523 G : graph
524 A NetworkX graph
525
526 with_data : bool (default=True)
527 Propagate Graph and Nodes data to the new graph.
528
529 See Also
530 -----
531 empty_graph
532
533 """
534 H = G.__class__()
535 H.add_nodes_from(G.nodes(data=with_data))
536 if with_data:
537 H.graph.update(G.graph)
538 return H
539
540
541 def info(G, n=None):
542 """Print short summary of information for the graph G or the node n.
543
544 Parameters
545 ----------
546 G : Networkx graph
547 A graph
548 n : node (any hashable)
549 A node in the graph G
550 """
551 info = '' # append this all to a string
552 if n is None:
553 info += "Name: %s\n" % G.name
554 type_name = [type(G).__name__]
555 info += "Type: %s\n" % ",".join(type_name)
556 info += "Number of nodes: %d\n" % G.number_of_nodes()
557 info += "Number of edges: %d\n" % G.number_of_edges()
558 nnodes = G.number_of_nodes()
559 if len(G) > 0:
560 if G.is_directed():
561 deg = sum(d for n, d in G.in_degree()) / float(nnodes)
562 info += "Average in degree: %8.4f\n" % deg
563 deg = sum(d for n, d in G.out_degree()) / float(nnodes)
564 info += "Average out degree: %8.4f" % deg
565 else:
566 s = sum(dict(G.degree()).values())
567 info += "Average degree: %8.4f" % (float(s) / float(nnodes))
568
569 else:
570 if n not in G:
571 raise nx.NetworkXError("node %s not in graph" % (n,))
572 info += "Node % s has the following properties:\n" % n
573 info += "Degree: %d\n" % G.degree(n)
574 info += "Neighbors: "
575 info += ' '.join(str(nbr) for nbr in G.neighbors(n))
576 return info
577
578
579 def set_node_attributes(G, values, name=None):
580 """Sets node attributes from a given value or dictionary of values.
581
582 .. Warning:: The call order of arguments `values` and `name`
583 switched between v1.x & v2.x.
584
585 Parameters
586 ----------
587 G : NetworkX Graph
588
589 values : scalar value, dict-like
590 What the node attribute should be set to. If `values` is
591 not a dictionary, then it is treated as a single attribute value
592 that is then applied to every node in `G`. This means that if
593 you provide a mutable object, like a list, updates to that object
594 will be reflected in the node attribute for every node.
595 The attribute name will be `name`.
596
597 If `values` is a dict or a dict of dict, it should be keyed
598 by node to either an attribute value or a dict of attribute key/value
599 pairs used to update the node's attributes.
600
601 name : string (optional, default=None)
602 Name of the node attribute to set if values is a scalar.
603
604 Examples
605 --------
606 After computing some property of the nodes of a graph, you may want
607 to assign a node attribute to store the value of that property for
608 each node::
609
610 >>> G = nx.path_graph(3)
611 >>> bb = nx.betweenness_centrality(G)
612 >>> isinstance(bb, dict)
613 True
614 >>> nx.set_node_attributes(G, bb, 'betweenness')
615 >>> G.nodes[1]['betweenness']
616 1.0
617
618 If you provide a list as the second argument, updates to the list
619 will be reflected in the node attribute for each node::
620
621 >>> G = nx.path_graph(3)
622 >>> labels = []
623 >>> nx.set_node_attributes(G, labels, 'labels')
624 >>> labels.append('foo')
625 >>> G.nodes[0]['labels']
626 ['foo']
627 >>> G.nodes[1]['labels']
628 ['foo']
629 >>> G.nodes[2]['labels']
630 ['foo']
631
632 If you provide a dictionary of dictionaries as the second argument,
633 the outer dictionary is assumed to be keyed by node to an inner
634 dictionary of node attributes for that node::
635
636 >>> G = nx.path_graph(3)
637 >>> attrs = {0: {'attr1': 20, 'attr2': 'nothing'}, 1: {'attr2': 3}}
638 >>> nx.set_node_attributes(G, attrs)
639 >>> G.nodes[0]['attr1']
640 20
641 >>> G.nodes[0]['attr2']
642 'nothing'
643 >>> G.nodes[1]['attr2']
644 3
645 >>> G.nodes[2]
646 {}
647
648 """
649 # Set node attributes based on type of `values`
650 if name is not None: # `values` must not be a dict of dict
651 try: # `values` is a dict
652 for n, v in values.items():
653 try:
654 G.nodes[n][name] = values[n]
655 except KeyError:
656 pass
657 except AttributeError: # `values` is a constant
658 for n in G:
659 G.nodes[n][name] = values
660 else: # `values` must be dict of dict
661 for n, d in values.items():
662 try:
663 G.nodes[n].update(d)
664 except KeyError:
665 pass
666
667
668 def get_node_attributes(G, name):
669 """Get node attributes from graph
670
671 Parameters
672 ----------
673 G : NetworkX Graph
674
675 name : string
676 Attribute name
677
678 Returns
679 -------
680 Dictionary of attributes keyed by node.
681
682 Examples
683 --------
684 >>> G = nx.Graph()
685 >>> G.add_nodes_from([1, 2, 3], color='red')
686 >>> color = nx.get_node_attributes(G, 'color')
687 >>> color[1]
688 'red'
689 """
690 return {n: d[name] for n, d in G.nodes.items() if name in d}
691
692
693 def set_edge_attributes(G, values, name=None):
694 """Sets edge attributes from a given value or dictionary of values.
695
696 .. Warning:: The call order of arguments `values` and `name`
697 switched between v1.x & v2.x.
698
699 Parameters
700 ----------
701 G : NetworkX Graph
702
703 values : scalar value, dict-like
704 What the edge attribute should be set to. If `values` is
705 not a dictionary, then it is treated as a single attribute value
706 that is then applied to every edge in `G`. This means that if
707 you provide a mutable object, like a list, updates to that object
708 will be reflected in the edge attribute for each edge. The attribute
709 name will be `name`.
710
711 If `values` is a dict or a dict of dict, it should be keyed
712 by edge tuple to either an attribute value or a dict of attribute
713 key/value pairs used to update the edge's attributes.
714 For multigraphs, the edge tuples must be of the form ``(u, v, key)``,
715 where `u` and `v` are nodes and `key` is the edge key.
716 For non-multigraphs, the keys must be tuples of the form ``(u, v)``.
717
718 name : string (optional, default=None)
719 Name of the edge attribute to set if values is a scalar.
720
721 Examples
722 --------
723 After computing some property of the edges of a graph, you may want
724 to assign a edge attribute to store the value of that property for
725 each edge::
726
727 >>> G = nx.path_graph(3)
728 >>> bb = nx.edge_betweenness_centrality(G, normalized=False)
729 >>> nx.set_edge_attributes(G, bb, 'betweenness')
730 >>> G.edges[1, 2]['betweenness']
731 2.0
732
733 If you provide a list as the second argument, updates to the list
734 will be reflected in the edge attribute for each edge::
735
736 >>> labels = []
737 >>> nx.set_edge_attributes(G, labels, 'labels')
738 >>> labels.append('foo')
739 >>> G.edges[0, 1]['labels']
740 ['foo']
741 >>> G.edges[1, 2]['labels']
742 ['foo']
743
744 If you provide a dictionary of dictionaries as the second argument,
745 the entire dictionary will be used to update edge attributes::
746
747 >>> G = nx.path_graph(3)
748 >>> attrs = {(0, 1): {'attr1': 20, 'attr2': 'nothing'},
749 ... (1, 2): {'attr2': 3}}
750 >>> nx.set_edge_attributes(G, attrs)
751 >>> G[0][1]['attr1']
752 20
753 >>> G[0][1]['attr2']
754 'nothing'
755 >>> G[1][2]['attr2']
756 3
757
758 """
759 if name is not None:
760 # `values` does not contain attribute names
761 try:
762 # if `values` is a dict using `.items()` => {edge: value}
763 if G.is_multigraph():
764 for (u, v, key), value in values.items():
765 try:
766 G[u][v][key][name] = value
767 except KeyError:
768 pass
769 else:
770 for (u, v), value in values.items():
771 try:
772 G[u][v][name] = value
773 except KeyError:
774 pass
775 except AttributeError:
776 # treat `values` as a constant
777 for u, v, data in G.edges(data=True):
778 data[name] = values
779 else:
780 # `values` consists of doct-of-dict {edge: {attr: value}} shape
781 if G.is_multigraph():
782 for (u, v, key), d in values.items():
783 try:
784 G[u][v][key].update(d)
785 except KeyError:
786 pass
787 else:
788 for (u, v), d in values.items():
789 try:
790 G[u][v].update(d)
791 except KeyError:
792 pass
793
794
795 def get_edge_attributes(G, name):
796 """Get edge attributes from graph
797
798 Parameters
799 ----------
800 G : NetworkX Graph
801
802 name : string
803 Attribute name
804
805 Returns
806 -------
807 Dictionary of attributes keyed by edge. For (di)graphs, the keys are
808 2-tuples of the form: (u, v). For multi(di)graphs, the keys are 3-tuples of
809 the form: (u, v, key).
810
811 Examples
812 --------
813 >>> G = nx.Graph()
814 >>> nx.add_path(G, [1, 2, 3], color='red')
815 >>> color = nx.get_edge_attributes(G, 'color')
816 >>> color[(1, 2)]
817 'red'
818 """
819 if G.is_multigraph():
820 edges = G.edges(keys=True, data=True)
821 else:
822 edges = G.edges(data=True)
823 return {x[:-1]: x[-1][name] for x in edges if name in x[-1]}
824
825
826 def all_neighbors(graph, node):
827 """Returns all of the neighbors of a node in the graph.
828
829 If the graph is directed returns predecessors as well as successors.
830
831 Parameters
832 ----------
833 graph : NetworkX graph
834 Graph to find neighbors.
835
836 node : node
837 The node whose neighbors will be returned.
838
839 Returns
840 -------
841 neighbors : iterator
842 Iterator of neighbors
843 """
844 if graph.is_directed():
845 values = chain(graph.predecessors(node), graph.successors(node))
846 else:
847 values = graph.neighbors(node)
848 return values
849
850
851 def non_neighbors(graph, node):
852 """Returns the non-neighbors of the node in the graph.
853
854 Parameters
855 ----------
856 graph : NetworkX graph
857 Graph to find neighbors.
858
859 node : node
860 The node whose neighbors will be returned.
861
862 Returns
863 -------
864 non_neighbors : iterator
865 Iterator of nodes in the graph that are not neighbors of the node.
866 """
867 nbors = set(neighbors(graph, node)) | {node}
868 return (nnode for nnode in graph if nnode not in nbors)
869
870
871 def non_edges(graph):
872 """Returns the non-existent edges in the graph.
873
874 Parameters
875 ----------
876 graph : NetworkX graph.
877 Graph to find non-existent edges.
878
879 Returns
880 -------
881 non_edges : iterator
882 Iterator of edges that are not in the graph.
883 """
884 if graph.is_directed():
885 for u in graph:
886 for v in non_neighbors(graph, u):
887 yield (u, v)
888 else:
889 nodes = set(graph)
890 while nodes:
891 u = nodes.pop()
892 for v in nodes - set(graph[u]):
893 yield (u, v)
894
895
896 @not_implemented_for('directed')
897 def common_neighbors(G, u, v):
898 """Returns the common neighbors of two nodes in a graph.
899
900 Parameters
901 ----------
902 G : graph
903 A NetworkX undirected graph.
904
905 u, v : nodes
906 Nodes in the graph.
907
908 Returns
909 -------
910 cnbors : iterator
911 Iterator of common neighbors of u and v in the graph.
912
913 Raises
914 ------
915 NetworkXError
916 If u or v is not a node in the graph.
917
918 Examples
919 --------
920 >>> G = nx.complete_graph(5)
921 >>> sorted(nx.common_neighbors(G, 0, 1))
922 [2, 3, 4]
923 """
924 if u not in G:
925 raise nx.NetworkXError('u is not in the graph.')
926 if v not in G:
927 raise nx.NetworkXError('v is not in the graph.')
928
929 # Return a generator explicitly instead of yielding so that the above
930 # checks are executed eagerly.
931 return (w for w in G[u] if w in G[v] and w not in (u, v))
932
933
934 def is_weighted(G, edge=None, weight='weight'):
935 """Returns True if `G` has weighted edges.
936
937 Parameters
938 ----------
939 G : graph
940 A NetworkX graph.
941
942 edge : tuple, optional
943 A 2-tuple specifying the only edge in `G` that will be tested. If
944 None, then every edge in `G` is tested.
945
946 weight: string, optional
947 The attribute name used to query for edge weights.
948
949 Returns
950 -------
951 bool
952 A boolean signifying if `G`, or the specified edge, is weighted.
953
954 Raises
955 ------
956 NetworkXError
957 If the specified edge does not exist.
958
959 Examples
960 --------
961 >>> G = nx.path_graph(4)
962 >>> nx.is_weighted(G)
963 False
964 >>> nx.is_weighted(G, (2, 3))
965 False
966
967 >>> G = nx.DiGraph()
968 >>> G.add_edge(1, 2, weight=1)
969 >>> nx.is_weighted(G)
970 True
971
972 """
973 if edge is not None:
974 data = G.get_edge_data(*edge)
975 if data is None:
976 msg = 'Edge {!r} does not exist.'.format(edge)
977 raise nx.NetworkXError(msg)
978 return weight in data
979
980 if is_empty(G):
981 # Special handling required since: all([]) == True
982 return False
983
984 return all(weight in data for u, v, data in G.edges(data=True))
985
986
987 def is_negatively_weighted(G, edge=None, weight='weight'):
988 """Returns True if `G` has negatively weighted edges.
989
990 Parameters
991 ----------
992 G : graph
993 A NetworkX graph.
994
995 edge : tuple, optional
996 A 2-tuple specifying the only edge in `G` that will be tested. If
997 None, then every edge in `G` is tested.
998
999 weight: string, optional
1000 The attribute name used to query for edge weights.
1001
1002 Returns
1003 -------
1004 bool
1005 A boolean signifying if `G`, or the specified edge, is negatively
1006 weighted.
1007
1008 Raises
1009 ------
1010 NetworkXError
1011 If the specified edge does not exist.
1012
1013 Examples
1014 --------
1015 >>> G = nx.Graph()
1016 >>> G.add_edges_from([(1, 3), (2, 4), (2, 6)])
1017 >>> G.add_edge(1, 2, weight=4)
1018 >>> nx.is_negatively_weighted(G, (1, 2))
1019 False
1020 >>> G[2][4]['weight'] = -2
1021 >>> nx.is_negatively_weighted(G)
1022 True
1023 >>> G = nx.DiGraph()
1024 >>> edges = [('0', '3', 3), ('0', '1', -5), ('1', '0', -2)]
1025 >>> G.add_weighted_edges_from(edges)
1026 >>> nx.is_negatively_weighted(G)
1027 True
1028
1029 """
1030 if edge is not None:
1031 data = G.get_edge_data(*edge)
1032 if data is None:
1033 msg = 'Edge {!r} does not exist.'.format(edge)
1034 raise nx.NetworkXError(msg)
1035 return weight in data and data[weight] < 0
1036
1037 return any(weight in data and data[weight] < 0
1038 for u, v, data in G.edges(data=True))
1039
1040
1041 def is_empty(G):
1042 """Returns True if `G` has no edges.
1043
1044 Parameters
1045 ----------
1046 G : graph
1047 A NetworkX graph.
1048
1049 Returns
1050 -------
1051 bool
1052 True if `G` has no edges, and False otherwise.
1053
1054 Notes
1055 -----
1056 An empty graph can have nodes but not edges. The empty graph with zero
1057 nodes is known as the null graph. This is an $O(n)$ operation where n
1058 is the number of nodes in the graph.
1059
1060 """
1061 return not any(G.adj.values())
1062
1063
1064 def nodes_with_selfloops(G):
1065 """Returns an iterator over nodes with self loops.
1066
1067 A node with a self loop has an edge with both ends adjacent
1068 to that node.
1069
1070 Returns
1071 -------
1072 nodelist : iterator
1073 A iterator over nodes with self loops.
1074
1075 See Also
1076 --------
1077 selfloop_edges, number_of_selfloops
1078
1079 Examples
1080 --------
1081 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc
1082 >>> G.add_edge(1, 1)
1083 >>> G.add_edge(1, 2)
1084 >>> list(nx.nodes_with_selfloops(G))
1085 [1]
1086
1087 """
1088 return (n for n, nbrs in G.adj.items() if n in nbrs)
1089
1090
1091 def selfloop_edges(G, data=False, keys=False, default=None):
1092 """Returns an iterator over selfloop edges.
1093
1094 A selfloop edge has the same node at both ends.
1095
1096 Parameters
1097 ----------
1098 data : string or bool, optional (default=False)
1099 Return selfloop edges as two tuples (u, v) (data=False)
1100 or three-tuples (u, v, datadict) (data=True)
1101 or three-tuples (u, v, datavalue) (data='attrname')
1102 keys : bool, optional (default=False)
1103 If True, return edge keys with each edge.
1104 default : value, optional (default=None)
1105 Value used for edges that don't have the requested attribute.
1106 Only relevant if data is not True or False.
1107
1108 Returns
1109 -------
1110 edgeiter : iterator over edge tuples
1111 An iterator over all selfloop edges.
1112
1113 See Also
1114 --------
1115 nodes_with_selfloops, number_of_selfloops
1116
1117 Examples
1118 --------
1119 >>> G = nx.MultiGraph() # or Graph, DiGraph, MultiDiGraph, etc
1120 >>> ekey = G.add_edge(1, 1)
1121 >>> ekey = G.add_edge(1, 2)
1122 >>> list(nx.selfloop_edges(G))
1123 [(1, 1)]
1124 >>> list(nx.selfloop_edges(G, data=True))
1125 [(1, 1, {})]
1126 >>> list(nx.selfloop_edges(G, keys=True))
1127 [(1, 1, 0)]
1128 >>> list(nx.selfloop_edges(G, keys=True, data=True))
1129 [(1, 1, 0, {})]
1130 """
1131 if data is True:
1132 if G.is_multigraph():
1133 if keys is True:
1134 return ((n, n, k, d)
1135 for n, nbrs in G.adj.items()
1136 if n in nbrs for k, d in nbrs[n].items())
1137 else:
1138 return ((n, n, d)
1139 for n, nbrs in G.adj.items()
1140 if n in nbrs for d in nbrs[n].values())
1141 else:
1142 return ((n, n, nbrs[n]) for n, nbrs in G.adj.items() if n in nbrs)
1143 elif data is not False:
1144 if G.is_multigraph():
1145 if keys is True:
1146 return ((n, n, k, d.get(data, default))
1147 for n, nbrs in G.adj.items()
1148 if n in nbrs for k, d in nbrs[n].items())
1149 else:
1150 return ((n, n, d.get(data, default))
1151 for n, nbrs in G.adj.items()
1152 if n in nbrs for d in nbrs[n].values())
1153 else:
1154 return ((n, n, nbrs[n].get(data, default))
1155 for n, nbrs in G.adj.items() if n in nbrs)
1156 else:
1157 if G.is_multigraph():
1158 if keys is True:
1159 return ((n, n, k)
1160 for n, nbrs in G.adj.items()
1161 if n in nbrs for k in nbrs[n])
1162 else:
1163 return ((n, n)
1164 for n, nbrs in G.adj.items()
1165 if n in nbrs for d in nbrs[n].values())
1166 else:
1167 return ((n, n) for n, nbrs in G.adj.items() if n in nbrs)
1168
1169
1170 def number_of_selfloops(G):
1171 """Returns the number of selfloop edges.
1172
1173 A selfloop edge has the same node at both ends.
1174
1175 Returns
1176 -------
1177 nloops : int
1178 The number of selfloops.
1179
1180 See Also
1181 --------
1182 nodes_with_selfloops, selfloop_edges
1183
1184 Examples
1185 --------
1186 >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc
1187 >>> G.add_edge(1, 1)
1188 >>> G.add_edge(1, 2)
1189 >>> nx.number_of_selfloops(G)
1190 1
1191 """
1192 return sum(1 for _ in nx.selfloop_edges(G))