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

class TestFloyd:
    def setUp(self):
        pass

    def test_floyd_warshall_predecessor_and_distance(self):
        XG=nx.DiGraph()
        XG.add_weighted_edges_from([('s','u',10) ,('s','x',5) ,
                                    ('u','v',1) ,('u','x',2) ,
                                    ('v','y',1) ,('x','u',3) ,
                                    ('x','v',5) ,('x','y',2) ,
                                    ('y','s',7) ,('y','v',6)])
        path, dist =nx.floyd_warshall_predecessor_and_distance(XG)
        assert_equal(dist['s']['v'],9)
        assert_equal(path['s']['v'],'u')
        assert_equal(dist,
                     {'y': {'y': 0, 'x': 12, 's': 7, 'u': 15, 'v': 6},
                      'x': {'y': 2, 'x': 0, 's': 9, 'u': 3, 'v': 4},
                      's': {'y': 7, 'x': 5, 's': 0, 'u': 8, 'v': 9},
                      'u': {'y': 2, 'x': 2, 's': 9, 'u': 0, 'v': 1},
                      'v': {'y': 1, 'x': 13, 's': 8, 'u': 16, 'v': 0}})


        GG=XG.to_undirected()
        # make sure we get lower weight
        # to_undirected might choose either edge with weight 2 or weight 3
        GG['u']['x']['weight']=2
        path, dist = nx.floyd_warshall_predecessor_and_distance(GG)
        assert_equal(dist['s']['v'],8)
        # skip this test, could be alternate path s-u-v
#        assert_equal(path['s']['v'],'y')

        G=nx.DiGraph()  # no weights
        G.add_edges_from([('s','u'), ('s','x'),
                          ('u','v'), ('u','x'),
                          ('v','y'), ('x','u'),
                          ('x','v'), ('x','y'),
                          ('y','s'), ('y','v')])
        path, dist = nx.floyd_warshall_predecessor_and_distance(G)
        assert_equal(dist['s']['v'],2)
        # skip this test, could be alternate path s-u-v
 #       assert_equal(path['s']['v'],'x')

        # alternate interface
        dist = nx.floyd_warshall(G)
        assert_equal(dist['s']['v'],2)

    def test_cycle(self):
        path, dist = nx.floyd_warshall_predecessor_and_distance(nx.cycle_graph(7))
        assert_equal(dist[0][3],3)
        assert_equal(path[0][3],2)
        assert_equal(dist[0][4],3)

    def test_weighted(self):
        XG3=nx.Graph()
        XG3.add_weighted_edges_from([ [0,1,2],[1,2,12],[2,3,1],
                                      [3,4,5],[4,5,1],[5,0,10] ])
        path, dist = nx.floyd_warshall_predecessor_and_distance(XG3)
        assert_equal(dist[0][3],15)
        assert_equal(path[0][3],2)

    def test_weighted2(self):
        XG4=nx.Graph()
        XG4.add_weighted_edges_from([ [0,1,2],[1,2,2],[2,3,1],
                                      [3,4,1],[4,5,1],[5,6,1],
                                      [6,7,1],[7,0,1] ])
        path, dist = nx.floyd_warshall_predecessor_and_distance(XG4)
        assert_equal(dist[0][2],4)
        assert_equal(path[0][2],1)

    def test_weight_parameter(self):
        XG4 = nx.Graph()
        XG4.add_edges_from([ (0, 1, {'heavy': 2}), (1, 2, {'heavy': 2}),
                             (2, 3, {'heavy': 1}), (3, 4, {'heavy': 1}),
                             (4, 5, {'heavy': 1}), (5, 6, {'heavy': 1}),
                             (6, 7, {'heavy': 1}), (7, 0, {'heavy': 1}) ])
        path, dist = nx.floyd_warshall_predecessor_and_distance(XG4,
                                                            weight='heavy')
        assert_equal(dist[0][2], 4)
        assert_equal(path[0][2], 1)

    def test_zero_distance(self):
        XG=nx.DiGraph()
        XG.add_weighted_edges_from([('s','u',10) ,('s','x',5) ,
                                    ('u','v',1) ,('u','x',2) ,
                                    ('v','y',1) ,('x','u',3) ,
                                    ('x','v',5) ,('x','y',2) ,
                                    ('y','s',7) ,('y','v',6)])
        path, dist =nx.floyd_warshall_predecessor_and_distance(XG)

        for u in XG:
            assert_equal(dist[u][u], 0)

        GG=XG.to_undirected()
        # make sure we get lower weight
        # to_undirected might choose either edge with weight 2 or weight 3
        GG['u']['x']['weight']=2
        path, dist = nx.floyd_warshall_predecessor_and_distance(GG)

        for u in GG:
            dist[u][u] = 0

    def test_zero_weight(self):
        G = nx.DiGraph()
        edges = [(1,2,-2), (2,3,-4), (1,5,1), (5,4,0), (4,3,-5), (2,5,-7)]
        G.add_weighted_edges_from(edges)
        dist = nx.floyd_warshall(G)
        assert_equal(dist[1][3], -14)

        G = nx.MultiDiGraph()
        edges.append( (2,5,-7) )
        G.add_weighted_edges_from(edges)
        dist = nx.floyd_warshall(G)
        assert_equal(dist[1][3], -14)