# Path: pyalgs/algorithms/graphs/search.py
# class DepthFirstSearch(Paths):
#     marked = None
#     edgesTo = None
#     s = None
# 
#     def __init__(self, G, s):
#         if isinstance(G, EdgeWeightedGraph):
#             G = G.to_graph()
#         self.s = s
#         vertex_count = G.vertex_count()
#         self.marked = [False] * vertex_count
#         self.edgesTo = [-1] * vertex_count
#         self.dfs(G, s)
# 
#     def dfs(self, G, v):
#         self.marked[v] = True
#         for w in G.adj(v):
#             if not self.marked[w]:
#                 self.edgesTo[w] = v
#                 self.dfs(G, w)
# 
#     def hasPathTo(self, v):
#         return self.marked[v]
# 
#     def pathTo(self, v):
#         x = v
#         path = Stack.create()
#         while x != self.s:
#             path.push(x)
#             x = self.edgesTo[x]
#         path.push(self.s)
#         return path.iterate()
# 
# class BreadthFirstSearch(Paths):
# 
#     marked = None
#     s = None
#     edgeTo = None
# 
#     def __init__(self, G, s):
#         if isinstance(G, EdgeWeightedGraph):
#             G = G.to_graph()
#         self.s = s
#         vertex_count = G.vertex_count()
#         self.marked = [False] * vertex_count
#         self.edgeTo = [-1] * vertex_count
# 
#         queue = Queue.create()
# 
#         queue.enqueue(s)
#         while not queue.is_empty():
#             v = queue.dequeue()
#             self.marked[v] = True
#             for w in G.adj(v):
#                 if not self.marked[w]:
#                     self.edgeTo[w] = v
#                     queue.enqueue(w)
# 
#     def hasPathTo(self, v):
#         return self.marked[v]
# 
#     def pathTo(self, v):
#         x = v
#         path = Stack.create()
#         while x != self.s:
#             path.push(x)
#             x = self.edgeTo[x]
#         path.push(self.s)
#         return path.iterate()
# 
# Path: tests/algorithms/graphs/util.py
# def create_graph():
#     g = Graph(6)
#     g.add_edge(0, 5)
#     g.add_edge(2, 4)
#     g.add_edge(2, 3)
#     g.add_edge(1, 2)
#     g.add_edge(0, 1)
#     g.add_edge(3, 4)
#     g.add_edge(3, 5)
#     g.add_edge(0, 2)
# 
#     return g
# 
# def create_digraph():
#     g = Digraph(13)
#     g.add_edge(4, 2)
#     g.add_edge(2, 3)
#     g.add_edge(3, 2)
#     g.add_edge(6, 0)
#     g.add_edge(0, 1)
#     g.add_edge(2, 0)
#     g.add_edge(11, 12)
#     g.add_edge(12, 9)
#     g.add_edge(9, 10)
#     g.add_edge(9, 11)
#     g.add_edge(7, 9)
#     g.add_edge(10, 12)
#     g.add_edge(11, 4)
#     g.add_edge(4, 3)
#     g.add_edge(3, 5)
#     g.add_edge(6, 8)
#     g.add_edge(8, 6)
#     g.add_edge(5, 4)
#     g.add_edge(0, 5)
#     g.add_edge(6, 4)
#     g.add_edge(6, 9)
#     g.add_edge(7, 6)
# 
#     return g


import unittest
from pyalgs.algorithms.graphs.search import DepthFirstSearch, BreadthFirstSearch
from tests.algorithms.graphs.util import create_graph, create_digraph

        for v in range(1, g.vertex_count()):
            if dfs.hasPathTo(v):
                print(str(s) + ' is connected to ' + str(v))
                print('path is ' + ' => '.join([str(i) for i in dfs.pathTo(v)]))

    def test_dfs_digraph(self):
        g = create_digraph()
        s = 0
        dfs = DepthFirstSearch(g, s)

        for v in range(1, g.vertex_count()):
            if dfs.hasPathTo(v):
                print(str(s) + ' is connected to ' + str(v))
                print('path is ' + ' => '.join([str(i) for i in dfs.pathTo(v)]))

class BreadthFirstSearchUnitTest(unittest.TestCase):
    def test_dfs(self):
        g = create_graph() # or create_digraph
        s = 0
        dfs = BreadthFirstSearch(g, s)

        for v in range(1, g.vertex_count()):
            if dfs.hasPathTo(v):
                print(str(s) + ' is connected to ' + str(v))
                print('path is ' + ' => '.join([str(i) for i in dfs.pathTo(v)]))

    def test_dfs_digraph(self):
        g = create_digraph()
        s = 0

# Path: pyalgs/algorithms/graphs/search.py
# class DepthFirstSearch(Paths):
#     marked = None
#     edgesTo = None
#     s = None
# 
#     def __init__(self, G, s):
#         if isinstance(G, EdgeWeightedGraph):
#             G = G.to_graph()
#         self.s = s
#         vertex_count = G.vertex_count()
#         self.marked = [False] * vertex_count
#         self.edgesTo = [-1] * vertex_count
#         self.dfs(G, s)
# 
#     def dfs(self, G, v):
#         self.marked[v] = True
#         for w in G.adj(v):
#             if not self.marked[w]:
#                 self.edgesTo[w] = v
#                 self.dfs(G, w)
# 
#     def hasPathTo(self, v):
#         return self.marked[v]
# 
#     def pathTo(self, v):
#         x = v
#         path = Stack.create()
#         while x != self.s:
#             path.push(x)
#             x = self.edgesTo[x]
#         path.push(self.s)
#         return path.iterate()
# 
# class BreadthFirstSearch(Paths):
# 
#     marked = None
#     s = None
#     edgeTo = None
# 
#     def __init__(self, G, s):
#         if isinstance(G, EdgeWeightedGraph):
#             G = G.to_graph()
#         self.s = s
#         vertex_count = G.vertex_count()
#         self.marked = [False] * vertex_count
#         self.edgeTo = [-1] * vertex_count
# 
#         queue = Queue.create()
# 
#         queue.enqueue(s)
#         while not queue.is_empty():
#             v = queue.dequeue()
#             self.marked[v] = True
#             for w in G.adj(v):
#                 if not self.marked[w]:
#                     self.edgeTo[w] = v
#                     queue.enqueue(w)
# 
#     def hasPathTo(self, v):
#         return self.marked[v]
# 
#     def pathTo(self, v):
#         x = v
#         path = Stack.create()
#         while x != self.s:
#             path.push(x)
#             x = self.edgeTo[x]
#         path.push(self.s)
#         return path.iterate()
# 
# Path: tests/algorithms/graphs/util.py
# def create_graph():
#     g = Graph(6)
#     g.add_edge(0, 5)
#     g.add_edge(2, 4)
#     g.add_edge(2, 3)
#     g.add_edge(1, 2)
#     g.add_edge(0, 1)
#     g.add_edge(3, 4)
#     g.add_edge(3, 5)
#     g.add_edge(0, 2)
# 
#     return g
# 
# def create_digraph():
#     g = Digraph(13)
#     g.add_edge(4, 2)
#     g.add_edge(2, 3)
#     g.add_edge(3, 2)
#     g.add_edge(6, 0)
#     g.add_edge(0, 1)
#     g.add_edge(2, 0)
#     g.add_edge(11, 12)
#     g.add_edge(12, 9)
#     g.add_edge(9, 10)
#     g.add_edge(9, 11)
#     g.add_edge(7, 9)
#     g.add_edge(10, 12)
#     g.add_edge(11, 4)
#     g.add_edge(4, 3)
#     g.add_edge(3, 5)
#     g.add_edge(6, 8)
#     g.add_edge(8, 6)
#     g.add_edge(5, 4)
#     g.add_edge(0, 5)
#     g.add_edge(6, 4)
#     g.add_edge(6, 9)
#     g.add_edge(7, 6)
# 
#     return g


# Path: tests/algorithms/graphs/search_unit_test.py
import unittest
from pyalgs.algorithms.graphs.search import DepthFirstSearch, BreadthFirstSearch
from tests.algorithms.graphs.util import create_graph, create_digraph


        for v in range(1, g.vertex_count()):
            if dfs.hasPathTo(v):
                print(str(s) + ' is connected to ' + str(v))
                print('path is ' + ' => '.join([str(i) for i in dfs.pathTo(v)]))

    def test_dfs_digraph(self):
        g = create_digraph()
        s = 0
        dfs = DepthFirstSearch(g, s)

        for v in range(1, g.vertex_count()):
            if dfs.hasPathTo(v):
                print(str(s) + ' is connected to ' + str(v))
                print('path is ' + ' => '.join([str(i) for i in dfs.pathTo(v)]))

class BreadthFirstSearchUnitTest(unittest.TestCase):
    def test_dfs(self):
        g = create_graph() # or create_digraph
        s = 0
        dfs = BreadthFirstSearch(g, s)

        for v in range(1, g.vertex_count()):
            if dfs.hasPathTo(v):
                print(str(s) + ' is connected to ' + str(v))
                print('path is ' + ' => '.join([str(i) for i in dfs.pathTo(v)]))

    def test_dfs_digraph(self):
        g = create_digraph()
        s = 0

        dfs = BreadthFirstSearch(g, s)