Repository: networkx/networkx

Issue:
Trophic levels (feature suggestion)
Would it be interesting to include an algorithm to calculate trophic levels?

Related notions which could be included are trophic difference and trophic coherence - see wikipedia [1] and [2]. 

This may be a duplicate of #577 from 2012, which was closed due to inactivity.

I've made an initial attempt over at [3], adding a module at `algorithms.centrality.trophic`.

1. https://en.wikipedia.org/wiki/Trophic_coherence
2. Stephen Levine (1980) Several measures of trophic structure applicable to complex food webs. J. theor. Biol. 83, 2, 195-207. https://doi.org/10.1016/0022-5193(80)90288-X
3. https://github.com/tomalrussell/networkx/commit/e715def4abe0a184c0934aa7d6a886b6d5ffe705

Discussion:
pep8speaks: Hello @tomalrussell! Thanks for opening this PR. We checked the lines you've touched for [PEP 8](https://www.python.org/dev/peps/pep-0008) issues, and found:

* In the file [`networkx/algorithms/centrality/__init__.py`](https://github.com/networkx/networkx/blob/0ecea08aa251d346a0a4fec3ab2cc7891b323151/networkx/algorithms/centrality/__init__.py):

> [Line 18:1](https://github.com/networkx/networkx/blob/0ecea08aa251d346a0a4fec3ab2cc7891b323151/networkx/algorithms/centrality/__init__.py#L18): [F403](https://duckduckgo.com/?q=pep8%20F403) 'from .trophic import *' used; unable to detect undefined names
> [Line 18:1](https://github.com/networkx/networkx/blob/0ecea08aa251d346a0a4fec3ab2cc7891b323151/networkx/algorithms/centrality/__init__.py#L18): [F401](https://duckduckgo.com/?q=pep8%20F401) '.trophic.*' imported but unused






dschult: Yes -- there are many modules that use numpy. Any that do are set up so that if numpy is not installed you can still import networkx. Take a look at a module that uses numpy. e.g. ```drawing/layout.py``` (and there may be better examples -- this is one I was looking at recently).  Mostly, you just import within the function that uses numpy instead of at the module level.

Testing is a little trickier because you don't want to run the tests that require numpy if numpy isn't available. But pytest actually makes it fairly straightforward.  Again, take a look at an existing test module, e.g. test_layout.py .  Ask if you have questions
tomalrussell: Thanks @dschult - that's working since https://github.com/networkx/networkx/pull/3804/commits/dfb792652dbcb4cd812a85611eed5d59550a7f3e with `pytest.importorskip` in the tests and try/except around `import numpy` within functions.

I'm not sure why codecov/patch is complaining - the only changes in this PR are adding new files, and they should be 100% covered. Is there anything I should do about this?
dschult: When I click on the codecov "Details" link and then on the "Diff" label, it shows which code has been run during a test and which hasn't. The error handling of no numpy obviously haven't been tested when the environment includes numpy, so that's not a worry. 

The only suggested change is to test a case when cannibalism is False and there are not self-loops.
The "Avoid copy otherwise" comment code doesn't get run during any tests. Minor for sure. But perhaps easy to fix??

Patch:
diff --git a/doc/reference/algorithms/centrality.rst b/doc/reference/algorithms/centrality.rst
index a9e235a90..cf3e0ba0e 100644
--- a/doc/reference/algorithms/centrality.rst
+++ b/doc/reference/algorithms/centrality.rst
@@ -132,6 +132,13 @@ Second Order Centrality
 
    second_order_centrality
 
+Trophic
+-------
+.. autosummary::
+   :toctree: generated/
+
+   trophic
+
 VoteRank
 -----------
 .. autosummary::
diff --git a/networkx/algorithms/centrality/__init__.py b/networkx/algorithms/centrality/__init__.py
index 99dccd628..c15304c89 100644
--- a/networkx/algorithms/centrality/__init__.py
+++ b/networkx/algorithms/centrality/__init__.py
@@ -15,4 +15,5 @@ from .load import *
 from .reaching import *
 from .percolation import *
 from .second_order import *
+from .trophic import *
 from .voterank_alg import *
diff --git a/networkx/algorithms/centrality/trophic.py b/networkx/algorithms/centrality/trophic.py
new file mode 100644
index 000000000..234441851
--- /dev/null
+++ b/networkx/algorithms/centrality/trophic.py
@@ -0,0 +1,169 @@
+"""Trophic levels"""
+import networkx as nx
+
+from networkx.utils import not_implemented_for
+
+__all__ = ['trophic_levels', 'trophic_differences',
+           'trophic_incoherence_parameter']
+
+
+@not_implemented_for('undirected')
+def trophic_levels(G, weight='weight'):
+    r"""Compute the trophic levels of nodes.
+
+    The trophic level of a node $i$ is
+
+    .. math::
+
+        s_i = 1 + \frac{1}{k_^{in}_i \sum_{j} a_{ij} s_j
+
+    where $k_^{in}_i$ is the in-degree of i
+
+    .. math::
+
+        k^{in}_i = \sum_{j} a_{ij}
+
+    and nodes with $k_^{in}_i = 0$ have $s_i = 1$ by convention.
+
+    These are calculated using the method outlined in Levine [1]_.
+
+    Parameters
+    ----------
+    G : DiGraph
+        A directed networkx graph
+
+    Returns
+    -------
+    nodes : dict
+        Dictionary of nodes with trophic level as the vale.
+
+    References
+    ----------
+    .. [1] Stephen Levine (1980) J. theor. Biol. 83, 195-207
+    """
+    try:
+        import numpy as np
+    except ImportError:
+        raise ImportError(
+            "trophic_levels() requires NumPy: http://scipy.org/")
+
+    # find adjacency matrix
+    a = nx.adjacency_matrix(G, weight=weight).T.toarray()
+
+    # drop rows/columns where in-degree is zero
+    rowsum = np.sum(a, axis=1)
+    p = a[rowsum != 0][:, rowsum != 0]
+    # normalise so sum of in-degree weights is 1 along each row
+    p = p / rowsum[rowsum != 0][:, np.newaxis]
+
+    # calculate trophic levels
+    nn = p.shape[0]
+    i = np.eye(nn)
+    try:
+        n = np.linalg.inv(i - p)
+    except np.linalg.LinAlgError as err:
+        # LinAlgError is raised when there is a non-basal node
+        msg = "Trophic levels are only defined for graphs where every " + \
+              "node has a path from a basal node (basal nodes are nodes " + \
+              "with no incoming edges)."
+        raise nx.NetworkXError(msg) from err
+    y = n.sum(axis=1) + 1
+
+    levels = {}
+
+    # all nodes with in-degree zero have trophic level == 1
+    zero_node_ids = (node_id for node_id, degree in G.in_degree if degree == 0)
+    for node_id in zero_node_ids:
+        levels[node_id] = 1
+
+    # all other nodes have levels as calculated
+    nonzero_node_ids = (node_id for node_id, degree in G.in_degree
+                        if degree != 0)
+    for i, node_id in enumerate(nonzero_node_ids):
+        levels[node_id] = y[i]
+
+    return levels
+
+
+@not_implemented_for('undirected')
+def trophic_differences(G, weight='weight'):
+    r"""Compute the trophic differences of the edges of a directed graph.
+
+    The trophic difference $x_ij$ for each edge is defined in Johnson et al.
+    [1]_ as:
+
+    .. math::
+        x_ij = s_j - s_i
+
+    Where $s_i$ is the trophic level of node $i$.
+
+    Parameters
+    ----------
+    G : DiGraph
+        A directed networkx graph
+
+    Returns
+    -------
+    diffs : dict
+        Dictionary of edges with trophic differences as the value.
+
+    References
+    ----------
+    .. [1] Samuel Johnson, Virginia Dominguez-Garcia, Luca Donetti, Miguel A.
+        Munoz (2014) PNAS "Trophic coherence determines food-web stability"
+    """
+    levels = trophic_levels(G, weight=weight)
+    diffs = {}
+    for u, v in G.edges:
+        diffs[(u, v)] = levels[v] - levels[u]
+    return diffs
+
+
+@not_implemented_for('undirected')
+def trophic_incoherence_parameter(G, weight='weight', cannibalism=False):
+    r"""Compute the trophic incoherence parameter of a graph.
+
+    Trophic coherence is defined as the homogeneity of the distribution of
+    trophic distances: the more similar, the more coherent. This is measured by
+    the standard deviation of the trophic differences and referred to as the
+    trophic incoherence parameter $q$ by [1].
+
+    Parameters
+    ----------
+    G : DiGraph
+        A directed networkx graph
+
+    cannibalism: Boolean
+        If set to False, self edges are not considered in the calculation
+
+    Returns
+    -------
+    trophic_incoherence_parameter : float
+        The trophic coherence of a graph
+
+    References
+    ----------
+    .. [1] Samuel Johnson, Virginia Dominguez-Garcia, Luca Donetti, Miguel A.
+        Munoz (2014) PNAS "Trophic coherence determines food-web stability"
+    """
+    try:
+        import numpy as np
+    except ImportError:
+        raise ImportError(
+            "trophic_incoherence_parameter() requires NumPy: " +
+            "http://scipy.org/")
+
+    if cannibalism:
+        diffs = trophic_differences(G, weight=weight)
+    else:
+        # If no cannibalism, remove self-edges
+        self_loops = list(nx.selfloop_edges(G))
+        if self_loops:
+            # Make a copy so we do not change G's edges in memory
+            G_2 = G.copy()
+            G_2.remove_edges_from(self_loops)
+        else:
+            # Avoid copy otherwise
+            G_2 = G
+        diffs = trophic_differences(G_2, weight=weight)
+    return np.std(list(diffs.values()))
diff --git a/networkx/algorithms/isomorphism/vf2userfunc.py b/networkx/algorithms/isomorphism/vf2userfunc.py
index a0d8edd5b..57213c084 100644
--- a/networkx/algorithms/isomorphism/vf2userfunc.py
+++ b/networkx/algorithms/isomorphism/vf2userfunc.py
@@ -53,20 +53,21 @@ def _semantic_feasibility(self, G1_node, G2_node):
     if self.edge_match is not None:
 
         # Cached lookups
-        G1_adj = self.G1_adj
-        G2_adj = self.G2_adj
+        G1nbrs = self.G1_adj[G1_node]
+        G2nbrs = self.G2_adj[G2_node]
         core_1 = self.core_1
         edge_match = self.edge_match
 
-        for neighbor in G1_adj[G1_node]:
+        for neighbor in G1nbrs:
             # G1_node is not in core_1, so we must handle R_self separately
             if neighbor == G1_node:
-                if not edge_match(G1_adj[G1_node][G1_node],
-                                  G2_adj[G2_node][G2_node]):
+                if G2_node in G2nbrs and \
+                        not edge_match(G1nbrs[G1_node], G2nbrs[G2_node]):
                     return False
             elif neighbor in core_1:
-                if not edge_match(G1_adj[G1_node][neighbor],
-                                  G2_adj[G2_node][core_1[neighbor]]):
+                G2_nbr = core_1[neighbor]
+                if G2_nbr in G2nbrs and \
+                        not edge_match(G1nbrs[neighbor], G2nbrs[G2_nbr]):
                     return False
         # syntactic check has already verified that neighbors are symmetric
 
diff --git a/networkx/drawing/nx_pylab.py b/networkx/drawing/nx_pylab.py
index ca5ab9573..4b2f34bed 100644
--- a/networkx/drawing/nx_pylab.py
+++ b/networkx/drawing/nx_pylab.py
@@ -638,12 +638,13 @@ def draw_networkx_edges(G, pos,
             shrink_source = 0  # space from source to tail
             shrink_target = 0  # space from  head to target
             if np.iterable(node_size):  # many node sizes
-                src_node, dst_node = edgelist[i][:2]
-                index_node = nodelist.index(dst_node)
-                marker_size = node_size[index_node]
-                shrink_target = to_marker_edge(marker_size, node_shape)
+                source, target = edgelist[i][:2]
+                source_node_size = node_size[nodelist.index(source)]
+                target_node_size = node_size[nodelist.index(target)]
+                shrink_source = to_marker_edge(source_node_size, node_shape)
+                shrink_target = to_marker_edge(target_node_size, node_shape)
             else:
-                shrink_target = to_marker_edge(node_size, node_shape)
+                shrink_source = shrink_target = to_marker_edge(node_size, node_shape)
 
             if shrink_source < min_source_margin:
                 shrink_source = min_source_margin
diff --git a/networkx/generators/lattice.py b/networkx/generators/lattice.py
index 9bc99ad1f..b4ac7d7f5 100644
--- a/networkx/generators/lattice.py
+++ b/networkx/generators/lattice.py
@@ -20,12 +20,11 @@ from networkx.algorithms.minors import contracted_nodes
 from networkx.algorithms.operators.product import cartesian_product
 from networkx.exception import NetworkXError
 from networkx.relabel import relabel_nodes
-from networkx.utils import flatten
-from networkx.utils import nodes_or_number
-from networkx.utils import pairwise
+from networkx.utils import flatten, nodes_or_number, pairwise, iterable
 from networkx.generators.classic import cycle_graph
 from networkx.generators.classic import empty_graph
 from networkx.generators.classic import path_graph
+from itertools import repeat
 
 __all__ = ['grid_2d_graph', 'grid_graph', 'hypercube_graph',
            'triangular_lattice_graph', 'hexagonal_lattice_graph']
@@ -43,9 +42,11 @@ def grid_2d_graph(m, n, periodic=False, create_using=None):
         If an integer, nodes are from `range(n)`.
         If a container, elements become the coordinate of the nodes.
 
-    periodic : bool (default: False)
-        If this is ``True`` the nodes on the grid boundaries are joined
-        to the corresponding nodes on the opposite grid boundaries.
+    periodic : bool or iterable
+        If `periodic` is True, both dimensions are periodic. If False, none
+        are periodic.  If `periodic` is iterable, it should yield 2 bool
+        values indicating whether the 1st and 2nd axes, respectively, are
+        periodic.
 
     create_using : NetworkX graph constructor, optional (default=nx.Graph)
         Graph type to create. If graph instance, then cleared before populated.
@@ -64,15 +65,20 @@ def grid_2d_graph(m, n, periodic=False, create_using=None):
                      for pi, i in pairwise(rows) for j in cols)
     G.add_edges_from(((i, j), (i, pj))
                      for i in rows for pj, j in pairwise(cols))
-    if periodic is True:
-        if len(rows) > 2:
-            first = rows[0]
-            last = rows[-1]
-            G.add_edges_from(((first, j), (last, j)) for j in cols)
-        if len(cols) > 2:
-            first = cols[0]
-            last = cols[-1]
-            G.add_edges_from(((i, first), (i, last)) for i in rows)
+
+    if iterable(periodic):
+        periodic_r, periodic_c = periodic
+    else:
+        periodic_r = periodic_c = periodic
+
+    if periodic_r and len(rows) > 2:
+        first = rows[0]
+        last = rows[-1]
+        G.add_edges_from(((first, j), (last, j)) for j in cols)
+    if periodic_c and len(cols) > 2:
+        first = cols[0]
+        last = cols[-1]
+        G.add_edges_from(((i, first), (i, last)) for i in rows)
     # both directions for directed
     if G.is_directed():
         G.add_edges_from((v, u) for u, v in G.edges())
@@ -93,9 +99,11 @@ def grid_graph(dim, periodic=False):
         that dimension. The dimension of the grid_graph is the length
         of `dim`.
 
-    periodic : bool
-        If `periodic is True` the nodes on the grid boundaries are joined
-        to the corresponding nodes on the opposite grid boundaries.
+    periodic : bool or iterable
+        If `periodic` is True, all dimensions are periodic. If False all
+        dimensions are not periodic. If `periodic` is iterable, it should
+        yield `dim` bool values each of which indicates whether the
+        corresponding axis is periodic.
 
     Returns
     -------
@@ -117,10 +125,14 @@ def grid_graph(dim, periodic=False):
     if not dim:
         return empty_graph(0)
 
-    func = cycle_graph if periodic else path_graph
-    G = func(dim[0])
+    if iterable(periodic):
+        func = (cycle_graph if p else path_graph for p in periodic)
+    else:
+        func = repeat(cycle_graph if periodic else path_graph)
+
+    G = next(func)(dim[0])
     for current_dim in dim[1:]:
-        Gnew = func(current_dim)
+        Gnew = next(func)(current_dim)
         G = cartesian_product(Gnew, G)
     # graph G is done but has labels of the form (1, (2, (3, 1))) so relabel
     H = relabel_nodes(G, flatten)


Test patch:
diff --git a/networkx/algorithms/centrality/tests/test_trophic.py b/networkx/algorithms/centrality/tests/test_trophic.py
new file mode 100644
index 000000000..9240f43f5
--- /dev/null
+++ b/networkx/algorithms/centrality/tests/test_trophic.py
@@ -0,0 +1,285 @@
+"""Test trophic levels, trophic differences and trophic coherence
+"""
+import pytest
+np = pytest.importorskip('numpy')
+
+import networkx as nx
+from networkx.testing import almost_equal
+
+
+def test_trophic_levels():
+    """Trivial example
+    """
+    G = nx.DiGraph()
+    G.add_edge("a", "b")
+    G.add_edge("b", "c")
+
+    d = nx.trophic_levels(G)
+    assert d == {"a": 1, "b": 2, "c": 3}
+
+
+def test_trophic_levels_levine():
+    """Example from Figure 5 in Stephen Levine (1980) J. theor. Biol. 83,
+    195-207
+    """
+    S = nx.DiGraph()
+    S.add_edge(1, 2, weight=1.0)
+    S.add_edge(1, 3, weight=0.2)
+    S.add_edge(1, 4, weight=0.8)
+    S.add_edge(2, 3, weight=0.2)
+    S.add_edge(2, 5, weight=0.3)
+    S.add_edge(4, 3, weight=0.6)
+    S.add_edge(4, 5, weight=0.7)
+    S.add_edge(5, 4, weight=0.2)
+
+    # save copy for later, test intermediate implementation details first
+    S2 = S.copy()
+
+    # drop nodes of in-degree zero
+    z = [nid for nid, d in S.in_degree if d == 0]
+    for nid in z:
+        S.remove_node(nid)
+
+    # find adjacency matrix
+    q = nx.linalg.graphmatrix.adjacency_matrix(S).T
+
+    expected_q = np.array([
+        [0, 0, 0., 0],
+        [0.2, 0, 0.6, 0],
+        [0, 0, 0, 0.2],
+        [0.3, 0, 0.7, 0]
+    ])
+    assert np.array_equal(q.todense(), expected_q)
+
+    # must be square, size of number of nodes
+    assert len(q.shape) == 2
+    assert q.shape[0] == q.shape[1]
+    assert q.shape[0] == len(S)
+
+    nn = q.shape[0]
+
+    i = np.eye(nn)
+    n = np.linalg.inv(i - q)
+    y = np.dot(np.asarray(n), np.ones(nn))
+
+    expected_y = np.array([1, 2.07906977, 1.46511628, 2.3255814])
+    assert np.allclose(y, expected_y)
+
+    expected_d = {
+        1: 1,
+        2: 2,
+        3: 3.07906977,
+        4: 2.46511628,
+        5: 3.3255814
+    }
+
+    d = nx.trophic_levels(S2)
+
+    for nid, level in d.items():
+        expected_level = expected_d[nid]
+        assert almost_equal(expected_level, level)
+
+
+def test_trophic_levels_simple():
+    matrix_a = np.array([[0, 0], [1, 0]])
+    G = nx.from_numpy_matrix(matrix_a, create_using=nx.DiGraph)
+    d = nx.trophic_levels(G)
+    assert almost_equal(d[0], 2)
+    assert almost_equal(d[1], 1)
+
+
+def test_trophic_levels_more_complex():
+    matrix = np.array([
+        [0, 1, 0, 0],
+        [0, 0, 1, 0],
+        [0, 0, 0, 1],
+        [0, 0, 0, 0]
+    ])
+    G = nx.from_numpy_matrix(matrix, create_using=nx.DiGraph)
+    d = nx.trophic_levels(G)
+    expected_result = [1, 2, 3, 4]
+    for ind in range(4):
+        assert almost_equal(d[ind], expected_result[ind])
+
+    matrix = np.array([
+        [0, 1, 1, 0],
+        [0, 0, 1, 1],
+        [0, 0, 0, 1],
+        [0, 0, 0, 0]
+    ])
+    G = nx.from_numpy_matrix(matrix, create_using=nx.DiGraph)
+    d = nx.trophic_levels(G)
+
+    expected_result = [1, 2, 2.5, 3.25]
+    print("Calculated result: ", d)
+    print("Expected Result: ", expected_result)
+
+    for ind in range(4):
+        assert almost_equal(d[ind], expected_result[ind])
+
+
+def test_trophic_levels_even_more_complex():
+    # Another, bigger matrix
+    matrix = np.array([
+        [0, 0, 0, 0, 0],
+        [0, 1, 0, 1, 0],
+        [1, 0, 0, 0, 0],
+        [0, 1, 0, 0, 0],
+        [0, 0, 0, 1, 0]
+    ])
+
+    # Generated this linear system using pen and paper:
+    K = np.array([
+        [1, 0, -1, 0, 0],
+        [0, 0.5, 0, -0.5, 0],
+        [0, 0, 1, 0, 0],
+        [0, -0.5, 0, 1, -0.5],
+        [0, 0, 0, 0, 1],
+    ])
+    result_1 = np.ravel(np.matmul(np.linalg.inv(K), np.ones(5)))
+    G = nx.from_numpy_matrix(matrix, create_using=nx.DiGraph)
+    result_2 = nx.trophic_levels(G)
+
+    for ind in range(5):
+        assert almost_equal(result_1[ind], result_2[ind])
+
+
+def test_trophic_levels_singular_matrix():
+    """Should raise an error with graphs with only non-basal nodes
+    """
+    matrix = np.identity(4)
+    G = nx.from_numpy_matrix(matrix, create_using=nx.DiGraph)
+    with pytest.raises(nx.NetworkXError) as e:
+        nx.trophic_levels(G)
+    msg = "Trophic levels are only defined for graphs where every node " + \
+          "has a path from a basal node (basal nodes are nodes with no " + \
+          "incoming edges)."
+    assert msg in str(e.value)
+
+
+def test_trophic_levels_singular_with_basal():
+    """Should fail to compute if there are any parts of the graph which are not
+    reachable from any basal node (with in-degree zero).
+    """
+    G = nx.DiGraph()
+    # a has in-degree zero
+    G.add_edge('a', 'b')
+
+    # b is one level above a, c and d
+    G.add_edge('c', 'b')
+    G.add_edge('d', 'b')
+
+    # c and d form a loop, neither are reachable from a
+    G.add_edge('c', 'd')
+    G.add_edge('d', 'c')
+
+    with pytest.raises(nx.NetworkXError) as e:
+        nx.trophic_levels(G)
+    msg = "Trophic levels are only defined for graphs where every node " + \
+          "has a path from a basal node (basal nodes are nodes with no " + \
+          "incoming edges)."
+    assert msg in str(e.value)
+
+    # if self-loops are allowed, smaller example:
+    G = nx.DiGraph()
+    G.add_edge('a', 'b')  # a has in-degree zero
+    G.add_edge('c', 'b')  # b is one level above a and c
+    G.add_edge('c', 'c')  # c has a self-loop
+    with pytest.raises(nx.NetworkXError) as e:
+        nx.trophic_levels(G)
+    msg = "Trophic levels are only defined for graphs where every node " + \
+          "has a path from a basal node (basal nodes are nodes with no " + \
+          "incoming edges)."
+    assert msg in str(e.value)
+
+
+def test_trophic_differences():
+    matrix_a = np.array([[0, 1], [0, 0]])
+    G = nx.from_numpy_matrix(matrix_a, create_using=nx.DiGraph)
+    diffs = nx.trophic_differences(G)
+    assert almost_equal(diffs[(0, 1)], 1)
+
+    matrix_b = np.array([
+        [0, 1, 1, 0],
+        [0, 0, 1, 1],
+        [0, 0, 0, 1],
+        [0, 0, 0, 0]
+    ])
+    G = nx.from_numpy_matrix(matrix_b, create_using=nx.DiGraph)
+    diffs = nx.trophic_differences(G)
+
+    assert almost_equal(diffs[(0, 1)], 1)
+    assert almost_equal(diffs[(0, 2)], 1.5)
+    assert almost_equal(diffs[(1, 2)], 0.5)
+    assert almost_equal(diffs[(1, 3)], 1.25)
+    assert almost_equal(diffs[(2, 3)], 0.75)
+
+
+def test_trophic_incoherence_parameter_no_cannibalism():
+    matrix_a = np.array([[0, 1], [0, 0]])
+    G = nx.from_numpy_matrix(matrix_a, create_using=nx.DiGraph)
+    q = nx.trophic_incoherence_parameter(G, cannibalism=False)
+    assert almost_equal(q, 0)
+
+    matrix_b = np.array([
+        [0, 1, 1, 0],
+        [0, 0, 1, 1],
+        [0, 0, 0, 1],
+        [0, 0, 0, 0]
+    ])
+    G = nx.from_numpy_matrix(matrix_b, create_using=nx.DiGraph)
+    q = nx.trophic_incoherence_parameter(G, cannibalism=False)
+    assert almost_equal(q, np.std([1, 1.5, 0.5, 0.75, 1.25]))
+
+    matrix_c = np.array([
+        [0, 1, 1, 0],
+        [0, 1, 1, 1],
+        [0, 0, 0, 1],
+        [0, 0, 0, 1]
+    ])
+    G = nx.from_numpy_matrix(matrix_c, create_using=nx.DiGraph)
+    q = nx.trophic_incoherence_parameter(G, cannibalism=False)
+    # Ignore the -link
+    assert almost_equal(q, np.std([1, 1.5, 0.5, 0.75, 1.25]))
+
+    # no self-loops case
+    matrix_d = np.array([
+        [0, 1, 1, 0],
+        [0, 0, 1, 1],
+        [0, 0, 0, 1],
+        [0, 0, 0, 0]
+    ])
+    G = nx.from_numpy_matrix(matrix_d, create_using=nx.DiGraph)
+    q = nx.trophic_incoherence_parameter(G, cannibalism=False)
+    # Ignore the -link
+    assert almost_equal(q, np.std([1, 1.5, 0.5, 0.75, 1.25]))
+
+
+
+def test_trophic_incoherence_parameter_cannibalism():
+    matrix_a = np.array([[0, 1], [0, 0]])
+    G = nx.from_numpy_matrix(matrix_a, create_using=nx.DiGraph)
+    q = nx.trophic_incoherence_parameter(G, cannibalism=True)
+    assert almost_equal(q, 0)
+
+    matrix_b = np.array([
+        [0, 0, 0, 0, 0],
+        [0, 1, 0, 1, 0],
+        [1, 0, 0, 0, 0],
+        [0, 1, 0, 0, 0],
+        [0, 0, 0, 1, 0]
+    ])
+    G = nx.from_numpy_matrix(matrix_b, create_using=nx.DiGraph)
+    q = nx.trophic_incoherence_parameter(G, cannibalism=True)
+    assert almost_equal(q, 2)
+
+    matrix_c = np.array([
+        [0, 1, 1, 0],
+        [0, 0, 1, 1],
+        [0, 0, 0, 1],
+        [0, 0, 0, 0]
+    ])
+    G = nx.from_numpy_matrix(matrix_c, create_using=nx.DiGraph)
+    q = nx.trophic_incoherence_parameter(G, cannibalism=True)
+    # Ignore the -link
+    assert almost_equal(q, np.std([1, 1.5, 0.5, 0.75, 1.25]))
diff --git a/networkx/algorithms/isomorphism/tests/test_isomorphvf2.py b/networkx/algorithms/isomorphism/tests/test_isomorphvf2.py
index 577b514d5..2ee418494 100644
--- a/networkx/algorithms/isomorphism/tests/test_isomorphvf2.py
+++ b/networkx/algorithms/isomorphism/tests/test_isomorphvf2.py
@@ -318,3 +318,20 @@ def test_noncomparable_nodes():
     assert dgm.is_isomorphic()
     # Just testing some cases
     assert gm.subgraph_is_monomorphic()
+
+
+def test_monomorphism_edge_match():
+    G = nx.DiGraph()
+    G.add_node(1)
+    G.add_node(2)
+    G.add_edge(1, 2, label="A")
+    G.add_edge(2, 1, label="B")
+    G.add_edge(2, 2, label="C")
+
+    SG = nx.DiGraph()
+    SG.add_node(5)
+    SG.add_node(6)
+    SG.add_edge(5, 6, label="A")
+
+    gm = iso.DiGraphMatcher(G, SG, edge_match=iso.categorical_edge_match('label', None))
+    assert gm.subgraph_is_monomorphic()
diff --git a/networkx/algorithms/shortest_paths/astar.py b/networkx/algorithms/shortest_paths/astar.py
index 7ad0e34e1..538017dea 100644
--- a/networkx/algorithms/shortest_paths/astar.py
+++ b/networkx/algorithms/shortest_paths/astar.py
@@ -5,11 +5,11 @@ from itertools import count
 
 import networkx as nx
 from networkx.utils import not_implemented_for
+from networkx.algorithms.shortest_paths.weighted import _weight_function
 
 __all__ = ['astar_path', 'astar_path_length']
 
 
-@not_implemented_for('multigraph')
 def astar_path(G, source, target, heuristic=None, weight='weight'):
     """Returns a list of nodes in a shortest path between source and target
     using the A* ("A-star") algorithm.
@@ -70,6 +70,7 @@ def astar_path(G, source, target, heuristic=None, weight='weight'):
 
     push = heappush
     pop = heappop
+    weight = _weight_function(G, weight)
 
     # The queue stores priority, node, cost to reach, and parent.
     # Uses Python heapq to keep in priority order.
@@ -112,7 +113,7 @@ def astar_path(G, source, target, heuristic=None, weight='weight'):
         explored[curnode] = parent
 
         for neighbor, w in G[curnode].items():
-            ncost = dist + w.get(weight, 1)
+            ncost = dist + weight(curnode, neighbor, w)
             if neighbor in enqueued:
                 qcost, h = enqueued[neighbor]
                 # if qcost <= ncost, a less costly path from the
@@ -162,5 +163,6 @@ def astar_path_length(G, source, target, heuristic=None, weight='weight'):
         msg = f"Either source {source} or target {target} is not in G"
         raise nx.NodeNotFound(msg)
 
+    weight = _weight_function(G, weight)
     path = astar_path(G, source, target, heuristic, weight)
-    return sum(G[u][v].get(weight, 1) for u, v in zip(path[:-1], path[1:]))
+    return sum(weight(u, v, G[u][v]) for u, v in zip(path[:-1], path[1:]))
diff --git a/networkx/algorithms/shortest_paths/tests/test_astar.py b/networkx/algorithms/shortest_paths/tests/test_astar.py
index c4012c7de..ad8cde30f 100644
--- a/networkx/algorithms/shortest_paths/tests/test_astar.py
+++ b/networkx/algorithms/shortest_paths/tests/test_astar.py
@@ -39,9 +39,9 @@ class TestAStar:
 
     def test_astar_multigraph(self):
         G = nx.MultiDiGraph(self.XG)
-        pytest.raises(nx.NetworkXNotImplemented, nx.astar_path, G, 's', 'v')
-        pytest.raises(nx.NetworkXNotImplemented, nx.astar_path_length,
-                      G, 's', 'v')
+        G.add_weighted_edges_from((u, v, 1000) for (u, v) in list(G.edges()))
+        assert nx.astar_path(G, 's', 'v') == ['s', 'x', 'u', 'v']
+        assert nx.astar_path_length(G, 's', 'v') == 9
 
     def test_astar_undirected(self):
         GG = self.XG.to_undirected()
diff --git a/networkx/algorithms/shortest_paths/tests/test_weighted.py b/networkx/algorithms/shortest_paths/tests/test_weighted.py
index 8176dd8f8..d8f44ac62 100644
--- a/networkx/algorithms/shortest_paths/tests/test_weighted.py
+++ b/networkx/algorithms/shortest_paths/tests/test_weighted.py
@@ -4,21 +4,27 @@ import networkx as nx
 from networkx.utils import pairwise
 
 
-def validate_path(G, s, t, soln_len, path):
+def validate_path(G, s, t, soln_len, path, weight='weight'):
     assert path[0] == s
     assert path[-1] == t
-    if not G.is_multigraph():
-        computed = sum(G[u][v].get('weight', 1) for u, v in pairwise(path))
-        assert soln_len == computed
+
+    if callable(weight):
+        weight_f = weight
     else:
-        computed = sum(min(e.get('weight', 1) for e in G[u][v].values())
-                       for u, v in pairwise(path))
-        assert soln_len == computed
+        if G.is_multigraph():
+            def weight_f(u, v, d):
+                return min(e.get(weight, 1) for e in d.values())
+        else:
+            def weight_f(u, v, d):
+                return d.get(weight, 1)
+
+    computed = sum(weight_f(u, v, G[u][v]) for u, v in pairwise(path))
+    assert soln_len == computed
 
 
-def validate_length_path(G, s, t, soln_len, length, path):
+def validate_length_path(G, s, t, soln_len, length, path, weight='weight'):
     assert soln_len == length
-    validate_path(G, s, t, length, path)
+    validate_path(G, s, t, length, path, weight=weight)
 
 
 class WeightedTestBase:
@@ -142,6 +148,52 @@ class TestWeightedPath(WeightedTestBase):
         G = nx.path_graph(2)
         pytest.raises(nx.NodeNotFound, nx.bidirectional_dijkstra, G, 3, 0)
 
+    def test_weight_functions(self):
+        def heuristic(*z):
+            return hash(z)
+
+        def getpath(pred, v, s):
+            return [v] if v == s else getpath(pred, pred[v], s) + [v]
+
+        def goldberg_radzik(g, s, t, weight='weight'):
+            pred, dist = nx.goldberg_radzik(g, s, weight=weight)
+            dist = dist[t]
+            return dist, getpath(pred, t, s)
+
+        def astar(g, s, t, weight='weight'):
+            path = nx.astar_path(g, s, t, heuristic, weight=weight)
+            dist = nx.astar_path_length(g, s, t, heuristic, weight=weight)
+            return dist, path
+
+        def vlp(G, s, t, l, F, w):
+            res = F(G, s, t, weight=w)
+            validate_length_path(G, s, t, l, *res, weight=w)
+
+        G = self.cycle
+        s = 6
+        t = 4
+        path = [6] + list(range(t + 1))
+
+        def weight(u, v, _):
+            return 1 + v**2
+
+        length = sum(weight(u, v, None) for u, v in pairwise(path))
+        vlp(G, s, t, length, nx.bidirectional_dijkstra, weight)
+        vlp(G, s, t, length, nx.single_source_dijkstra, weight)
+        vlp(G, s, t, length, nx.single_source_bellman_ford, weight)
+        vlp(G, s, t, length, goldberg_radzik, weight)
+        vlp(G, s, t, length, astar, weight)
+
+        def weight(u, v, _):
+            return 2**(u * v)
+
+        length = sum(weight(u, v, None) for u, v in pairwise(path))
+        vlp(G, s, t, length, nx.bidirectional_dijkstra, weight)
+        vlp(G, s, t, length, nx.single_source_dijkstra, weight)
+        vlp(G, s, t, length, nx.single_source_bellman_ford, weight)
+        vlp(G, s, t, length, goldberg_radzik, weight)
+        vlp(G, s, t, length, astar, weight)
+
     def test_bidirectional_dijkstra_no_path(self):
         with pytest.raises(nx.NetworkXNoPath):
             G = nx.Graph()
diff --git a/networkx/algorithms/shortest_paths/weighted.py b/networkx/algorithms/shortest_paths/weighted.py
index 2832944bd..faa60aa31 100644
--- a/networkx/algorithms/shortest_paths/weighted.py
+++ b/networkx/algorithms/shortest_paths/weighted.py
@@ -1279,7 +1279,7 @@ def _bellman_ford(G, source, weight, pred=None, paths=None, dist=None,
         if all(pred_u not in in_q for pred_u in pred[u]):
             dist_u = dist[u]
             for v, e in G_succ[u].items():
-                dist_v = dist_u + weight(v, u, e)
+                dist_v = dist_u + weight(u, v, e)
 
                 if dist_v < dist.get(v, inf):
                     if v not in in_q:
@@ -1997,6 +1997,8 @@ def bidirectional_dijkstra(G, source, target, weight='weight'):
 
     if source == target:
         return (0, [source])
+
+    weight = _weight_function(G, weight)
     push = heappush
     pop = heappop
     # Init:  [Forward, Backward]
@@ -2010,9 +2012,9 @@ def bidirectional_dijkstra(G, source, target, weight='weight'):
     push(fringe[1], (0, next(c), target))
     # neighs for extracting correct neighbor information
     if G.is_directed():
-        neighs = [G.successors, G.predecessors]
+        neighs = [G._succ, G._pred]
     else:
-        neighs = [G.neighbors, G.neighbors]
+        neighs = [G._adj, G._adj]
     # variables to hold shortest discovered path
     # finaldist = 1e30000
     finalpath = []
@@ -2033,22 +2035,11 @@ def bidirectional_dijkstra(G, source, target, weight='weight'):
             # we have now discovered the shortest path
             return (finaldist, finalpath)
 
-        for w in neighs[dir](v):
+        for w, d in neighs[dir][v].items():
             if(dir == 0):  # forward
-                if G.is_multigraph():
-                    minweight = min((dd.get(weight, 1)
-                                     for k, dd in G[v][w].items()))
-                else:
-                    minweight = G[v][w].get(weight, 1)
-                vwLength = dists[dir][v] + minweight  # G[v][w].get(weight,1)
+                vwLength = dists[dir][v] + weight(v, w, d)
             else:  # back, must remember to change v,w->w,v
-                if G.is_multigraph():
-                    minweight = min((dd.get(weight, 1)
-                                     for k, dd in G[w][v].items()))
-                else:
-                    minweight = G[w][v].get(weight, 1)
-                vwLength = dists[dir][v] + minweight  # G[w][v].get(weight,1)
-
+                vwLength = dists[dir][v] + weight(w, v, d)
             if w in dists[dir]:
                 if vwLength < dists[dir][w]:
                     raise ValueError(
diff --git a/networkx/generators/tests/test_lattice.py b/networkx/generators/tests/test_lattice.py
index d164bccf0..839b88e87 100644
--- a/networkx/generators/tests/test_lattice.py
+++ b/networkx/generators/tests/test_lattice.py
@@ -4,6 +4,7 @@ import pytest
 
 import networkx as nx
 from networkx.testing import assert_edges_equal
+from itertools import product
 
 
 class TestGrid2DGraph:
@@ -46,6 +47,13 @@ class TestGrid2DGraph:
             G = nx.grid_2d_graph(m, n, periodic=True)
             assert nx.could_be_isomorphic(G, H)
 
+    def test_periodic_iterable(self):
+        m, n = 3, 7
+        for a, b in product([0, 1], [0, 1]):
+            G = nx.grid_2d_graph(m, n, periodic=(a, b))
+            assert G.number_of_nodes() == m * n
+            assert G.number_of_edges() == (m + a - 1) * n + (n + b - 1) * m
+
     def test_periodic_directed(self):
         G = nx.grid_2d_graph(4, 2, periodic=True)
         H = nx.grid_2d_graph(4, 2, periodic=True, create_using=nx.DiGraph())
@@ -98,6 +106,16 @@ class TestGridGraph:
         assert len(G) == 2 * 3
         assert nx.is_isomorphic(G, nx.grid_graph([2, 3]))
 
+    def test_periodic_iterable(self):
+        m, n, k = 3, 7, 5
+        for a, b, c in product([0, 1], [0, 1], [0, 1]):
+            G = nx.grid_graph([m, n, k], periodic=(a, b, c))
+            num_e = ((m + a - 1) * n * k
+                     + (n + b - 1) * m * k
+                     + (k + c - 1) * m * n)
+            assert G.number_of_nodes() == m * n * k
+            assert G.number_of_edges() == num_e
+
 
 class TestHypercubeGraph:
     """Unit tests for :func:`networkx.generators.lattice.hypercube_graph`"""