Download code

Jump to: navigation, search

Back to Depth-first_search_(Python)

Download for Windows: single file, zip

Download for UNIX: single file, zip, tar.gz, tar.bz2

vertex.py

 1 # The authors of this work have released all rights to it and placed it
 2 # in the public domain under the Creative Commons CC0 1.0 waiver
 3 # (http://creativecommons.org/publicdomain/zero/1.0/).
 4 # 
 5 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 6 # EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 7 # MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 8 # IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
 9 # CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
10 # TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
11 # SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
12 # 
13 # Retrieved from: http://en.literateprograms.org/Depth-first_search_(Python)?oldid=15001
14 
15 class Vertex:
16     def __init__(self, data):
17         self.data = data
18         self.successors = []
19 
20 
21 def depthFirstSearch(start, isGoal, result):
22     if start in result:
23         return False
24 
25     result.append(start)
26 
27     if isGoal(start):
28         return True
29     for v in start.successors:
30         if depthFirstSearch(v, isGoal, result):
31             return True
32 
33     # No path was found
34     result.pop()
35     return False
36 
37 def petersenGraph():
38     v = [Vertex(i) for i in xrange(10)]
39     edges = \
40         [(0,1), (1,0), (1,2), (2,1), (2,3), (3,2), (3,4), (4,3), (4,0), (0,4),
41          (5,6), (6,5), (6,7), (7,6), (7,8), (8,7), (8,9), (9,8), (9,5), (5,9),
42          (5,0), (0,5), (6,2), (2,6), (7,4), (4,7), (8,1), (1,8), (9,3), (3,9)]
43     for a, b in edges:
44         v[a].successors.append(v[b])
45     return v
46 
47 if __name__ == "__main__":
48     v = petersenGraph()
49     path = []
50     if depthFirstSearch(v[0], (lambda v: v.data == 7), path):
51         print "Found path:", [u.data for u in path]
52     else:
53         print "No path found"
54 


hijacker
hijacker
hijacker
hijacker