text: # -*- coding: utf-8 -*-
  #    Copyright (C) 2004-2018 by
  #    Aric Hagberg <hagberg@lanl.gov>
  #    Dan Schult <dschult@colgate.edu>
  #    Pieter Swart <swart@lanl.gov>
  #    All rights reserved.
  #    BSD license.
  #
  # Authors:  Aric Hagberg (hagberg@lanl.gov) and Dan Schult (dschult@colgate.edu)
  #
  """
  Provides functions for finding and testing for locally `(k, l)`-connected
  graphs.
  
  """
  import copy
  import networkx as nx
  
  __all__ = ['kl_connected_subgraph', 'is_kl_connected']
  
  
  def kl_connected_subgraph(G, k, l, low_memory=False, same_as_graph=False):
      """Returns the maximum locally `(k, l)`-connected subgraph of `G`.
  
      A graph is locally `(k, l)`-connected if for each edge `(u, v)` in the
      graph there are at least `l` edge-disjoint paths of length at most `k`
      joining `u` to `v`.
  
      Parameters
      ----------
      G : NetworkX graph
          The graph in which to find a maximum locally `(k, l)`-connected
          subgraph.
  
      k : integer
          The maximum length of paths to consider. A higher number means a looser
          connectivity requirement.
  
      l : integer
          The number of edge-disjoint paths. A higher number means a stricter
          connectivity requirement.
  
      low_memory : bool
          If this is True, this function uses an algorithm that uses slightly
          more time but less memory.
  
      same_as_graph : bool
          If True then return a tuple of the form `(H, is_same)`,
          where `H` is the maximum locally `(k, l)`-connected subgraph and
          `is_same` is a Boolean representing whether `G` is locally `(k,
          l)`-connected (and hence, whether `H` is simply a copy of the input
          graph `G`).
  
      Returns
      -------
      NetworkX graph or two-tuple
          If `same_as_graph` is True, then this function returns a
          two-tuple as described above. Otherwise, it returns only the maximum
          locally `(k, l)`-connected subgraph.
  
      See also
      --------
      is_kl_connected
  
      References
      ----------
      .. [1]: Chung, Fan and Linyuan Lu. "The Small World Phenomenon in Hybrid
              Power Law Graphs." *Complex Networks*. Springer Berlin Heidelberg,
              2004. 89--104.
  
      """
      H = copy.deepcopy(G)    # subgraph we construct by removing from G
  
      graphOK = True
      deleted_some = True  # hack to start off the while loop
      while deleted_some:
          deleted_some = False
          # We use `for edge in list(H.edges()):` instead of
          # `for edge in H.edges():` because we edit the graph `H` in
          # the loop. Hence using an iterator will result in
          # `RuntimeError: dictionary changed size during iteration`
          for edge in list(H.edges()):
              (u, v) = edge
              # Get copy of graph needed for this search
              if low_memory:
                  verts = set([u, v])
                  for i in range(k):
                      for w in verts.copy():
                          verts.update(G[w])
                  G2 = G.subgraph(verts).copy()
              else:
                  G2 = copy.deepcopy(G)
              ###
              path = [u, v]
              cnt = 0
              accept = 0
              while path:
                  cnt += 1  # Found a path
                  if cnt >= l:
                      accept = 1
                      break
                  # record edges along this graph
                  prev = u
                  for w in path:
                      if prev != w:
                          G2.remove_edge(prev, w)
                          prev = w
  #                path = shortest_path(G2, u, v, k) # ??? should "Cutoff" be k+1?
                  try:
                      path = nx.shortest_path(G2, u, v)  # ??? should "Cutoff" be k+1?
                  except nx.NetworkXNoPath:
                      path = False
              # No Other Paths
              if accept == 0:
                  H.remove_edge(u, v)
                  deleted_some = True
                  if graphOK:
                      graphOK = False
      # We looked through all edges and removed none of them.
      # So, H is the maximal (k,l)-connected subgraph of G
      if same_as_graph:
          return (H, graphOK)
      return H
  
  
  def is_kl_connected(G, k, l, low_memory=False):
      """Returns True if and only if `G` is locally `(k, l)`-connected.
  
      A graph is locally `(k, l)`-connected if for each edge `(u, v)` in the
      graph there are at least `l` edge-disjoint paths of length at most `k`
      joining `u` to `v`.
  
      Parameters
      ----------
      G : NetworkX graph
          The graph to test for local `(k, l)`-connectedness.
  
      k : integer
          The maximum length of paths to consider. A higher number means a looser
          connectivity requirement.
  
      l : integer
          The number of edge-disjoint paths. A higher number means a stricter
          connectivity requirement.
  
      low_memory : bool
          If this is True, this function uses an algorithm that uses slightly
          more time but less memory.
  
      Returns
      -------
      bool
          Whether the graph is locally `(k, l)`-connected subgraph.
  
      See also
      --------
      kl_connected_subgraph
  
      References
      ----------
      .. [1]: Chung, Fan and Linyuan Lu. "The Small World Phenomenon in Hybrid
              Power Law Graphs." *Complex Networks*. Springer Berlin Heidelberg,
              2004. 89--104.
  
      """
      graphOK = True
      for edge in G.edges():
          (u, v) = edge
          # Get copy of graph needed for this search
          if low_memory:
              verts = set([u, v])
              for i in range(k):
                  [verts.update(G.neighbors(w)) for w in verts.copy()]
              G2 = G.subgraph(verts)
          else:
              G2 = copy.deepcopy(G)
          ###
          path = [u, v]
          cnt = 0
          accept = 0
          while path:
              cnt += 1  # Found a path
              if cnt >= l:
                  accept = 1
                  break
              # record edges along this graph
              prev = u
              for w in path:
                  if w != prev:
                      G2.remove_edge(prev, w)
                      prev = w
  #            path = shortest_path(G2, u, v, k) # ??? should "Cutoff" be k+1?
              try:
                  path = nx.shortest_path(G2, u, v)  # ??? should "Cutoff" be k+1?
              except nx.NetworkXNoPath:
                  path = False
          # No Other Paths
          if accept == 0:
              graphOK = False
              break
      # return status
      return graphOK
  