# Path: pyalgs/algorithms/graphs/directed_cycle.py
# class DirectedCycle(object):
# 
#     marked = None
#     onStack = None
#     cycle = None
#     edgeTo = None
# 
#     def __init__(self, G):
#         if isinstance(G, DirectedEdgeWeightedGraph):
#             G = G.to_digraph()
# 
#         if not isinstance(G, Digraph):
#             raise ValueError('Graph must be unweighted digraph')
# 
#         vertex_count = G.vertex_count()
#         self.marked = [False] * vertex_count
#         self.onStack = [False] * vertex_count
#         self.edgeTo = [-1] * vertex_count
# 
#         for v in range(vertex_count):
#             if not self.marked[v]:
#                 self.dfs(G, v)
# 
#     def dfs(self, G, v):
#         self.marked[v] = True
#         self.onStack[v] = True
# 
#         for w in G.adj(v):
#             if not self.marked[w]:
#                 self.edgeTo[w] = v
#                 self.dfs(G, w)
#             elif self.cycle is not None:
#                 break
#             elif self.onStack[w]:
#                 self.cycle = Stack.create()
#                 x = v
#                 while x != w:
#                     self.cycle.push(x)
#                     x = self.edgeTo[x]
#                 self.cycle.push(w)
#                 self.cycle.push(v)
#                 break
# 
#         self.onStack[v] = False
# 
#     def hasCycle(self):
#         return self.cycle is not None
# 
#     def get_cycle(self):
#         return self.cycle.iterate()
# 
# Path: tests/algorithms/graphs/util.py
# def create_dag():
#     dag = Digraph(7)
# 
#     dag.add_edge(0, 5)
#     dag.add_edge(0, 2)
#     dag.add_edge(0, 1)
#     dag.add_edge(3, 6)
#     dag.add_edge(3, 5)
#     dag.add_edge(3, 4)
#     dag.add_edge(5, 4)
#     dag.add_edge(6, 4)
#     dag.add_edge(6, 0)
#     dag.add_edge(3, 2)
#     dag.add_edge(1, 4)
# 
#     return dag


import unittest
from pyalgs.algorithms.graphs.directed_cycle import DirectedCycle
from tests.algorithms.graphs.util import create_dag



class DirectedCycleUnitTest(unittest.TestCase):

    def test_cycle(self):

        dag = create_dag()
        dc = DirectedCycle(dag)

        self.assertFalse(dc.hasCycle())



# Path: pyalgs/algorithms/graphs/directed_cycle.py
# class DirectedCycle(object):
# 
#     marked = None
#     onStack = None
#     cycle = None
#     edgeTo = None
# 
#     def __init__(self, G):
#         if isinstance(G, DirectedEdgeWeightedGraph):
#             G = G.to_digraph()
# 
#         if not isinstance(G, Digraph):
#             raise ValueError('Graph must be unweighted digraph')
# 
#         vertex_count = G.vertex_count()
#         self.marked = [False] * vertex_count
#         self.onStack = [False] * vertex_count
#         self.edgeTo = [-1] * vertex_count
# 
#         for v in range(vertex_count):
#             if not self.marked[v]:
#                 self.dfs(G, v)
# 
#     def dfs(self, G, v):
#         self.marked[v] = True
#         self.onStack[v] = True
# 
#         for w in G.adj(v):
#             if not self.marked[w]:
#                 self.edgeTo[w] = v
#                 self.dfs(G, w)
#             elif self.cycle is not None:
#                 break
#             elif self.onStack[w]:
#                 self.cycle = Stack.create()
#                 x = v
#                 while x != w:
#                     self.cycle.push(x)
#                     x = self.edgeTo[x]
#                 self.cycle.push(w)
#                 self.cycle.push(v)
#                 break
# 
#         self.onStack[v] = False
# 
#     def hasCycle(self):
#         return self.cycle is not None
# 
#     def get_cycle(self):
#         return self.cycle.iterate()
# 
# Path: tests/algorithms/graphs/util.py
# def create_dag():
#     dag = Digraph(7)
# 
#     dag.add_edge(0, 5)
#     dag.add_edge(0, 2)
#     dag.add_edge(0, 1)
#     dag.add_edge(3, 6)
#     dag.add_edge(3, 5)
#     dag.add_edge(3, 4)
#     dag.add_edge(5, 4)
#     dag.add_edge(6, 4)
#     dag.add_edge(6, 0)
#     dag.add_edge(3, 2)
#     dag.add_edge(1, 4)
# 
#     return dag


# Path: tests/algorithms/graphs/directed_cycle_unit_test.py
import unittest
from pyalgs.algorithms.graphs.directed_cycle import DirectedCycle
from tests.algorithms.graphs.util import create_dag




class DirectedCycleUnitTest(unittest.TestCase):

    def test_cycle(self):

        dag = create_dag()
        dc = DirectedCycle(dag)

        self.assertFalse(dc.hasCycle())



if __name__ == '__main__':