add simple cycle enumerator for undirected class (#6461)

* add simple cycle enumerator for undirected class

* Implemented Gupta & Suzumura and refactored Johnson in a common form
and unified their call-site.  Now, users can enumerate simple cycles
of directed or undireced graphs, with bounded or unbounded length,
all from the same `simple_cycles` function.  I abandoned the stretch
goal of enumerating chordless cycles, as they are not gracefully
handled by the algorithms of Johnson nor Gupta & Suzumura.

* updated tests for simple_cycles to include undirected graphs

* * fixed documentation issues, elaborated on algorithm details
* restricted to nontrivial components
* removed specialized DFS to pick edges from undirected components
    lemma: if G is a biconnected graph with at least 3 nodes and
    e is an edge in G, then e belongs to a cycle

* added tests for undirected and bounded cases for simple_cycles

* added handling for digons in multigraphs

* * Improved support for multigraphs
* Split chordless_cycles out from simple_cycles because the case
  analysis got so tricky
* Added enhanced cycle-testing framework to tests for simple_cycles
* Added tests for multigraphs
* Needs more documentation

* * Documented simple_cycles
* Caught incorrectly-handled case of parallel self-loops

* removed chordless option from simple_cycles

* typos/raises/leftovers in docs and error/corner tests

* add a quick example to chordless_cycles

* Add chordless_cycles to docs

---------

Co-authored-by: Dan Schult <dschult@colgate.edu>
Co-authored-by: Mridul Seth <git@mriduls.com>

3 files changed, 1132 insertions, 88 deletions

diff --git a/doc/reference/algorithms/cycles.rst b/doc/reference/algorithms/cycles.rst
index 94cf3f8d..fe97e4de 100644
--- a/doc/reference/algorithms/cycles.rst
+++ b/doc/reference/algorithms/cycles.rst
@@ -11,3 +11,4 @@ Cycles
    recursive_simple_cycles
    find_cycle
    minimum_cycle_basis
+   chordless_cycles
diff --git a/networkx/algorithms/cycles.py b/networkx/algorithms/cycles.py
index 2ab610cd..21138d8c 100644
--- a/networkx/algorithms/cycles.py
+++ b/networkx/algorithms/cycles.py
@@ -5,6 +5,7 @@ Cycle finding algorithms
 """
 
 from collections import defaultdict
+from itertools import combinations, product
 
 import networkx as nx
 from networkx.utils import not_implemented_for, pairwise
@@ -15,6 +16,7 @@ __all__ = [
     "recursive_simple_cycles",
     "find_cycle",
     "minimum_cycle_basis",
+    "chordless_cycles",
 ]
 
 
@@ -95,22 +97,44 @@ def cycle_basis(G, root=None):
     return cycles
 
 
-@not_implemented_for("undirected")
-def simple_cycles(G):
-    """Find simple cycles (elementary circuits) of a directed graph.
+def simple_cycles(G, length_bound=None):
+    """Find simple cycles (elementary circuits) of a graph.
 
     A `simple cycle`, or `elementary circuit`, is a closed path where
-    no node appears twice. Two elementary circuits are distinct if they
-    are not cyclic permutations of each other.
-
-    This is a nonrecursive, iterator/generator version of Johnson's
-    algorithm [1]_.  There may be better algorithms for some cases [2]_ [3]_.
+    no node appears twice.  In a directed graph, two simple cycles are distinct
+    if they are not cyclic permutations of each other.  In an undirected graph,
+    two simple cycles are distinct if they are not cyclic permutations of each
+    other nor of the other's reversal.
+
+    Optionally, the cycles are bounded in length.  In the unbounded case, we use
+    a nonrecursive, iterator/generator version of Johnson's algorithm [1]_.  In
+    the bounded case, we use a version of the algorithm of Gupta and
+    Suzumura[2]_. There may be better algorithms for some cases [3]_ [4]_ [5]_.
+
+    The algorithms of Johnson, and Gupta and Suzumura, are enhanced by some
+    well-known preprocessing techniques.  When G is directed, we restrict our
+    attention to strongly connected components of G, generate all simple cycles
+    containing a certain node, remove that node, and further decompose the
+    remainder into strongly connected components.  When G is undirected, we
+    restrict our attention to biconnected components, generate all simple cycles
+    containing a particular edge, remove that edge, and further decompose the
+    remainder into biconnected components.
+
+    Note that multigraphs are supported by this function -- and in undirected
+    multigraphs, a pair of parallel edges is considered a cycle of length 2.
+    Likewise, self-loops are considered to be cycles of length 1.  We define
+    cycles as sequences of nodes; so the presence of loops and parallel edges
+    does not change the number of simple cycles in a graph.
 
     Parameters
     ----------
     G : NetworkX DiGraph
        A directed graph
 
+    length_bound : int or None, optional (default=None)
+       If length_bound is an int, generate all simple cycles of G with length at
+       most length_bound.  Otherwise, generate all simple cycles of G.
+
     Yields
     ------
     list of nodes
@@ -134,92 +158,602 @@ def simple_cycles(G):
 
     Notes
     -----
-    The implementation follows pp. 79-80 in [1]_.
+    When length_bound is None, the time complexity is $O((n+e)(c+1))$ for $n$
+    nodes, $e$ edges and $c$ simple circuits.  Otherwise, when length_bound > 1,
+    the time complexity is $O((c+n)(k-1)d^k)$ where $d$ is the average degree of
+    the nodes of G and $k$ = length_bound.
 
-    The time complexity is $O((n+e)(c+1))$ for $n$ nodes, $e$ edges and $c$
-    elementary circuits.
+    Raises
+    ------
+    ValueError
+        when length_bound < 0.
 
     References
     ----------
     .. [1] Finding all the elementary circuits of a directed graph.
        D. B. Johnson, SIAM Journal on Computing 4, no. 1, 77-84, 1975.
        https://doi.org/10.1137/0204007
-    .. [2] Enumerating the cycles of a digraph: a new preprocessing strategy.
+    .. [2] Finding All Bounded-Length Simple Cycles in a Directed Graph
+       A. Gupta and T. Suzumura https://arxiv.org/abs/2105.10094
+    .. [3] Enumerating the cycles of a digraph: a new preprocessing strategy.
        G. Loizou and P. Thanish, Information Sciences, v. 27, 163-182, 1982.
-    .. [3] A search strategy for the elementary cycles of a directed graph.
+    .. [4] A search strategy for the elementary cycles of a directed graph.
        J.L. Szwarcfiter and P.E. Lauer, BIT NUMERICAL MATHEMATICS,
        v. 16, no. 2, 192-204, 1976.
+    .. [5] Optimal Listing of Cycles and st-Paths in Undirected Graphs
+        R. Ferreira and R. Grossi and A. Marino and N. Pisanti and R. Rizzi and
+        G. Sacomoto https://arxiv.org/abs/1205.2766
 
     See Also
     --------
     cycle_basis
+    chordless_cycles
     """
 
-    def _unblock(thisnode, blocked, B):
-        stack = {thisnode}
-        while stack:
-            node = stack.pop()
-            if node in blocked:
-                blocked.remove(node)
-                stack.update(B[node])
-                B[node].clear()
+    if length_bound is not None:
+        if length_bound == 0:
+            return
+        elif length_bound < 0:
+            raise ValueError("length bound must be non-negative")
 
-    # Johnson's algorithm requires some ordering of the nodes.
-    # We assign the arbitrary ordering given by the strongly connected comps
-    # There is no need to track the ordering as each node removed as processed.
-    # Also we save the actual graph so we can mutate it. We only take the
-    # edges because we do not want to copy edge and node attributes here.
-    subG = type(G)(G.edges())
-    sccs = [scc for scc in nx.strongly_connected_components(subG) if len(scc) > 1]
+    directed = G.is_directed()
+    yield from ([v] for v, Gv in G.adj.items() if v in Gv)
 
-    # Johnson's algorithm exclude self cycle edges like (v, v)
-    # To be backward compatible, we record those cycles in advance
-    # and then remove from subG
-    for v in subG:
-        if subG.has_edge(v, v):
-            yield [v]
-            subG.remove_edge(v, v)
-
-    while sccs:
-        scc = sccs.pop()
-        sccG = subG.subgraph(scc)
-        # order of scc determines ordering of nodes
-        startnode = scc.pop()
-        # Processing node runs "circuit" routine from recursive version
-        path = [startnode]
-        blocked = set()  # vertex: blocked from search?
-        closed = set()  # nodes involved in a cycle
-        blocked.add(startnode)
-        B = defaultdict(set)  # graph portions that yield no elementary circuit
-        stack = [(startnode, list(sccG[startnode]))]  # sccG gives comp nbrs
-        while stack:
-            thisnode, nbrs = stack[-1]
-            if nbrs:
-                nextnode = nbrs.pop()
-                if nextnode == startnode:
-                    yield path[:]
-                    closed.update(path)
-                #                        print "Found a cycle", path, closed
-                elif nextnode not in blocked:
-                    path.append(nextnode)
-                    stack.append((nextnode, list(sccG[nextnode])))
-                    closed.discard(nextnode)
-                    blocked.add(nextnode)
-                    continue
-            # done with nextnode... look for more neighbors
-            if not nbrs:  # no more nbrs
-                if thisnode in closed:
-                    _unblock(thisnode, blocked, B)
+    if length_bound is not None and length_bound == 1:
+        return
+
+    if G.is_multigraph() and not directed:
+        visited = set()
+        for u, Gu in G.adj.items():
+            multiplicity = ((v, len(Guv)) for v, Guv in Gu.items() if v in visited)
+            yield from ([u, v] for v, m in multiplicity if m > 1)
+            visited.add(u)
+
+    # explicitly filter out loops; implicitly filter out parallel edges
+    if directed:
+        G = nx.DiGraph((u, v) for u, Gu in G.adj.items() for v in Gu if v != u)
+    else:
+        G = nx.Graph((u, v) for u, Gu in G.adj.items() for v in Gu if v != u)
+
+    # this case is not strictly necessary but improves performance
+    if length_bound is not None and length_bound == 2:
+        if directed:
+            visited = set()
+            for u, Gu in G.adj.items():
+                yield from (
+                    [v, u] for v in visited.intersection(Gu) if G.has_edge(v, u)
+                )
+                visited.add(u)
+        return
+
+    if directed:
+        yield from _directed_cycle_search(G, length_bound)
+    else:
+        yield from _undirected_cycle_search(G, length_bound)
+
+
+def _directed_cycle_search(G, length_bound):
+    """A dispatch function for `simple_cycles` for directed graphs.
+
+    We generate all cycles of G through binary partition.
+
+        1. Pick a node v in G which belongs to at least one cycle
+            a. Generate all cycles of G which contain the node v.
+            b. Recursively generate all cycles of G \\ v.
+
+    This is accomplished through the following:
+
+        1. Compute the strongly connected components SCC of G.
+        2. Select and remove a biconnected component C from BCC.  Select a
+           non-tree edge (u, v) of a depth-first search of G[C].
+        3. For each simple cycle P containing v in G[C], yield P.
+        4. Add the biconnected components of G[C \\ v] to BCC.
+
+    If the parameter length_bound is not None, then step 3 will be limited to
+    simple cycles of length at most length_bound.
+
+    Parameters
+    ----------
+    G : NetworkX DiGraph
+       A directed graph
+
+    length_bound : int or None
+       If length_bound is an int, generate all simple cycles of G with length at most length_bound.
+       Otherwise, generate all simple cycles of G.
+
+    Yields
+    ------
+    list of nodes
+       Each cycle is represented by a list of nodes along the cycle.
+    """
+
+    scc = nx.strongly_connected_components
+    components = [c for c in scc(G) if len(c) >= 2]
+    while components:
+        c = components.pop()
+        Gc = G.subgraph(c)
+        v = next(iter(c))
+        if length_bound is None:
+            yield from _johnson_cycle_search(Gc, [v])
+        else:
+            yield from _bounded_cycle_search(Gc, [v], length_bound)
+        # delete v after searching G, to make sure we can find v
+        G.remove_node(v)
+        components.extend(c for c in scc(Gc) if len(c) >= 2)
+
+
+def _undirected_cycle_search(G, length_bound):
+    """A dispatch function for `simple_cycles` for undirected graphs.
+
+    We generate all cycles of G through binary partition.
+
+        1. Pick an edge (u, v) in G which belongs to at least one cycle
+            a. Generate all cycles of G which contain the edge (u, v)
+            b. Recursively generate all cycles of G \\ (u, v)
+
+    This is accomplished through the following:
+
+        1. Compute the biconnected components BCC of G.
+        2. Select and remove a biconnected component C from BCC.  Select a
+           non-tree edge (u, v) of a depth-first search of G[C].
+        3. For each (v -> u) path P remaining in G[C] \\ (u, v), yield P.
+        4. Add the biconnected components of G[C] \\ (u, v) to BCC.
+
+    If the parameter length_bound is not None, then step 3 will be limited to simple paths
+    of length at most length_bound.
+
+    Parameters
+    ----------
+    G : NetworkX Graph
+       An undirected graph
+
+    length_bound : int or None
+       If length_bound is an int, generate all simple cycles of G with length at most length_bound.
+       Otherwise, generate all simple cycles of G.
+
+    Yields
+    ------
+    list of nodes
+       Each cycle is represented by a list of nodes along the cycle.
+    """
+
+    bcc = nx.biconnected_components
+    components = [c for c in bcc(G) if len(c) >= 3]
+    while components:
+        c = components.pop()
+        Gc = G.subgraph(c)
+        uv = list(next(iter(Gc.edges)))
+        G.remove_edge(*uv)
+        # delete (u, v) before searching G, to avoid fake 3-cycles [u, v, u]
+        if length_bound is None:
+            yield from _johnson_cycle_search(Gc, uv)
+        else:
+            yield from _bounded_cycle_search(Gc, uv, length_bound)
+        components.extend(c for c in bcc(Gc) if len(c) >= 3)
+
+
+class _NeighborhoodCache(dict):
+    """Very lightweight graph wrapper which caches neighborhoods as list.
+
+    This dict subclass uses the __missing__ functionality to query graphs for
+    their neighborhoods, and store the result as a list.  This is used to avoid
+    the performance penalty incurred by subgraph views.
+    """
+
+    def __init__(self, G):
+        self.G = G
+
+    def __missing__(self, v):
+        Gv = self[v] = list(self.G[v])
+        return Gv
+
+
+def _johnson_cycle_search(G, path):
+    """The main loop of the cycle-enumeration algorithm of Johnson.
+
+    Parameters
+    ----------
+    G : NetworkX Graph or DiGraph
+       A graph
+
+    path : list
+       A cycle prefix.  All cycles generated will begin with this prefix.
+
+    Yields
+    ------
+    list of nodes
+       Each cycle is represented by a list of nodes along the cycle.
+
+    References
+    ----------
+        .. [1] Finding all the elementary circuits of a directed graph.
+       D. B. Johnson, SIAM Journal on Computing 4, no. 1, 77-84, 1975.
+       https://doi.org/10.1137/0204007
+
+    """
+
+    G = _NeighborhoodCache(G)
+    blocked = set(path)
+    B = defaultdict(set)  # graph portions that yield no elementary circuit
+    start = path[0]
+    stack = [iter(G[path[-1]])]
+    closed = [False]
+    while stack:
+        nbrs = stack[-1]
+        for w in nbrs:
+            if w == start:
+                yield path[:]
+                closed[-1] = True
+            elif w not in blocked:
+                path.append(w)
+                closed.append(False)
+                stack.append(iter(G[w]))
+                blocked.add(w)
+                break
+        else:  # no more nbrs
+            stack.pop()
+            v = path.pop()
+            if closed.pop():
+                if closed:
+                    closed[-1] = True
+                unblock_stack = {v}
+                while unblock_stack:
+                    u = unblock_stack.pop()
+                    if u in blocked:
+                        blocked.remove(u)
+                        unblock_stack.update(B[u])
+                        B[u].clear()
+            else:
+                for w in G[v]:
+                    B[w].add(v)
+
+
+def _bounded_cycle_search(G, path, length_bound):
+    """The main loop of the cycle-enumeration algorithm of Gupta and Suzumura.
+
+    Parameters
+    ----------
+    G : NetworkX Graph or DiGraph
+       A graph
+
+    path : list
+       A cycle prefix.  All cycles generated will begin with this prefix.
+
+    length_bound: int
+        A length bound.  All cycles generated will have length at most length_bound.
+
+    Yields
+    ------
+    list of nodes
+       Each cycle is represented by a list of nodes along the cycle.
+
+    References
+    ----------
+    .. [1] Finding All Bounded-Length Simple Cycles in a Directed Graph
+       A. Gupta and T. Suzumura https://arxiv.org/abs/2105.10094
+
+    """
+    G = _NeighborhoodCache(G)
+    lock = {v: 0 for v in path}
+    B = defaultdict(set)
+    start = path[0]
+    stack = [iter(G[path[-1]])]
+    blen = [length_bound]
+    while stack:
+        nbrs = stack[-1]
+        for w in nbrs:
+            if w == start:
+                yield path[:]
+                blen[-1] = 1
+            elif len(path) < lock.get(w, length_bound):
+                path.append(w)
+                blen.append(length_bound)
+                lock[w] = len(path)
+                stack.append(iter(G[w]))
+                break
+        else:
+            stack.pop()
+            v = path.pop()
+            bl = blen.pop()
+            if blen:
+                blen[-1] = min(blen[-1], bl)
+            if bl < length_bound:
+                relax_stack = [(bl, v)]
+                while relax_stack:
+                    bl, u = relax_stack.pop()
+                    if lock.get(u, length_bound) < length_bound - bl + 1:
+                        lock[u] = length_bound - bl + 1
+                        relax_stack.extend((bl + 1, w) for w in B[u].difference(path))
+            else:
+                for w in G[v]:
+                    B[w].add(v)
+
+
+def chordless_cycles(G, length_bound=None):
+    """Find simple chordless cycles of a graph.
+
+    A `simple cycle` is a closed path where no node appears twice.  In a simple
+    cycle, a `chord` is an additional edge between two nodes in the cycle.  A
+    `chordless cycle` is a simple cycle without chords.  Said differently, a
+    chordless cycle is a cycle C in a graph G where the number of edges in the
+    induced graph G[C] is equal to the length of `C`.
+
+    Note that some care must be taken in the case that G is not a simple graph
+    nor a simple digraph.  Some authors limit the definition of chordless cycles
+    to have a prescribed minimum length; we do not.
+
+        1. We interpret self-loops to be chordless cycles, except in multigraphs
+           with multiple loops in parallel.  Likewise, in a chordless cycle of
+           length greater than 1, there can be no nodes with self-loops.
+
+        2. We interpret directed two-cycles to be chordless cycles, except in
+           multi-digraphs when any edge in a two-cycle has a parallel copy.
+
+        3. We interpret parallel pairs of undirected edges as two-cycles, except
+           when a third (or more) parallel edge exists between the two nodes.
+
+        4. Generalizing the above, edges with parallel clones may not occur in
+           chordless cycles.
+
+    In a directed graph, two chordless cycles are distinct if they are not
+    cyclic permutations of each other.  In an undirected graph, two chordless
+    cycles are distinct if they are not cyclic permutations of each other nor of
+    the other's reversal.
+
+    Optionally, the cycles are bounded in length.
+
+    We use an algorithm strongly inspired by that of Dias et al [1]_.  It has
+    been modified in the following ways:
+
+        1. Recursion is avoided, per Python's limitations
+
+        2. The labeling function is not necessary, because the starting paths
+            are chosen (and deleted from the host graph) to prevent multiple
+            occurrences of the same path
+
+        3. The search is optionally bounded at a specified length
+
+        4. Support for directed graphs is provided by extending cycles along
+            forward edges, and blocking nodes along forward and reverse edges
+
+        5. Support for multigraphs is provided by omitting digons from the set
+            of forward edges
+
+    Parameters
+    ----------
+    G : NetworkX DiGraph
+       A directed graph
+
+    length_bound : int or None, optional (default=None)
+       If length_bound is an int, generate all simple cycles of G with length at
+       most length_bound.  Otherwise, generate all simple cycles of G.
+
+    Yields
+    ------
+    list of nodes
+       Each cycle is represented by a list of nodes along the cycle.
+
+    Examples
+    --------
+    >>> sorted(list(nx.chordless_cycles(nx.complete_graph(4))))
+    [[1, 0, 2], [1, 0, 3], [2, 0, 3], [2, 1, 3]]
+
+    Notes
+    -----
+    When length_bound is None, and the graph is simple, the time complexity is
+    $O((n+e)(c+1))$ for $n$ nodes, $e$ edges and $c$ chordless cycles.
+
+    Raises
+    ------
+    ValueError
+        when length_bound < 0.
+
+    References
+    ----------
+    .. [1] Efficient enumeration of chordless cycles
+       E. Dias and D. Castonguay and H. Longo and W.A.R. Jradi
+       https://arxiv.org/abs/1309.1051
+
+    See Also
+    --------
+    simple_cycles
+    """
+
+    if length_bound is not None:
+        if length_bound == 0:
+            return
+        elif length_bound < 0:
+            raise ValueError("length bound must be non-negative")
+
+    directed = G.is_directed()
+    multigraph = G.is_multigraph()
+
+    if multigraph:
+        yield from ([v] for v, Gv in G.adj.items() if len(Gv.get(v, ())) == 1)
+    else:
+        yield from ([v] for v, Gv in G.adj.items() if v in Gv)
+
+    if length_bound is not None and length_bound == 1:
+        return
+
+    # Nodes with loops cannot belong to longer cycles.  Let's delete them here.
+    # also, we implicitly reduce the multiplicty of edges down to 1 in the case
+    # of multiedges.
+    if directed:
+        F = nx.DiGraph((u, v) for u, Gu in G.adj.items() if u not in Gu for v in Gu)
+        B = F.to_undirected(as_view=False)
+    else:
+        F = nx.Graph((u, v) for u, Gu in G.adj.items() if u not in Gu for v in Gu)
+        B = None
+
+    # If we're given a multigraph, we have a few cases to consider with parallel
+    # edges.
+    #
+    # 1. If we have 2 or more edges in parallel between the nodes (u, v), we
+    #    must not construct longer cycles along (u, v).
+    # 2. If G is not directed, then a pair of parallel edges between (u, v) is a
+    #    chordless cycle unless there exists a third (or more) parallel edge.
+    # 3. If G is directed, then parallel edges do not form cyles, but do
+    #    preclude back-edges from forming cycles (handled in the next section),
+    #    Thus, if an edge (u, v) is duplicated and the reverse (v, u) is also
+    #    present, then we remove both from F.
+    #
+    # In directed graphs, we need to consider both directions that edges can
+    # take, so iterate over all edges (u, v) and posibly (v, u).  In undirected
+    # graphs, we need to be a little careful to only consider every edge once,
+    # so we use a "visited" set to emulate node-order comparisons.
+
+    if multigraph:
+        if not directed:
+            B = F.copy()
+            visited = set()
+        for u, Gu in G.adj.items():
+            if directed:
+                multiplicity = ((v, len(Guv)) for v, Guv in Gu.items())
+                for v, m in multiplicity:
+                    if m > 1:
+                        F.remove_edges_from(((u, v), (v, u)))
+            else:
+                multiplicity = ((v, len(Guv)) for v, Guv in Gu.items() if v in visited)
+                for v, m in multiplicity:
+                    if m == 2:
+                        yield [u, v]
+                    if m > 1:
+                        F.remove_edge(u, v)
+                visited.add(u)
+
+    # If we're given a directed graphs, we need to think about digons.  If we
+    # have two edges (u, v) and (v, u), then that's a two-cycle.  If either edge
+    # was duplicated above, then we removed both from F.  So, any digons we find
+    # here are chordless.  After finding digons, we remove their edges from F
+    # to avoid traversing them in the search for chordless cycles.
+    if directed:
+        for u, Fu in F.adj.items():
+            digons = [[u, v] for v in Fu if F.has_edge(v, u)]
+            yield from digons
+            F.remove_edges_from(digons)
+            F.remove_edges_from(e[::-1] for e in digons)
+
+    if length_bound is not None and length_bound == 2:
+        return
+
+    # Now, we prepare to search for cycles.  We have removed all cycles of
+    # lengths 1 and 2, so F is a simple graph or simple digraph.  We repeatedly
+    # separate digraphs into their strongly connected components, and undirected
+    # graphs into their biconnected components.  For each component, we pick a
+    # node v, search for chordless cycles based at each "stem" (u, v, w), and
+    # then remove v from that component before separating the graph again.
+    if directed:
+        separate = nx.strongly_connected_components
+
+        # Directed stems look like (u -> v -> w), so we use the product of
+        # predecessors of v with successors of v.
+        def stems(C, v):
+            for u, w in product(C.pred[v], C.succ[v]):
+                if not G.has_edge(u, w):  # omit stems with acyclic chords
+                    yield [u, v, w], F.has_edge(w, u)
+
+    else:
+        separate = nx.biconnected_components
+
+        # Undirected stems look like (u ~ v ~ w), but we must not also search
+        # (w ~ v ~ u), so we use combinations of v's neighbors of length 2.
+        def stems(C, v):
+            yield from (([u, v, w], F.has_edge(w, u)) for u, w in combinations(C[v], 2))
+
+    components = [c for c in separate(F) if len(c) > 2]
+    while components:
+        c = components.pop()
+        v = next(iter(c))
+        Fc = F.subgraph(c)
+        Fcc = Bcc = None
+        for S, is_triangle in stems(Fc, v):
+            if is_triangle:
+                yield S
+            else:
+                if Fcc is None:
+                    Fcc = _NeighborhoodCache(Fc)
+                    Bcc = Fcc if B is None else _NeighborhoodCache(B.subgraph(c))
+                yield from _chordless_cycle_search(Fcc, Bcc, S, length_bound)
+
+        components.extend(c for c in separate(F.subgraph(c - {v})) if len(c) > 2)
+
+
+def _chordless_cycle_search(F, B, path, length_bound):
+    """The main loop for chordless cycle enumeration.
+
+    This algorithm is strongly inspired by that of Dias et al [1]_.  It has been
+    modified in the following ways:
+
+        1. Recursion is avoided, per Python's limitations
+
+        2. The labeling function is not necessary, because the starting paths
+            are chosen (and deleted from the host graph) to prevent multiple
+            occurrences of the same path
+
+        3. The search is optionally bounded at a specified length
+
+        4. Support for directed graphs is provided by extending cycles along
+            forward edges, and blocking nodes along forward and reverse edges
+
+        5. Support for multigraphs is provided by omitting digons from the set
+            of forward edges
+
+    Parameters
+    ----------
+    F : _NeighborhoodCache
+       A graph of forward edges to follow in constructing cycles
+
+    B : _NeighborhoodCache
+       A graph of blocking edges to prevent the production of chordless cycles
+
+    path : list
+       A cycle prefix.  All cycles generated will begin with this prefix.
+
+    length_bound : int
+       A length bound.  All cycles generated will have length at most length_bound.
+
+
+    Yields
+    ------
+    list of nodes
+       Each cycle is represented by a list of nodes along the cycle.
+
+    References
+    ----------
+    .. [1] Efficient enumeration of chordless cycles
+       E. Dias and D. Castonguay and H. Longo and W.A.R. Jradi
+       https://arxiv.org/abs/1309.1051
+
+    """
+    blocked = defaultdict(int)
+    target = path[0]
+    blocked[path[1]] = 1
+    for w in path[1:]:
+        for v in B[w]:
+            blocked[v] += 1
+
+    stack = [iter(F[path[2]])]
+    while stack:
+        nbrs = stack[-1]
+        for w in nbrs:
+            if blocked[w] == 1 and (length_bound is None or len(path) < length_bound):
+                Fw = F[w]
+                if target in Fw:
+                    yield path + [w]
                 else:
-                    for nbr in sccG[thisnode]:
-                        if thisnode not in B[nbr]:
-                            B[nbr].add(thisnode)
-                stack.pop()
-                #                assert path[-1] == thisnode
-                path.pop()
-        # done processing this node
-        H = subG.subgraph(scc)  # make smaller to avoid work in SCC routine
-        sccs.extend(scc for scc in nx.strongly_connected_components(H) if len(scc) > 1)
+                    Bw = B[w]
+                    if target in Bw:
+                        continue
+                    for v in Bw:
+                        blocked[v] += 1
+                    path.append(w)
+                    stack.append(iter(Fw))
+                    break
+        else:
+            stack.pop()
+            for v in B[path.pop()]:
+                blocked[v] -= 1
 
 
 @not_implemented_for("undirected")
diff --git a/networkx/algorithms/tests/test_cycles.py b/networkx/algorithms/tests/test_cycles.py
index ff8e10cd..3c4108f5 100644
--- a/networkx/algorithms/tests/test_cycles.py
+++ b/networkx/algorithms/tests/test_cycles.py
@@ -1,3 +1,6 @@
+from itertools import chain, islice, tee
+from random import shuffle
+
 import pytest
 
 import networkx
@@ -68,16 +71,13 @@ class TestCycles:
         for c in cc:
             assert any(self.is_cyclic_permutation(c, rc) for rc in ca)
 
-    def test_simple_cycles_graph(self):
-        with pytest.raises(nx.NetworkXNotImplemented):
-            G = nx.Graph()
-            c = sorted(nx.simple_cycles(G))
-
     def test_unsortable(self):
-        #  TODO What does this test do?  das 6/2013
+        # this test ensures that graphs whose nodes without an intrinsic
+        # ordering do not cause issues
         G = nx.DiGraph()
         nx.add_cycle(G, ["a", 1])
         c = list(nx.simple_cycles(G))
+        assert len(c) == 1
 
     def test_simple_cycles_small(self):
         G = nx.DiGraph()
@@ -96,13 +96,6 @@ class TestCycles:
         G = nx.DiGraph()
         assert list(nx.simple_cycles(G)) == []
 
-    def test_complete_directed_graph(self):
-        # see table 2 in Johnson's paper
-        ncircuits = [1, 5, 20, 84, 409, 2365, 16064]
-        for n, c in zip(range(2, 9), ncircuits):
-            G = nx.DiGraph(nx.complete_graph(n))
-            assert len(list(nx.simple_cycles(G))) == c
-
     def worst_case_graph(self, k):
         # see figure 1 in Johnson's paper
         # this graph has exactly 3k simple cycles
@@ -169,6 +162,522 @@ class TestCycles:
             assert any(self.is_cyclic_permutation(rc, c) for c in cc)
 
 
+def pairwise(iterable):
+    a, b = tee(iterable)
+    next(b, None)
+    return zip(a, b)
+
+
+def cycle_edges(c):
+    return pairwise(chain(c, islice(c, 1)))
+
+
+def directed_cycle_edgeset(c):
+    return frozenset(cycle_edges(c))
+
+
+def undirected_cycle_edgeset(c):
+    if len(c) == 1:
+        return frozenset(cycle_edges(c))
+    return frozenset(map(frozenset, cycle_edges(c)))
+
+
+def multigraph_cycle_edgeset(c):
+    if len(c) <= 2:
+        return frozenset(cycle_edges(c))
+    else:
+        return frozenset(map(frozenset, cycle_edges(c)))
+
+
+class TestCycleEnumeration:
+    @staticmethod
+    def K(n):
+        return nx.complete_graph(n)
+
+    @staticmethod
+    def D(n):
+        return nx.complete_graph(n).to_directed()
+
+    @staticmethod
+    def edgeset_function(g):
+        if g.is_directed():
+            return directed_cycle_edgeset
+        elif g.is_multigraph():
+            return multigraph_cycle_edgeset
+        else:
+            return undirected_cycle_edgeset
+
+    def check_cycle(self, g, c, es, cache, source, original_c, length_bound, chordless):
+        if length_bound is not None and len(c) > length_bound:
+            raise RuntimeError(
+                f"computed cycle {original_c} exceeds length bound {length_bound}"
+            )
+        if source == "computed":
+            if es in cache:
+                raise RuntimeError(
+                    f"computed cycle {original_c} has already been found!"
+                )
+            else:
+                cache[es] = tuple(original_c)
+        else:
+            if es in cache:
+                cache.pop(es)
+            else:
+                raise RuntimeError(f"expected cycle {original_c} was not computed")
+
+        if not all(g.has_edge(*e) for e in es):
+            raise RuntimeError(
+                f"{source} claimed cycle {original_c} is not a cycle of g"
+            )
+        if chordless and len(g.subgraph(c).edges) > len(c):
+            raise RuntimeError(f"{source} cycle {original_c} is not chordless")
+
+    def check_cycle_algorithm(
+        self,
+        g,
+        expected_cycles,
+        length_bound=None,
+        chordless=False,
+        algorithm=None,
+    ):
+        if algorithm is None:
+            algorithm = nx.chordless_cycles if chordless else nx.simple_cycles
+
+        # note: we shuffle the labels of g to rule out accidentally-correct
+        # behavior which occurred during the development of chordless cycle
+        # enumeration algorithms
+
+        relabel = list(range(len(g)))
+        shuffle(relabel)
+        label = dict(zip(g, relabel))
+        unlabel = dict(zip(relabel, g))
+        h = nx.relabel_nodes(g, label, copy=True)
+
+        edgeset = self.edgeset_function(h)
+
+        params = {}
+        if length_bound is not None:
+            params["length_bound"] = length_bound
+
+        cycle_cache = {}
+        for c in algorithm(h, **params):
+            original_c = [unlabel[x] for x in c]
+            es = edgeset(c)
+            self.check_cycle(
+                h, c, es, cycle_cache, "computed", original_c, length_bound, chordless
+            )
+
+        if isinstance(expected_cycles, int):
+            if len(cycle_cache) != expected_cycles:
+                raise RuntimeError(
+                    f"expected {expected_cycles} cycles, got {len(cycle_cache)}"
+                )
+            return
+        for original_c in expected_cycles:
+            c = [label[x] for x in original_c]
+            es = edgeset(c)
+            self.check_cycle(
+                h, c, es, cycle_cache, "expected", original_c, length_bound, chordless
+            )
+
+        if len(cycle_cache):
+            for c in cycle_cache.values():
+                raise RuntimeError(
+                    f"computed cycle {c} is valid but not in the expected cycle set!"
+                )
+
+    def check_cycle_enumeration_integer_sequence(
+        self,
+        g_family,
+        cycle_counts,
+        length_bound=None,
+        chordless=False,
+        algorithm=None,
+    ):
+        for g, num_cycles in zip(g_family, cycle_counts):
+            self.check_cycle_algorithm(
+                g,
+                num_cycles,
+                length_bound=length_bound,
+                chordless=chordless,
+                algorithm=algorithm,
+            )
+
+    def test_directed_chordless_cycle_digons(self):
+        g = nx.DiGraph()
+        nx.add_cycle(g, range(5))
+        nx.add_cycle(g, range(5)[::-1])
+        g.add_edge(0, 0)
+        expected_cycles = [(0,), (1, 2), (2, 3), (3, 4)]
+        self.check_cycle_algorithm(g, expected_cycles, chordless=True)
+
+        self.check_cycle_algorithm(g, expected_cycles, chordless=True, length_bound=2)
+
+        expected_cycles = [c for c in expected_cycles if len(c) < 2]
+        self.check_cycle_algorithm(g, expected_cycles, chordless=True, length_bound=1)
+
+    def test_directed_chordless_cycle_undirected(self):
+        g = nx.DiGraph([(1, 2), (2, 3), (3, 4), (4, 5), (5, 0), (5, 1), (0, 2)])
+        expected_cycles = [(0, 2, 3, 4, 5), (1, 2, 3, 4, 5)]
+        self.check_cycle_algorithm(g, expected_cycles, chordless=True)
+
+        g = nx.DiGraph()
+        nx.add_cycle(g, range(5))
+        nx.add_cycle(g, range(4, 9))
+        g.add_edge(7, 3)
+        expected_cycles = [(0, 1, 2, 3, 4), (3, 4, 5, 6, 7), (4, 5, 6, 7, 8)]
+        self.check_cycle_algorithm(g, expected_cycles, chordless=True)
+
+        g.add_edge(3, 7)
+        expected_cycles = [(0, 1, 2, 3, 4), (3, 7), (4, 5, 6, 7, 8)]
+        self.check_cycle_algorithm(g, expected_cycles, chordless=True)
+
+        expected_cycles = [(3, 7)]
+        self.check_cycle_algorithm(g, expected_cycles, chordless=True, length_bound=4)
+
+        g.remove_edge(7, 3)
+        expected_cycles = [(0, 1, 2, 3, 4), (4, 5, 6, 7, 8)]
+        self.check_cycle_algorithm(g, expected_cycles, chordless=True)
+
+        g = nx.DiGraph((i, j) for i in range(10) for j in range(i))
+        expected_cycles = []
+        self.check_cycle_algorithm(g, expected_cycles, chordless=True)
+
+    def test_chordless_cycles_directed(self):
+        G = nx.DiGraph()
+        nx.add_cycle(G, range(5))
+        nx.add_cycle(G, range(4, 12))
+        expected = [[*range(5)], [*range(4, 12)]]
+        self.check_cycle_algorithm(G, expected, chordless=True)
+        self.check_cycle_algorithm(
+            G, [c for c in expected if len(c) <= 5], length_bound=5, chordless=True
+        )
+
+        G.add_edge(7, 3)
+        expected.append([*range(3, 8)])
+        self.check_cycle_algorithm(G, expected, chordless=True)
+        self.check_cycle_algorithm(
+            G, [c for c in expected if len(c) <= 5], length_bound=5, chordless=True
+        )
+
+        G.add_edge(3, 7)
+        expected[-1] = [7, 3]
+        self.check_cycle_algorithm(G, expected, chordless=True)
+        self.check_cycle_algorithm(
+            G, [c for c in expected if len(c) <= 5], length_bound=5, chordless=True
+        )
+
+        expected.pop()
+        G.remove_edge(7, 3)
+        self.check_cycle_algorithm(G, expected, chordless=True)
+        self.check_cycle_algorithm(
+            G, [c for c in expected if len(c) <= 5], length_bound=5, chordless=True
+        )
+
+    def test_directed_chordless_cycle_diclique(self):
+        g_family = [self.D(n) for n in range(10)]
+        expected_cycles = [(n * n - n) // 2 for n in range(10)]
+        self.check_cycle_enumeration_integer_sequence(
+            g_family, expected_cycles, chordless=True
+        )
+
+        expected_cycles = [(n * n - n) // 2 for n in range(10)]
+        self.check_cycle_enumeration_integer_sequence(
+            g_family, expected_cycles, length_bound=2
+        )
+
+    def test_directed_chordless_loop_blockade(self):
+        g = nx.DiGraph((i, i) for i in range(10))
+        nx.add_cycle(g, range(10))
+        expected_cycles = [(i,) for i in range(10)]
+        self.check_cycle_algorithm(g, expected_cycles, chordless=True)
+
+        self.check_cycle_algorithm(g, expected_cycles, length_bound=1)
+
+        g = nx.MultiDiGraph(g)
+        g.add_edges_from((i, i) for i in range(0, 10, 2))
+        expected_cycles = [(i,) for i in range(1, 10, 2)]
+        self.check_cycle_algorithm(g, expected_cycles, chordless=True)
+
+    def test_simple_cycles_notable_clique_sequences(self):
+        # A000292: Number of labeled graphs on n+3 nodes that are triangles.
+        g_family = [self.K(n) for n in range(2, 12)]
+        expected = [0, 1, 4, 10, 20, 35, 56, 84, 120, 165, 220]
+        self.check_cycle_enumeration_integer_sequence(
+            g_family, expected, length_bound=3
+        )
+
+        def triangles(g, **kwargs):
+            yield from (c for c in nx.simple_cycles(g, **kwargs) if len(c) == 3)
+
+        # directed complete graphs have twice as many triangles thanks to reversal
+        g_family = [self.D(n) for n in range(2, 12)]
+        expected = [2 * e for e in expected]
+        self.check_cycle_enumeration_integer_sequence(
+            g_family, expected, length_bound=3, algorithm=triangles
+        )
+
+        def four_cycles(g, **kwargs):
+            yield from (c for c in nx.simple_cycles(g, **kwargs) if len(c) == 4)
+
+        # A050534: the number of 4-cycles in the complete graph K_{n+1}
+        expected = [0, 0, 0, 3, 15, 45, 105, 210, 378, 630, 990]
+        g_family = [self.K(n) for n in range(1, 12)]
+        self.check_cycle_enumeration_integer_sequence(
+            g_family, expected, length_bound=4, algorithm=four_cycles
+        )
+
+        # directed complete graphs have twice as many 4-cycles thanks to reversal
+        expected = [2 * e for e in expected]
+        g_family = [self.D(n) for n in range(1, 15)]
+        self.check_cycle_enumeration_integer_sequence(
+            g_family, expected, length_bound=4, algorithm=four_cycles
+        )
+
+        # A006231: the number of elementary circuits in a complete directed graph with n nodes
+        expected = [0, 1, 5, 20, 84, 409, 2365]
+        g_family = [self.D(n) for n in range(1, 8)]
+        self.check_cycle_enumeration_integer_sequence(g_family, expected)
+
+        # A002807: Number of cycles in the complete graph on n nodes K_{n}.
+        expected = [0, 0, 0, 1, 7, 37, 197, 1172]
+        g_family = [self.K(n) for n in range(8)]
+        self.check_cycle_enumeration_integer_sequence(g_family, expected)
+
+    def test_directed_chordless_cycle_parallel_multiedges(self):
+        g = nx.MultiGraph()
+
+        nx.add_cycle(g, range(5))
+        expected = [[*range(5)]]
+        self.check_cycle_algorithm(g, expected, chordless=True)
+
+        nx.add_cycle(g, range(5))
+        expected = [*cycle_edges(range(5))]
+        self.check_cycle_algorithm(g, expected, chordless=True)
+
+        nx.add_cycle(g, range(5))
+        expected = []
+        self.check_cycle_algorithm(g, expected, chordless=True)
+
+        g = nx.MultiDiGraph()
+
+        nx.add_cycle(g, range(5))
+        expected = [[*range(5)]]
+        self.check_cycle_algorithm(g, expected, chordless=True)
+
+        nx.add_cycle(g, range(5))
+        self.check_cycle_algorithm(g, [], chordless=True)
+
+        nx.add_cycle(g, range(5))
+        self.check_cycle_algorithm(g, [], chordless=True)
+
+        g = nx.MultiDiGraph()
+
+        nx.add_cycle(g, range(5))
+        nx.add_cycle(g, range(5)[::-1])
+        expected = [*cycle_edges(range(5))]
+        self.check_cycle_algorithm(g, expected, chordless=True)
+
+        nx.add_cycle(g, range(5))
+        self.check_cycle_algorithm(g, [], chordless=True)
+
+    def test_chordless_cycles_graph(self):
+        G = nx.Graph()
+        nx.add_cycle(G, range(5))
+        nx.add_cycle(G, range(4, 12))
+        expected = [[*range(5)], [*range(4, 12)]]
+        self.check_cycle_algorithm(G, expected, chordless=True)
+        self.check_cycle_algorithm(
+            G, [c for c in expected if len(c) <= 5], length_bound=5, chordless=True
+        )
+
+        G.add_edge(7, 3)
+        expected.append([*range(3, 8)])
+        expected.append([4, 3, 7, 8, 9, 10, 11])
+        self.check_cycle_algorithm(G, expected, chordless=True)
+        self.check_cycle_algorithm(
+            G, [c for c in expected if len(c) <= 5], length_bound=5, chordless=True
+        )
+
+    def test_chordless_cycles_giant_hamiltonian(self):
+        # ... o - e - o - e - o ... # o = odd, e = even
+        # ... ---/ \-----/ \--- ... # <-- "long" edges
+        #
+        # each long edge belongs to exactly one triangle, and one giant cycle
+        # of length n/2.  The remaining edges each belong to a triangle
+
+        n = 1000
+        assert n % 2 == 0
+        G = nx.Graph()
+        for v in range(n):
+            if not v % 2:
+                G.add_edge(v, (v + 2) % n)
+            G.add_edge(v, (v + 1) % n)
+
+        expected = [[*range(0, n, 2)]] + [
+            [x % n for x in range(i, i + 3)] for i in range(0, n, 2)
+        ]
+        self.check_cycle_algorithm(G, expected, chordless=True)
+        self.check_cycle_algorithm(
+            G, [c for c in expected if len(c) <= 3], length_bound=3, chordless=True
+        )
+
+        # ... o -> e -> o -> e -> o ... # o = odd, e = even
+        # ... <---/ \---<---/ \---< ... # <-- "long" edges
+        #
+        # this time, we orient the short and long edges in opposition
+        # the cycle structure of this graph is the same, but we need to reverse
+        # the long one in our representation.  Also, we need to drop the size
+        # because our partitioning algorithm uses strongly connected components
+        # instead of separating graphs by their strong articulation points
+
+        n = 100
+        assert n % 2 == 0
+        G = nx.DiGraph()
+        for v in range(n):
+            G.add_edge(v, (v + 1) % n)
+            if not v % 2:
+                G.add_edge((v + 2) % n, v)
+
+        expected = [[*range(n - 2, -2, -2)]] + [
+            [x % n for x in range(i, i + 3)] for i in range(0, n, 2)
+        ]
+        self.check_cycle_algorithm(G, expected, chordless=True)
+        self.check_cycle_algorithm(
+            G, [c for c in expected if len(c) <= 3], length_bound=3, chordless=True
+        )
+
+    def test_simple_cycles_acyclic_tournament(self):
+        n = 10
+        G = nx.DiGraph((x, y) for x in range(n) for y in range(x))
+        self.check_cycle_algorithm(G, [])
+        self.check_cycle_algorithm(G, [], chordless=True)
+
+        for k in range(n + 1):
+            self.check_cycle_algorithm(G, [], length_bound=k)
+            self.check_cycle_algorithm(G, [], length_bound=k, chordless=True)
+
+    def test_simple_cycles_graph(self):
+        testG = nx.cycle_graph(8)
+        cyc1 = tuple(range(8))
+        self.check_cycle_algorithm(testG, [cyc1])
+
+        testG.add_edge(4, -1)
+        nx.add_path(testG, [3, -2, -3, -4])
+        self.check_cycle_algorithm(testG, [cyc1])
+
+        testG.update(nx.cycle_graph(range(8, 16)))
+        cyc2 = tuple(range(8, 16))
+        self.check_cycle_algorithm(testG, [cyc1, cyc2])
+
+        testG.update(nx.cycle_graph(range(4, 12)))
+        cyc3 = tuple(range(4, 12))
+        expected = {
+            (0, 1, 2, 3, 4, 5, 6, 7),  # cyc1
+            (8, 9, 10, 11, 12, 13, 14, 15),  # cyc2
+            (4, 5, 6, 7, 8, 9, 10, 11),  # cyc3
+            (4, 5, 6, 7, 8, 15, 14, 13, 12, 11),  # cyc2 + cyc3
+            (0, 1, 2, 3, 4, 11, 10, 9, 8, 7),  # cyc1 + cyc3
+            (0, 1, 2, 3, 4, 11, 12, 13, 14, 15, 8, 7),  # cyc1 + cyc2 + cyc3
+        }
+        self.check_cycle_algorithm(testG, expected)
+        assert len(expected) == (2**3 - 1) - 1  # 1 disjoint comb: cyc1 + cyc2
+
+        # Basis size = 5 (2 loops overlapping gives 5 small loops
+        #        E
+        #       / \         Note: A-F = 10-15
+        #    1-2-3-4-5
+        #    / |   |  \   cyc1=012DAB -- left
+        #   0  D   F  6   cyc2=234E   -- top
+        #   \  |   |  /   cyc3=45678F -- right
+        #    B-A-9-8-7    cyc4=89AC   -- bottom
+        #       \ /       cyc5=234F89AD -- middle
+        #        C
+        #
+        # combinations of 5 basis elements: 2^5 - 1  (one includes no cycles)
+        #
+        # disjoint combs: (11 total) not simple cycles
+        #   Any pair not including cyc5 => choose(4, 2) = 6
+        #   Any triple not including cyc5 => choose(4, 3) = 4
+        #   Any quad not including cyc5 => choose(4, 4) = 1
+        #
+        # we expect 31 - 11 = 20 simple cycles
+        #
+        testG = nx.cycle_graph(12)
+        testG.update(nx.cycle_graph([12, 10, 13, 2, 14, 4, 15, 8]).edges)
+        expected = (2**5 - 1) - 11  # 11 disjoint combinations
+        self.check_cycle_algorithm(testG, expected)
+
+    def test_simple_cycles_bounded(self):
+        # iteratively construct a cluster of nested cycles running in the same direction
+        # there should be one cycle of every length
+        d = nx.DiGraph()
+        expected = []
+        for n in range(10):
+            nx.add_cycle(d, range(n))
+            expected.append(n)
+            for k, e in enumerate(expected):
+                self.check_cycle_algorithm(d, e, length_bound=k)
+
+        # iteratively construct a path of undirected cycles, connected at articulation
+        # points.  there should be one cycle of every length except 2: no digons
+        g = nx.Graph()
+        top = 0
+        expected = []
+        for n in range(10):
+            expected.append(n if n < 2 else n - 1)
+            if n == 2:
+                # no digons in undirected graphs
+                continue
+            nx.add_cycle(g, range(top, top + n))
+            top += n
+            for k, e in enumerate(expected):
+                self.check_cycle_algorithm(g, e, length_bound=k)
+
+    def test_simple_cycles_bound_corner_cases(self):
+        G = nx.cycle_graph(4)
+        DG = nx.cycle_graph(4, create_using=nx.DiGraph)
+        assert list(nx.simple_cycles(G, length_bound=0)) == []
+        assert list(nx.simple_cycles(DG, length_bound=0)) == []
+        assert list(nx.chordless_cycles(G, length_bound=0)) == []
+        assert list(nx.chordless_cycles(DG, length_bound=0)) == []
+
+    def test_simple_cycles_bound_error(self):
+        with pytest.raises(ValueError):
+            G = nx.DiGraph()
+            for c in nx.simple_cycles(G, -1):
+                assert False
+
+        with pytest.raises(ValueError):
+            G = nx.Graph()
+            for c in nx.simple_cycles(G, -1):
+                assert False
+
+        with pytest.raises(ValueError):
+            G = nx.Graph()
+            for c in nx.chordless_cycles(G, -1):
+                assert False
+
+        with pytest.raises(ValueError):
+            G = nx.DiGraph()
+            for c in nx.chordless_cycles(G, -1):
+                assert False
+
+    def test_chordless_cycles_clique(self):
+        g_family = [self.K(n) for n in range(2, 15)]
+        expected = [0, 1, 4, 10, 20, 35, 56, 84, 120, 165, 220, 286, 364]
+        self.check_cycle_enumeration_integer_sequence(
+            g_family, expected, chordless=True
+        )
+
+        # directed cliques have as many digons as undirected graphs have edges
+        expected = [(n * n - n) // 2 for n in range(15)]
+        g_family = [self.D(n) for n in range(15)]
+        self.check_cycle_enumeration_integer_sequence(
+            g_family, expected, chordless=True
+        )
+
+
 # These tests might fail with hash randomization since they depend on
 # edge_dfs. For more information, see the comments in:
 #    networkx/algorithms/traversal/tests/test_edgedfs.py