# Path: pyalgs/data_structures/commons/queue.py
# class Queue(object):
#     """ Queue interface
#     
#     """
# 
#     __metaclass__ = ABCMeta
# 
#     @abstractmethod
#     def enqueue(self, item):
#         pass
# 
#     @abstractmethod
#     def dequeue(self):
#         pass
# 
#     @abstractmethod
#     def is_empty(self):
#         pass
# 
#     @abstractmethod
#     def size(self):
#         pass
# 
#     @staticmethod
#     def create():
#         return LinkedListQueue()
# 
#     @abstractmethod
#     def iterate(self):
#         pass
# 
# Path: pyalgs/data_structures/commons/stack.py
# class Stack(object):
#     """ Stack interface which provides the API for stack data structure
#     """
# 
#     __metaclass__ = ABCMeta
# 
#     @abstractmethod
#     def push(self, item):
#         pass
# 
#     @abstractmethod
#     def pop(self):
#         pass
# 
#     @abstractmethod
#     def is_empty(self):
#         pass
# 
#     @abstractmethod
#     def size(self):
#         pass
# 
#     @abstractmethod
#     def iterate(self):
#         pass
# 
#     @staticmethod
#     def create():
#         return LinkedListStack()
# 
# Path: pyalgs/data_structures/graphs/graph.py
# class EdgeWeightedGraph(object):
#     adjList = None
#     V = 0
# 
#     def __init__(self, vertex_count):
#         self.V = vertex_count
#         self.adjList = [None] * vertex_count
#         for v in range(vertex_count):
#             self.adjList[v] = Bag()
# 
#     def add_edge(self, edge):
#         v = edge.either()
#         w = edge.other(v)
#         self.adjList[v].add(edge)
#         self.adjList[w].add(edge)
# 
#     def adj(self, v):
#         return self.adjList[v].iterate()
# 
#     def vertex_count(self):
#         return self.V
# 
#     def edges(self):
#         for v in range(self.V):
#             for e in self.adj(v):
#                 if e.either() == v:
#                     yield e
# 
#     def to_graph(self):
#         g = Graph()
# 
#         for e in self.edges():
#             g.add_edge(e.start(), e.end())
#         return g
# 
#     def to_edge_weighted_digraph(self):
#         g = DirectedEdgeWeightedGraph(self.V)
# 
#         for e in self.edges():
#             g.add_edge(e)
#             g.add_edge(e.reverse())
#         return g


from abc import ABCMeta, abstractmethod
from pyalgs.data_structures.commons.queue import Queue
from pyalgs.data_structures.commons.stack import Stack
from pyalgs.data_structures.graphs.graph import EdgeWeightedGraph
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: pyalgs/data_structures/commons/queue.py
# class Queue(object):
#     """ Queue interface
#     
#     """
# 
#     __metaclass__ = ABCMeta
# 
#     @abstractmethod
#     def enqueue(self, item):
#         pass
# 
#     @abstractmethod
#     def dequeue(self):
#         pass
# 
#     @abstractmethod
#     def is_empty(self):
#         pass
# 
#     @abstractmethod
#     def size(self):
#         pass
# 
#     @staticmethod
#     def create():
#         return LinkedListQueue()
# 
#     @abstractmethod
#     def iterate(self):
#         pass
# 
# Path: pyalgs/data_structures/commons/stack.py
# class Stack(object):
#     """ Stack interface which provides the API for stack data structure
#     """
# 
#     __metaclass__ = ABCMeta
# 
#     @abstractmethod
#     def push(self, item):
#         pass
# 
#     @abstractmethod
#     def pop(self):
#         pass
# 
#     @abstractmethod
#     def is_empty(self):
#         pass
# 
#     @abstractmethod
#     def size(self):
#         pass
# 
#     @abstractmethod
#     def iterate(self):
#         pass
# 
#     @staticmethod
#     def create():
#         return LinkedListStack()
# 
# Path: pyalgs/data_structures/graphs/graph.py
# class EdgeWeightedGraph(object):
#     adjList = None
#     V = 0
# 
#     def __init__(self, vertex_count):
#         self.V = vertex_count
#         self.adjList = [None] * vertex_count
#         for v in range(vertex_count):
#             self.adjList[v] = Bag()
# 
#     def add_edge(self, edge):
#         v = edge.either()
#         w = edge.other(v)
#         self.adjList[v].add(edge)
#         self.adjList[w].add(edge)
# 
#     def adj(self, v):
#         return self.adjList[v].iterate()
# 
#     def vertex_count(self):
#         return self.V
# 
#     def edges(self):
#         for v in range(self.V):
#             for e in self.adj(v):
#                 if e.either() == v:
#                     yield e
# 
#     def to_graph(self):
#         g = Graph()
# 
#         for e in self.edges():
#             g.add_edge(e.start(), e.end())
#         return g
# 
#     def to_edge_weighted_digraph(self):
#         g = DirectedEdgeWeightedGraph(self.V)
# 
#         for e in self.edges():
#             g.add_edge(e)
#             g.add_edge(e.reverse())
#         return g


# Path: pyalgs/algorithms/graphs/search.py
from abc import ABCMeta, abstractmethod
from pyalgs.data_structures.commons.queue import Queue
from pyalgs.data_structures.commons.stack import Stack
from pyalgs.data_structures.graphs.graph import EdgeWeightedGraph

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()