pyAlgr/graph_paths.py at master · whille/pyAlgr · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
"""
   Execution:  python depth_first_paths.py G s

   Data files:   https://algs4.cs.princeton.edu/41graph/tinyCG.txt
                 https://algs4.cs.princeton.edu/41graph/tinyG.txt
                 https://algs4.cs.princeton.edu/41graph/mediumG.txt
                 https://algs4.cs.princeton.edu/41graph/largeG.txt

   Run depth first search on an undirected graph.
   Runs in O(E + V) time.

   % python depth_first_paths.py tinyCG.txt 0
   0 to 0:  0
   0 to 1:  0-2-1
   0 to 2:  0-2
   0 to 3:  0-2-3
   0 to 4:  0-2-3-4
   0 to 5:  0-2-3-5

"""
from utils import Stack, Queue
from graph import graph_from_file


class GraphPaths:
    def __init__(self, G, src):
        self.marked = [False for _ in range(G.V)]
        self.edge_to = [0 for _ in range(G.V)]
        self.s = src
        self.build_path(G, src)

    def build_path(self, G, v):
        raise 'implement in subclass'

    def has_path_to(self, v):
        return self.marked[v]

    def path_to(self, v):
        if not self.has_path_to(v):
            return []
        path = Stack()
        x = v
        while x != self.s:
            path.push(x)
            x = self.edge_to[x]
        path.push(self.s)
        return path


class DepthFirstPaths(GraphPaths):
    def build_path(self, G, v):
        self.marked[v] = True
        for w in G.adj[v]:
            if not self.marked[w]:
                self.edge_to[w] = v
                self.build_path(G, w)


class BreadthFirstPaths(GraphPaths):
    def build_path(self, G, s):
        self.marked[s] = True
        queue = Queue()
        queue.enqueue(s)
        while not queue.is_empty():
            v = queue.dequeue()
            for w in G.adj[v]:
                if not self.marked[w]:
                    self.edge_to[w] = v
                    self.marked[w] = True
                    queue.enqueue(w)


def test_path(cls, g, s):
    gp = cls(g, s)
    for v in range(g.V):
        s_path = '-'.join([str(i) for i in gp.path_to(v)])
        if not s_path:
            s_path = "not connected"
        print("%d to %d: %s" % (s, v, s_path))


if __name__ == '__main__':
    import sys
    f = open(sys.argv[1])
    s = int(sys.argv[2])
    g = graph_from_file(f)
    for cls in DepthFirstPaths, BreadthFirstPaths:
        print cls
        test_path(cls, g, s)