import networkx
import logging
import grafon.constants as constants
from itertools import combinations
from reducerinterface import ReducerInterface

class SimpleReducer(ReducerInterface):
  """!
  A simple reducer class that finds the shortest paths between each pair of
  nodes from the text.
  """
  def __init__(self, options, reducer_name = "SimpleReducer"):
    """!
    Create the simple reducer. It doesn't expect any additional options.

    @param options no additional parameters are expected by this class.
    @type options: dict(str: str)
    @param reducer_name the name of the reducer that is actually created.
    @type reducer_name: str
    """
    super(SimpleReducer, self).__init__(options, reducer_name)

  def reduce(self, digraph, text_nodes):
    """!
    Reduce the graph by finding the shortest paths between each pair of nodes.

    A very simple method to obtain minimum subgraphs. This method finds
    all minimal paths between all nodes from the text (text_nodes).

    Firstly, this method creates a new graph of the type networkx.MultiDiGraph.
    For each pair of nodes from the text it finds the shortest path between them
    (not a path with the lowest cost, but the shortest path in the graph).
    Each path is added to the new graph as a new path. The labels from 
    the original graph are retained as well as the edges' directions 
    (from node -> to node).

    @param graph the directed graph to be reduced.
    @type graph: networkx.DiGraph()
    @param text_nodes nodes from a text.
    @type text_nodes: grafon.structures.textnodes.TextNodes

    @return the reduced graph.
    @rtype: networkx.DiGraph()
    """
    # This was the _simple_shortest_paths_min_subgraphs(self, nodes) method
    # of the graphs.semgraph.SemGraph class
    undirected_graph = digraph.to_undirected()
    out_graph = networkx.DiGraph()
    # Find paths
    for source, target in text_nodes.get_combinations():
      try:
        shortest_path = networkx.shortest_path(
          undirected_graph, 
          source, 
          target)
        for n in shortest_path:
          if not out_graph.has_node(n):
            out_graph.add_node(n, attr_dict = digraph.node[n])
        out_graph.add_edges_from(
          self._get_directed_edges_of_path(shortest_path, digraph))

      except Exception, e:
        logger = logging.getLogger(__name__)
        logger.error(e)
    # There may be still nodes in txt_nodes that aren't in the new_g
    for n in text_nodes.graph_keys:
      if not n in out_graph:
          out_graph.add_node(n, attr_dict = {
              constants.NODE_TOKENS  : [],
              constants.NODE_COUNT   : 1,
              constants.NODE_SOURCES : [constants.NODE_FROM_TEXT]})

    return out_graph

class SimpleTraversalCostReducer(ReducerInterface):
  """!
  A simple reducer class that finds paths with the lowest traversal cost
  between each pair of nodes from the text.
  """
  def __init__(self, options, reducer_name = "SimpleTraversalCostReducer"):
    """!
    Create the simple traversal cost reducer. 
    
    It doesn't expect any additional options.

    @param options no additional parameters are expected by this class.
    @type options: dict(str: str)
    @param reducer_name the name of the reducer that is actually created.
    @type reducer_name: str
    """
    super(SimpleTraversalCostReducer, self).__init__(options, reducer_name)

  def reduce(self, digraph, text_nodes):
    """!
    Reduce the graph by finding the paths of the lowest traversal cost.

    A simple method to obtain minimum subgraphs. This method finds a path 
    of the lowest traversal cost between each pair of nodes from the text
    The edges' weights are assigned as follows:
    1) 0 if both nodes connected with the edge belong to the text,
    2) 1 if only one node of the two connected with the edge belongs to the 
      text,
    3) 2 if none of the nodes connected with the edge belong to the text.

    @param graph the directed graph to be reduced.
    @type graph: networkx.DiGraph()
    @param text_nodes nodes from a text.
    @type text_nodes: grafon.structures.textnodes.TextNodes

    @return the reduced graph.
    @rtype: networkx.DiGraph()
    """
    txt_nodes = text_nodes.graph_keys
    weighted_graph = networkx.Graph()
    out_graph = networkx.DiGraph()
    if len(txt_nodes) == 1:
      out_graph.add_node(list(txt_nodes)[0])
    else:
      # Add weights to tmp graph
      for node_from, node_to in digraph.edges_iter():
        weight = 2
        if node_from in txt_nodes:
          weight -= 1
        if node_to in txt_nodes:
          weight -= 1
        weighted_graph.add_edge(
          node_from, 
          node_to, 
          {constants.EDGE_WEIGHT: weight})
      # Find paths
      for source, target in text_nodes.get_combinations():
        try:
          shortest_path = networkx.shortest_path(
            weighted_graph, 
            source, 
            target, 
            weight = constants.EDGE_WEIGHT)
          out_graph.add_edges_from(
            self._get_directed_edges_of_path(shortest_path, digraph))
        except Exception, e:
          logger = logging.getLogger(__name__)
          logger.error(e)
      # There may be still nodes in txt_nodes that aren't in the new_g
      for node in txt_nodes:
        if not node in out_graph:
          out_graph.add_node(node)
    return out_graph