|
1 # Copyright (c) 2007-2008 Pedro Matiello <pmatiello@gmail.com> |
|
2 # |
|
3 # Permission is hereby granted, free of charge, to any person |
|
4 # obtaining a copy of this software and associated documentation |
|
5 # files (the "Software"), to deal in the Software without |
|
6 # restriction, including without limitation the rights to use, |
|
7 # copy, modify, merge, publish, distribute, sublicense, and/or sell |
|
8 # copies of the Software, and to permit persons to whom the |
|
9 # Software is furnished to do so, subject to the following |
|
10 # conditions: |
|
11 |
|
12 # The above copyright notice and this permission notice shall be |
|
13 # included in all copies or substantial portions of the Software. |
|
14 |
|
15 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, |
|
16 # EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES |
|
17 # OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND |
|
18 # NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT |
|
19 # HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, |
|
20 # WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING |
|
21 # FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR |
|
22 # OTHER DEALINGS IN THE SOFTWARE. |
|
23 |
|
24 |
|
25 """ |
|
26 Search algorithms for python-graph. |
|
27 |
|
28 @sort: breadth_first_search, depth_first_search, _bfs, _dfs |
|
29 """ |
|
30 |
|
31 |
|
32 # Depth-first search |
|
33 |
|
34 def depth_first_search(graph, root=None): |
|
35 """ |
|
36 Depth-first search. |
|
37 |
|
38 @type graph: graph |
|
39 @param graph: Graph. |
|
40 |
|
41 @type root: node |
|
42 @param root: Optional root node (will explore only root's connected component) |
|
43 |
|
44 @rtype: tuple |
|
45 @return: A tupple containing a dictionary and two lists: |
|
46 1. Generated spanning tree |
|
47 2. Graph's preordering |
|
48 3. Graph's postordering |
|
49 """ |
|
50 visited = {} # List for marking visited and non-visited nodes |
|
51 spanning_tree = {} # Spanning tree |
|
52 pre = [] # Graph's preordering |
|
53 post = [] # Graph's postordering |
|
54 |
|
55 # DFS from one node only |
|
56 if (root is not None): |
|
57 spanning_tree[root] = None |
|
58 _dfs(graph, visited, spanning_tree, pre, post, root) |
|
59 return spanning_tree, pre, post |
|
60 |
|
61 # Algorithm loop |
|
62 for each in graph: |
|
63 # Select a non-visited node |
|
64 if (each not in visited): |
|
65 spanning_tree[each] = None |
|
66 # Explore node's connected component |
|
67 _dfs(graph, visited, spanning_tree, pre, post, each) |
|
68 |
|
69 return spanning_tree, pre, post |
|
70 |
|
71 |
|
72 def _dfs(graph, visited, spanning_tree, pre, post, node): |
|
73 """ |
|
74 Depht-first search subfunction. |
|
75 |
|
76 @type graph: graph |
|
77 @param graph: Graph. |
|
78 |
|
79 @type visited: dictionary |
|
80 @param visited: List of nodes (visited nodes are marked non-zero). |
|
81 |
|
82 @type spanning_tree: dictionary |
|
83 @param spanning_tree: Spanning tree being built for the graph by DFS. |
|
84 |
|
85 @type pre: list |
|
86 @param pre: Graph's preordering. |
|
87 |
|
88 @type post: list |
|
89 @param post: Graph's postordering. |
|
90 |
|
91 @type node: node |
|
92 @param node: Node to be explored by DFS. |
|
93 """ |
|
94 visited[node] = 1 |
|
95 pre.append(node) |
|
96 # Explore recursively the connected component |
|
97 for each in graph[node]: |
|
98 if (each not in visited): |
|
99 spanning_tree[each] = node |
|
100 _dfs(graph, visited, spanning_tree, pre, post, each) |
|
101 post.append(node) |
|
102 |
|
103 |
|
104 # Breadth-first search |
|
105 |
|
106 def breadth_first_search(graph, root=None): |
|
107 """ |
|
108 Breadth-first search. |
|
109 |
|
110 @type graph: graph |
|
111 @param graph: Graph. |
|
112 |
|
113 @type root: node |
|
114 @param root: Optional root node (will explore only root's connected component) |
|
115 |
|
116 @rtype: tuple |
|
117 @return: A tuple containing a dictionary and a list. |
|
118 1. Generated spanning tree |
|
119 2. Graph's level-based ordering |
|
120 """ |
|
121 queue = [] # Visiting queue |
|
122 spanning_tree = {} # Spanning tree |
|
123 ordering = [] |
|
124 |
|
125 # BFS from one node only |
|
126 if (root is not None): |
|
127 queue.append(root) |
|
128 ordering.append(root) |
|
129 spanning_tree[root] = None |
|
130 _bfs(graph, queue, spanning_tree, ordering) |
|
131 return spanning_tree, ordering |
|
132 |
|
133 # Algorithm |
|
134 for each in graph: |
|
135 if (each not in spanning_tree): |
|
136 queue.append(each) |
|
137 ordering.append(root) |
|
138 spanning_tree[each] = None |
|
139 _bfs(graph, queue, spanning_tree, ordering) |
|
140 |
|
141 return spanning_tree, ordering[1:] |
|
142 |
|
143 |
|
144 def _bfs(graph, queue, spanning_tree, ordering): |
|
145 """ |
|
146 Breadth-first search subfunction. |
|
147 |
|
148 @type graph: graph |
|
149 @param graph: Graph. |
|
150 |
|
151 @type spanning_tree: dictionary |
|
152 @param spanning_tree: Spanning tree being built for the graph by DFS. |
|
153 |
|
154 @type ordering: list |
|
155 @param ordering: Graph's level-based ordering. |
|
156 |
|
157 @type queue: list |
|
158 @param queue: Nodes to be visited (ordered). |
|
159 """ |
|
160 while (queue != []): |
|
161 node = queue.pop(0) |
|
162 |
|
163 for other in graph[node]: |
|
164 if (other not in spanning_tree): |
|
165 queue.append(other) |
|
166 ordering.append(other) |
|
167 spanning_tree[other] = node |