# Path: pyalgs/algorithms/graphs/connectivity.py
# class ConnectedComponents(object):
#     marked = None
#     _id = None
#     _count = 0
# 
#     def __init__(self, G):
#         if isinstance(G, EdgeWeightedGraph):
#             G = G.to_graph()
# 
#         vertex_count = G.vertex_count()
#         self.marked = [False] * vertex_count
#         self._id = [-1] * vertex_count
#         for v in range(vertex_count):
#             if not self.marked[v]:
#                 self.dfs(G, v)
#                 self._count += 1
# 
#     def dfs(self, G, v):
#         self.marked[v] = True
#         self._id[v] = self._count
#         for w in G.adj(v):
#             if not self.marked[w]:
#                 self.dfs(G, w)
# 
#     def connected(self, v, w):
#         return self._id[v] == self._id[w]
# 
#     def count(self):
#         return self._count
# 
#     def id(self, v):
#         return self._id[v]
# 
# class StronglyConnectedComponents(object):
#     marked = None
#     _id = None
#     _count = 0
# 
#     def __init__(self, G):
#         if isinstance(G, EdgeWeightedGraph):
#             raise ValueError('Graph must be directed graph for strongly connected components')
#         if isinstance(G, DirectedEdgeWeightedGraph):
#             G = G.to_digrah()
#         if not isinstance(G, Digraph):
#             raise ValueError('Graph must be directed graph for strongly connected components')
# 
#         vertex_count = G.vertex_count()
#         self.marked = [False] * vertex_count
#         self._id = [-1] * vertex_count
# 
#         dfo = DepthFirstOrder(G.reverse())
#         orders = dfo.postOrder()
# 
#         for v in orders:
#             if not self.marked[v]:
#                 self.dfs(G, v)
#                 self._count += 1
# 
#     def dfs(self, G, v):
#         self.marked[v] = True
#         self._id[v] = self._count
#         for w in G.adj(v):
#             if not self.marked[w]:
#                 self.dfs(G, w)
# 
#     def connected(self, v, w):
#         return self._id[v] == self._id[w]
# 
#     def count(self):
#         return self._count
# 
#     def id(self, v):
#         return self._id[v]
# 
# Path: tests/algorithms/graphs/util.py
# def create_graph_4_connected_components():
#     g = Graph(13)
#     g.add_edge(0, 5)
#     g.add_edge(4, 3)
#     g.add_edge(0, 1)
#     g.add_edge(9, 12)
#     g.add_edge(6, 4)
#     g.add_edge(5, 4)
#     g.add_edge(0, 2)
#     g.add_edge(11, 12)
#     g.add_edge(9, 10)
#     g.add_edge(0, 6)
#     g.add_edge(7, 8)
#     g.add_edge(9, 11)
#     g.add_edge(5, 3)
#     return g
# 
# def create_digraph_4_strongly_connected_components():
#     graph = Digraph(13)
#     graph.add_edge(4, 2)
#     graph.add_edge(2, 3)
#     graph.add_edge(3, 2)
#     graph.add_edge(6, 0)
#     graph.add_edge(0, 1)
#     graph.add_edge(2, 0)
#     graph.add_edge(11, 12)
#     graph.add_edge(12, 9)
#     graph.add_edge(9, 10)
#     graph.add_edge(9, 11)
#     graph.add_edge(8, 9)
#     graph.add_edge(10, 12)
#     graph.add_edge(11, 4)
#     graph.add_edge(4, 3)
#     graph.add_edge(3, 5)
#     graph.add_edge(7, 8)
#     graph.add_edge(8, 7)
#     graph.add_edge(5, 4)
#     graph.add_edge(0, 5)
#     graph.add_edge(6, 4)
#     graph.add_edge(6, 9)
#     graph.add_edge(7, 6)
# 
#     return graph


import unittest
from random import randint
from pyalgs.algorithms.graphs.connectivity import ConnectedComponents, StronglyConnectedComponents
from tests.algorithms.graphs.util import create_graph_4_connected_components, \
    create_digraph_4_strongly_connected_components



class ConnectedComponentsUnitTest(unittest.TestCase):
    def test_cc(self):
        G = create_graph_4_connected_components()

        cc = ConnectedComponents(G)
        print('connected component count: ' + str(cc.count()))

        self.assertEqual(3, cc.count())

        for v in range(G.vertex_count()):
            print('id[' + str(v) + ']: ' + str(cc.id(v)))
        for v in range(G.vertex_count()):
            r = randint(0, G.vertex_count() - 1)
            if cc.connected(v, r):
                print(str(v) + ' is connected to ' + str(r))


class StronglyConnectedComponentsUnitTest(unittest.TestCase):

# Path: pyalgs/algorithms/graphs/connectivity.py
# class ConnectedComponents(object):
#     marked = None
#     _id = None
#     _count = 0
# 
#     def __init__(self, G):
#         if isinstance(G, EdgeWeightedGraph):
#             G = G.to_graph()
# 
#         vertex_count = G.vertex_count()
#         self.marked = [False] * vertex_count
#         self._id = [-1] * vertex_count
#         for v in range(vertex_count):
#             if not self.marked[v]:
#                 self.dfs(G, v)
#                 self._count += 1
# 
#     def dfs(self, G, v):
#         self.marked[v] = True
#         self._id[v] = self._count
#         for w in G.adj(v):
#             if not self.marked[w]:
#                 self.dfs(G, w)
# 
#     def connected(self, v, w):
#         return self._id[v] == self._id[w]
# 
#     def count(self):
#         return self._count
# 
#     def id(self, v):
#         return self._id[v]
# 
# class StronglyConnectedComponents(object):
#     marked = None
#     _id = None
#     _count = 0
# 
#     def __init__(self, G):
#         if isinstance(G, EdgeWeightedGraph):
#             raise ValueError('Graph must be directed graph for strongly connected components')
#         if isinstance(G, DirectedEdgeWeightedGraph):
#             G = G.to_digrah()
#         if not isinstance(G, Digraph):
#             raise ValueError('Graph must be directed graph for strongly connected components')
# 
#         vertex_count = G.vertex_count()
#         self.marked = [False] * vertex_count
#         self._id = [-1] * vertex_count
# 
#         dfo = DepthFirstOrder(G.reverse())
#         orders = dfo.postOrder()
# 
#         for v in orders:
#             if not self.marked[v]:
#                 self.dfs(G, v)
#                 self._count += 1
# 
#     def dfs(self, G, v):
#         self.marked[v] = True
#         self._id[v] = self._count
#         for w in G.adj(v):
#             if not self.marked[w]:
#                 self.dfs(G, w)
# 
#     def connected(self, v, w):
#         return self._id[v] == self._id[w]
# 
#     def count(self):
#         return self._count
# 
#     def id(self, v):
#         return self._id[v]
# 
# Path: tests/algorithms/graphs/util.py
# def create_graph_4_connected_components():
#     g = Graph(13)
#     g.add_edge(0, 5)
#     g.add_edge(4, 3)
#     g.add_edge(0, 1)
#     g.add_edge(9, 12)
#     g.add_edge(6, 4)
#     g.add_edge(5, 4)
#     g.add_edge(0, 2)
#     g.add_edge(11, 12)
#     g.add_edge(9, 10)
#     g.add_edge(0, 6)
#     g.add_edge(7, 8)
#     g.add_edge(9, 11)
#     g.add_edge(5, 3)
#     return g
# 
# def create_digraph_4_strongly_connected_components():
#     graph = Digraph(13)
#     graph.add_edge(4, 2)
#     graph.add_edge(2, 3)
#     graph.add_edge(3, 2)
#     graph.add_edge(6, 0)
#     graph.add_edge(0, 1)
#     graph.add_edge(2, 0)
#     graph.add_edge(11, 12)
#     graph.add_edge(12, 9)
#     graph.add_edge(9, 10)
#     graph.add_edge(9, 11)
#     graph.add_edge(8, 9)
#     graph.add_edge(10, 12)
#     graph.add_edge(11, 4)
#     graph.add_edge(4, 3)
#     graph.add_edge(3, 5)
#     graph.add_edge(7, 8)
#     graph.add_edge(8, 7)
#     graph.add_edge(5, 4)
#     graph.add_edge(0, 5)
#     graph.add_edge(6, 4)
#     graph.add_edge(6, 9)
#     graph.add_edge(7, 6)
# 
#     return graph


# Path: tests/algorithms/graphs/connectivity_unit_test.py
import unittest
from random import randint
from pyalgs.algorithms.graphs.connectivity import ConnectedComponents, StronglyConnectedComponents
from tests.algorithms.graphs.util import create_graph_4_connected_components, \
    create_digraph_4_strongly_connected_components




class ConnectedComponentsUnitTest(unittest.TestCase):
    def test_cc(self):
        G = create_graph_4_connected_components()

        cc = ConnectedComponents(G)
        print('connected component count: ' + str(cc.count()))

        self.assertEqual(3, cc.count())

        for v in range(G.vertex_count()):
            print('id[' + str(v) + ']: ' + str(cc.id(v)))
        for v in range(G.vertex_count()):
            r = randint(0, G.vertex_count() - 1)
            if cc.connected(v, r):
                print(str(v) + ' is connected to ' + str(r))


class StronglyConnectedComponentsUnitTest(unittest.TestCase):

    def test_cc(self):