Mercurial > repos > shellac > guppy_basecaller
diff env/lib/python3.7/site-packages/networkx/classes/graph.py @ 5:9b1c78e6ba9c draft default tip
"planemo upload commit 6c0a8142489327ece472c84e558c47da711a9142"
| author | shellac |
|---|---|
| date | Mon, 01 Jun 2020 08:59:25 -0400 |
| parents | 79f47841a781 |
| children |
line wrap: on
line diff
--- a/env/lib/python3.7/site-packages/networkx/classes/graph.py Thu May 14 16:47:39 2020 -0400 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,1890 +0,0 @@ -# Copyright (C) 2004-2019 by -# Aric Hagberg <hagberg@lanl.gov> -# Dan Schult <dschult@colgate.edu> -# Pieter Swart <swart@lanl.gov> -# All rights reserved. -# BSD license. -# -# Author: Aric Hagberg (hagberg@lanl.gov), -# Pieter Swart (swart@lanl.gov), -# Dan Schult(dschult@colgate.edu) -"""Base class for undirected graphs. - -The Graph class allows any hashable object as a node -and can associate key/value attribute pairs with each undirected edge. - -Self-loops are allowed but multiple edges are not (see MultiGraph). - -For directed graphs see DiGraph and MultiDiGraph. -""" -import warnings -from copy import deepcopy -from collections.abc import Mapping - -import networkx as nx -from networkx.classes.coreviews import AtlasView, AdjacencyView -from networkx.classes.reportviews import NodeView, EdgeView, DegreeView -from networkx.exception import NetworkXError -import networkx.convert as convert -from networkx.utils import pairwise - - -class Graph(object): - """ - Base class for undirected graphs. - - A Graph stores nodes and edges with optional data, or attributes. - - Graphs hold undirected edges. Self loops are allowed but multiple - (parallel) edges are not. - - Nodes can be arbitrary (hashable) Python objects with optional - key/value attributes. By convention `None` is not used as a node. - - Edges are represented as links between nodes with optional - key/value attributes. - - Parameters - ---------- - incoming_graph_data : input graph (optional, default: None) - Data to initialize graph. If None (default) an empty - graph is created. The data can be any format that is supported - by the to_networkx_graph() function, currently including edge list, - dict of dicts, dict of lists, NetworkX graph, NumPy matrix - or 2d ndarray, SciPy sparse matrix, or PyGraphviz graph. - - attr : keyword arguments, optional (default= no attributes) - Attributes to add to graph as key=value pairs. - - See Also - -------- - DiGraph - MultiGraph - MultiDiGraph - OrderedGraph - - Examples - -------- - Create an empty graph structure (a "null graph") with no nodes and - no edges. - - >>> G = nx.Graph() - - G can be grown in several ways. - - **Nodes:** - - Add one node at a time: - - >>> G.add_node(1) - - Add the nodes from any container (a list, dict, set or - even the lines from a file or the nodes from another graph). - - >>> G.add_nodes_from([2, 3]) - >>> G.add_nodes_from(range(100, 110)) - >>> H = nx.path_graph(10) - >>> G.add_nodes_from(H) - - In addition to strings and integers any hashable Python object - (except None) can represent a node, e.g. a customized node object, - or even another Graph. - - >>> G.add_node(H) - - **Edges:** - - G can also be grown by adding edges. - - Add one edge, - - >>> G.add_edge(1, 2) - - a list of edges, - - >>> G.add_edges_from([(1, 2), (1, 3)]) - - or a collection of edges, - - >>> G.add_edges_from(H.edges) - - If some edges connect nodes not yet in the graph, the nodes - are added automatically. There are no errors when adding - nodes or edges that already exist. - - **Attributes:** - - Each graph, node, and edge can hold key/value attribute pairs - in an associated attribute dictionary (the keys must be hashable). - By default these are empty, but can be added or changed using - add_edge, add_node or direct manipulation of the attribute - dictionaries named graph, node and edge respectively. - - >>> G = nx.Graph(day="Friday") - >>> G.graph - {'day': 'Friday'} - - Add node attributes using add_node(), add_nodes_from() or G.nodes - - >>> G.add_node(1, time='5pm') - >>> G.add_nodes_from([3], time='2pm') - >>> G.nodes[1] - {'time': '5pm'} - >>> G.nodes[1]['room'] = 714 # node must exist already to use G.nodes - >>> del G.nodes[1]['room'] # remove attribute - >>> list(G.nodes(data=True)) - [(1, {'time': '5pm'}), (3, {'time': '2pm'})] - - Add edge attributes using add_edge(), add_edges_from(), subscript - notation, or G.edges. - - >>> G.add_edge(1, 2, weight=4.7 ) - >>> G.add_edges_from([(3, 4), (4, 5)], color='red') - >>> G.add_edges_from([(1, 2, {'color': 'blue'}), (2, 3, {'weight': 8})]) - >>> G[1][2]['weight'] = 4.7 - >>> G.edges[1, 2]['weight'] = 4 - - Warning: we protect the graph data structure by making `G.edges` a - read-only dict-like structure. However, you can assign to attributes - in e.g. `G.edges[1, 2]`. Thus, use 2 sets of brackets to add/change - data attributes: `G.edges[1, 2]['weight'] = 4` - (For multigraphs: `MG.edges[u, v, key][name] = value`). - - **Shortcuts:** - - Many common graph features allow python syntax to speed reporting. - - >>> 1 in G # check if node in graph - True - >>> [n for n in G if n < 3] # iterate through nodes - [1, 2] - >>> len(G) # number of nodes in graph - 5 - - Often the best way to traverse all edges of a graph is via the neighbors. - The neighbors are reported as an adjacency-dict `G.adj` or `G.adjacency()` - - >>> for n, nbrsdict in G.adjacency(): - ... for nbr, eattr in nbrsdict.items(): - ... if 'weight' in eattr: - ... # Do something useful with the edges - ... pass - - But the edges() method is often more convenient: - - >>> for u, v, weight in G.edges.data('weight'): - ... if weight is not None: - ... # Do something useful with the edges - ... pass - - **Reporting:** - - Simple graph information is obtained using object-attributes and methods. - Reporting typically provides views instead of containers to reduce memory - usage. The views update as the graph is updated similarly to dict-views. - The objects `nodes, `edges` and `adj` provide access to data attributes - via lookup (e.g. `nodes[n], `edges[u, v]`, `adj[u][v]`) and iteration - (e.g. `nodes.items()`, `nodes.data('color')`, - `nodes.data('color', default='blue')` and similarly for `edges`) - Views exist for `nodes`, `edges`, `neighbors()`/`adj` and `degree`. - - For details on these and other miscellaneous methods, see below. - - **Subclasses (Advanced):** - - The Graph class uses a dict-of-dict-of-dict data structure. - The outer dict (node_dict) holds adjacency information keyed by node. - The next dict (adjlist_dict) represents the adjacency information and holds - edge data keyed by neighbor. The inner dict (edge_attr_dict) represents - the edge data and holds edge attribute values keyed by attribute names. - - Each of these three dicts can be replaced in a subclass by a user defined - dict-like object. In general, the dict-like features should be - maintained but extra features can be added. To replace one of the - dicts create a new graph class by changing the class(!) variable - holding the factory for that dict-like structure. The variable names are - node_dict_factory, node_attr_dict_factory, adjlist_inner_dict_factory, - adjlist_outer_dict_factory, edge_attr_dict_factory and graph_attr_dict_factory. - - node_dict_factory : function, (default: dict) - Factory function to be used to create the dict containing node - attributes, keyed by node id. - It should require no arguments and return a dict-like object - - node_attr_dict_factory: function, (default: dict) - Factory function to be used to create the node attribute - dict which holds attribute values keyed by attribute name. - It should require no arguments and return a dict-like object - - adjlist_outer_dict_factory : function, (default: dict) - Factory function to be used to create the outer-most dict - in the data structure that holds adjacency info keyed by node. - It should require no arguments and return a dict-like object. - - adjlist_inner_dict_factory : function, (default: dict) - Factory function to be used to create the adjacency list - dict which holds edge data keyed by neighbor. - It should require no arguments and return a dict-like object - - edge_attr_dict_factory : function, (default: dict) - Factory function to be used to create the edge attribute - dict which holds attribute values keyed by attribute name. - It should require no arguments and return a dict-like object. - - graph_attr_dict_factory : function, (default: dict) - Factory function to be used to create the graph attribute - dict which holds attribute values keyed by attribute name. - It should require no arguments and return a dict-like object. - - Typically, if your extension doesn't impact the data structure all - methods will inherit without issue except: `to_directed/to_undirected`. - By default these methods create a DiGraph/Graph class and you probably - want them to create your extension of a DiGraph/Graph. To facilitate - this we define two class variables that you can set in your subclass. - - to_directed_class : callable, (default: DiGraph or MultiDiGraph) - Class to create a new graph structure in the `to_directed` method. - If `None`, a NetworkX class (DiGraph or MultiDiGraph) is used. - - to_undirected_class : callable, (default: Graph or MultiGraph) - Class to create a new graph structure in the `to_undirected` method. - If `None`, a NetworkX class (Graph or MultiGraph) is used. - - Examples - -------- - - Create a low memory graph class that effectively disallows edge - attributes by using a single attribute dict for all edges. - This reduces the memory used, but you lose edge attributes. - - >>> class ThinGraph(nx.Graph): - ... all_edge_dict = {'weight': 1} - ... def single_edge_dict(self): - ... return self.all_edge_dict - ... edge_attr_dict_factory = single_edge_dict - >>> G = ThinGraph() - >>> G.add_edge(2, 1) - >>> G[2][1] - {'weight': 1} - >>> G.add_edge(2, 2) - >>> G[2][1] is G[2][2] - True - - Please see :mod:`~networkx.classes.ordered` for more examples of - creating graph subclasses by overwriting the base class `dict` with - a dictionary-like object. - """ - node_dict_factory = dict - node_attr_dict_factory = dict - adjlist_outer_dict_factory = dict - adjlist_inner_dict_factory = dict - edge_attr_dict_factory = dict - graph_attr_dict_factory = dict - - def to_directed_class(self): - """Returns the class to use for empty directed copies. - - If you subclass the base classes, use this to designate - what directed class to use for `to_directed()` copies. - """ - return nx.DiGraph - - def to_undirected_class(self): - """Returns the class to use for empty undirected copies. - - If you subclass the base classes, use this to designate - what directed class to use for `to_directed()` copies. - """ - return Graph - - def __init__(self, incoming_graph_data=None, **attr): - """Initialize a graph with edges, name, or graph attributes. - - Parameters - ---------- - incoming_graph_data : input graph (optional, default: None) - Data to initialize graph. If None (default) an empty - graph is created. The data can be an edge list, or any - NetworkX graph object. If the corresponding optional Python - packages are installed the data can also be a NumPy matrix - or 2d ndarray, a SciPy sparse matrix, or a PyGraphviz graph. - - attr : keyword arguments, optional (default= no attributes) - Attributes to add to graph as key=value pairs. - - See Also - -------- - convert - - Examples - -------- - >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc - >>> G = nx.Graph(name='my graph') - >>> e = [(1, 2), (2, 3), (3, 4)] # list of edges - >>> G = nx.Graph(e) - - Arbitrary graph attribute pairs (key=value) may be assigned - - >>> G = nx.Graph(e, day="Friday") - >>> G.graph - {'day': 'Friday'} - - """ - self.graph_attr_dict_factory = self.graph_attr_dict_factory - self.node_dict_factory = self.node_dict_factory - self.node_attr_dict_factory = self.node_attr_dict_factory - self.adjlist_outer_dict_factory = self.adjlist_outer_dict_factory - self.adjlist_inner_dict_factory = self.adjlist_inner_dict_factory - self.edge_attr_dict_factory = self.edge_attr_dict_factory - - self.graph = self.graph_attr_dict_factory() # dictionary for graph attributes - self._node = self.node_dict_factory() # empty node attribute dict - self._adj = self.adjlist_outer_dict_factory() # empty adjacency dict - # attempt to load graph with data - if incoming_graph_data is not None: - convert.to_networkx_graph(incoming_graph_data, create_using=self) - # load graph attributes (must be after convert) - self.graph.update(attr) - - @property - def adj(self): - """Graph adjacency object holding the neighbors of each node. - - This object is a read-only dict-like structure with node keys - and neighbor-dict values. The neighbor-dict is keyed by neighbor - to the edge-data-dict. So `G.adj[3][2]['color'] = 'blue'` sets - the color of the edge `(3, 2)` to `"blue"`. - - Iterating over G.adj behaves like a dict. Useful idioms include - `for nbr, datadict in G.adj[n].items():`. - - The neighbor information is also provided by subscripting the graph. - So `for nbr, foovalue in G[node].data('foo', default=1):` works. - - For directed graphs, `G.adj` holds outgoing (successor) info. - """ - return AdjacencyView(self._adj) - - @property - def name(self): - """String identifier of the graph. - - This graph attribute appears in the attribute dict G.graph - keyed by the string `"name"`. as well as an attribute (technically - a property) `G.name`. This is entirely user controlled. - """ - return self.graph.get('name', '') - - @name.setter - def name(self, s): - self.graph['name'] = s - - def __str__(self): - """Returns the graph name. - - Returns - ------- - name : string - The name of the graph. - - Examples - -------- - >>> G = nx.Graph(name='foo') - >>> str(G) - 'foo' - """ - return self.name - - def __iter__(self): - """Iterate over the nodes. Use: 'for n in G'. - - Returns - ------- - niter : iterator - An iterator over all nodes in the graph. - - Examples - -------- - >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc - >>> [n for n in G] - [0, 1, 2, 3] - >>> list(G) - [0, 1, 2, 3] - """ - return iter(self._node) - - def __contains__(self, n): - """Returns True if n is a node, False otherwise. Use: 'n in G'. - - Examples - -------- - >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc - >>> 1 in G - True - """ - try: - return n in self._node - except TypeError: - return False - - def __len__(self): - """Returns the number of nodes in the graph. Use: 'len(G)'. - - Returns - ------- - nnodes : int - The number of nodes in the graph. - - See Also - -------- - number_of_nodes, order which are identical - - Examples - -------- - >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc - >>> len(G) - 4 - - """ - return len(self._node) - - def __getitem__(self, n): - """Returns a dict of neighbors of node n. Use: 'G[n]'. - - Parameters - ---------- - n : node - A node in the graph. - - Returns - ------- - adj_dict : dictionary - The adjacency dictionary for nodes connected to n. - - Notes - ----- - G[n] is the same as G.adj[n] and similar to G.neighbors(n) - (which is an iterator over G.adj[n]) - - Examples - -------- - >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc - >>> G[0] - AtlasView({1: {}}) - """ - return self.adj[n] - - def add_node(self, node_for_adding, **attr): - """Add a single node `node_for_adding` and update node attributes. - - Parameters - ---------- - node_for_adding : node - A node can be any hashable Python object except None. - attr : keyword arguments, optional - Set or change node attributes using key=value. - - See Also - -------- - add_nodes_from - - Examples - -------- - >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc - >>> G.add_node(1) - >>> G.add_node('Hello') - >>> K3 = nx.Graph([(0, 1), (1, 2), (2, 0)]) - >>> G.add_node(K3) - >>> G.number_of_nodes() - 3 - - Use keywords set/change node attributes: - - >>> G.add_node(1, size=10) - >>> G.add_node(3, weight=0.4, UTM=('13S', 382871, 3972649)) - - Notes - ----- - A hashable object is one that can be used as a key in a Python - dictionary. This includes strings, numbers, tuples of strings - and numbers, etc. - - On many platforms hashable items also include mutables such as - NetworkX Graphs, though one should be careful that the hash - doesn't change on mutables. - """ - if node_for_adding not in self._node: - self._adj[node_for_adding] = self.adjlist_inner_dict_factory() - attr_dict = self._node[node_for_adding] = self.node_attr_dict_factory() - attr_dict.update(attr) - else: # update attr even if node already exists - self._node[node_for_adding].update(attr) - - def add_nodes_from(self, nodes_for_adding, **attr): - """Add multiple nodes. - - Parameters - ---------- - nodes_for_adding : iterable container - A container of nodes (list, dict, set, etc.). - OR - A container of (node, attribute dict) tuples. - Node attributes are updated using the attribute dict. - attr : keyword arguments, optional (default= no attributes) - Update attributes for all nodes in nodes. - Node attributes specified in nodes as a tuple take - precedence over attributes specified via keyword arguments. - - See Also - -------- - add_node - - Examples - -------- - >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc - >>> G.add_nodes_from('Hello') - >>> K3 = nx.Graph([(0, 1), (1, 2), (2, 0)]) - >>> G.add_nodes_from(K3) - >>> sorted(G.nodes(), key=str) - [0, 1, 2, 'H', 'e', 'l', 'o'] - - Use keywords to update specific node attributes for every node. - - >>> G.add_nodes_from([1, 2], size=10) - >>> G.add_nodes_from([3, 4], weight=0.4) - - Use (node, attrdict) tuples to update attributes for specific nodes. - - >>> G.add_nodes_from([(1, dict(size=11)), (2, {'color':'blue'})]) - >>> G.nodes[1]['size'] - 11 - >>> H = nx.Graph() - >>> H.add_nodes_from(G.nodes(data=True)) - >>> H.nodes[1]['size'] - 11 - - """ - for n in nodes_for_adding: - # keep all this inside try/except because - # CPython throws TypeError on n not in self._node, - # while pre-2.7.5 ironpython throws on self._adj[n] - try: - if n not in self._node: - self._adj[n] = self.adjlist_inner_dict_factory() - attr_dict = self._node[n] = self.node_attr_dict_factory() - attr_dict.update(attr) - else: - self._node[n].update(attr) - except TypeError: - nn, ndict = n - if nn not in self._node: - self._adj[nn] = self.adjlist_inner_dict_factory() - newdict = attr.copy() - newdict.update(ndict) - attr_dict = self._node[nn] = self.node_attr_dict_factory() - attr_dict.update(newdict) - else: - olddict = self._node[nn] - olddict.update(attr) - olddict.update(ndict) - - def remove_node(self, n): - """Remove node n. - - Removes the node n and all adjacent edges. - Attempting to remove a non-existent node will raise an exception. - - Parameters - ---------- - n : node - A node in the graph - - Raises - ------- - NetworkXError - If n is not in the graph. - - See Also - -------- - remove_nodes_from - - Examples - -------- - >>> G = nx.path_graph(3) # or DiGraph, MultiGraph, MultiDiGraph, etc - >>> list(G.edges) - [(0, 1), (1, 2)] - >>> G.remove_node(1) - >>> list(G.edges) - [] - - """ - adj = self._adj - try: - nbrs = list(adj[n]) # list handles self-loops (allows mutation) - del self._node[n] - except KeyError: # NetworkXError if n not in self - raise NetworkXError("The node %s is not in the graph." % (n,)) - for u in nbrs: - del adj[u][n] # remove all edges n-u in graph - del adj[n] # now remove node - - def remove_nodes_from(self, nodes): - """Remove multiple nodes. - - Parameters - ---------- - nodes : iterable container - A container of nodes (list, dict, set, etc.). If a node - in the container is not in the graph it is silently - ignored. - - See Also - -------- - remove_node - - Examples - -------- - >>> G = nx.path_graph(3) # or DiGraph, MultiGraph, MultiDiGraph, etc - >>> e = list(G.nodes) - >>> e - [0, 1, 2] - >>> G.remove_nodes_from(e) - >>> list(G.nodes) - [] - - """ - adj = self._adj - for n in nodes: - try: - del self._node[n] - for u in list(adj[n]): # list handles self-loops - del adj[u][n] # (allows mutation of dict in loop) - del adj[n] - except KeyError: - pass - - @property - def nodes(self): - """A NodeView of the Graph as G.nodes or G.nodes(). - - Can be used as `G.nodes` for data lookup and for set-like operations. - Can also be used as `G.nodes(data='color', default=None)` to return a - NodeDataView which reports specific node data but no set operations. - It presents a dict-like interface as well with `G.nodes.items()` - iterating over `(node, nodedata)` 2-tuples and `G.nodes[3]['foo']` - providing the value of the `foo` attribute for node `3`. In addition, - a view `G.nodes.data('foo')` provides a dict-like interface to the - `foo` attribute of each node. `G.nodes.data('foo', default=1)` - provides a default for nodes that do not have attribute `foo`. - - Parameters - ---------- - data : string or bool, optional (default=False) - The node attribute returned in 2-tuple (n, ddict[data]). - If True, return entire node attribute dict as (n, ddict). - If False, return just the nodes n. - - default : value, optional (default=None) - Value used for nodes that don't have the requested attribute. - Only relevant if data is not True or False. - - Returns - ------- - NodeView - Allows set-like operations over the nodes as well as node - attribute dict lookup and calling to get a NodeDataView. - A NodeDataView iterates over `(n, data)` and has no set operations. - A NodeView iterates over `n` and includes set operations. - - When called, if data is False, an iterator over nodes. - Otherwise an iterator of 2-tuples (node, attribute value) - where the attribute is specified in `data`. - If data is True then the attribute becomes the - entire data dictionary. - - Notes - ----- - If your node data is not needed, it is simpler and equivalent - to use the expression ``for n in G``, or ``list(G)``. - - Examples - -------- - There are two simple ways of getting a list of all nodes in the graph: - - >>> G = nx.path_graph(3) - >>> list(G.nodes) - [0, 1, 2] - >>> list(G) - [0, 1, 2] - - To get the node data along with the nodes: - - >>> G.add_node(1, time='5pm') - >>> G.nodes[0]['foo'] = 'bar' - >>> list(G.nodes(data=True)) - [(0, {'foo': 'bar'}), (1, {'time': '5pm'}), (2, {})] - >>> list(G.nodes.data()) - [(0, {'foo': 'bar'}), (1, {'time': '5pm'}), (2, {})] - - >>> list(G.nodes(data='foo')) - [(0, 'bar'), (1, None), (2, None)] - >>> list(G.nodes.data('foo')) - [(0, 'bar'), (1, None), (2, None)] - - >>> list(G.nodes(data='time')) - [(0, None), (1, '5pm'), (2, None)] - >>> list(G.nodes.data('time')) - [(0, None), (1, '5pm'), (2, None)] - - >>> list(G.nodes(data='time', default='Not Available')) - [(0, 'Not Available'), (1, '5pm'), (2, 'Not Available')] - >>> list(G.nodes.data('time', default='Not Available')) - [(0, 'Not Available'), (1, '5pm'), (2, 'Not Available')] - - If some of your nodes have an attribute and the rest are assumed - to have a default attribute value you can create a dictionary - from node/attribute pairs using the `default` keyword argument - to guarantee the value is never None:: - - >>> G = nx.Graph() - >>> G.add_node(0) - >>> G.add_node(1, weight=2) - >>> G.add_node(2, weight=3) - >>> dict(G.nodes(data='weight', default=1)) - {0: 1, 1: 2, 2: 3} - - """ - nodes = NodeView(self) - # Lazy View creation: overload the (class) property on the instance - # Then future G.nodes use the existing View - # setattr doesn't work because attribute already exists - self.__dict__['nodes'] = nodes - return nodes - - def number_of_nodes(self): - """Returns the number of nodes in the graph. - - Returns - ------- - nnodes : int - The number of nodes in the graph. - - See Also - -------- - order, __len__ which are identical - - Examples - -------- - >>> G = nx.path_graph(3) # or DiGraph, MultiGraph, MultiDiGraph, etc - >>> G.number_of_nodes() - 3 - """ - return len(self._node) - - def order(self): - """Returns the number of nodes in the graph. - - Returns - ------- - nnodes : int - The number of nodes in the graph. - - See Also - -------- - number_of_nodes, __len__ which are identical - - Examples - -------- - >>> G = nx.path_graph(3) # or DiGraph, MultiGraph, MultiDiGraph, etc - >>> G.order() - 3 - """ - return len(self._node) - - def has_node(self, n): - """Returns True if the graph contains the node n. - - Identical to `n in G` - - Parameters - ---------- - n : node - - Examples - -------- - >>> G = nx.path_graph(3) # or DiGraph, MultiGraph, MultiDiGraph, etc - >>> G.has_node(0) - True - - It is more readable and simpler to use - - >>> 0 in G - True - - """ - try: - return n in self._node - except TypeError: - return False - - def add_edge(self, u_of_edge, v_of_edge, **attr): - """Add an edge between u and v. - - The nodes u and v will be automatically added if they are - not already in the graph. - - Edge attributes can be specified with keywords or by directly - accessing the edge's attribute dictionary. See examples below. - - Parameters - ---------- - u, v : nodes - Nodes can be, for example, strings or numbers. - Nodes must be hashable (and not None) Python objects. - attr : keyword arguments, optional - Edge data (or labels or objects) can be assigned using - keyword arguments. - - See Also - -------- - add_edges_from : add a collection of edges - - Notes - ----- - Adding an edge that already exists updates the edge data. - - Many NetworkX algorithms designed for weighted graphs use - an edge attribute (by default `weight`) to hold a numerical value. - - Examples - -------- - The following all add the edge e=(1, 2) to graph G: - - >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc - >>> e = (1, 2) - >>> G.add_edge(1, 2) # explicit two-node form - >>> G.add_edge(*e) # single edge as tuple of two nodes - >>> G.add_edges_from([(1, 2)]) # add edges from iterable container - - Associate data to edges using keywords: - - >>> G.add_edge(1, 2, weight=3) - >>> G.add_edge(1, 3, weight=7, capacity=15, length=342.7) - - For non-string attribute keys, use subscript notation. - - >>> G.add_edge(1, 2) - >>> G[1][2].update({0: 5}) - >>> G.edges[1, 2].update({0: 5}) - """ - u, v = u_of_edge, v_of_edge - # add nodes - if u not in self._node: - self._adj[u] = self.adjlist_inner_dict_factory() - self._node[u] = self.node_attr_dict_factory() - if v not in self._node: - self._adj[v] = self.adjlist_inner_dict_factory() - self._node[v] = self.node_attr_dict_factory() - # add the edge - datadict = self._adj[u].get(v, self.edge_attr_dict_factory()) - datadict.update(attr) - self._adj[u][v] = datadict - self._adj[v][u] = datadict - - def add_edges_from(self, ebunch_to_add, **attr): - """Add all the edges in ebunch_to_add. - - Parameters - ---------- - ebunch_to_add : container of edges - Each edge given in the container will be added to the - graph. The edges must be given as as 2-tuples (u, v) or - 3-tuples (u, v, d) where d is a dictionary containing edge data. - attr : keyword arguments, optional - Edge data (or labels or objects) can be assigned using - keyword arguments. - - See Also - -------- - add_edge : add a single edge - add_weighted_edges_from : convenient way to add weighted edges - - Notes - ----- - Adding the same edge twice has no effect but any edge data - will be updated when each duplicate edge is added. - - Edge attributes specified in an ebunch take precedence over - attributes specified via keyword arguments. - - Examples - -------- - >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc - >>> G.add_edges_from([(0, 1), (1, 2)]) # using a list of edge tuples - >>> e = zip(range(0, 3), range(1, 4)) - >>> G.add_edges_from(e) # Add the path graph 0-1-2-3 - - Associate data to edges - - >>> G.add_edges_from([(1, 2), (2, 3)], weight=3) - >>> G.add_edges_from([(3, 4), (1, 4)], label='WN2898') - """ - for e in ebunch_to_add: - ne = len(e) - if ne == 3: - u, v, dd = e - elif ne == 2: - u, v = e - dd = {} # doesn't need edge_attr_dict_factory - else: - raise NetworkXError( - "Edge tuple %s must be a 2-tuple or 3-tuple." % (e,)) - if u not in self._node: - self._adj[u] = self.adjlist_inner_dict_factory() - self._node[u] = self.node_attr_dict_factory() - if v not in self._node: - self._adj[v] = self.adjlist_inner_dict_factory() - self._node[v] = self.node_attr_dict_factory() - datadict = self._adj[u].get(v, self.edge_attr_dict_factory()) - datadict.update(attr) - datadict.update(dd) - self._adj[u][v] = datadict - self._adj[v][u] = datadict - - def add_weighted_edges_from(self, ebunch_to_add, weight='weight', **attr): - """Add weighted edges in `ebunch_to_add` with specified weight attr - - Parameters - ---------- - ebunch_to_add : container of edges - Each edge given in the list or container will be added - to the graph. The edges must be given as 3-tuples (u, v, w) - where w is a number. - weight : string, optional (default= 'weight') - The attribute name for the edge weights to be added. - attr : keyword arguments, optional (default= no attributes) - Edge attributes to add/update for all edges. - - See Also - -------- - add_edge : add a single edge - add_edges_from : add multiple edges - - Notes - ----- - Adding the same edge twice for Graph/DiGraph simply updates - the edge data. For MultiGraph/MultiDiGraph, duplicate edges - are stored. - - Examples - -------- - >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc - >>> G.add_weighted_edges_from([(0, 1, 3.0), (1, 2, 7.5)]) - """ - self.add_edges_from(((u, v, {weight: d}) for u, v, d in ebunch_to_add), - **attr) - - def remove_edge(self, u, v): - """Remove the edge between u and v. - - Parameters - ---------- - u, v : nodes - Remove the edge between nodes u and v. - - Raises - ------ - NetworkXError - If there is not an edge between u and v. - - See Also - -------- - remove_edges_from : remove a collection of edges - - Examples - -------- - >>> G = nx.path_graph(4) # or DiGraph, etc - >>> G.remove_edge(0, 1) - >>> e = (1, 2) - >>> G.remove_edge(*e) # unpacks e from an edge tuple - >>> e = (2, 3, {'weight':7}) # an edge with attribute data - >>> G.remove_edge(*e[:2]) # select first part of edge tuple - """ - try: - del self._adj[u][v] - if u != v: # self-loop needs only one entry removed - del self._adj[v][u] - except KeyError: - raise NetworkXError("The edge %s-%s is not in the graph" % (u, v)) - - def remove_edges_from(self, ebunch): - """Remove all edges specified in ebunch. - - Parameters - ---------- - ebunch: list or container of edge tuples - Each edge given in the list or container will be removed - from the graph. The edges can be: - - - 2-tuples (u, v) edge between u and v. - - 3-tuples (u, v, k) where k is ignored. - - See Also - -------- - remove_edge : remove a single edge - - Notes - ----- - Will fail silently if an edge in ebunch is not in the graph. - - Examples - -------- - >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc - >>> ebunch=[(1, 2), (2, 3)] - >>> G.remove_edges_from(ebunch) - """ - adj = self._adj - for e in ebunch: - u, v = e[:2] # ignore edge data if present - if u in adj and v in adj[u]: - del adj[u][v] - if u != v: # self loop needs only one entry removed - del adj[v][u] - - def update(self, edges=None, nodes=None): - """Update the graph using nodes/edges/graphs as input. - - Like dict.update, this method takes a graph as input, adding the - graph's nodes and edges to this graph. It can also take two inputs: - edges and nodes. Finally it can take either edges or nodes. - To specify only nodes the keyword `nodes` must be used. - - The collections of edges and nodes are treated similarly to - the add_edges_from/add_nodes_from methods. When iterated, they - should yield 2-tuples (u, v) or 3-tuples (u, v, datadict). - - Parameters - ---------- - edges : Graph object, collection of edges, or None - The first parameter can be a graph or some edges. If it has - attributes `nodes` and `edges`, then it is taken to be a - Graph-like object and those attributes are used as collections - of nodes and edges to be added to the graph. - If the first parameter does not have those attributes, it is - treated as a collection of edges and added to the graph. - If the first argument is None, no edges are added. - nodes : collection of nodes, or None - The second parameter is treated as a collection of nodes - to be added to the graph unless it is None. - If `edges is None` and `nodes is None` an exception is raised. - If the first parameter is a Graph, then `nodes` is ignored. - - Examples - -------- - >>> G = nx.path_graph(5) - >>> G.update(nx.complete_graph(range(4,10))) - >>> from itertools import combinations - >>> edges = ((u, v, {'power': u * v}) - ... for u, v in combinations(range(10, 20), 2) - ... if u * v < 225) - >>> nodes = [1000] # for singleton, use a container - >>> G.update(edges, nodes) - - Notes - ----- - It you want to update the graph using an adjacency structure - it is straightforward to obtain the edges/nodes from adjacency. - The following examples provide common cases, your adjacency may - be slightly different and require tweaks of these examples. - - >>> # dict-of-set/list/tuple - >>> adj = {1: {2, 3}, 2: {1, 3}, 3: {1, 2}} - >>> e = [(u, v) for u, nbrs in adj.items() for v in nbrs] - >>> G.update(edges=e, nodes=adj) - - >>> DG = nx.DiGraph() - >>> # dict-of-dict-of-attribute - >>> adj = {1: {2: 1.3, 3: 0.7}, 2: {1: 1.4}, 3: {1: 0.7}} - >>> e = [(u, v, {'weight': d}) for u, nbrs in adj.items() - ... for v, d in nbrs.items()] - >>> DG.update(edges=e, nodes=adj) - - >>> # dict-of-dict-of-dict - >>> adj = {1: {2: {'weight': 1.3}, 3: {'color': 0.7, 'weight':1.2}}} - >>> e = [(u, v, {'weight': d}) for u, nbrs in adj.items() - ... for v, d in nbrs.items()] - >>> DG.update(edges=e, nodes=adj) - - >>> # predecessor adjacency (dict-of-set) - >>> pred = {1: {2, 3}, 2: {3}, 3: {3}} - >>> e = [(v, u) for u, nbrs in pred.items() for v in nbrs] - - >>> # MultiGraph dict-of-dict-of-dict-of-attribute - >>> MDG = nx.MultiDiGraph() - >>> adj = {1: {2: {0: {'weight': 1.3}, 1: {'weight': 1.2}}}, - ... 3: {2: {0: {'weight': 0.7}}}} - >>> e = [(u, v, ekey, d) for u, nbrs in adj.items() - ... for v, keydict in nbrs.items() - ... for ekey, d in keydict.items()] - >>> MDG.update(edges=e) - - See Also - -------- - add_edges_from: add multiple edges to a graph - add_nodes_from: add multiple nodes to a graph - """ - if edges is not None: - if nodes is not None: - self.add_nodes_from(nodes) - self.add_edges_from(edges) - else: - # check if edges is a Graph object - try: - graph_nodes = edges.nodes - graph_edges = edges.edges - except AttributeError: - # edge not Graph-like - self.add_edges_from(edges) - else: # edges is Graph-like - self.add_nodes_from(graph_nodes.data()) - self.add_edges_from(graph_edges.data()) - self.graph.update(edges.graph) - elif nodes is not None: - self.add_nodes_from(nodes) - else: - raise NetworkXError("update needs nodes or edges input") - - def has_edge(self, u, v): - """Returns True if the edge (u, v) is in the graph. - - This is the same as `v in G[u]` without KeyError exceptions. - - Parameters - ---------- - u, v : nodes - Nodes can be, for example, strings or numbers. - Nodes must be hashable (and not None) Python objects. - - Returns - ------- - edge_ind : bool - True if edge is in the graph, False otherwise. - - Examples - -------- - >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc - >>> G.has_edge(0, 1) # using two nodes - True - >>> e = (0, 1) - >>> G.has_edge(*e) # e is a 2-tuple (u, v) - True - >>> e = (0, 1, {'weight':7}) - >>> G.has_edge(*e[:2]) # e is a 3-tuple (u, v, data_dictionary) - True - - The following syntax are equivalent: - - >>> G.has_edge(0, 1) - True - >>> 1 in G[0] # though this gives KeyError if 0 not in G - True - - """ - try: - return v in self._adj[u] - except KeyError: - return False - - def neighbors(self, n): - """Returns an iterator over all neighbors of node n. - - This is identical to `iter(G[n])` - - Parameters - ---------- - n : node - A node in the graph - - Returns - ------- - neighbors : iterator - An iterator over all neighbors of node n - - Raises - ------ - NetworkXError - If the node n is not in the graph. - - Examples - -------- - >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc - >>> [n for n in G.neighbors(0)] - [1] - - Notes - ----- - It is usually more convenient (and faster) to access the - adjacency dictionary as ``G[n]``: - - >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc - >>> G.add_edge('a', 'b', weight=7) - >>> G['a'] - AtlasView({'b': {'weight': 7}}) - >>> G = nx.path_graph(4) - >>> [n for n in G[0]] - [1] - """ - try: - return iter(self._adj[n]) - except KeyError: - raise NetworkXError("The node %s is not in the graph." % (n,)) - - @property - def edges(self): - """An EdgeView of the Graph as G.edges or G.edges(). - - edges(self, nbunch=None, data=False, default=None) - - The EdgeView provides set-like operations on the edge-tuples - as well as edge attribute lookup. When called, it also provides - an EdgeDataView object which allows control of access to edge - attributes (but does not provide set-like operations). - Hence, `G.edges[u, v]['color']` provides the value of the color - attribute for edge `(u, v)` while - `for (u, v, c) in G.edges.data('color', default='red'):` - iterates through all the edges yielding the color attribute - with default `'red'` if no color attribute exists. - - Parameters - ---------- - nbunch : single node, container, or all nodes (default= all nodes) - The view will only report edges incident to these nodes. - data : string or bool, optional (default=False) - The edge attribute returned in 3-tuple (u, v, ddict[data]). - If True, return edge attribute dict in 3-tuple (u, v, ddict). - If False, return 2-tuple (u, v). - default : value, optional (default=None) - Value used for edges that don't have the requested attribute. - Only relevant if data is not True or False. - - Returns - ------- - edges : EdgeView - A view of edge attributes, usually it iterates over (u, v) - or (u, v, d) tuples of edges, but can also be used for - attribute lookup as `edges[u, v]['foo']`. - - Notes - ----- - Nodes in nbunch that are not in the graph will be (quietly) ignored. - For directed graphs this returns the out-edges. - - Examples - -------- - >>> G = nx.path_graph(3) # or MultiGraph, etc - >>> G.add_edge(2, 3, weight=5) - >>> [e for e in G.edges] - [(0, 1), (1, 2), (2, 3)] - >>> G.edges.data() # default data is {} (empty dict) - EdgeDataView([(0, 1, {}), (1, 2, {}), (2, 3, {'weight': 5})]) - >>> G.edges.data('weight', default=1) - EdgeDataView([(0, 1, 1), (1, 2, 1), (2, 3, 5)]) - >>> G.edges([0, 3]) # only edges incident to these nodes - EdgeDataView([(0, 1), (3, 2)]) - >>> G.edges(0) # only edges incident to a single node (use G.adj[0]?) - EdgeDataView([(0, 1)]) - """ - return EdgeView(self) - - def get_edge_data(self, u, v, default=None): - """Returns the attribute dictionary associated with edge (u, v). - - This is identical to `G[u][v]` except the default is returned - instead of an exception if the edge doesn't exist. - - Parameters - ---------- - u, v : nodes - default: any Python object (default=None) - Value to return if the edge (u, v) is not found. - - Returns - ------- - edge_dict : dictionary - The edge attribute dictionary. - - Examples - -------- - >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc - >>> G[0][1] - {} - - Warning: Assigning to `G[u][v]` is not permitted. - But it is safe to assign attributes `G[u][v]['foo']` - - >>> G[0][1]['weight'] = 7 - >>> G[0][1]['weight'] - 7 - >>> G[1][0]['weight'] - 7 - - >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc - >>> G.get_edge_data(0, 1) # default edge data is {} - {} - >>> e = (0, 1) - >>> G.get_edge_data(*e) # tuple form - {} - >>> G.get_edge_data('a', 'b', default=0) # edge not in graph, return 0 - 0 - """ - try: - return self._adj[u][v] - except KeyError: - return default - - def adjacency(self): - """Returns an iterator over (node, adjacency dict) tuples for all nodes. - - For directed graphs, only outgoing neighbors/adjacencies are included. - - Returns - ------- - adj_iter : iterator - An iterator over (node, adjacency dictionary) for all nodes in - the graph. - - Examples - -------- - >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc - >>> [(n, nbrdict) for n, nbrdict in G.adjacency()] - [(0, {1: {}}), (1, {0: {}, 2: {}}), (2, {1: {}, 3: {}}), (3, {2: {}})] - - """ - return iter(self._adj.items()) - - @property - def degree(self): - """A DegreeView for the Graph as G.degree or G.degree(). - - The node degree is the number of edges adjacent to the node. - The weighted node degree is the sum of the edge weights for - edges incident to that node. - - This object provides an iterator for (node, degree) as well as - lookup for the degree for a single node. - - Parameters - ---------- - nbunch : single node, container, or all nodes (default= all nodes) - The view will only report edges incident to these nodes. - - weight : string or None, optional (default=None) - The name of an edge attribute that holds the numerical value used - as a weight. If None, then each edge has weight 1. - The degree is the sum of the edge weights adjacent to the node. - - Returns - ------- - If a single node is requested - deg : int - Degree of the node - - OR if multiple nodes are requested - nd_view : A DegreeView object capable of iterating (node, degree) pairs - - Examples - -------- - >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc - >>> G.degree[0] # node 0 has degree 1 - 1 - >>> list(G.degree([0, 1, 2])) - [(0, 1), (1, 2), (2, 2)] - """ - return DegreeView(self) - - def clear(self): - """Remove all nodes and edges from the graph. - - This also removes the name, and all graph, node, and edge attributes. - - Examples - -------- - >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc - >>> G.clear() - >>> list(G.nodes) - [] - >>> list(G.edges) - [] - - """ - self._adj.clear() - self._node.clear() - self.graph.clear() - - def is_multigraph(self): - """Returns True if graph is a multigraph, False otherwise.""" - return False - - def is_directed(self): - """Returns True if graph is directed, False otherwise.""" - return False - - def copy(self, as_view=False): - """Returns a copy of the graph. - - The copy method by default returns an independent shallow copy - of the graph and attributes. That is, if an attribute is a - container, that container is shared by the original an the copy. - Use Python's `copy.deepcopy` for new containers. - - If `as_view` is True then a view is returned instead of a copy. - - Notes - ----- - All copies reproduce the graph structure, but data attributes - may be handled in different ways. There are four types of copies - of a graph that people might want. - - Deepcopy -- A "deepcopy" copies the graph structure as well as - all data attributes and any objects they might contain. - The entire graph object is new so that changes in the copy - do not affect the original object. (see Python's copy.deepcopy) - - Data Reference (Shallow) -- For a shallow copy the graph structure - is copied but the edge, node and graph attribute dicts are - references to those in the original graph. This saves - time and memory but could cause confusion if you change an attribute - in one graph and it changes the attribute in the other. - NetworkX does not provide this level of shallow copy. - - Independent Shallow -- This copy creates new independent attribute - dicts and then does a shallow copy of the attributes. That is, any - attributes that are containers are shared between the new graph - and the original. This is exactly what `dict.copy()` provides. - You can obtain this style copy using: - - >>> G = nx.path_graph(5) - >>> H = G.copy() - >>> H = G.copy(as_view=False) - >>> H = nx.Graph(G) - >>> H = G.__class__(G) - - Fresh Data -- For fresh data, the graph structure is copied while - new empty data attribute dicts are created. The resulting graph - is independent of the original and it has no edge, node or graph - attributes. Fresh copies are not enabled. Instead use: - - >>> H = G.__class__() - >>> H.add_nodes_from(G) - >>> H.add_edges_from(G.edges) - - View -- Inspired by dict-views, graph-views act like read-only - versions of the original graph, providing a copy of the original - structure without requiring any memory for copying the information. - - See the Python copy module for more information on shallow - and deep copies, https://docs.python.org/2/library/copy.html. - - Parameters - ---------- - as_view : bool, optional (default=False) - If True, the returned graph-view provides a read-only view - of the original graph without actually copying any data. - - Returns - ------- - G : Graph - A copy of the graph. - - See Also - -------- - to_directed: return a directed copy of the graph. - - Examples - -------- - >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc - >>> H = G.copy() - - """ - if as_view is True: - return nx.graphviews.generic_graph_view(self) - G = self.__class__() - G.graph.update(self.graph) - G.add_nodes_from((n, d.copy()) for n, d in self._node.items()) - G.add_edges_from((u, v, datadict.copy()) - for u, nbrs in self._adj.items() - for v, datadict in nbrs.items()) - return G - - def to_directed(self, as_view=False): - """Returns a directed representation of the graph. - - Returns - ------- - G : DiGraph - A directed graph with the same name, same nodes, and with - each edge (u, v, data) replaced by two directed edges - (u, v, data) and (v, u, data). - - Notes - ----- - This returns a "deepcopy" of the edge, node, and - graph attributes which attempts to completely copy - all of the data and references. - - This is in contrast to the similar D=DiGraph(G) which returns a - shallow copy of the data. - - See the Python copy module for more information on shallow - and deep copies, https://docs.python.org/2/library/copy.html. - - Warning: If you have subclassed Graph to use dict-like objects - in the data structure, those changes do not transfer to the - DiGraph created by this method. - - Examples - -------- - >>> G = nx.Graph() # or MultiGraph, etc - >>> G.add_edge(0, 1) - >>> H = G.to_directed() - >>> list(H.edges) - [(0, 1), (1, 0)] - - If already directed, return a (deep) copy - - >>> G = nx.DiGraph() # or MultiDiGraph, etc - >>> G.add_edge(0, 1) - >>> H = G.to_directed() - >>> list(H.edges) - [(0, 1)] - """ - graph_class = self.to_directed_class() - if as_view is True: - return nx.graphviews.generic_graph_view(self, graph_class) - # deepcopy when not a view - G = graph_class() - G.graph.update(deepcopy(self.graph)) - G.add_nodes_from((n, deepcopy(d)) for n, d in self._node.items()) - G.add_edges_from((u, v, deepcopy(data)) - for u, nbrs in self._adj.items() - for v, data in nbrs.items()) - return G - - def to_undirected(self, as_view=False): - """Returns an undirected copy of the graph. - - Parameters - ---------- - as_view : bool (optional, default=False) - If True return a view of the original undirected graph. - - Returns - ------- - G : Graph/MultiGraph - A deepcopy of the graph. - - See Also - -------- - Graph, copy, add_edge, add_edges_from - - Notes - ----- - This returns a "deepcopy" of the edge, node, and - graph attributes which attempts to completely copy - all of the data and references. - - This is in contrast to the similar `G = nx.DiGraph(D)` which returns a - shallow copy of the data. - - See the Python copy module for more information on shallow - and deep copies, https://docs.python.org/2/library/copy.html. - - Warning: If you have subclassed DiGraph to use dict-like objects - in the data structure, those changes do not transfer to the - Graph created by this method. - - Examples - -------- - >>> G = nx.path_graph(2) # or MultiGraph, etc - >>> H = G.to_directed() - >>> list(H.edges) - [(0, 1), (1, 0)] - >>> G2 = H.to_undirected() - >>> list(G2.edges) - [(0, 1)] - """ - graph_class = self.to_undirected_class() - if as_view is True: - return nx.graphviews.generic_graph_view(self, graph_class) - # deepcopy when not a view - G = graph_class() - G.graph.update(deepcopy(self.graph)) - G.add_nodes_from((n, deepcopy(d)) for n, d in self._node.items()) - G.add_edges_from((u, v, deepcopy(d)) - for u, nbrs in self._adj.items() - for v, d in nbrs.items()) - return G - - def subgraph(self, nodes): - """Returns a SubGraph view of the subgraph induced on `nodes`. - - The induced subgraph of the graph contains the nodes in `nodes` - and the edges between those nodes. - - Parameters - ---------- - nodes : list, iterable - A container of nodes which will be iterated through once. - - Returns - ------- - G : SubGraph View - A subgraph view of the graph. The graph structure cannot be - changed but node/edge attributes can and are shared with the - original graph. - - Notes - ----- - The graph, edge and node attributes are shared with the original graph. - Changes to the graph structure is ruled out by the view, but changes - to attributes are reflected in the original graph. - - To create a subgraph with its own copy of the edge/node attributes use: - G.subgraph(nodes).copy() - - For an inplace reduction of a graph to a subgraph you can remove nodes: - G.remove_nodes_from([n for n in G if n not in set(nodes)]) - - Subgraph views are sometimes NOT what you want. In most cases where - you want to do more than simply look at the induced edges, it makes - more sense to just create the subgraph as its own graph with code like: - - :: - - # Create a subgraph SG based on a (possibly multigraph) G - SG = G.__class__() - SG.add_nodes_from((n, G.nodes[n]) for n in largest_wcc) - if SG.is_multigraph: - SG.add_edges_from((n, nbr, key, d) - for n, nbrs in G.adj.items() if n in largest_wcc - for nbr, keydict in nbrs.items() if nbr in largest_wcc - for key, d in keydict.items()) - else: - SG.add_edges_from((n, nbr, d) - for n, nbrs in G.adj.items() if n in largest_wcc - for nbr, d in nbrs.items() if nbr in largest_wcc) - SG.graph.update(G.graph) - - Examples - -------- - >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc - >>> H = G.subgraph([0, 1, 2]) - >>> list(H.edges) - [(0, 1), (1, 2)] - """ - induced_nodes = nx.filters.show_nodes(self.nbunch_iter(nodes)) - # if already a subgraph, don't make a chain - subgraph = nx.graphviews.subgraph_view - if hasattr(self, '_NODE_OK'): - return subgraph(self._graph, induced_nodes, self._EDGE_OK) - return subgraph(self, induced_nodes) - - def edge_subgraph(self, edges): - """Returns the subgraph induced by the specified edges. - - The induced subgraph contains each edge in `edges` and each - node incident to any one of those edges. - - Parameters - ---------- - edges : iterable - An iterable of edges in this graph. - - Returns - ------- - G : Graph - An edge-induced subgraph of this graph with the same edge - attributes. - - Notes - ----- - The graph, edge, and node attributes in the returned subgraph - view are references to the corresponding attributes in the original - graph. The view is read-only. - - To create a full graph version of the subgraph with its own copy - of the edge or node attributes, use:: - - >>> G.edge_subgraph(edges).copy() # doctest: +SKIP - - Examples - -------- - >>> G = nx.path_graph(5) - >>> H = G.edge_subgraph([(0, 1), (3, 4)]) - >>> list(H.nodes) - [0, 1, 3, 4] - >>> list(H.edges) - [(0, 1), (3, 4)] - - """ - return nx.edge_subgraph(self, edges) - - def size(self, weight=None): - """Returns the number of edges or total of all edge weights. - - Parameters - ---------- - weight : string or None, optional (default=None) - The edge attribute that holds the numerical value used - as a weight. If None, then each edge has weight 1. - - Returns - ------- - size : numeric - The number of edges or - (if weight keyword is provided) the total weight sum. - - If weight is None, returns an int. Otherwise a float - (or more general numeric if the weights are more general). - - See Also - -------- - number_of_edges - - Examples - -------- - >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc - >>> G.size() - 3 - - >>> G = nx.Graph() # or DiGraph, MultiGraph, MultiDiGraph, etc - >>> G.add_edge('a', 'b', weight=2) - >>> G.add_edge('b', 'c', weight=4) - >>> G.size() - 2 - >>> G.size(weight='weight') - 6.0 - """ - s = sum(d for v, d in self.degree(weight=weight)) - # If `weight` is None, the sum of the degrees is guaranteed to be - # even, so we can perform integer division and hence return an - # integer. Otherwise, the sum of the weighted degrees is not - # guaranteed to be an integer, so we perform "real" division. - return s // 2 if weight is None else s / 2 - - def number_of_edges(self, u=None, v=None): - """Returns the number of edges between two nodes. - - Parameters - ---------- - u, v : nodes, optional (default=all edges) - If u and v are specified, return the number of edges between - u and v. Otherwise return the total number of all edges. - - Returns - ------- - nedges : int - The number of edges in the graph. If nodes `u` and `v` are - specified return the number of edges between those nodes. If - the graph is directed, this only returns the number of edges - from `u` to `v`. - - See Also - -------- - size - - Examples - -------- - For undirected graphs, this method counts the total number of - edges in the graph: - - >>> G = nx.path_graph(4) - >>> G.number_of_edges() - 3 - - If you specify two nodes, this counts the total number of edges - joining the two nodes: - - >>> G.number_of_edges(0, 1) - 1 - - For directed graphs, this method can count the total number of - directed edges from `u` to `v`: - - >>> G = nx.DiGraph() - >>> G.add_edge(0, 1) - >>> G.add_edge(1, 0) - >>> G.number_of_edges(0, 1) - 1 - - """ - if u is None: - return int(self.size()) - if v in self._adj[u]: - return 1 - return 0 - - def nbunch_iter(self, nbunch=None): - """Returns an iterator over nodes contained in nbunch that are - also in the graph. - - The nodes in nbunch are checked for membership in the graph - and if not are silently ignored. - - Parameters - ---------- - nbunch : single node, container, or all nodes (default= all nodes) - The view will only report edges incident to these nodes. - - Returns - ------- - niter : iterator - An iterator over nodes in nbunch that are also in the graph. - If nbunch is None, iterate over all nodes in the graph. - - Raises - ------ - NetworkXError - If nbunch is not a node or or sequence of nodes. - If a node in nbunch is not hashable. - - See Also - -------- - Graph.__iter__ - - Notes - ----- - When nbunch is an iterator, the returned iterator yields values - directly from nbunch, becoming exhausted when nbunch is exhausted. - - To test whether nbunch is a single node, one can use - "if nbunch in self:", even after processing with this routine. - - If nbunch is not a node or a (possibly empty) sequence/iterator - or None, a :exc:`NetworkXError` is raised. Also, if any object in - nbunch is not hashable, a :exc:`NetworkXError` is raised. - """ - if nbunch is None: # include all nodes via iterator - bunch = iter(self._adj) - elif nbunch in self: # if nbunch is a single node - bunch = iter([nbunch]) - else: # if nbunch is a sequence of nodes - def bunch_iter(nlist, adj): - try: - for n in nlist: - if n in adj: - yield n - except TypeError as e: - message = e.args[0] - # capture error for non-sequence/iterator nbunch. - if 'iter' in message: - msg = "nbunch is not a node or a sequence of nodes." - raise NetworkXError(msg) - # capture error for unhashable node. - elif 'hashable' in message: - msg = "Node {} in sequence nbunch is not a valid node." - raise NetworkXError(msg.format(n)) - else: - raise - bunch = bunch_iter(nbunch, self._adj) - return bunch