def create_release_graph(objects, release, previous):
    release_graph = hypergraph()
    release_graph.add_nodes(objects)
    release_graph.add_edges([release, previous])

    file_objects = [ccm_cache.get_object(o) for o in objects]
    for o in file_objects:
        link = True
        # Bind objects to this release
        successors = o.get_successors()
        if successors:
            for s in successors:
                if s not in release_graph.nodes():
                    link &= True
                else:
                    link &=False
        if link:
            if o.get_object_name() not in release_graph.links(release):
                release_graph.link(o.get_object_name(), release)

        # Bind objects to previous release
        predecessors = o.get_predecessors()
        if predecessors is not None:
            for p in predecessors:
                if p not in objects:
                    if not release_graph.has_node(p):
                        release_graph.add_node(p)
                        #print "linking", p, "to release", previous
                        release_graph.link(p, previous)

    return release_graph

 def test_cut_nodes_in_hypergraph(self):
     gr = hypergraph()
     
     # Add some nodes / edges
     gr.add_nodes(range(9))
     gr.add_hyperedges(['a', 'b', 'c'])
     
     # Connect the 9 nodes with three size-3 hyperedges
     for node_set in [['a',0,1,2], ['b',3,4,5], ['c',6,7,8]]:
         for node in node_set[1:]:
             gr.link(node, node_set[0])
     
     # Connect the groups
     gr.add_hyperedges(['l1','l2'])
     gr.link(0, 'l1')
     gr.link(3, 'l1')
     gr.link(5, 'l2')
     gr.link(8, 'l2')
     
     cn = cut_nodes(gr);
     
     assert 0 in cn
     assert 3 in cn
     assert 5 in cn
     assert 8 in cn
     assert len(cn) == 4

 def test_hypergraph_equality_labels(self):
     """
     Hyperaph equality test. This one checks edge equality. 
     """
     gr = hypergraph()
     gr.add_nodes([0,1,2,3])
     gr.add_edge('e1')
     gr.add_edge('e2')
     gr.add_edge('e3')
     gr.set_edge_label('e1', 'l1')
     gr.set_edge_label('e2', 'l2')
     
     gr2 = deepcopy(gr)
     
     gr3 = deepcopy(gr)
     gr3.set_edge_label('e3', 'l3')
     
     gr4 = deepcopy(gr)
     gr4.set_edge_label('e1', 'lx')
     
     gr5 = deepcopy(gr)
     gr5.del_edge('e1')
     gr5.add_edge('e1')
     
     assert gr == gr2
     assert gr2 == gr
     assert gr != gr3
     assert gr3 != gr
     assert gr != gr4
     assert gr4 != gr
     assert gr != gr5
     assert gr5 != gr

 def test_hypergraph_equality_edges(self):
     """
     Hyperaph equality test. This one checks edge equality. 
     """
     gr = hypergraph()
     gr.add_nodes([0,1,2,3])
     gr.add_edge('e1')
     gr.add_edge('e2')
     gr.link(0, 'e1')
     gr.link(1, 'e1')
     gr.link(1, 'e2')
     gr.link(2, 'e2')
     
     gr2 = deepcopy(gr)
     
     gr3 = deepcopy(gr)
     gr3.del_edge('e2')
     
     gr4 = deepcopy(gr)
     gr4.unlink(1, 'e2')
     
     assert gr == gr2
     assert gr2 == gr
     assert gr != gr3
     assert gr3 != gr
     assert gr != gr4
     assert gr4 != gr

 def test_hypergraph_equality_weight(self):
     """
     Hyperaph equality test. This one checks edge equality. 
     """
     gr = hypergraph()
     gr.add_nodes([0,1,2,3])
     gr.add_edge('e1')
     gr.add_edge('e2')
     gr.add_edge('e3')
     gr.set_edge_weight('e1', 2)
     
     gr2 = deepcopy(gr)
     
     gr3 = deepcopy(gr)
     gr3.set_edge_weight('e3', 2)
     
     gr4 = deepcopy(gr)
     gr4.set_edge_weight('e1', 1)
     
     assert gr == gr2
     assert gr2 == gr
     assert gr != gr3
     assert gr3 != gr
     assert gr != gr4
     assert gr4 != gr

def read_hypergraph(string):
    """
    Read a hypergraph from a string in dot format. Nodes and edges specified in the input will be
    added to the current hypergraph.
    
    @type  string: string
    @param string: Input string in dot format specifying a graph.
    
    @rtype:  hypergraph
    @return: Hypergraph
    """
    hgr = hypergraph()
    dotG = pydot.graph_from_dot_data(string)
    
    # Read the hypernode nodes...
    # Note 1: We need to assume that all of the nodes are listed since we need to know if they
    #           are a hyperedge or a normal node
    # Note 2: We should read in all of the nodes before putting in the links
    for each_node in dotG.get_nodes():
        if 'hypernode' == each_node.get('hyper_node_type'):
            hgr.add_node(each_node.get_name())
        elif 'hyperedge' == each_node.get('hyper_node_type'):
            hgr.add_hyperedge(each_node.get_name())
    
    # Now read in the links to connect the hyperedges
    for each_link in dotG.get_edges():
        if hgr.has_node(each_link.get_source()):
            link_hypernode = each_link.get_source()
            link_hyperedge = each_link.get_destination()
        elif hgr.has_node(each_link.get_destination()):
            link_hypernode = each_link.get_destination()
            link_hyperedge = each_link.get_source()
        hgr.link(link_hypernode, link_hyperedge)
    
    return hgr

 def test_cut_edges_in_hypergraph(self):
     gr = hypergraph()
     
     # Add some nodes / edges
     gr.add_nodes(range(9))
     gr.add_hyperedges(['a1', 'b1', 'c1'])
     gr.add_hyperedges(['a2', 'b2', 'c2'])
     
     # Connect the 9 nodes with three size-3 hyperedges
     for node_set in [['a1',0,1,2], ['b1',3,4,5], ['c1',6,7,8], ['a2',0,1,2], ['b2',3,4,5], ['c2',6,7,8]]:
         for node in node_set[1:]:
             gr.link(node, node_set[0])
     
     # Connect the groups
     gr.add_hyperedges(['l1','l2'])
     gr.link(0, 'l1')
     gr.link(3, 'l1')
     gr.link(5, 'l2')
     gr.link(8, 'l2')
     
     ce = cut_edges(gr)
     
     assert 'l1' in ce
     assert 'l2' in ce
     assert len(ce) == 2

    def test_check_add_node_s(self):
        gr = hypergraph()
        nodes = [1, 2, 3]
        gr.add_nodes(nodes)
        gr.add_node(0)

        for n in [0] + nodes:
            assert n in gr
            assert gr.has_node(n)

 def test_raise_exception_on_duplicate_node_addition(self):
     gr = hypergraph()
     gr.add_node("a_node")
     try:
         gr.add_node("a_node")
     except AdditionError:
         pass
     else:
         fail()

 def test_raise_exception_when_edge_added_to_non_existing_node(self):
     gr = hypergraph()
     gr.add_nodes([0, 1])
     try:
         gr.link(0, 3)
     except KeyError:
         pass
     else:
         fail()
     assert gr.neighbors(0) == []

 def test_raise_exception_on_non_existing_link_removal(self):
     gr = hypergraph()
     gr.add_node(0)
     gr.add_hyperedge(1)
     try:
         gr.unlink(0, 1)
     except ValueError:
         pass
     else:
         fail()

 def test_raise_exception_on_duplicate_edge_link(self):
     gr = hypergraph()
     gr.add_node("a node")
     gr.add_hyperedge("an edge")
     gr.link("a node", "an edge")
     try:
         gr.link("a node", "an edge")
     except AdditionError:
         pass
     else:
         fail()

 def test_connected_components_hypergraph(self):
     gr = hypergraph()
     
     # Add some nodes / edges
     gr.add_nodes(range(9))
     gr.add_hyperedges(['a', 'b', 'c'])
     
     # Connect the 9 nodes with three size-3 hyperedges
     for node_set in [['a',0,1,2], ['b',3,4,5], ['c',6,7,8]]:
         for node in node_set[1:]:
             gr.link(node, node_set[0])
     
     cc = connected_components(gr)
     
     assert 3 == len(set(cc.values()))
     
     assert cc[0] == cc[1] and cc[1] == cc[2]
     assert cc[3] == cc[4] and cc[4] == cc[5]
     assert cc[6] == cc[7] and cc[7] == cc[8]
     
     
     # Do it again with two components and more than one edge for each
     gr = hypergraph()
     gr.add_nodes(range(9))
     gr.add_hyperedges(['a', 'b', 'c', 'd'])
     
     for node_set in [['a',0,1,2], ['b',2,3,4], ['c',5,6,7], ['d',6,7,8]]:
         for node in node_set[1:]:
             gr.link(node, node_set[0])
     
     cc = connected_components(gr)
     
     assert 2 == len(set(cc.values()))
     
     for i in [0,1,2,3]:
         assert cc[i] == cc[i+1]
     
     for i in [5,6,7]:
         assert cc[i] == cc[i+1]
         
     assert cc[4] != cc[5]

 def test_hypergraph_link_unlink_link(self):
     """
     Hypergraph link-unlink-link test. It makes sure that unlink cleans 
     everything properly. No AdditionError should occur.
     """
     h = hypergraph()
     h.add_nodes([1,2])
     h.add_edges(['e1'])
     
     h.link(1, 'e1')
     h.unlink(1, 'e1')
     h.link(1,'e1')

def create_task_graph(tasks, objects):
    task_graph = hypergraph()
    task_graph.add_nodes([o.get_object_name() for o in objects])
    task_graph.add_hyperedges([t.get_object_name() for t in tasks])
    #link the objects and the tasks
    for t in tasks:
        for o in t.get_objects():
            #print "linking:", o, "and", t.get_object_name()
            task_graph.link(o, t.get_object_name())
    # Add single_objects to task_graph
    for o in find_objects_without_associated_tasks(objects, tasks):
        task_graph.add_hyperedge(o.get_object_name())
        #print "linking:", o.get_object_name(), "and", o.get_object_name()
        task_graph.link(o.get_object_name(), o.get_object_name())

    return task_graph

def generate_hypergraph(num_nodes, num_edges, r=0):
    """
    Create a random hyper graph.
    
    @type  num_nodes: number
    @param num_nodes: Number of nodes.
    
    @type  num_edges: number
    @param num_edges: Number of edges.
    
    @type  r: number
    @param r: Uniform edges of size r.
    """
    # Graph creation
    random_graph = hypergraph()

    # Nodes
    nodes = map(str, list(range(num_nodes)))
    random_graph.add_nodes(nodes)

    # Base edges
    edges = map(str, list(range(num_nodes, num_nodes + num_edges)))

    random_graph.add_hyperedges(edges)

    # Connect the edges
    if 0 == r:
        # Add each edge with 50/50 probability
        for e in edges:
            for n in nodes:
                if choice([True, False]):
                    random_graph.link(n, e)

    else:
        # Add only uniform edges
        for e in edges:
            # First shuffle the nodes
            shuffle(nodes)

            # Then take the first r nodes
            for i in range(r):
                random_graph.link(nodes[i], e)

    return random_graph

 def test_remove_edge(self):
     h = hypergraph()
     h.add_nodes([1,2])
     h.add_edges(['a', 'b'])
     
     h.link(1,'a')
     h.link(2,'a')
     h.link(1,'b')
     h.link(2,'b')
     
     # Delete an edge
     h.del_edge('a')
     
     assert 1 == len(h.hyperedges())
     
     gr = testlib.new_hypergraph()
     edge_no = len(gr.nodes())+1
     gr.del_hyperedge(edge_no)
     self.assertTrue(edge_no not in gr.hyperedges())

 def test_accessibility_hypergraph(self):
     gr = hypergraph()
     
     # Add some nodes / edges
     gr.add_nodes(range(8))
     gr.add_hyperedges(['a', 'b', 'c'])
     
     # Connect the 9 nodes with three size-3 hyperedges
     for node_set in [['a',0,1,2], ['b',2,3,4], ['c',5,6,7]]:
         for node in node_set[1:]:
             gr.link(node, node_set[0])
     
     access = accessibility(gr)
     
     assert 8 == len(access)
     
     for i in range(5):
         assert set(access[i]) == set(range(5))
     
     for i in range(5,8):
         assert set(access[i]) == set(range(5,8))

 def test_hypergraph_equality_nodes(self):
     """
     Hyperaph equality test. This one checks node equality. 
     """
     gr = hypergraph()
     gr.add_nodes([0,1,2,3,4,5])
     
     gr2 = deepcopy(gr)
     
     gr3 = deepcopy(gr)
     gr3.del_node(5)
     
     gr4 = deepcopy(gr)
     gr4.add_node(6)
     gr4.del_node(0)
     
     assert gr == gr2
     assert gr2 == gr
     assert gr != gr3
     assert gr3 != gr
     assert gr != gr4
     assert gr4 != gr

def create_release_graph(objects, release, previous):
    release_graph = hypergraph()
    release_graph.add_nodes([o.get_object_name() for o in objects])
    release_graph.add_edges([release, previous])

    object_names = [o.get_object_name() for o in objects]
    for o in objects:
        # Bind objects to this release
        if o.get_successors() is None:
            #print "linking", o.get_object_name(), "to release", release
            release_graph.link(o.get_object_name(), release)

        # Bind objects to previous release
        predecessors = o.get_predecessors()
        if predecessors is not None:
            for p in predecessors:
                if p not in object_names:
                    if not release_graph.has_node(p):
                        release_graph.add_node(p)
                        #print "linking", p, "to release", previous
                        release_graph.link(p, previous)

    return release_graph