Merge branch 'master' of ssh://git.onelab.eu/git/myslice
[myslice.git] / 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