# -*- coding: utf-8 -*-
# test_centrality.py - unit tests for algorithms.community.centrality
#
# Copyright 2015, 2016 NetworkX developers.
#
# This file is part of NetworkX.
#
# NetworkX is distributed under a BSD license; see LICENSE.txt for more
# information.
"""Unit tests for the :mod:`networkx.algorithms.community.centrality`
module.

"""
from operator import itemgetter

from nose.tools import assert_equal
from nose.tools import assert_true

import networkx as nx
from networkx.algorithms.community import girvan_newman


def set_of_sets(iterable):
    return set(map(frozenset, iterable))


def validate_communities(result, expected):
    assert_equal(set_of_sets(result), set_of_sets(expected))


def validate_possible_communities(result, *expected):
    assert_true(any(set_of_sets(result) == set_of_sets(p) for p in expected))


class TestGirvanNewman(object):
    """Unit tests for the
    :func:`networkx.algorithms.community.centrality.girvan_newman`
    function.

    """

    def test_no_edges(self):
        G = nx.empty_graph(3)
        communities = list(girvan_newman(G))
        assert_equal(len(communities), 1)
        validate_communities(communities[0], [{0}, {1}, {2}])

    def test_undirected(self):
        # Start with the graph .-.-.-.
        G = nx.path_graph(4)
        communities = list(girvan_newman(G))
        assert_equal(len(communities), 3)
        # After one removal, we get the graph .-. .-.
        validate_communities(communities[0], [{0, 1}, {2, 3}])
        # After the next, we get the graph .-. . ., but there are two
        # symmetric possible verisons.
        validate_possible_communities(communities[1], [{0}, {1}, {2, 3}],
                                      [{0, 1}, {2}, {3}])
        # After the last removal, we alway get the empty graph.
        validate_communities(communities[2], [{0}, {1}, {2}, {3}])

    def test_directed(self):
        G = nx.DiGraph(nx.path_graph(4))
        communities = list(girvan_newman(G))
        assert_equal(len(communities), 3)
        validate_communities(communities[0], [{0, 1}, {2, 3}])
        validate_possible_communities(communities[1], [{0}, {1}, {2, 3}],
                                      [{0, 1}, {2}, {3}])
        validate_communities(communities[2], [{0}, {1}, {2}, {3}])

    def test_selfloops(self):
        G = nx.path_graph(4)
        G.add_edge(0, 0)
        G.add_edge(2, 2)
        communities = list(girvan_newman(G))
        assert_equal(len(communities), 3)
        validate_communities(communities[0], [{0, 1}, {2, 3}])
        validate_possible_communities(communities[1], [{0}, {1}, {2, 3}],
                                      [{0, 1}, {2}, {3}])
        validate_communities(communities[2], [{0}, {1}, {2}, {3}])

    def test_most_valuable_edge(self):
        G = nx.Graph()
        G.add_weighted_edges_from([(0, 1, 3), (1, 2, 2), (2, 3, 1)])
        # Let the most valuable edge be the one with the highest weight.
        heaviest = lambda G: max(G.edges(data='weight'), key=itemgetter(2))[:2]
        communities = list(girvan_newman(G, heaviest))
        assert_equal(len(communities), 3)
        validate_communities(communities[0], [{0}, {1, 2, 3}])
        validate_communities(communities[1], [{0}, {1}, {2, 3}])
        validate_communities(communities[2], [{0}, {1}, {2}, {3}])