#
# <one line to give the library's name and an idea of what it does.>
# Copyright (C) 2015  <copyright holder> <email>
# 
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
# 
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
# 
# You should have received a copy of the GNU General Public License
# along with this program.  If not, see <http://www.gnu.org/licenses/>.
# 
#

import math
import spreadinginterface

class SplashSpreading(spreadinginterface.SpreadingInterface):
  """!
  This class is implementation of "Splash" spreading.
  
  For each nodes with non-zero weight makes the "Splash". The splash
  is defined by the number of iteration of "splashs" and maximum depth
  of single splash. Splash is calculated into each iteration as below:

                                 1
  splash(n) = valeof(n_k)  * ----------
                              deg(n)^k


  TODO: Handlig different functions
  The second function to propagate values is as follow:

                                 1
  splash(n) = valeof(n_k)  + ----------
                              deg(n)^k

  Where k is depth from the starting splash node. Where the depth (k) will 
  increase the the output weight of node will decrease. valueof(n_k) is weight
  of successor node in the depth k from starting node n.
  """

  def __init__(self, str_name = 'SplashSpreading'):
    """!
    Constructor only sets the name of spreading 
    and calls the partens constructor.

    @param str_name Name of spreading method
    @type str_name: String
    """
    super(SplashSpreading, self).__init__(str_name)

  def spread(self, g, max_it, max_depth):
    """!
    Splash spreading implementation.

    @param g Graph into which the weight will be spread
    @type g: networkx.DiGraph/networkx.MultiDiGraph
    @param max_it Number of iterations of spreading
    @type max_it: Integer
    @param max_depth The number of graph levelst to spread the value
    @type max_depth: Positive integer
    """
    assert(max_it > 0), "Number of iteration have to be greater than zero!"
    for nit in range(1, max_it + 1):
      # non zero nodes in the step
      snnzds = [n for n in g.nodes()
        if g.node[n].has_key('value') and g.node[n]['value'] != 0.0]
      # generate list of the nodes on the given depth from nodes into snnzds
      for dpth, dnodes in \
        self._generate_depth_nodes(g, snnzds, max_depth).iteritems():
          for n in dnodes:
            g.node[n]['value'] = \
              0 if not g.node[n].has_key('value') and g.out_degree(n) == 0 else (
              g.node[n]['value'] if g.out_degree(n) == 0 else (
                1 if not g.node[n].has_key('value') else g.node[n]['value']) * \
                (1.0 / math.pow(g.out_degree(n), dpth)))

  def _generate_depth_nodes(self, g, nodes, max_depth):
    """!
    For the given list of nodes generates max_depth number of next levels.

    For each level in returned dictionary the key represents number of level
    and as value is the list of nodes in this level.

    @param g The graph which contains nodes 
    @type g: networkx.DiGraph/networkx.MultiDiGraph

    @param nodes List of nodes to find the next max_depth levels
    @type nodes: List of nodes from networkx.DiGraph

    @param max_depth Maximum nymber of levels
    @type max_depth: Integer

    @return Dictionary where as the key is level number and as value 
            is the list of nodes in this level
    @rtype dictionary
    """
    ndict = dict()
    ndict[0] = nodes
    all_nodes = nodes
    for dpth in range(1, max_depth + 1):
      ndict[dpth] = []
      for n in ndict[dpth - 1]:
        for sn in g.successors(n):
          if sn not in all_nodes:
            ndict[dpth].append(sn)
      all_nodes.extend(ndict[dpth])
    return ndict