Repository: networkx/networkx

Issue:
Approximation TSP - Bug when custom weight is not correctly add in input
<!-- If you have a general question about NetworkX, please use the discussions tab to create a new discussion -->

<!--- Provide a general summary of the issue in the Title above -->
When the weight has a different label than 'weight', it is not properly considered `networkx.algorithms.approximation.traveling_salesman.threshold_accepting_tsp` ( it ius working for the `greedy`approximation but I didnt check the others approximations)


### Current Behavior
```python
import networkx as nx
from networkx.algorithms import approximation as approx
from networkx.utils import pairwise

G = nx.DiGraph()
G.add_weighted_edges_from({
    ("A", "B", 3), ("A", "C", 17), ("A", "D", 14), ("B", "A", 3),
    ("B", "C", 12), ("B", "D", 16), ("C", "A", 13),("C", "B", 12),
    ("C", "D", 4), ("D", "A", 14), ("D", "B", 15), ("D", "C", 2)
})
cycle = approx.greedy_tsp(G, source="D")
cost = sum(G[n][nbr]["weight"] for n, nbr in pairwise(cycle))
print(cycle)
print(cost)


# Test new graph with weight attribute 'length'
H = nx.DiGraph()
H.add_edges_from([
    ("A", "B", {'length':3}), ("A", "C", {'length':17}), ("A", "D", {'length':14}), ("B", "A", {'length':3}),
    ("B", "C", {'length':12}), ("B", "D", {'length':16}), ("C", "A", {'length':13}),("C", "B", {'length':12}),
    ("C", "D", {'length':4}), ("D", "A", {'length':14}), ("D", "B", {'length':15}), ("D", "C", {'length':2})
])
cycle = approx.greedy_tsp(H, weight='length',source="D")
cost = sum(H[n][nbr]["length"] for n, nbr in pairwise(cycle))
print(cycle)
print(cost)

print(nx.approximation.threshold_accepting_tsp(H, "greedy", weight='length', source='D'))

tsp = nx.approximation.traveling_salesman_problem
TA_tsp = nx.approximation.threshold_accepting_tsp
method = lambda Graph, wt: TA_tsp(Graph, "greedy", weight=wt, source='D')
path = tsp(H, weight='length', cycle=True, method=method)
print(path)

path = tsp(G, cycle=True, method=method)
print(path)
```

```
['D', 'C', 'B', 'A', 'D']
31
['D', 'C', 'B', 'A', 'D']
31
['D', 'C', 'B', 'A', 'D']
['D', 'C', 'B', 'C', 'A', 'D']
['D', 'C', 'B', 'A', 'D']
```

### Expected behavior:

```python
tsp = nx.approximation.traveling_salesman_problem
TA_tsp = nx.approximation.threshold_accepting_tsp
method = lambda Graph, wt: TA_tsp(Graph, "greedy", weight=wt, source='D')
path = tsp(H, weight='length', cycle=True, method=method)
```
returns `['D', 'C', 'B', 'C', 'A', 'D']` but it should return `['D', 'C', 'B', 'A', 'D']`

### Environment
<!--- Please provide details about your local environment -->
Python version: 3.9.4
NetworkX version: 2.6rc1.dev0


### Additional context
<!--- Add any other context about the problem here, screenshots, etc. -->
The problem may come from the way `nx.approximation.traveling_salesman_problem` is handling custom weight?  

Have you considered not assigning a default weight of 1 when the weight attribute is not present? I think it could make the software more "robust" maybe?

For example, when running the command below:
```python
cycle = approx.greedy_tsp(H, source="D")
cost = sum(H[n][nbr]["length"] for n, nbr in nx.utils.pairwise(cycle))
print(cycle)
print(cost)
```
I got:
```
['D', 'B', 'C', 'A', 'D']
54
```

But it is not the behavior I would expect. I would rather have the approximation made on the only edge attribute available ("length") or getting an error message telling me `"Weight attribute not present "` .




Discussion:

Patch:
diff --git a/examples/algorithms/plot_parallel_betweenness.py b/examples/algorithms/plot_parallel_betweenness.py
index 7a27abaaf..aa88652b6 100644
--- a/examples/algorithms/plot_parallel_betweenness.py
+++ b/examples/algorithms/plot_parallel_betweenness.py
@@ -10,8 +10,12 @@ The function betweenness centrality accepts a bunch of nodes and computes
 the contribution of those nodes to the betweenness centrality of the whole
 network. Here we divide the network in chunks of nodes and we compute their
 contribution to the betweenness centrality of the whole network.
-"""
 
+Note: The example output below shows that the non-parallel implementation is
+faster. This is a limitation of our CI/CD pipeline running on a single core.
+
+Depending on your setup, you will likely observe a speedup.
+"""
 from multiprocessing import Pool
 import time
 import itertools
diff --git a/networkx/algorithms/approximation/traveling_salesman.py b/networkx/algorithms/approximation/traveling_salesman.py
index ad88f7f19..dc6964c80 100644
--- a/networkx/algorithms/approximation/traveling_salesman.py
+++ b/networkx/algorithms/approximation/traveling_salesman.py
@@ -447,13 +447,11 @@ def simulated_annealing_tsp(
         The distance between all pairs of nodes should be included.
 
     init_cycle : list of all nodes or "greedy"
-        The initial solution (a cycle through all nodes).
-        Usually you should use `greedy_tsp(G, weight)`.
-        But you can start with `list(G)` or the final result
-        of `simulated_annealing_tsp` when doing `threshold_accepting_tsp`.
-
-        This argument is required. A shortcut if you don't want to think
-        about it is to use the string "greedy" which calls `greedy_tsp`.
+        The initial solution (a cycle through all nodes returning to the start).
+        This argument has no default to make you think about it.
+        If "greedy", use `greedy_tsp(G, weight)`.
+        Other common starting cycles are `list(G) + [next(iter(G))]` or the final
+        result of `simulated_annealing_tsp` when doing `threshold_accepting_tsp`.
 
     weight : string, optional (default="weight")
         Edge data key corresponding to the edge weight.
@@ -663,6 +661,13 @@ def threshold_accepting_tsp(
         `G` should be a complete weighted undirected graph.
         The distance between all pairs of nodes should be included.
 
+    init_cycle : list or "greedy"
+        The initial solution (a cycle through all nodes returning to the start).
+        This argument has no default to make you think about it.
+        If "greedy", use `greedy_tsp(G, weight)`.
+        Other common starting cycles are `list(G) + [next(iter(G))]` or the final
+        result of `simulated_annealing_tsp` when doing `threshold_accepting_tsp`.
+
     weight : string, optional (default="weight")
         Edge data key corresponding to the edge weight.
         If any edge does not have this attribute the weight is set to 1.
@@ -713,9 +718,6 @@ def threshold_accepting_tsp(
         least one acceptance of a neighbor solution.
         If no inner loop moves are accepted the threshold remains unchanged.
 
-    cycle : list, optional (default=compute using greedy algorithm)
-        The initial solution (a cycle all nodes).
-
     seed : integer, random_state, or None (default)
         Indicator of random number generation state.
         See :ref:`Randomness<randomness>`.
diff --git a/networkx/algorithms/assortativity/correlation.py b/networkx/algorithms/assortativity/correlation.py
index b885a22ee..8a244fc7d 100644
--- a/networkx/algorithms/assortativity/correlation.py
+++ b/networkx/algorithms/assortativity/correlation.py
@@ -73,8 +73,12 @@ def degree_assortativity_coefficient(G, x="out", y="in", weight=None, nodes=None
     .. [2] Foster, J.G., Foster, D.V., Grassberger, P. & Paczuski, M.
        Edge direction and the structure of networks, PNAS 107, 10815-20 (2010).
     """
-    M = degree_mixing_matrix(G, x=x, y=y, nodes=nodes, weight=weight)
-    return numeric_ac(M)
+    if nodes is None:
+        nodes = G.nodes
+    degrees = set([d for n, d in G.degree(nodes, weight=weight)])
+    mapping = {d: i for i, d, in enumerate(degrees)}
+    M = degree_mixing_matrix(G, x=x, y=y, nodes=nodes, weight=weight, mapping=mapping)
+    return numeric_ac(M, mapping=mapping)
 
 
 def degree_pearson_correlation_coefficient(G, x="out", y="in", weight=None, nodes=None):
@@ -223,8 +227,12 @@ def numeric_assortativity_coefficient(G, attribute, nodes=None):
     .. [1] M. E. J. Newman, Mixing patterns in networks
            Physical Review E, 67 026126, 2003
     """
-    a = numeric_mixing_matrix(G, attribute, nodes)
-    return numeric_ac(a)
+    if nodes is None:
+        nodes = G.nodes
+    vals = set(G.nodes[n][attribute] for n in nodes)
+    mapping = {d: i for i, d, in enumerate(vals)}
+    M = attribute_mixing_matrix(G, attribute, nodes, mapping)
+    return numeric_ac(M, mapping)
 
 
 def attribute_ac(M):
@@ -254,7 +262,7 @@ def attribute_ac(M):
     return r
 
 
-def numeric_ac(M):
+def numeric_ac(M, mapping):
     # M is a numpy matrix or array
     # numeric assortativity coefficient, pearsonr
     import numpy as np
@@ -262,12 +270,13 @@ def numeric_ac(M):
     if M.sum() != 1.0:
         M = M / float(M.sum())
     nx, ny = M.shape  # nx=ny
-    x = np.arange(nx)
-    y = np.arange(ny)
+    x = np.array(list(mapping.keys()))
+    y = x  # x and y have the same support
+    idx = list(mapping.values())
     a = M.sum(axis=0)
     b = M.sum(axis=1)
-    vara = (a * x ** 2).sum() - ((a * x).sum()) ** 2
-    varb = (b * x ** 2).sum() - ((b * x).sum()) ** 2
+    vara = (a[idx] * x ** 2).sum() - ((a[idx] * x).sum()) ** 2
+    varb = (b[idx] * y ** 2).sum() - ((b[idx] * y).sum()) ** 2
     xy = np.outer(x, y)
-    ab = np.outer(a, b)
+    ab = np.outer(a[idx], b[idx])
     return (xy * (M - ab)).sum() / np.sqrt(vara * varb)
diff --git a/networkx/algorithms/community/quality.py b/networkx/algorithms/community/quality.py
index ba972277c..9f374435f 100644
--- a/networkx/algorithms/community/quality.py
+++ b/networkx/algorithms/community/quality.py
@@ -3,8 +3,7 @@ communities).
 
 """
 
-from functools import wraps
-from itertools import product, combinations
+from itertools import combinations
 
 import networkx as nx
 from networkx import NetworkXError
@@ -78,7 +77,7 @@ def intra_community_edges(G, partition):
 
 
 def inter_community_edges(G, partition):
-    """Returns the number of inter-community edges for a prtition of `G`.
+    """Returns the number of inter-community edges for a partition of `G`.
     according to the given
     partition of the nodes of `G`.
 
@@ -112,9 +111,12 @@ def inter_community_non_edges(G, partition):
     """Returns the number of inter-community non-edges according to the
     given partition of the nodes of `G`.
 
-    `G` must be a NetworkX graph.
+    Parameters
+    ----------
+    G : NetworkX graph.
 
-    `partition` must be a partition of the nodes of `G`.
+    partition : iterable of sets of nodes
+        This must be a partition of the nodes of `G`.
 
     A *non-edge* is a pair of nodes (undirected if `G` is undirected)
     that are not adjacent in `G`. The *inter-community non-edges* are
@@ -145,8 +147,8 @@ def performance(G, partition):
     .. deprecated:: 2.6
        Use `partition_quality` instead.
 
-    The *performance* of a partition is the ratio of the number of
-    intra-community edges plus inter-community non-edges with the total
+    The *performance* of a partition is the number of
+    intra-community edges plus inter-community non-edges divided by the total
     number of potential edges.
 
     Parameters
@@ -358,8 +360,8 @@ def partition_quality(G, partition):
     The *coverage* of a partition is the ratio of the number of
     intra-community edges to the total number of edges in the graph.
 
-    The *performance* of a partition is the ratio of the number of
-    intra-community edges plus inter-community non-edges with the total
+    The *performance* of a partition is the number of
+    intra-community edges plus inter-community non-edges divided by the total
     number of potential edges.
 
     This algorithm has complexity $O(C^2 + L)$ where C is the number of communities and L is the number of links.


Test patch:
diff --git a/networkx/algorithms/approximation/tests/test_traveling_salesman.py b/networkx/algorithms/approximation/tests/test_traveling_salesman.py
index 78d933511..f36981d42 100644
--- a/networkx/algorithms/approximation/tests/test_traveling_salesman.py
+++ b/networkx/algorithms/approximation/tests/test_traveling_salesman.py
@@ -210,6 +210,11 @@ class TestSimulatedAnnealingTSP:
         cost = sum(self.UG2[n][nbr]["weight"] for n, nbr in pairwise(cycle))
         validate_symmetric_solution(cycle, cost, self.UG2_cycle, self.UG2_cost)
 
+    def test_error_on_input_order_mistake(self):
+        # see issue #4846 https://github.com/networkx/networkx/issues/4846
+        pytest.raises(TypeError, self.tsp, self.UG, weight="weight")
+        pytest.raises(nx.NetworkXError, self.tsp, self.UG, "weight")
+
     def test_not_complete_graph(self):
         pytest.raises(
             nx.NetworkXError,
diff --git a/networkx/algorithms/assortativity/tests/base_test.py b/networkx/algorithms/assortativity/tests/base_test.py
index 5b3712310..ee5b126c0 100644
--- a/networkx/algorithms/assortativity/tests/base_test.py
+++ b/networkx/algorithms/assortativity/tests/base_test.py
@@ -52,6 +52,10 @@ class BaseTestDegreeMixing:
         cls.W = nx.Graph()
         cls.W.add_edges_from([(0, 3), (1, 3), (2, 3)], weight=0.5)
         cls.W.add_edge(0, 2, weight=1)
+        S1 = nx.star_graph(4)
+        S2 = nx.star_graph(4)
+        cls.DS = nx.disjoint_union(S1, S2)
+        cls.DS.add_edge(4, 5)
 
 
 class BaseTestNumericMixing:
@@ -70,3 +74,10 @@ class BaseTestNumericMixing:
         F.add_edge(0, 2, weight=1)
         nx.set_node_attributes(F, dict(F.degree(weight="weight")), "margin")
         cls.F = F
+
+        M = nx.Graph()
+        M.add_nodes_from([1, 2], margin=-1)
+        M.add_nodes_from([3], margin=1)
+        M.add_nodes_from([4], margin=2)
+        M.add_edges_from([(3, 4), (1, 2), (1, 3)])
+        cls.M = M
diff --git a/networkx/algorithms/assortativity/tests/test_correlation.py b/networkx/algorithms/assortativity/tests/test_correlation.py
index 763f0a415..8da72652f 100644
--- a/networkx/algorithms/assortativity/tests/test_correlation.py
+++ b/networkx/algorithms/assortativity/tests/test_correlation.py
@@ -42,6 +42,10 @@ class TestDegreeMixingCorrelation(BaseTestDegreeMixing):
         r = nx.degree_assortativity_coefficient(self.W, weight="weight")
         np.testing.assert_almost_equal(r, -0.1429, decimal=4)
 
+    def test_degree_assortativity_double_star(self):
+        r = nx.degree_assortativity_coefficient(self.DS)
+        np.testing.assert_almost_equal(r, -0.9339, decimal=4)
+
 
 class TestAttributeMixingCorrelation(BaseTestAttributeMixing):
     def test_attribute_assortativity_undirected(self):
@@ -91,3 +95,7 @@ class TestNumericMixingCorrelation(BaseTestNumericMixing):
     def test_numeric_assortativity_float(self):
         r = nx.numeric_assortativity_coefficient(self.F, "margin")
         np.testing.assert_almost_equal(r, -0.1429, decimal=4)
+
+    def test_numeric_assortativity_mixed(self):
+        r = nx.numeric_assortativity_coefficient(self.M, "margin")
+        np.testing.assert_almost_equal(r, 0.4340, decimal=4)
diff --git a/networkx/conftest.py b/networkx/conftest.py
index 68dd1dda7..4f80d6bb3 100644
--- a/networkx/conftest.py
+++ b/networkx/conftest.py
@@ -7,7 +7,7 @@ General guidelines for writing good tests:
 - doctests always assume ``import networkx as nx`` so don't add that
 - prefer pytest fixtures over classes with setup methods.
 - use the ``@pytest.mark.parametrize``  decorator
-- use ``pytest.importskip`` for numpy, scipy, pandas, and matplotlib b/c of PyPy.
+- use ``pytest.importorskip`` for numpy, scipy, pandas, and matplotlib b/c of PyPy.
   and add the module to the relevant entries below.
 
 """