def testAddEmptyGraph(self):
     gr1 = pygraph.digraph()
     gr1.generate(25, 100)
     gr1c = copy.copy(gr1)
     gr2 = pygraph.digraph()
     gr1.add_graph(gr2)
     self.assertTrue(gr1.nodes() == gr1c.nodes())
     self.assertTrue(gr1.edges() == gr1c.edges())

 def testAddGraph(self):
     gr1 = pygraph.digraph()
     gr1.generate(25, 100)
     gr2 = pygraph.digraph()
     gr2.generate(40, 200)
     gr1.add_graph(gr2)
     for each in gr2.nodes():
         self.assertTrue(each in gr1)
     for each in gr2.edges():
         self.assertTrue(each in gr1.edges())

  def graphize(self):
    try:
      self.graph = pygraph.digraph()
    except (NameError, AttributeError):
      self.graph = digraph()   

    modules = [self.topModule] + self.moduleList
    # first, we must add all the nodes. Only then can we add all the edges
    self.graph.add_nodes(modules)

    # here we have a strictly directed graph, so we need only insert directed edges
    for module in modules:
      def checkParent(child):
        if module.name == child.parent:
          return True
        else:
          return False

      children = filter(checkParent, modules)
      for child in children:
        # due to compatibility issues, we need these try catch to pick the 
        # right function prototype.
        try:
          self.graph.add_edge(module,child) 
        except TypeError:
          self.graph.add_edge((module,child)) 

  def graphizeSynth(self):
    try:
      self.graphSynth = pygraph.digraph()
    except (NameError, AttributeError):
      self.graphSynth = digraph()
    modulesUnfiltered = [self.topModule] + self.moduleList
    # first, we must add all the nodes. Only then can we add all the edges
    # filter by synthesis boundaries
    modules = filter(checkSynth, modulesUnfiltered)
    self.graphSynth.add_nodes(modules)

    # here we have a strictly directed graph, so we need only insert directed edges
    for module in modules:
      def checkParent(child):
        if module.name == child.synthParent:
          return True
        else:
          return False

      children = filter(checkParent, modules)
      for child in children:
        #print "Adding p: " + module.name + " c: " + child.name
        try:
          self.graphSynth.add_edge(module,child) 
        except TypeError:
          self.graphSynth.add_edge((module,child)) 

def sort_out_covering_exons (cursor, exons):

    # havana is manually curated and gets priority
    is_ensembl = {}
    is_havana  = {}
    for exon in exons:
        logic_name = get_logic_name(cursor, exon.analysis_id)
        is_ensembl[exon] = ('ensembl' in logic_name)
        is_havana [exon] = ('havana'  in logic_name)

    dg = digraph()
    dg.add_nodes(exons)
    for exon1, exon2 in combinations(dg.nodes(),2):
        master, covered = find_master(cursor, exon1,exon2,is_ensembl,is_havana)
        if master is not None and covered is not None:
            dg.add_edge(master,covered)
    assert not find_cycle(dg)
    clusters = dict(((k,v) for k,v in accessibility(dg).iteritems()
                     if not dg.incidents(k)))
    for k in clusters:
        clusters[k].remove(k)

    for master_exon, covered_list in clusters.iteritems():
        master_exon.covering_exon       = -1 # nobody's covering this guy
        master_exon.covering_exon_known = -1 # formal
        for covered_exon in covered_list:
            covered_exon.covering_exon       = master_exon.exon_id
            covered_exon.covering_exon_known = master_exon.is_known

 def testSanityDigraph(self):
     G = pygraph.digraph()
     G.generate(100, 500)
     st, lo = G.breadth_first_search()
     for each in G:
         if (st[each] != None):
             assert lo.index(each) > lo.index(st[each])

 def testDigraph(self):
     
     def has_parent(node, list):
         for each in list:
             if gr.has_edge(each, node):
                 return True
         return (ts == [])
         
     gr = pygraph.digraph()
     gr.add_nodes([0,1,2,3,4,5,6,7,8])
     gr.add_edge(0,1)
     gr.add_edge(0,2)
     gr.add_edge(1,3)
     gr.add_edge(1,4)
     gr.add_edge(2,5)
     gr.add_edge(2,6)
     gr.add_edge(3,7)
     gr.add_edge(8,0)
     gr.add_edge(7,5)
     gr.add_edge(3,0)
     gr.add_edge(4,3)
     gr.add_edge(2,7)
     gr.add_edge(6,0)
     ts = topological_sorting(gr)
     while (ts):
         x = ts.pop()
         assert has_parent(x, ts)

 def testReadDigraphDot(self):
     dot = ['digraph graphname {', '1;', '2;', '3;', '4;', '5;', '1 -> 2;', '4 -> 5;', '1 -> 5;', '2 -> 3;', '2 -> 4;', '3 -> 5;', '}', '']
     dot = "\n".join(dot)
     gr = pygraph.digraph()
     gr.read(dot, 'dot')
     self._check_nodes(gr, dot)
     self._check_arrows(gr, dot)

 def testGraphComplete(self):
     gr = pygraph.digraph()
     gr.add_nodes(xrange(10))
     gr.complete()
     for i in xrange(10):
         for j in range(10):
             self.assertTrue((i, j) in gr.edges() or i == j)

 def testNoCycleDigraph2(self):
     G = pygraph.digraph()
     G.add_nodes([1,2,3])
     G.add_edge(1,2)
     G.add_edge(1,3)
     G.add_edge(2,3)
     assert G.find_cycle() == []

 def testGraphInverse(self):
     gr = pygraph.digraph()
     gr.generate(50, 300)
     inv = gr.inverse()
     for each in gr.edges():
         self.assertTrue(each not in inv.edges())
     for each in inv.edges():
         self.assertTrue(each not in gr.edges())

 def testRandomGraph(self):
     gr = pygraph.digraph()
     gr.generate(100, 500)
     self.assertEqual(gr.nodes(), range(100))
     self.assertEqual(len(gr.edges()), 500)
     for each, other in gr.edges():
         self.assertTrue(each in gr)
         self.assertTrue(other in gr)

 def testNodeRemoval(self):
     gr = pygraph.digraph()
     gr.generate(10, 90)
     gr.del_node(0)
     self.assertTrue(0 not in gr)
     for each, other in gr.edges():
         self.assertTrue(each in gr)
         self.assertTrue(other in gr)

 def testNoCycleDigraph(self):
     G = pygraph.digraph()
     G.add_nodes([1, 2, 3, 4, 5])
     G.add_edge(1, 2)
     G.add_edge(2, 3)
     G.add_edge(2, 4)
     G.add_edge(4, 5)
     G.add_edge(3, 5)
     assert G.find_cycle() == []

 def testMisleadingDigraph(self):
     G = pygraph.digraph()
     G.add_nodes([1, 2, 3, 4, 5])
     G.add_edge(1, 2)
     G.add_edge(2, 3)
     G.add_edge(2, 4)
     G.add_edge(4, 5)
     G.add_edge(3, 5)
     G.add_edge(3, 1)
     assert G.find_cycle() == [1, 2, 3]

 def testSmallCycleDigraph(self):
     G = pygraph.digraph()
     G.add_nodes([1, 2, 3, 4, 5])
     G.add_edge(1, 2)
     G.add_edge(2, 3)
     G.add_edge(2, 4)
     G.add_edge(4, 5)
     G.add_edge(2, 1)
     # Cycle: 1-2
     assert G.find_cycle() == [1,2]

 def testDigraph(self):
     G = pygraph.digraph()
     G.add_nodes([1, 2, 3, 4, 5])
     G.add_edge(1, 2)
     G.add_edge(2, 3)
     G.add_edge(2, 4)
     G.add_edge(4, 5)
     G.add_edge(5, 1)
     # Cycle: 1-2-4-5
     assert find_cycle(G) == [1,2,4,5]

 def testWriteDigraphDot(self):
     gr = pygraph.digraph()
     gr.add_nodes([1, 2, 3, 4, 5])
     gr.add_edge(1, 2)
     gr.add_edge(2, 3)
     gr.add_edge(2, 4)
     gr.add_edge(4, 5)
     gr.add_edge(1, 5)
     gr.add_edge(3, 5)
     dotstr = dot.write(gr)
     self._check_nodes(gr, dotstr)
     self._check_arrows(gr, dotstr)

 def testDigraphDFS(self):
     G = pygraph.digraph()
     G.add_nodes([1, 2, 3, 4, 5, 6])
     G.add_edge(1, 2)
     G.add_edge(1, 3)
     G.add_edge(2, 4)
     G.add_edge(4, 3)
     G.add_edge(5, 1)
     G.add_edge(3, 5)
     G.add_edge(5, 6)
     st, pre, post = depth_first_search(G, 1, filter=filters.find(5))
     assert st == {1: None, 2: 1, 3: 4, 4: 2, 5: 3}

    def __init__(self, connections):

        self.unmatchedChannels = False                    
        
        self.modules = {}
 
        for connection in connections:
            # give channels unit weight
            connection.activity = 1
            if (not connection.module_name in self.modules):
                # for now, type and name are the same
                if(DUMP_GRAPH_DEBUG):
                    print "Adding module, Found channel " + connection.name + " with module " + connection.module_name
                self.modules[connection.module_name] = LIModule(connection.module_name,\
                                                                connection.module_name)
       
            if (isinstance(connection, LIChannel)):
                self.modules[connection.module_name].addChannel(connection)
            else:
                self.modules[connection.module_name].addChain(connection)
 

        # let's match up all those connections
        self.matchGraphChannels()       

        # now that we have a dictionary, we can create a graph
        try:
            self.graph = pygraph.digraph() 
        except (NameError, AttributeError): 
            self.graph = digraph() 
      
        self.graph.add_nodes(self.modules.values())
        self.weights = {} # unfortunately pygraph does not support multiedges
    
        # add edges - for now all edges have unit weight
        for module in self.modules.values():
            for channel in module.channels:
                # depending on what we are doing with the graph,
                # unmatched channels may not be an error.  We will
                # instead mark the object in case the caller cares
                if (not (channel.matched or channel.optional)):
                    self.unmatchedChannels = True                    
                    continue
                # It is possible that optional channels do not have a match
                if (not channel.matched):
                    continue
                #Only add an edge if the channel is a source.
                if (channel.isSource()):
                    if (not self.graph.has_edge((module, channel.partnerModule))):
                        self.graph.add_edge((module, channel.partnerModule))
                        self.weights[(module, channel.partnerModule)] = channel.activity
                    else:
                        self.weights[(module, channel.partnerModule)] += channel.activity