#
# <one line to give the library's name and an idea of what it does.>
# Copyright (C) 2014  <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 networkx, math
import structuralsimilaritymeasure
import grafon.constants as constants

class PageRankDiffMeasure(
  structuralsimilaritymeasure.StructuralSimilarityMeasure):
  """!
  Imeplemntation of similarity using difference between two same elements in
  different  vectors.  For a  given two graphs,  the PageRank algorithm is run.
  After  that,  the values  of  PageRank ranking  are used as  the  values into
  elements of  created vecors.  The nodes from graph are  transforms  to a flat
  vector  for each graph.  Next,  the difference  between the same positions of
  elements is calculate. As the result is returned sum of the absolute value of 
  all differences (or not differences when the diff=0). In general:
                                                n
  PageRankDiffMeasure(G1, G2) = 1 - 0.5*       SUM(   | PR(G1(n))-PR(G2(n)) |)
                                      n in {G1.noes \/ G2noes}
  """

  def __init__(self, options, str_name = 'PageRankDiffMeasure'):
    """!
    Constructor
    @param options: a dictionary containing additional options for this measure
    @para str_name: default value same as the class name "PageRankDiffMeasure"
    """
    super(PageRankDiffMeasure, self).__init__(options, str_name)

  def calculate(self, g1, g2):
    """!
    Implementation of abstract calculate function from interface. Calculates
    the difference between two created vectors based on the PageRankg ranking.
    The given graphs are copied into new bewfore running pagerank 
    because the PageRank function is not defined to run on multigraphs.

    @param g1 first graph
    @type g1: networgx.DiGraph/networkx.MultiDiGraph

    @param g2 second graph
    @type g1: networgx.DiGraph/networkx.MultiDiGraph

    @return Difference silimarity of two pagerank vectors
    @rtype: double
    """
    if not g1 or not g2:
      return 0

    if len(g1.nodes()) == 0 or len(g2.nodes()) == 0:
      return 0.0

    prg1 = networkx.Graph()
    prg1.add_edges_from(g1.edges())
    prg2 = networkx.Graph()
    prg2.add_edges_from(g2.edges())
    p1 = networkx.pagerank(prg1, max_iter = constants.PAGE_RANK_MAX_ITER)
    p2 = networkx.pagerank(prg2, max_iter = constants.PAGE_RANK_MAX_ITER)

    """
    # if the pr is empty, then different between graphs
    # is maximun, so it is equal to 1
    p1_p2_diff_sum = 0 if len(p1) > 0 else 1.0
    p2_p1_diff_sum = 0 if len(p2) > 0 else 1.0
    for pr1_k, pr1_v in p1.iteritems():
      pr2_v = p2.get(pr1_k, 0.0)
      p1_p2_diff_sum += pr1_v - pr2_v
    for pr2_k, pr2_v in p2.iteritems():
      prv_1 = p2.get(pr2_k, 0.0)
      p2_p1_diff_sum += pr2_v - prv_1
    return 1.0 - (p1_p2_diff_sum + p2_p1_diff_sum)
    """

    diff_sum = 0.0
    for k in set(p1.keys() + p2.keys()):
      diff_sum += math.fabs(p1.get(k, 0.0) - p2.get(k, 0.0))
    return 1.0 - (0.5 * diff_sum)