def test_directed_projection(self):
        G=nx.DiGraph()
        G.add_edge('A',1)
        G.add_edge(1,'B')
        G.add_edge('A',2)
        G.add_edge('B',2)
        P=bipartite.projected_graph(G,'AB')
        assert_edges_equal(list(P.edges()),[('A','B')])
        P=bipartite.weighted_projected_graph(G,'AB')
        assert_edges_equal(list(P.edges()),[('A','B')])
        assert_equal(P['A']['B']['weight'],1)

        P=bipartite.projected_graph(G,'AB',multigraph=True)
        assert_edges_equal(list(P.edges()),[('A','B')])

        G=nx.DiGraph()
        G.add_edge('A',1)
        G.add_edge(1,'B')
        G.add_edge('A',2)
        G.add_edge(2,'B')
        P=bipartite.projected_graph(G,'AB')
        assert_edges_equal(list(P.edges()),[('A','B')])
        P=bipartite.weighted_projected_graph(G,'AB')
        assert_edges_equal(list(P.edges()),[('A','B')])
        assert_equal(P['A']['B']['weight'],2)

        P=bipartite.projected_graph(G,'AB',multigraph=True)
        assert_edges_equal(list(P.edges()),[('A','B'),('A','B')])

    def test_directed_projection(self):
        G = nx.DiGraph()
        G.add_edge("A", 1)
        G.add_edge(1, "B")
        G.add_edge("A", 2)
        G.add_edge("B", 2)
        P = bipartite.projected_graph(G, "AB")
        assert_equal(sorted(P.edges()), [("A", "B")])
        P = bipartite.weighted_projected_graph(G, "AB")
        assert_equal(sorted(P.edges()), [("A", "B")])
        assert_equal(P["A"]["B"]["weight"], 1)

        P = bipartite.projected_graph(G, "AB", multigraph=True)
        assert_equal(sorted(P.edges()), [("A", "B")])

        G = nx.DiGraph()
        G.add_edge("A", 1)
        G.add_edge(1, "B")
        G.add_edge("A", 2)
        G.add_edge(2, "B")
        P = bipartite.projected_graph(G, "AB")
        assert_equal(sorted(P.edges()), [("A", "B")])
        P = bipartite.weighted_projected_graph(G, "AB")
        assert_equal(sorted(P.edges()), [("A", "B")])
        assert_equal(P["A"]["B"]["weight"], 2)

        P = bipartite.projected_graph(G, "AB", multigraph=True)
        assert_equal(sorted(P.edges()), [("A", "B"), ("A", "B")])

    def test_project_weighted_ratio(self):
        edges = [
            ("A", "B", 2 / 6.0),
            ("A", "C", 1 / 6.0),
            ("B", "C", 1 / 6.0),
            ("B", "D", 1 / 6.0),
            ("B", "E", 2 / 6.0),
            ("E", "F", 1 / 6.0),
        ]
        Panswer = nx.Graph()
        Panswer.add_weighted_edges_from(edges)
        P = bipartite.weighted_projected_graph(self.G, "ABCDEF", ratio=True)
        assert_equal(P.edges(), Panswer.edges())
        for u, v in P.edges():
            assert_equal(P[u][v]["weight"], Panswer[u][v]["weight"])

        edges = [
            ("A", "B", 3 / 3.0),
            ("A", "E", 1 / 3.0),
            ("A", "C", 1 / 3.0),
            ("A", "D", 1 / 3.0),
            ("B", "E", 1 / 3.0),
            ("B", "C", 1 / 3.0),
            ("B", "D", 1 / 3.0),
            ("C", "D", 1 / 3.0),
        ]
        Panswer = nx.Graph()
        Panswer.add_weighted_edges_from(edges)
        P = bipartite.weighted_projected_graph(self.N, "ABCDE", ratio=True)
        assert_equal(P.edges(), Panswer.edges())
        for u, v in P.edges():
            assert_equal(P[u][v]["weight"], Panswer[u][v]["weight"])

    def test_project_weighted_shared(self):
        edges = [("A", "B", 2), ("A", "C", 1), ("B", "C", 1), ("B", "D", 1), ("B", "E", 2), ("E", "F", 1)]
        Panswer = nx.Graph()
        Panswer.add_weighted_edges_from(edges)
        P = bipartite.weighted_projected_graph(self.G, "ABCDEF")
        assert_edges_equal(P.edges(), Panswer.edges())
        for u, v in P.edges():
            assert_equal(P[u][v]["weight"], Panswer[u][v]["weight"])

        edges = [
            ("A", "B", 3),
            ("A", "E", 1),
            ("A", "C", 1),
            ("A", "D", 1),
            ("B", "E", 1),
            ("B", "C", 1),
            ("B", "D", 1),
            ("C", "D", 1),
        ]
        Panswer = nx.Graph()
        Panswer.add_weighted_edges_from(edges)
        P = bipartite.weighted_projected_graph(self.N, "ABCDE")
        assert_edges_equal(P.edges(), Panswer.edges())
        for u, v in P.edges():
            assert_equal(P[u][v]["weight"], Panswer[u][v]["weight"])

    def test_project_weighted_shared(self):
        edges=[('A','B',2),
               ('A','C',1),
               ('B','C',1),
               ('B','D',1),
               ('B','E',2),
               ('E','F',1)]
        Panswer=nx.Graph()
        Panswer.add_weighted_edges_from(edges)
        P=bipartite.weighted_projected_graph(self.G,'ABCDEF')
        assert_equal(P.edges(),Panswer.edges())
        for u,v in P.edges():
            assert_equal(P[u][v]['weight'],Panswer[u][v]['weight'])

        edges=[('A','B',3),
               ('A','E',1),
               ('A','C',1),
               ('A','D',1),
               ('B','E',1),
               ('B','C',1),
               ('B','D',1),
               ('C','D',1)]
        Panswer=nx.Graph()
        Panswer.add_weighted_edges_from(edges)
        P=bipartite.weighted_projected_graph(self.N,'ABCDE')
        assert_equal(P.edges(),Panswer.edges())
        for u,v in P.edges():
            assert_equal(P[u][v]['weight'],Panswer[u][v]['weight'])

    def test_project_weighted_ratio(self):
        edges=[('A','B',2/6.0),
               ('A','C',1/6.0),
               ('B','C',1/6.0),
               ('B','D',1/6.0),
               ('B','E',2/6.0),
               ('E','F',1/6.0)]
        Panswer=nx.Graph()
        Panswer.add_weighted_edges_from(edges)
        P=bipartite.weighted_projected_graph(self.G, 'ABCDEF', ratio=True)
        assert_edges_equal(list(P.edges()),Panswer.edges())
        for u,v in list(P.edges()):
            assert_equal(P[u][v]['weight'],Panswer[u][v]['weight'])

        edges=[('A','B',3/3.0),
               ('A','E',1/3.0),
               ('A','C',1/3.0),
               ('A','D',1/3.0),
               ('B','E',1/3.0),
               ('B','C',1/3.0),
               ('B','D',1/3.0),
               ('C','D',1/3.0)]
        Panswer=nx.Graph()
        Panswer.add_weighted_edges_from(edges)
        P=bipartite.weighted_projected_graph(self.N, 'ABCDE', ratio=True)
        assert_edges_equal(list(P.edges()),Panswer.edges())
        for u,v in list(P.edges()):
            assert_equal(P[u][v]['weight'],Panswer[u][v]['weight'])

 def test_path_weighted_projected_graph(self):
     G=nx.path_graph(4)
     P=bipartite.weighted_projected_graph(G,[1,3])
     assert_nodes_equal(list(P),[1,3])
     assert_edges_equal(list(P.edges()),[(1,3)])
     P[1][3]['weight']=1
     P=bipartite.weighted_projected_graph(G,[0,2])
     assert_nodes_equal(list(P),[0,2])
     assert_edges_equal(list(P.edges()),[(0,2)])
     P[0][2]['weight']=1

 def test_path_weighted_projected_graph(self):
     G = nx.path_graph(4)
     P = bipartite.weighted_projected_graph(G, [1, 3])
     assert_equal(sorted(P.nodes()), [1, 3])
     assert_equal(sorted(P.edges()), [(1, 3)])
     P[1][3]["weight"] = 1
     P = bipartite.weighted_projected_graph(G, [0, 2])
     assert_equal(sorted(P.nodes()), [0, 2])
     assert_equal(sorted(P.edges()), [(0, 2)])
     P[0][2]["weight"] = 1

def create_complete_graph(CProject):
    """
    Creates a multipartite graph consisting of papers on the one hand,
    and all facts of available plugin-results on the other hand.

    Args: CProject
    Returns: (bipartite_graph, monopartite_fact_graph, monopartite_paper_graph, paper_nodes, fact_nodes)
    """
        
    partition_mapping = {"papers":0,
                         "binomial":1, "genus":2, "genussp":3,
                         "carb3":4, "prot3":5, "dna":6, "prot":7,
                         "human":8}
    
    gene = ["human"]
    species = ["binomial"]
    sequence = ["dna", "prot"]
    plugins = {"gene":gene, "species": species, "sequence":sequence}
    
    
    M = nx.Graph()
    labels = {}

    for ctree in CProject.get_ctrees():

        for plugin, types in plugins.items():
            for ptype in types:
        
                try:
                    results = ctree.show_results(plugin).get(ptype, [])
                except AttributeError:
                    continue

                if len(results) > 0:
                    source = " ".join(ctree.get_title().split())
                    if not source in M.nodes():
                        # add paper node to one side of the bipartite network
                        M.add_node(source, bipartite=0)
                        labels[str(source)] = str(source)

                    for result in results:
                        target = result.get("exact")
                        # add fact node to other side of the bipartite network
                        if not target in M.nodes():
                            M.add_node(target, bipartite=1, ptype=ptype)
                            labels[target] = target.encode("utf-8").decode("utf-8")
                        # add a link between a paper and author
                        M.add_edge(source, target)

    paper_nodes = set(n for n,d in M.nodes(data=True) if d.get('bipartite')==0)
    fact_nodes = set(M) - paper_nodes
    fact_graph = bipartite.weighted_projected_graph(M, fact_nodes)
    paper_graph = bipartite.weighted_projected_graph(M, paper_nodes)
    
    return M, fact_graph, paper_graph, fact_nodes, paper_nodes

 def test_path_weighted_projected_directed_graph(self):
     G = nx.DiGraph()
     G.add_path(list(range(4)))
     P = bipartite.weighted_projected_graph(G, [1, 3])
     assert_equal(sorted(P.nodes()), [1, 3])
     assert_equal(sorted(P.edges()), [(1, 3)])
     P[1][3]["weight"] = 1
     P = bipartite.weighted_projected_graph(G, [0, 2])
     assert_equal(sorted(P.nodes()), [0, 2])
     assert_equal(sorted(P.edges()), [(0, 2)])
     P[0][2]["weight"] = 1

def create_network(CProject, plugin, query):
        """
        Creates the network between papers and plugin results.
        Plugin may be any of ["regex", "gene", "sequence", "species"]
        Query corresponds to the fact types found by a plugin,
        for "species" it is one of ["binomial", "genus", "genussp"]
        for "sequences" it is one of ["carb3", "prot3", "dna", "prot"]
        for "gene" it is "human"
        for "regex" it is "regexname".
        
        Args: CProject object
              plugin = "string"
              query = "string"
        
        Returns: (bipartite_graph, monopartite_graph, fact_nodes, paper_nodes)
        >>> bipartiteGraph, factGraph, paperGraph, fact_nodes, paper_nodes = create_network(CProject, "species", "binomial")
        """
        
        B = nx.Graph()
        labels = {}

        for ctree in CProject.get_ctrees():

            try:
                results = ctree.show_results(plugin).get(query, [])
            except AttributeError:
                continue

            if len(results) > 0:
                # add paper node to one side of the bipartite network
                source = " ".join(ctree.get_title().split())
                B.add_node(source, bipartite=0)
                labels[str(source)] = str(source)

                for result in results:
                    exact = result.get("exact")
                    # add fact node to other side of the bipartite network
                    B.add_node(exact, bipartite=1)
                    labels[exact] = exact.encode("utf-8").decode("utf-8")
                    # add a link between a paper and author
                    B.add_edge(source, exact)

        
        paper_nodes = set(n for n,d in B.nodes(data=True) if d['bipartite']==0)
        fact_nodes = set(B) - paper_nodes
        fact_graph = bipartite.weighted_projected_graph(B, fact_nodes)
        paper_graph = bipartite.weighted_projected_graph(B, paper_nodes)
        
        return B, fact_graph, paper_graph, fact_nodes, paper_nodes

def incremental_reconstruction(data):
    data.invent_reference_lla()
    graph = data.load_tracks_graph()
    tracks, images = tracks_and_images(graph)
    remaining_images = set(images)
    print 'images', len(images)
    print 'nonfisheye images', len(remaining_images)
    image_graph = bipartite.weighted_projected_graph(graph, images)
    reconstructions = []
    pairs = compute_image_pairs(graph, image_graph, data.config)
    for im1, im2 in pairs:
        if im1 in remaining_images and im2 in remaining_images:
            reconstruction = bootstrap_reconstruction(data, graph, im1, im2)
            if reconstruction:
                remaining_images.remove(im1)
                remaining_images.remove(im2)
                reconstruction = grow_reconstruction(data, graph, reconstruction, remaining_images)
                reconstructions.append(reconstruction)
                reconstructions = sorted(reconstructions, key=lambda x: -len(x.shots))
                data.save_reconstruction(reconstructions)

    for k, r in enumerate(reconstructions):
        print 'Reconstruction', k, ':', len(r.shots), 'images', ',', len(r.points),'points'

    print len(reconstructions), 'partial reconstructions in total.'

def make_network(raw_file_list):

# handles the individual nodes
    collect_nodes_by_source = []
    list_of_source_names = []
    node_list = []

    GB = nx.Graph()

# for all the nodes...
    for i in range(len(raw_file_list)):    
        # check whether they are name, source or else (not returned). "i" works as an index to identify the respective node when it comes back
        checker, a = my_containsAny(raw_file_list[i], i)

        # raw data starts with a source, all following non-source lines refer to names or tags. So all returned nodes should be linked to each other
        
        if checker == "source":
            GB.add_node(raw_file_list[a], bipartite = 0)
            source = raw_file_list[a]

        while source == raw_file_list[a]:
            if checker == "node":
                GB.add_node(raw_file_list[a], bipartite = 1)  
                GB.add_edge(raw_file_list[a], raw_file_list[a+1])


    G = bnx.weighted_projected_graph(GB, GB.nodes(["bipartite"]==1))

    #nx.write_graphml(GB, "abolitionists_bipartite.graphml")
    nx.write_pajek(G, "abolitionists.net")

    print "done!"

def incremental_reconstruction(data):
    """Run the entire incremental reconstruction pipeline."""
    data.invent_reference_lla()
    graph = data.load_tracks_graph()
    tracks, images = tracks_and_images(graph)
    remaining_images = set(images)
    gcp = None
    if data.ground_control_points_exist():
        gcp = data.load_ground_control_points()
    image_graph = bipartite.weighted_projected_graph(graph, images)
    reconstructions = []
    pairs = compute_image_pairs(graph, image_graph, data.config)
    for im1, im2 in pairs:
        if im1 in remaining_images and im2 in remaining_images:
            reconstruction = bootstrap_reconstruction(data, graph, im1, im2)
            if reconstruction:
                remaining_images.remove(im1)
                remaining_images.remove(im2)
                reconstruction = grow_reconstruction(
                    data, graph, reconstruction, remaining_images, gcp)
                reconstructions.append(reconstruction)
                reconstructions = sorted(reconstructions,
                                         key=lambda x: -len(x.shots))
                data.save_reconstruction(reconstructions)

    for k, r in enumerate(reconstructions):
        logger.info("Reconstruction {}: {} images, {} points".format(
            k, len(r.shots), len(r.points)))
    logger.info("{} partial reconstructions in total.".format(
        len(reconstructions)))

 def test_project_multigraph(self):
     G = nx.Graph()
     G.add_edge("a", 1)
     G.add_edge("b", 1)
     G.add_edge("a", 2)
     G.add_edge("b", 2)
     P = bipartite.projected_graph(G, "ab")
     assert_edges_equal(P.edges(), [("a", "b")])
     P = bipartite.weighted_projected_graph(G, "ab")
     assert_edges_equal(P.edges(), [("a", "b")])
     P = bipartite.projected_graph(G, "ab", multigraph=True)
     assert_edges_equal(P.edges(), [("a", "b"), ("a", "b")])

    def test_star_projected_graph(self):
        G = nx.star_graph(3)
        P = bipartite.projected_graph(G, [1, 2, 3])
        assert_equal(sorted(P.nodes()), [1, 2, 3])
        assert_equal(sorted(P.edges()), [(1, 2), (1, 3), (2, 3)])
        P = bipartite.weighted_projected_graph(G, [1, 2, 3])
        assert_equal(sorted(P.nodes()), [1, 2, 3])
        assert_equal(sorted(P.edges()), [(1, 2), (1, 3), (2, 3)])

        P = bipartite.projected_graph(G, [0])
        assert_equal(sorted(P.nodes()), [0])
        assert_equal(sorted(P.edges()), [])

 def test_project_multigraph(self):
     G=nx.Graph()
     G.add_edge('a',1)
     G.add_edge('b',1)
     G.add_edge('a',2)
     G.add_edge('b',2)
     P=bipartite.projected_graph(G,'ab')
     assert_edges_equal(list(P.edges()),[('a','b')])
     P=bipartite.weighted_projected_graph(G,'ab')
     assert_edges_equal(list(P.edges()),[('a','b')])
     P=bipartite.projected_graph(G,'ab',multigraph=True)
     assert_edges_equal(list(P.edges()),[('a','b'),('a','b')])

def main():
    path = os.getcwd() + "/Sampled_Data/second_guys/"

    edge_list,users,tracks = data_import(path+"merged2.txt")

    B = Bipartite(users,tracks,edge_list)

    projected_B = bipartite.weighted_projected_graph(B,users)
    print(weight_dist(projected_B))
    #print("number of tracks",len(projected_B.nodes()))
    #B_threshold = threshold(projected_B,6)
    #giant = max(nx.connected_component_subgraphs(B_threshold), key=len)

    #components = []

    with open("edge_list2_users.txt","w") as f:
        for i,j in projected_B.edges_iter():
            f.write(str(i)+ " " + str(j) +" "+ str(projected_B[i][j]["weight"]) +"\n")

def create_network(CProject, plugin, query):
        """
        Creates the network between papers and plugin results.
        Plugin may be any of ["regex", "gene", "sequence", "species"]
        Query corresponds to the fact types found by a plugin,
        for "species" it is one of ["binomial", "genus", "genussp"]
        for "sequences" it is one of ["carb3", "prot3", "dna", "prot"]
        for "gene" it is "human"
        for "regex" it is "regexname".
        
        Args: CProject object
              plugin = "string"
              query = "string"
        
        Returns: (bipartite_graph, monopartite_graph, paper_nodes, fact_nodes)

        >>> bipartiteGraph, factGraph, paperNodes, factNodes = create_network(CProject, "species", "binomial")
        """
        
        B = nx.Graph()
        labels = {}

        for ct in CProject.get_ctrees():
            
            ctree_ID, ctree = ct.items()[0]

            results = ctree.show_results(plugin).get(query, [])

            if len(results) > 0:
                B.add_node(ctree_ID, bipartite=0)
                labels[str(ctree_ID)] = str(ctree_ID)

                for result in results:
                    B.add_node(result, bipartite=1)
                    labels[result] = result.encode("utf-8").decode("utf-8")
                    # add a link between a paper and author
                    B.add_edge(ctree_ID, result)

        
        paper_nodes = set(n for n,d in B.nodes(data=True) if d['bipartite']==0)
        fact_nodes = set(B) - paper_nodes
        G = bipartite.weighted_projected_graph(B, fact_nodes)
        
        return B, G, paper_nodes, fact_nodes

    def write_report(self, data, graph,
                     features_time, matches_time, tracks_time):
        tracks, images = matching.tracks_and_images(graph)
        image_graph = bipartite.weighted_projected_graph(graph, images)
        view_graph = []
        for im1 in data.images():
            for im2 in data.images():
                if im1 in image_graph and im2 in image_graph[im1]:
                    weight = image_graph[im1][im2]['weight']
                    view_graph.append((im1, im2, weight))

        report = {
            "wall_times": {
                "load_features": features_time,
                "load_matches": matches_time,
                "compute_tracks": tracks_time,
            },
            "wall_time": features_time + matches_time + tracks_time,
            "num_images": len(images),
            "num_tracks": len(tracks),
            "view_graph": view_graph
        }
        data.save_report(io.json_dumps(report), 'tracks.json')