#
# <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 math
import networkx
import similarity
import structuralsimilaritymeasure

class SIDDDescriptorMeasure(
  structuralsimilaritymeasure.StructuralSimilarityMeasure):
  """!
  It is the base class for:
   * SIDDSumDescriptorsMeasure
   * SIDDSplashDescriptorsMeasure
   * SIDDPagerakDescriptorsMeasure
  
  Additionaly this class provide method to measure similarity 
  between two any nodes from given graph @see calculate_sim_nodes
  """
  DEFAULT_A = 1.0
  DEFAULT_B = 1.0
  DEFAULT_C = 1.0
  DEFAULT_ALFA = 1.0
  DEFAULT_BETA = 1.0

  """!
  Helper class representing node descriptor.

  This class contains descriptor (for a given node) as:
    - input edges
    - output edges
    - input nodes
    - output nodes
  It is only a wrapper for four lists containing description of a single node.
  """
  class NodeDescriptor():
    def __init__(self, node):
      self.node = node
      self.in_edges = []
      self.out_edges = []
      self.in_nodes = []
      self.out_nodes = []

  def __init__(self, options, str_name = 'SIDDDescriptorMeasure'):
    """!
    Constructor

    @param options: a dictionary containing options for this measure
    @para str_name: default value same as the class name 
                    "SIDDDescriptorMeasure"
    """
    super(SIDDDescriptorMeasure, self).__init__(options, str_name)
    self.a = float(options.get('a', self.DEFAULT_A) \
      if options else self.DEFAULT_A)
    self.b = float(options.get('b', self.DEFAULT_B) \
      if options else self.DEFAULT_B)
    self.c = float(options.get('c', self.DEFAULT_C) \
      if options else self.DEFAULT_C)
    self.alfa = float(options.get('alfa', self.DEFAULT_ALFA) \
      if options else self.DEFAULT_ALFA)
    self.beta = float(options.get('beta', self.DEFAULT_BETA) \
      if options else self.DEFAULT_BETA)
    
    #! Descriptors for the first and second graph
    self.g1descr = None
    self.g2descr = None

  def prepare_node_descriptor_dictionary(self, g1, g2):
    """!
    Prepares the dictionary containing descriptors for each nodes.

    Generates descriptors for each node into both graphs. Store the 
    descriptors into dictionaries where as the key is the node and as value 
    is descriptor of this node. For each node (existing in both graphs) 
    SIDD is calculated.

    @param g1 first graph
    @param g2 second graph

    @return dictionary of SIDD values, where as the key node is used 
            and the value is SIDD value of the node into g1 and g2
    @rtype: dict[networkx.node]=>double
    """
    # Generate descriptors for each node into first graph. 
    self.g1descr = dict()
    for n in g1.nodes():
      self.g1descr[n] = self.generate_node_descriptor(n, g1)
    # generate descriptors for each node into second graph
    self.g2descr = dict()
    for n in g2.nodes():
      self.g2descr[n] = self.generate_node_descriptor(n, g2)

    # Calculates SIDD for the nodes exists into both grahs
    g12d = dict()
    for n in self.g1descr.keys():
      if self.g2descr.has_key(n):
        g12d[n] = self.calculate_sidd(self.g1descr[n], self.g2descr[n], 
                                      self.a, self.b, self.c, 
                                      self.alfa, self.beta)
    return g12d

  def calculate_sim_nodes(self, g1, n1, g2, n2):
    """!
    Calculates SIDD similarity between two nodes from given graphs.
    
    @param g1
    @param n1
    @param g2
    @param n2
    """
    return \
      self.calculate_sidd(
        self.generate_node_descriptor(n1, g1),
        self.generate_node_descriptor(n2, g2),
        self.a, self.b, self.c, self.alfa, self.beta)

  def generate_node_descriptor(self, n, g):
    """!
    Generates descriptor for given node and graph with this node.

    @return Object of NodeDescriptor
    """
    nd = self.NodeDescriptor(n)
    nd.out_nodes = g.successors(n)
    nd.in_nodes  = g.predecessors(n)
    nd.out_edges = g.out_edges(n, data = True)
    nd.in_edges  = g.in_edges(n, data = True)
    return nd
  
  def calculate_sidd(self, d1, d2, a, b, c, alfa, beta):
    """!
    Calculates SIDD, actually it is:

                  / b*|I| - ((c*|D1| + c*|D2|) / 2) \
             1+   | ------------------------------- |
                  \               a*|S|             /
      SIDD = -------------------------------------
                                 2
    """
    assert(a > 0.0), "Sum factor must be greater than zero!"
    assert(a <= 1.0), "Sum factor must be lower or equal to one!"
    assert(b <= 1.0), "Intersection factor must be lower or equal to one!"
    assert(c <= 1.0), "Difference factor must be lower or equal to one!"
    assert(alfa <= 1.0), "Alpha must be lower or equal to one!"
    assert(beta <= 1.0), "Beta must be lower or equal to one!"

    S = self.calculate_s(d1, d2, alfa, beta)
    I = self.calculate_i(d1, d2, alfa, beta)
    D1 = self.calculate_d(d1, d2, alfa, beta)
    D2 = self.calculate_d(d2, d1, alfa, beta)
    if S == 0:
      return 0.0
    return 0.5 * (1.0 + ((b * I - (0.5 * (c * D1 + c * D2))) / float(a * S)))

  def calculate_s(self, d1, d2, alfa, beta):
    """!
    Calculates the sum of nodes and edges into both descriptors.

    The sum is calculated in two steps as 
     1) lenght of set of all nodes into given descriptors
     2) lenght of set of all edges into given descriptors
    The partial sums (1) and (2) are weighed with a given factors.

    S = alfa * s_nodes + beta * s_edges

    @param d1 Descripor of node "n" into first graph
    @type d1: NodeDescriptor
    @param d1 Descripor of node "n" into second graph
    @type d1: NodeDescriptor
    @param alfa Factor for a partial sum of nodes
    @type alfa: float
    @param beta Factor for a partial sum of edges
    @type beta: float

    @return Calculated value of S from SIDD
    @rtype: double
    """
    return (
      alfa * self.calculate_s_nodes(d1, d2) +
      beta * self.calculate_s_edges(d1, d2))
  
  def calculate_s_nodes(self, d1, d2):
    """!
    Calculate the sum of nodes into both descriptors. 
    
    The sum is calculated as lenght of set of all nodes into given descriptors.
    
    @param d1 Descripor of node "n" into first graph
    @type d1: NodeDescriptor
    @param d1 Descripor of node "n" into second graph
    @type d1: NodeDescriptor

    @return Calculated partial value of S from SIDD
    @rtype: double
    """
    # assert(d1.node == d2.node), "Given descriptors are not for the same node!"
    return (
      len(set(d1.in_nodes + d2.in_nodes)) + 
      len(set(d1.out_nodes + d2.out_nodes)))

  def calculate_s_edges(self, d1, d2):
    """!
    Calculate the sum of edges into both descriptors. 

    The sum is calculated as lenght of set of all edges into given descriptors.

    @param d1 Descripor of node "n" into first graph
    @type d1: NodeDescriptor
    @param d1 Descripor of node "n" into second graph
    @type d1: NodeDescriptor

    @return Calculated partial value of S from SIDD
    @rtype: double
    """
    # assert(d1.node == d2.node), "Given descriptors are not for the same node!"
    wdin = set(d['label'] for _, _, d in d1.in_edges)
    wdin = wdin.union(set(d['label'] for _, _, d in d2.in_edges))
    wdout = set(d['label'] for _, _, d in d1.out_edges)
    wdout = wdout.union(set(d['label'] for _, _, d in d2.out_edges))
    return len(wdin) + len(wdout)

  def calculate_i(self, d1, d2, alfa, beta):
    """!
    Calculates the intersection of nodes and edges into both descriptors.

    The intersection is calculated in two steps as 
     1) lenght of set of intersected nodes into given descriptors
     2) lenght of set of intersected edges into given descriptors
    The partial intersection (1) and (2) are weighed with a given factors.

    I = alfa * i_nodes + beta * i_edges

    @param d1 Descripor of node "n" into first graph
    @type d1: NodeDescriptor
    @param d1 Descripor of node "n" into second graph
    @type d1: NodeDescriptor
    @param alfa Factor for a partial intersection of nodes
    @type alfa: float
    @param beta Factor for a partial intersection of edges
    @type beta: float

    @return Calculated value of I from SIDD
    @rtype: double
    """
    return (
      (alfa * self.calculate_i_nodes(d1, d2)) +
      (beta * self.calculate_i_edges(d1, d2)))

  def calculate_i_nodes(self, d1, d2):
    """!
    Calculate the intersection of nodes into both descriptors. 

    The intersection is calculated as lenght of set of all nodes into 
    given descriptors.

    @param d1 Descripor of node "n" into first graph
    @type d1: NodeDescriptor
    @param d1 Descripor of node "n" into second graph
    @type d1: NodeDescriptor

    @return Calculated partial value of I from SIDD
    @rtype: double
    """
    # assert(d1.node == d2.node), "Given descriptors are not for the same node!"
    return (
      len(set(d1.in_nodes).intersection(set(d2.in_nodes))) + 
      len(set(d1.out_nodes).intersection(set(d2.out_nodes))))

  def calculate_i_edges(self, d1, d2):
    """!
    Calculate the sum of edges into both descriptors. 

    The sum is calculated as lenght of set of all edges into given descriptors.

    @param d1 Descripor of node "n" into first graph
    @type d1: NodeDescriptor
    @param d1 Descripor of node "n" into second graph
    @type d1: NodeDescriptor

    @return Calculated partial value of I from SIDD
    @rtype: double
    """
    # assert(d1.node == d2.node), "Given descriptors are not for the same node!"
    wdin = set(d['label'] for _, _, d in d1.in_edges)
    wdin = wdin.intersection(set(d['label'] for _, _, d in d2.in_edges))

    wdout = set(d['label'] for _, _, d in d1.out_edges)
    wdout = wdout.intersection(set(d['label'] for _, _, d in d2.out_edges))
    return len(wdin) + len(wdout)

  def calculate_d(self, d1, d2, alfa, beta):
    """!
    Calculates the difference of nodes and edges into both descriptors.

    The intersection is calculated in two steps as 
     1) lenght of set of different nodes into given descriptors
     2) lenght of set of different edges into given descriptors
    The partial differences (1) and (2) are weighed with a given factors.

    I = alfa * d_nodes + beta * d_edges

    @param d1 Descripor of node "n" into first graph
    @type d1: NodeDescriptor
    @param d1 Descripor of node "n" into second graph
    @type d1: NodeDescriptor
    @param alfa Factor for a partial intersection of nodes
    @type alfa: float
    @param beta Factor for a partial intersection of edges
    @type beta: float

    @return Calculated value of D from SIDD
    @rtype: double
    """
    return (
      (alfa * self.calculate_d_nodes(d1, d2)) +
      (beta * self.calculate_d_edges(d1, d2)))

  def calculate_d_nodes(self, d1, d2):
    """!
    Calculate the intersection of nodes into both descriptors. 

    The intersection is calculated as lenght of set of all nodes into 
    given descriptors.

    @param d1 Descripor of node "n" into first graph
    @type d1: NodeDescriptor
    @param d1 Descripor of node "n" into second graph
    @type d1: NodeDescriptor

    @return Calculated partial value of D from SIDD
    @rtype: double
    """
    # assert(d1.node == d2.node), "Given descriptors are not for the same node!"
    return (
      len(set(d1.in_nodes).difference(set(d2.in_nodes))) + 
      len(set(d1.out_nodes).difference(set(d2.out_nodes))))

  def calculate_d_edges(self, d1, d2):
    """!
    Calculate the sum of edges into both descriptors. 

    The sum is calculated as lenght of set of all edges into given descriptors.

    @param d1 Descripor of node "n" into first graph
    @type d1: NodeDescriptor
    @param d1 Descripor of node "n" into second graph
    @type d1: NodeDescriptor

    @return Calculated partial value of D from SIDD
    @rtype: double
    """
    # assert(d1.node == d2.node), "Given descriptors are not for the same node!"
    wdin = set(d['label'] for _, _, d in d1.in_edges)
    wdin = wdin.difference(set(d['label'] for _, _, d in d2.in_edges))
    wdout = set(d['label'] for _, _, d in d1.out_edges)
    wdout = wdout.difference(set(d['label'] for _, _, d in d2.out_edges))
    return len(wdin) + len(wdout)

  def calculate(self, g1, g2):
    """!
    This measure can be used to measure the similarity between any two nodes
    with function @see calculate_sim_nodes so it shouldn't be abstract.
    This function doing nothing.
    """
    pass