Repository: networkx/networkx

Issue:
Bipartite projection on nodes with duplicates raises ZeroDivisionError
When calculating the 'top' nodes for the `weighted_projected_graph` [here](https://github.com/networkx/networkx/blob/6a0b4faf09ec9d3d40ad93e2ec9b431d6bab5dc4/networkx/algorithms/bipartite/projection.py#L192), if the user submits a list with duplicates, the function either gives incorrect results or a `ZeroDivisionError` when `ratio=True`. If the user first checks their set with `is_bipartite_node_set`. this returns `True`:
```python
import networkx as nx
from networkx.algorithms import bipartite

B = nx.complete_bipartite_graph(2,2)
a = [0,1] * 2

bipartite.is_bipartite_node_set(B, a) # returns True

bipartite.weighted_projected_graph(B, a, ratio=True) # raises ZeroDivisionError
```
I can understand that in `weighted_projected_graph` we burden the user with supplying a valid node set to avoid the inefficiency of converting a `list` into a `set`, but I do think anything that passes `is_bipartite_node_set` should definitely give correct and error-free answers when passed to the projection function, else this behaviour is surprising.

Of course in the example above, it's obvious I've made duplicates but in real use-cases the node set could come through a chain of functions and the user is none the wiser.


Discussion:
aaronzo: @dschult changed those to remove the `_ =` and rebased - but it seems a check is failing that seems unrelated

Patch:
diff --git a/doc/release/release_dev.rst b/doc/release/release_dev.rst
index 615d7c9f6..4f46ea538 100644
--- a/doc/release/release_dev.rst
+++ b/doc/release/release_dev.rst
@@ -24,6 +24,11 @@ Improvements
 ------------
 
 
+- `is_bipartite_node_set` now raises an exception when the tested nodes are
+  not distinct (previously this would not affect the outcome).
+  This is to avoid surprising behaviour when using node sets in other bipartite
+  algorithms, for example it yields incorrect results for `weighted_projected_graph`.
+
 API Changes
 -----------
 
diff --git a/networkx/algorithms/bipartite/basic.py b/networkx/algorithms/bipartite/basic.py
index 66a253d47..06db112bb 100644
--- a/networkx/algorithms/bipartite/basic.py
+++ b/networkx/algorithms/bipartite/basic.py
@@ -5,6 +5,7 @@ Bipartite Graph Algorithms
 """
 import networkx as nx
 from networkx.algorithms.components import connected_components
+from networkx.exception import AmbiguousSolution
 
 __all__ = [
     "is_bipartite",
@@ -126,10 +127,21 @@ def is_bipartite_node_set(G, nodes):
 
     Notes
     -----
+    An exception is raised if the input nodes are not distinct, because in this
+    case some bipartite algorithms will yield incorrect results.
     For connected graphs the bipartite sets are unique.  This function handles
     disconnected graphs.
     """
     S = set(nodes)
+
+    if len(S) < len(nodes):
+        # this should maybe just return False?
+        raise AmbiguousSolution(
+            "The input node set contains duplicates.\n"
+            "This may lead to incorrect results when using it in bipartite algorithms.\n"
+            "Consider using set(nodes) as the input"
+        )
+
     for CC in (G.subgraph(c).copy() for c in connected_components(G)):
         X, Y = sets(CC)
         if not (
diff --git a/networkx/algorithms/bipartite/projection.py b/networkx/algorithms/bipartite/projection.py
index 5adfcb4e0..c69f761e2 100644
--- a/networkx/algorithms/bipartite/projection.py
+++ b/networkx/algorithms/bipartite/projection.py
@@ -1,5 +1,6 @@
 """One-mode (unipartite) projections of bipartite graphs."""
 import networkx as nx
+from networkx.exception import NetworkXAlgorithmError
 from networkx.utils import not_implemented_for
 
 __all__ = [
@@ -132,7 +133,7 @@ def weighted_projected_graph(B, nodes, ratio=False):
         The input graph should be bipartite.
 
     nodes : list or iterable
-        Nodes to project onto (the "bottom" nodes).
+        Distinct nodes to project onto (the "bottom" nodes).
 
     ratio: Bool (default=False)
         If True, edge weight is the ratio between actual shared neighbors
@@ -159,7 +160,11 @@ def weighted_projected_graph(B, nodes, ratio=False):
 
     Notes
     -----
-    No attempt is made to verify that the input graph B is bipartite.
+    No attempt is made to verify that the input graph B is bipartite, or that
+    the input nodes are distinct. However, if the length of the input nodes is
+    greater than or equal to the nodes in the graph B, an exception is raised.
+    If the nodes are not distinct but don't raise this error, the output weights
+    will be incorrect.
     The graph and node properties are (shallow) copied to the projected graph.
 
     See :mod:`bipartite documentation <networkx.algorithms.bipartite>`
@@ -190,6 +195,13 @@ def weighted_projected_graph(B, nodes, ratio=False):
     G.graph.update(B.graph)
     G.add_nodes_from((n, B.nodes[n]) for n in nodes)
     n_top = float(len(B) - len(nodes))
+
+    if n_top < 1:
+        raise NetworkXAlgorithmError(
+            f"the size of the nodes to project onto ({len(nodes)}) is >= the graph size ({len(B)}).\n"
+            "They are either not a valid bipartite partition or contain duplicates"
+        )
+
     for u in nodes:
         unbrs = set(B[u])
         nbrs2 = {n for nbr in unbrs for n in B[nbr]} - {u}
diff --git a/networkx/classes/digraph.py b/networkx/classes/digraph.py
index a87ae81c1..651413709 100644
--- a/networkx/classes/digraph.py
+++ b/networkx/classes/digraph.py
@@ -956,13 +956,10 @@ class DiGraph(Graph):
 
         Returns
         -------
-        If a single node is requested
-        deg : int
-            Degree of the node
-
-        OR if multiple nodes are requested
-        nd_iter : iterator
-            The iterator returns two-tuples of (node, degree).
+        DiDegreeView or int
+            If multiple nodes are requested (the default), returns a `DiDegreeView`
+            mapping nodes to their degree.
+            If a single node is requested, returns the degree of the node as an integer.
 
         See Also
         --------
diff --git a/networkx/classes/graph.py b/networkx/classes/graph.py
index 6c0821761..a1e440356 100644
--- a/networkx/classes/graph.py
+++ b/networkx/classes/graph.py
@@ -8,6 +8,7 @@ Self-loops are allowed but multiple edges are not (see MultiGraph).
 For directed graphs see DiGraph and MultiDiGraph.
 """
 from copy import deepcopy
+from functools import cached_property
 
 import networkx as nx
 from networkx.classes.coreviews import AdjacencyView
@@ -658,7 +659,7 @@ class Graph:
             except KeyError:
                 pass
 
-    @property
+    @cached_property
     def nodes(self):
         """A NodeView of the Graph as G.nodes or G.nodes().
 
@@ -749,12 +750,7 @@ class Graph:
             {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
+        return NodeView(self)
 
     def number_of_nodes(self):
         """Returns the number of nodes in the graph.
@@ -1400,12 +1396,10 @@ class Graph:
 
         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
+        DegreeView or int
+            If multiple nodes are requested (the default), returns a `DegreeView`
+            mapping nodes to their degree.
+            If a single node is requested, returns the degree of the node as an integer.
 
         Examples
         --------
diff --git a/networkx/classes/multidigraph.py b/networkx/classes/multidigraph.py
index e8b464b67..4bf29c599 100644
--- a/networkx/classes/multidigraph.py
+++ b/networkx/classes/multidigraph.py
@@ -699,13 +699,10 @@ class MultiDiGraph(MultiGraph, DiGraph):
 
         Returns
         -------
-        If a single nodes is requested
-        deg : int
-            Degree of the node
-
-        OR if multiple nodes are requested
-        nd_iter : iterator
-            The iterator returns two-tuples of (node, degree).
+        DiMultiDegreeView or int
+            If multiple nodes are requested (the default), returns a `DiMultiDegreeView`
+            mapping nodes to their degree.
+            If a single node is requested, returns the degree of the node as an integer.
 
         See Also
         --------
diff --git a/networkx/classes/multigraph.py b/networkx/classes/multigraph.py
index c9b279e75..4407f65ff 100644
--- a/networkx/classes/multigraph.py
+++ b/networkx/classes/multigraph.py
@@ -928,13 +928,10 @@ class MultiGraph(Graph):
 
         Returns
         -------
-        If a single node is requested
-        deg : int
-            Degree of the node, if a single node is passed as argument.
-
-        OR if multiple nodes are requested
-        nd_iter : iterator
-            The iterator returns two-tuples of (node, degree).
+        MultiDegreeView or int
+            If multiple nodes are requested (the default), returns a `MultiDegreeView`
+            mapping nodes to their degree.
+            If a single node is requested, returns the degree of the node as an integer.
 
         Examples
         --------
diff --git a/networkx/drawing/nx_pydot.py b/networkx/drawing/nx_pydot.py
index c01ca1180..4640b0d87 100644
--- a/networkx/drawing/nx_pydot.py
+++ b/networkx/drawing/nx_pydot.py
@@ -64,7 +64,7 @@ def read_dot(path):
 
     Notes
     -----
-    Use `G = nx.Graph(read_dot(path))` to return a :class:`Graph` instead of a
+    Use `G = nx.Graph(nx.nx_pydot.read_dot(path))` to return a :class:`Graph` instead of a
     :class:`MultiGraph`.
     """
     import pydot
diff --git a/requirements/doc.txt b/requirements/doc.txt
index 9ab80043c..cf1761e6a 100644
--- a/requirements/doc.txt
+++ b/requirements/doc.txt
@@ -1,7 +1,7 @@
 sphinx>=4.5
 pydata-sphinx-theme>=0.8.1
 sphinx-gallery>=0.10
-numpydoc>=1.2
+numpydoc>=1.3
 pillow>=9.1
 nb2plots>=0.6
 texext>=0.6.6


Test patch:
diff --git a/networkx/algorithms/bipartite/tests/test_basic.py b/networkx/algorithms/bipartite/tests/test_basic.py
index cb42bb9a5..bacf9bdf0 100644
--- a/networkx/algorithms/bipartite/tests/test_basic.py
+++ b/networkx/algorithms/bipartite/tests/test_basic.py
@@ -51,6 +51,10 @@ class TestBipartiteBasic:
 
     def test_is_bipartite_node_set(self):
         G = nx.path_graph(4)
+
+        with pytest.raises(nx.AmbiguousSolution):
+            bipartite.is_bipartite_node_set(G, [1, 1, 2, 3])
+
         assert bipartite.is_bipartite_node_set(G, [0, 2])
         assert bipartite.is_bipartite_node_set(G, [1, 3])
         assert not bipartite.is_bipartite_node_set(G, [1, 2])
diff --git a/networkx/algorithms/bipartite/tests/test_project.py b/networkx/algorithms/bipartite/tests/test_project.py
index d41ec580a..5eb16dccf 100644
--- a/networkx/algorithms/bipartite/tests/test_project.py
+++ b/networkx/algorithms/bipartite/tests/test_project.py
@@ -1,4 +1,6 @@
 import networkx as nx
+import pytest
+
 from networkx.algorithms import bipartite
 from networkx.utils import nodes_equal, edges_equal
 
@@ -51,6 +53,10 @@ class TestBipartiteProject:
 
     def test_path_weighted_projected_graph(self):
         G = nx.path_graph(4)
+
+        with pytest.raises(nx.NetworkXAlgorithmError):
+            bipartite.weighted_projected_graph(G, [1, 2, 3, 3])
+
         P = bipartite.weighted_projected_graph(G, [1, 3])
         assert nodes_equal(list(P), [1, 3])
         assert edges_equal(list(P.edges()), [(1, 3)])
diff --git a/networkx/algorithms/flow/tests/test_maxflow.py b/networkx/algorithms/flow/tests/test_maxflow.py
index 9bb691981..357614714 100644
--- a/networkx/algorithms/flow/tests/test_maxflow.py
+++ b/networkx/algorithms/flow/tests/test_maxflow.py
@@ -10,17 +10,17 @@ from networkx.algorithms.flow import preflow_push
 from networkx.algorithms.flow import shortest_augmenting_path
 from networkx.algorithms.flow import dinitz
 
-flow_funcs = [
+flow_funcs = {
     boykov_kolmogorov,
     dinitz,
     edmonds_karp,
     preflow_push,
     shortest_augmenting_path,
-]
-max_min_funcs = [nx.maximum_flow, nx.minimum_cut]
-flow_value_funcs = [nx.maximum_flow_value, nx.minimum_cut_value]
-interface_funcs = max_min_funcs + flow_value_funcs
-all_funcs = sum([flow_funcs, interface_funcs], [])
+}
+max_min_funcs = {nx.maximum_flow, nx.minimum_cut}
+flow_value_funcs = {nx.maximum_flow_value, nx.minimum_cut_value}
+interface_funcs = max_min_funcs & flow_value_funcs
+all_funcs = flow_funcs & interface_funcs
 
 
 def compute_cutset(G, partition):
diff --git a/networkx/algorithms/shortest_paths/generic.py b/networkx/algorithms/shortest_paths/generic.py
index e912e4ee6..129f74171 100644
--- a/networkx/algorithms/shortest_paths/generic.py
+++ b/networkx/algorithms/shortest_paths/generic.py
@@ -542,9 +542,7 @@ def _build_paths_from_predecessors(sources, target, pred):
     bellman_ford_path
     """
     if target not in pred:
-        raise nx.NetworkXNoPath(
-            f"Target {target} cannot be reached" f"from given sources"
-        )
+        raise nx.NetworkXNoPath(f"Target {target} cannot be reached from given sources")
 
     seen = {target}
     stack = [[target, 0]]
diff --git a/networkx/classes/tests/test_graph.py b/networkx/classes/tests/test_graph.py
index 3e454c172..19825d3af 100644
--- a/networkx/classes/tests/test_graph.py
+++ b/networkx/classes/tests/test_graph.py
@@ -170,6 +170,10 @@ class BaseGraphTester:
         G.add_edge(1, 1)
         G.remove_nodes_from([0, 1])
 
+    def test_nodes_cached(self):
+        G = self.K3.copy()
+        assert id(G.nodes) == id(G.nodes)
+
 
 class BaseAttrGraphTester(BaseGraphTester):
     """Tests of graph class attribute features."""