manifold/util/dfs.py

   1 #!/usr/bin/env python
   2 # -*- coding: utf-8 -*-
   3 #
   4 # Depth first search algorithm
   5 # Based on http://www.boost.org/doc/libs/1_52_0/libs/graph/doc/depth_first_search.html
   6 #
   7 # Copyright (C) UPMC Paris Universitas
   8 # Authors:
   9 #   Marc-Olivier Buob <marc-olivier.buob@lip6.fr>
  10 #   Jordan Augé       <jordan.auge@lip6.fr>
  11
  12 class dfs_color:
  13     WHITE = 1 # not yet visited
  14     GRAY  = 2 # currently visited
  15     BLACK = 3 # visited
  16
  17 #DFS(G)
  18 #  for each vertex u in V
  19 #    color[u] := WHITE
  20 #    p[u] = u
  21 #  end for
  22 #  time := 0
  23 #  if there is a starting vertex s
  24 #    call DFS-VISIT(G, s)
  25 #  for each vertex u in V
  26 #    if color[u] = WHITE
  27 #      call DFS-VISIT(G, u)
  28 #  end for
  29 #  return (p,d_time,f_time)
  30
  31 def dfs(graph, root, exclude_uv=None):
  32     """
  33     \brief Run the DFS algorithm
  34     \param graph The graph we explore
  35     \param root The starting vertex
  36     \return A dictionnary which maps each vertex of the tree
  37             to its predecessor, None otherwise.
  38             Only the root node as a predecessor equal to None.
  39             Nodes not referenced in this dictionnary do not
  40             belong to the tree.
  41     """
  42     # Initialization
  43     map_vertex_color = {}
  44     map_vertex_pred  = {}
  45     for u in graph.nodes():
  46         map_vertex_color[u] = dfs_color.WHITE
  47         map_vertex_pred[u] = None
  48
  49     # Recursive calls
  50     if not exclude_uv:
  51         exclude_uv = lambda u,v: False
  52     dfs_visit(graph, root, map_vertex_color, map_vertex_pred, exclude_uv)
  53
  54     # Remove from map_vertex_pred the vertices having no
  55     # predecessor but the root node.
  56     for v, u in map_vertex_pred.items():
  57         if u == None and v != root:
  58             del map_vertex_pred[v]
  59
  60     return map_vertex_pred
  61
  62 #DFS-VISIT(G, u)
  63 #  color[u] := GRAY
  64 #  d_time[u] := time := time + 1
  65 #  for each v in Adj[u]
  66 #    if (color[v] = WHITE)
  67 #      p[v] = u
  68 #      call DFS-VISIT(G, v)
  69 #    else if (color[v] = GRAY)
  70 #      ...
  71 #    else if (color[v] = BLACK)
  72 #      ...
  73 #  end for
  74 #  color[u] := BLACK
  75 #  f_time[u] := time := time + 1
  76
  77 def dfs_visit(graph, u, map_vertex_color, map_vertex_pred, exclude_uv):
  78     """
  79     \brief Internal usage (DFS implementation)
  80     \param graph The graph we explore
  81     \param u The current node
  82     \param map_vertex_color: maps each vertex to a color
  83         - dfs_color.WHITE: iif the vertex is not reachable from the root node
  84         - dfs_color.BLACK: otherwise
  85     \param map_vertex_pred: maps each vertex to its predecessor (if any) visited
  86         during the DFS exploration, None otherwise
  87     """
  88     map_vertex_color[u] = dfs_color.GRAY
  89     for v in graph.successors(u):
  90         color_v = map_vertex_color[v]
  91         if color_v == dfs_color.WHITE and not exclude_uv(u, v):
  92             map_vertex_pred[v] = u
  93             dfs_visit(graph, v, map_vertex_color, map_vertex_pred, exclude_uv)
  94     map_vertex_color[u] = dfs_color.BLACK
  95