#!/usr/bin/env python
from nose.tools import *
import networkx as nx
from networkx.algorithms import bipartite
from networkx.testing import *

class TestBipartiteProject:

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

    def test_path_projected_properties_graph(self):
        G=nx.path_graph(4)
        G.add_node(1,name='one')
        G.add_node(2,name='two')
        P=bipartite.projected_graph(G,[1,3]) 
        assert_equal(sorted(P.nodes()),[1,3])
        assert_equal(sorted(P.edges()),[(1,3)])
        assert_equal(P.node[1]['name'],G.node[1]['name'])
        P=bipartite.projected_graph(G,[0,2]) 
        assert_equal(sorted(P.nodes()),[0,2])
        assert_equal(sorted(P.edges()),[(0,2)])
        assert_equal(P.node[2]['name'],G.node[2]['name'])

    def test_path_collaboration_projected_graph(self):
        G=nx.path_graph(4)
        P=bipartite.collaboration_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.collaboration_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 test_directed_path_collaboration_projected_graph(self):
        G=nx.DiGraph()
        G.add_path(list(range(4)))
        P=bipartite.collaboration_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.collaboration_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 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 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 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(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_project_collaboration(self):
        G=nx.Graph()
        G.add_edge('a',1)
        G.add_edge('b',1)
        G.add_edge('b',2)
        G.add_edge('c',2)
        G.add_edge('c',3)
        G.add_edge('c',4)
        G.add_edge('b',4)
        P=bipartite.collaboration_weighted_projected_graph(G,'abc')
        assert_equal(P['a']['b']['weight'],1)
        assert_equal(P['b']['c']['weight'],2)

    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')])

         
class TestBipartiteWeightedProjection:

    def setUp(self):
        # Tore Opsahl's example
        # http://toreopsahl.com/2009/05/01/projecting-two-mode-networks-onto-weighted-one-mode-networks/
        self.G=nx.Graph()
        self.G.add_edge('A',1)
        self.G.add_edge('A',2)
        self.G.add_edge('B',1)
        self.G.add_edge('B',2)
        self.G.add_edge('B',3)
        self.G.add_edge('B',4)
        self.G.add_edge('B',5)
        self.G.add_edge('C',1)
        self.G.add_edge('D',3)
        self.G.add_edge('E',4)
        self.G.add_edge('E',5)
        self.G.add_edge('E',6)
        self.G.add_edge('F',6)
        # Graph based on figure 6 from Newman (2001)
        self.N=nx.Graph()
        self.N.add_edge('A',1)
        self.N.add_edge('A',2)
        self.N.add_edge('A',3)
        self.N.add_edge('B',1)
        self.N.add_edge('B',2)
        self.N.add_edge('B',3)
        self.N.add_edge('C',1)
        self.N.add_edge('D',1)
        self.N.add_edge('E',3)
        
    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_newman(self):
        edges=[('A','B',1.5),
               ('A','C',0.5),
               ('B','C',0.5),
               ('B','D',1),
               ('B','E',2),
               ('E','F',1)]
        Panswer=nx.Graph()
        Panswer.add_weighted_edges_from(edges)
        P=bipartite.collaboration_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',11/6.0),
               ('A','E',1/2.0),
               ('A','C',1/3.0),
               ('A','D',1/3.0),
               ('B','E',1/2.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.collaboration_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_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_overlap(self):
        edges=[('A','B',2/2.0),
               ('A','C',1/1.0),
               ('B','C',1/1.0),
               ('B','D',1/1.0),
               ('B','E',2/3.0),
               ('E','F',1/1.0)]
        Panswer=nx.Graph()
        Panswer.add_weighted_edges_from(edges)
        P=bipartite.overlap_weighted_projected_graph(self.G,'ABCDEF', jaccard=False)
        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/1.0),
               ('A','C',1/1.0),
               ('A','D',1/1.0),
               ('B','E',1/1.0),
               ('B','C',1/1.0),
               ('B','D',1/1.0),
               ('C','D',1/1.0)]
        Panswer=nx.Graph()
        Panswer.add_weighted_edges_from(edges)
        P=bipartite.overlap_weighted_projected_graph(self.N,'ABCDE', jaccard=False)
        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_jaccard(self):
        edges=[('A','B',2/5.0),
               ('A','C',1/2.0),
               ('B','C',1/5.0),
               ('B','D',1/5.0),
               ('B','E',2/6.0),
               ('E','F',1/3.0)]
        Panswer=nx.Graph()
        Panswer.add_weighted_edges_from(edges)
        P=bipartite.overlap_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/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/1.0)]
        Panswer=nx.Graph()
        Panswer.add_weighted_edges_from(edges)
        P=bipartite.overlap_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_generic_weighted_projected_graph_simple(self):
        def shared(G, u, v):
            return len(set(G[u]) & set(G[v]))
        B = nx.path_graph(5) 
        G = bipartite.generic_weighted_projected_graph(B, [0, 2, 4], weight_function=shared) 
        assert_equal(sorted(G.nodes()), [0, 2, 4]) 
        assert_equal(G.edges(data=True), 
                     [(0, 2, {'weight': 1}), (2, 4, {'weight': 1})] )

        G = bipartite.generic_weighted_projected_graph(B, [0, 2, 4]) 
        assert_equal(sorted(G.nodes()), [0, 2, 4]) 
        assert_equal(G.edges(data=True), 
                     [(0, 2, {'weight': 1}), (2, 4, {'weight': 1})] )
        B = nx.DiGraph()
        B.add_path(list(range(5)))
        G = bipartite.generic_weighted_projected_graph(B, [0, 2, 4]) 
        assert_equal(sorted(G.nodes()), [0, 2, 4]) 
        assert_equal(G.edges(data=True), 
                     [(0, 2, {'weight': 1}), (2, 4, {'weight': 1})] )

    def test_generic_weighted_projected_graph_custom(self):
        def jaccard(G, u, v):
            unbrs = set(G[u])
            vnbrs = set(G[v])
            return float(len(unbrs & vnbrs)) / len(unbrs | vnbrs)
        def my_weight(G, u, v, weight='weight'):
            w = 0
            for nbr in set(G[u]) & set(G[v]):
                w += G.edge[u][nbr].get(weight, 1) + G.edge[v][nbr].get(weight, 1)
            return w
        B = nx.complete_bipartite_graph(2,2)
        for i,(u,v) in enumerate(B.edges()):
            B.edge[u][v]['weight'] = i + 1
        G = bipartite.generic_weighted_projected_graph(B, [0, 1],                   
                                                        weight_function=jaccard)
        assert_equal(G.edges(data=True), [(0, 1, {'weight': 1.0})])
        G = bipartite.generic_weighted_projected_graph(B, [0, 1],                   
                                                        weight_function=my_weight)
        assert_equal(G.edges(data=True), [(0, 1, {'weight': 10})])
        G = bipartite.generic_weighted_projected_graph(B, [0, 1])
        assert_equal(G.edges(data=True), [(0, 1, {'weight': 2})])
