#
# <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/>.
# 
#

"""!
This module implements algorithms for calculating the Graph Edit Distance 
(GED) between two graphs. We can distinguish three ways of doing this:
1) the costs of the operations, i.e. substitution, insertion, deletion and 
match, are fixed. It means that is doesn't matter between which nodes the 
operation occures. Moreover, the edges are not considered.
2) The cost of the operation depends on both, the type of the operation and
the pair of nodes it occures between. This is solved with the Munkers algorithm.
However, the edges are not considered.
3) The same as the previous one, but in addition the type of an edge matters.

The FixedGraphEditDistanceMeasure class, that is the first case, has been 
implemented so far.
"""

import structuralsimilaritymeasure
import abc

class GraphEditDistanceMeasure(
  structuralsimilaritymeasure.StructuralSimilarityMeasure):
  """!
  An abstract class that groups the Graph Edit Distance (GED) measures (all 
  of them inherit from it).
  """
  __metaclass__ = abc.ABCMeta

  def __init__(self, options, str_name = 'GraphEditDistanceMeasure'):
    """!
    Initialize a child of the GraphEditDistanceMeasure. So far it hasn't done 
    anything except calling the __init__ method of it's parent.

    @param str_name: String like measure representation
    """
    super(GraphEditDistanceMeasure, self).__init__(options, str_name)

  @abc.abstractmethod
  def calculate(self, g1, g2):
    """!
    Abstract method

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

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

class FixedGraphEditDistanceMeasure(GraphEditDistanceMeasure):
  """!
  The class that calculates the GED between two graphs. However, the costs of 
  each available operation is fixed. It means that it doesn't matter which nodes
  are considered and what the edge between them is, the cost of the operation
  is always the same.

  The result is between 0 and 1, where 0 means not similar at all and 1 
  identity.
  """

  DEFAULT_MATCH_COST = 0.0
  DEFAULT_SUBSTITUTE_COST = 1.0
  DEFAULT_DELETE_COST = 2.5
  DEFAULT_INSERT_COST = 2.0

  def __init__(self, options, str_name = 'FixedGraphEditDistanceMeasure'):
    """!
    Create the instance of the FixedGraphEditDistanceMeasure class.

    The fixed GED algorithm needs four cost constants: the match cost, 
    the substitution cost, the deletion cost and the insertion cost. All of them
    should be provided in the options. Otherwise, the following default values
    will be assigned:
    - 0.0 for the match cost,
    - 1.0 for the substitution cost,
    - 2.5 for the deletion cost,
    - 2.0 for the insertion cost.
    You may provide this values as strings, they will be automatically 
    converted to floats.

    @param options A dictionary with the keys: 'match_cost', 'delete_cost',
      'substitute_cost', 'insert_cost'.
    @type options: dict(str: floats)|dict(str: str)|dict(str: unicode)
    @param str_name The name of this instance.
    @type str_name: str
    """
    super(FixedGraphEditDistanceMeasure, self).__init__(str_name)
    self.match_cost = options.get('match_cost', self.DEFAULT_MATCH_COST)
    self.substitute_cost = \
      options.get('substitute_cost', self.DEFAULT_SUBSTITUTE_COST)
    self.delete_cost = options.get('delete_cost', self.DEFAULT_DELETE_COST)
    self.insert_cost = options.get('insert_cost', self.DEFAULT_INSERT_COST)

    # If options are taken from the config then they may be str or unicode
    # convert them to float
    if isinstance(self.match_cost, (str, unicode, int)):
      self.match_cost = float(self.match_cost)
    if isinstance(self.substitute_cost, (str, unicode, int)):
      self.substitute_cost = float(self.substitute_cost)
    if isinstance(self.delete_cost, (str, unicode, int)):
      self.delete_cost = float(self.delete_cost)
    if isinstance(self.insert_cost, (str, unicode, int)):
      self.insert_cost = float(self.insert_cost)
  
  def calculate(self, g1, g2):
    """!
    Calculate the fixed GED.

    The method checks what the best method of transforming the g1 graph into the
    g2 graph is. It creates a distance matrix. The first row is the cost of 
    inserting the sequence of nodes up to some point, e.g if we have 10 nodes in
    the g2 graph in the 5th column (in the 1st row) is cost of inserting the
    first 5 nodes. Thus in the last column is the cost of inserting the whole g2
    graph. The cost of removing the nodes from the g1 graph is in the 1st column
    of the distance matrix. We process in the same way to obtain it as for 
    insertions.
    The rest of the matrix is filled by checking what the best operation is at
    a specific point conidering the best sequence of operations that has been
    created so far.

    Let us consider a part of a distance matrix:

          |   -  | G2_M2 | G2_M3 | 
          |------|-------|-------|
          |G1_N4 |   5.0 |   7.0 |
          |G1_N5 |   8.0 |   ??? |

    We would like to know what the best option is: to substitute the node G1_N5
    with G2_M3, to remove G1_N5, to insert G2_M3 or G2_M3 and G1_N5 are the same
    nodes and they match to each other. We calculate ???.
    The cost of insertion G2_M3 to the transformation is the cost from the upper
    cell plus the constant cost of the insertion operation. The cost of deletion
    G1_N5 from the transformation is the sum of the cost from the left cell and
    the constant cost of the deletion operation.
    If the nodes G1_N5 and G2_M3 are equal then we take the cost of created so
    far sequence (G1_N4, G2_M2) and add to it the constant cost of the match 
    operation. If G1_N5 and G2_M3 aren't the same, but G2_M3 is in the source
    graph G1 then the cost is the sum of the G1_N4, G2_M2 and the constant cost
    of the substitution operation. If none of the conditions hold, then we
    conider the cost of the substitution or the insertion at this point as
    infinity.
    The cost of G1_N5, G2_M3 (???) is the minimum of the cost of the insertion,
    the deletion and the substitution or the match at the current point.

    Thus, the final cost (GED) of the transformation is in the bottom right 
    corner of the distance matrix. The GED is normalized by the total cost of 
    deleting the g1 graph and inserting the g2 graph.

    @param g1 The source graph. It is the starting point of the transformation.
    @type g1: networx.DiGraph/networkx.MultiDiGraph

    @param g2 The target graph. It presents the final graph.
    @type g2: networx.DiGraph/networkx.MultiDiGraph

    @return 1 - GED
    @rtype: float
    """
    if not g1 or not g2:
      return 0
    source_nodes = g1.nodes()
    target_nodes = g2.nodes()
    n, m = len(source_nodes)+1, len(target_nodes)+1
    distance_matrix = [[0 for i in xrange(m)] for j in xrange(n)]
    # Fill the first column with the costs of deleting the sequences of nodes
    for i in xrange(1, n):
      distance_matrix[i][0] = distance_matrix[i-1][0] + self.delete_cost
    # Fill the first row with the costs of inserting the sequences of nodes
    for j in xrange(1, m):
      distance_matrix[0][j] = distance_matrix[0][j-1] + self.insert_cost

    # Fill the rest of the distance matrix
    for i in xrange(1, n):
      for j in xrange(1, m):
        # Set the match or the substitute cost to infinity, 
        # because none of them may be possible
        match_or_substitute_cost = float('inf')
        # Are nodes the same?
        if source_nodes[i-1] == target_nodes[j-1]:
          match_or_substitute_cost = distance_matrix[i-1][j-1] + self.match_cost
        # Or can we at least substitue one with another?
        elif g1.has_node(target_nodes[j-1]):
          match_or_substitute_cost = \
            distance_matrix[i-1][j-1] + self.substitute_cost
        # How much does the insertion of the new node cost?
        insert_cost = distance_matrix[i][j-1] + self.insert_cost
        # How much does the deletion of the old node cost?
        delete_cost = distance_matrix[i-1][j] + self.delete_cost
        # Take the minimal cost of those three
        distance_matrix[i][j] = \
          min(match_or_substitute_cost, insert_cost, delete_cost)
    normalization_factor = distance_matrix[-1][0] + distance_matrix[0][-1]
    return (
      1 - (1.*distance_matrix[-1][-1] / normalization_factor)) \
        if normalization_factor else 0.0

  def _print_distance_matrix(self, distance_matrix):
    print "\n".join("  ".join("{:>5.2f}".format(el) for el in inner_list) \
        for inner_list in distance_matrix)

