# Path: pyalgs/algorithms/graphs/minimum_spanning_trees.py
# class KruskalMST(MST):
#     tree = None
# 
#     def __init__(self, G):
#         if not isinstance(G, EdgeWeightedGraph):
#             raise ValueError('Graph must be edge weighted and undirected to run MST')
#         minpq = MinPQ.create()
#         self.tree = Bag()
#         for e in G.edges():
#             minpq.enqueue(e)
# 
#         uf = UnionFind.create(G.vertex_count())
# 
#         while not minpq.is_empty() and self.tree.size() < G.vertex_count() - 1:
#             e = minpq.del_min()
#             v = e.either()
#             w = e.other(v)
#             if not uf.connected(v, w):
#                 uf.union(v, w)
#                 self.tree.add(e)
# 
#     def spanning_tree(self):
#         return self.tree.iterate()
# 
# class LazyPrimMST(MST):
#     tree = None
#     marked = None
#     minpq = None
# 
#     def __init__(self, G):
#         if not isinstance(G, EdgeWeightedGraph):
#             raise ValueError('Graph must be edge weighted and undirected to run MST')
#         self.minpq = MinPQ.create()
#         self.tree = Bag()
#         vertex_count = G.vertex_count()
#         self.marked = [False] * vertex_count
#         self.visit(G, 0)
# 
#         while not self.minpq.is_empty() and self.tree.size() < vertex_count - 1:
#             edge = self.minpq.del_min()
#             v = edge.either()
#             w = edge.other(v)
#             if self.marked[v] and self.marked[w]:
#                 continue
#             self.tree.add(edge)
#             if not self.marked[v]:
#                 self.visit(G, v)
#             if not self.marked[w]:
#                 self.visit(G, w)
# 
#     def visit(self, G, v):
#         self.marked[v] = True
#         for e in G.adj(v):
#             w = e.other(v)
#             if not self.marked[w]:
#                 self.minpq.enqueue(e)
# 
#     def spanning_tree(self):
#         return self.tree.iterate()
# 
# class EagerPrimMST(MST):
#     path = None
#     pq = None
#     marked = None
# 
#     def __init__(self, G):
#         if not isinstance(G, EdgeWeightedGraph):
#             raise ValueError('Graph must be edge weighted and undirected to run MST')
#         vertex_count = G.vertex_count()
#         self.pq = IndexMinPQ(vertex_count)
#         self.path = Bag()
#         self.marked = [False] * vertex_count
# 
#         self.visit(G, 0)
# 
#         while not self.pq.is_empty() and self.path.size() < vertex_count - 1:
#             e = self.pq.min_key()
#             w = self.pq.del_min()
#             self.path.add(e)
#             if not self.marked[w]:
#                 self.visit(G, w)
# 
#     def visit(self, G, v):
#         self.marked[v] = True
#         for e in G.adj(v):
#             w = e.other(v)
#             if not self.marked[w]:
#                 if self.pq.contains_index(w):
#                     old_e = self.pq.get(w)
#                     if less(e, old_e):
#                         self.pq.decrease_key(w, e)
#                 else:
#                     self.pq.insert(w, e)
# 
#     def spanning_tree(self):
#         return self.path.iterate()
# 
# Path: tests/algorithms/graphs/util.py
# def create_edge_weighted_graph():
#     g = EdgeWeightedGraph(8)
#     g.add_edge(Edge(0, 7, 0.16))
#     g.add_edge(Edge(2, 3, 0.17))
#     g.add_edge(Edge(1, 7, 0.19))
#     g.add_edge(Edge(0, 2, 0.26))
#     g.add_edge(Edge(5, 7, 0.28))
#     g.add_edge(Edge(1, 3, 0.29))
#     g.add_edge(Edge(1, 5, 0.32))
#     g.add_edge(Edge(2, 7, 0.34))
#     g.add_edge(Edge(4, 5, 0.35))
#     g.add_edge(Edge(1, 2, 0.36))
#     g.add_edge(Edge(4, 7, 0.37))
#     g.add_edge(Edge(0, 4, 0.38))
#     g.add_edge(Edge(6, 2, 0.4))
#     g.add_edge(Edge(3, 6, 0.52))
#     g.add_edge(Edge(6, 0, 0.58))
#     g.add_edge(Edge(6, 4, 0.93))
# 
#     return g


import unittest
from pyalgs.algorithms.graphs.minimum_spanning_trees import KruskalMST, LazyPrimMST, EagerPrimMST
from tests.algorithms.graphs.util import create_edge_weighted_graph



class KruskalMSTUnitTest(unittest.TestCase):
    def test_mst(self):
        g = create_edge_weighted_graph()
        mst = KruskalMST(g)

        tree = mst.spanning_tree()

        for e in tree:
            print(e)


class LazyPrimMSTUnitTest(unittest.TestCase):
    def test_mst(self):
        g = create_edge_weighted_graph()
        mst = LazyPrimMST(g)

        tree = mst.spanning_tree()

        for e in tree:
            print(e)


class EagerPrimMSTUnitTest(unittest.TestCase):
    def test_mst(self):

# Path: pyalgs/algorithms/graphs/minimum_spanning_trees.py
# class KruskalMST(MST):
#     tree = None
# 
#     def __init__(self, G):
#         if not isinstance(G, EdgeWeightedGraph):
#             raise ValueError('Graph must be edge weighted and undirected to run MST')
#         minpq = MinPQ.create()
#         self.tree = Bag()
#         for e in G.edges():
#             minpq.enqueue(e)
# 
#         uf = UnionFind.create(G.vertex_count())
# 
#         while not minpq.is_empty() and self.tree.size() < G.vertex_count() - 1:
#             e = minpq.del_min()
#             v = e.either()
#             w = e.other(v)
#             if not uf.connected(v, w):
#                 uf.union(v, w)
#                 self.tree.add(e)
# 
#     def spanning_tree(self):
#         return self.tree.iterate()
# 
# class LazyPrimMST(MST):
#     tree = None
#     marked = None
#     minpq = None
# 
#     def __init__(self, G):
#         if not isinstance(G, EdgeWeightedGraph):
#             raise ValueError('Graph must be edge weighted and undirected to run MST')
#         self.minpq = MinPQ.create()
#         self.tree = Bag()
#         vertex_count = G.vertex_count()
#         self.marked = [False] * vertex_count
#         self.visit(G, 0)
# 
#         while not self.minpq.is_empty() and self.tree.size() < vertex_count - 1:
#             edge = self.minpq.del_min()
#             v = edge.either()
#             w = edge.other(v)
#             if self.marked[v] and self.marked[w]:
#                 continue
#             self.tree.add(edge)
#             if not self.marked[v]:
#                 self.visit(G, v)
#             if not self.marked[w]:
#                 self.visit(G, w)
# 
#     def visit(self, G, v):
#         self.marked[v] = True
#         for e in G.adj(v):
#             w = e.other(v)
#             if not self.marked[w]:
#                 self.minpq.enqueue(e)
# 
#     def spanning_tree(self):
#         return self.tree.iterate()
# 
# class EagerPrimMST(MST):
#     path = None
#     pq = None
#     marked = None
# 
#     def __init__(self, G):
#         if not isinstance(G, EdgeWeightedGraph):
#             raise ValueError('Graph must be edge weighted and undirected to run MST')
#         vertex_count = G.vertex_count()
#         self.pq = IndexMinPQ(vertex_count)
#         self.path = Bag()
#         self.marked = [False] * vertex_count
# 
#         self.visit(G, 0)
# 
#         while not self.pq.is_empty() and self.path.size() < vertex_count - 1:
#             e = self.pq.min_key()
#             w = self.pq.del_min()
#             self.path.add(e)
#             if not self.marked[w]:
#                 self.visit(G, w)
# 
#     def visit(self, G, v):
#         self.marked[v] = True
#         for e in G.adj(v):
#             w = e.other(v)
#             if not self.marked[w]:
#                 if self.pq.contains_index(w):
#                     old_e = self.pq.get(w)
#                     if less(e, old_e):
#                         self.pq.decrease_key(w, e)
#                 else:
#                     self.pq.insert(w, e)
# 
#     def spanning_tree(self):
#         return self.path.iterate()
# 
# Path: tests/algorithms/graphs/util.py
# def create_edge_weighted_graph():
#     g = EdgeWeightedGraph(8)
#     g.add_edge(Edge(0, 7, 0.16))
#     g.add_edge(Edge(2, 3, 0.17))
#     g.add_edge(Edge(1, 7, 0.19))
#     g.add_edge(Edge(0, 2, 0.26))
#     g.add_edge(Edge(5, 7, 0.28))
#     g.add_edge(Edge(1, 3, 0.29))
#     g.add_edge(Edge(1, 5, 0.32))
#     g.add_edge(Edge(2, 7, 0.34))
#     g.add_edge(Edge(4, 5, 0.35))
#     g.add_edge(Edge(1, 2, 0.36))
#     g.add_edge(Edge(4, 7, 0.37))
#     g.add_edge(Edge(0, 4, 0.38))
#     g.add_edge(Edge(6, 2, 0.4))
#     g.add_edge(Edge(3, 6, 0.52))
#     g.add_edge(Edge(6, 0, 0.58))
#     g.add_edge(Edge(6, 4, 0.93))
# 
#     return g


# Path: tests/algorithms/graphs/minimum_spanning_tree_unit_test.py
import unittest
from pyalgs.algorithms.graphs.minimum_spanning_trees import KruskalMST, LazyPrimMST, EagerPrimMST
from tests.algorithms.graphs.util import create_edge_weighted_graph




class KruskalMSTUnitTest(unittest.TestCase):
    def test_mst(self):
        g = create_edge_weighted_graph()
        mst = KruskalMST(g)

        tree = mst.spanning_tree()

        for e in tree:
            print(e)


class LazyPrimMSTUnitTest(unittest.TestCase):
    def test_mst(self):
        g = create_edge_weighted_graph()
        mst = LazyPrimMST(g)

        tree = mst.spanning_tree()

        for e in tree:
            print(e)


class EagerPrimMSTUnitTest(unittest.TestCase):
    def test_mst(self):

        g = create_edge_weighted_graph()