def _is_connected_by_alternating_path(G, v, matching, targets):
 matched_edges = {(u, v) for (u, v) in matching.items() if (u <= v)}
 unmatched_edges = (set(G.edges()) - matched_edges)
 def _alternating_dfs(u, depth, along_matched=True):
  'Returns True if and only if `u` is connected to one of the\n        targets by an alternating path.\n\n        `u` is a vertex in the graph `G`.\n\n        `depth` specifies the maximum recursion depth of the depth-first\n        search.\n\n        If `along_matched` is True, this step of the depth-first search\n        will continue only through edges in the given matching. Otherwise, it\n        will continue only through edges *not* in the given matching.\n\n        '
  if (u in targets):
   return True
  if (depth < 0):
   return False
  valid_edges = (matched_edges if along_matched else unmatched_edges)
  for v in G[u]:
   if (((u, v) in valid_edges) or ((v, u) in valid_edges)):
    return _alternating_dfs(v, (depth - 1), (not along_matched))
  return False
 return (_alternating_dfs(v, len(G), along_matched=True) or _alternating_dfs(v, len(G), along_matched=False))

def _is_connected_by_alternating_path ( G , v , matching , targets ) : matched_edges = { ( u , v ) for ( u , v ) in matching . items ( ) if ( u <= v ) } unmatched_edges = ( set ( G . edges ( ) ) - matched_edges ) def _alternating_dfs ( u , depth , along_matched = True ) : if ( u in targets ) : return True if ( depth < 0 ) : return False valid_edges = ( matched_edges if along_matched else unmatched_edges ) for v in G [ u ] : if ( ( ( u , v ) in valid_edges ) or ( ( v , u ) in valid_edges ) ) : return _alternating_dfs ( v , ( depth - 1 ) , ( not along_matched ) ) return False return ( _alternating_dfs ( v , len ( G ) , along_matched = True ) or _alternating_dfs ( v , len ( G ) , along_matched = False ) )
returns true if and only if the vertex v is connected to one of the target vertices by an alternating path in g .