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 Traversal algorithms for python-graph. |
|
27 |
|
28 @sort: traversal |
|
29 """ |
|
30 |
|
31 |
|
32 # Minimal spanning tree |
|
33 |
|
34 def traversal(graph, node, order): |
|
35 """ |
|
36 Graph traversal iterator. |
|
37 |
|
38 @type node: node |
|
39 @param node: Node. |
|
40 |
|
41 @type order: string |
|
42 @param order: traversal ordering. Possible values are: |
|
43 2. 'pre' - Preordering (default) |
|
44 1. 'post' - Postordering |
|
45 |
|
46 @rtype: iterator |
|
47 @return: Traversal iterator. |
|
48 """ |
|
49 visited = {} |
|
50 if (order == 'pre'): |
|
51 pre = 1 |
|
52 post = 0 |
|
53 elif (order == 'post'): |
|
54 pre = 0 |
|
55 post = 1 |
|
56 |
|
57 for each in _dfs(graph, visited, node, pre, post): |
|
58 yield each |
|
59 |
|
60 |
|
61 def _dfs(graph, visited, node, pre, post): |
|
62 """ |
|
63 Depht-first search subfunction for traversals. |
|
64 |
|
65 @type graph: graph |
|
66 @param graph: Graph. |
|
67 |
|
68 @type visited: dictionary |
|
69 @param visited: List of nodes (visited nodes are marked non-zero). |
|
70 |
|
71 @type node: node |
|
72 @param node: Node to be explored by DFS. |
|
73 """ |
|
74 visited[node] = 1 |
|
75 if (pre): yield node |
|
76 # Explore recursively the connected component |
|
77 for each in graph[node]: |
|
78 if (each not in visited): |
|
79 for other in _dfs(graph, visited, each, pre, post): |
|
80 yield other |
|
81 if (post): yield node |
|