# Path: props/graph_representation/word.py
# NO_INDEX = -1 # index used in cases where there's no such word in the sentence
# 
# class Word:
#     """
#     word container class, to add the index of the word in addition to the word 
#     
#     @type index: int
#     @var  index: the index of the word within the sentence
#     
#     @type text: string
#     @var  text: the text contained within this word
#     """
#     
#     def __init__(self,index,word):
#         """
#         initialize a word container object
#         """
#         self.index = index
#         self.word = word
#     
#     def to_conll_like(self):
#         return ",".join([str(self.index),self.word])
#     
#     def __str__(self):
#         ret = cgi.escape(self.word)
#         if self.index != NO_INDEX:
#             ret += '<FONT POINT-SIZE="7">[{0}]</FONT>'.format(self.index)
#         return ret
#     
#     def __eq__(self,other_word):
#         return (self.index == other_word.index) and (self.word == other_word.word)
#     
#     def __hash__(self):
#         return self.__str__().__hash__()
# 
# def strip_punctuations(ls):
#     """
#     removes punctuations from beginning and end of the list
#     """
#     puncts = ':.,;\t '
#     sep = "\t"
#     totalElms = len(ls)
#     s = sep.join([x.word for x in ls])
#     ret = ls[totalElms-len(s.lstrip(puncts).split(sep)):len(s.rstrip(puncts).split(sep))]
#     return ret
# 
# Path: props/graph_representation/newNode.py
# COPULA = "SameAs"          # the textual value of a copula node
# PROP = "PROP"          # the textual value of a property node
# RCMOD_PROP = "PROP"    # the textual value of a property for rcmod node
# POSSESSIVE = "have" # the textual value of a possessive node
# APPOSITION = "appos"   # the textual value of an appositio n node
# PREP = "PREP"          # the textual value of a preposition node
# PREP_TYPE = "TYPE"     # the textual value of a preposition node's type
# COND = "COND"          # the textual value of a conditional node
# TIME = "TIME"          # the textual value of a time node
# LOCATION = "LOCATION"  # the textual value of a location node
# CONJUNCTION = "CONJ -" # the textual value of a conjunction node
# ADVERB = "ADV"         # the textual value of a conjunction node
# EXISTENSIAL = "Exists" # the textual value of a conjunction node
# COND_TYPE= PREP_TYPE   # the textual value of a conditional node's type
# RECT_NODE_SHAPE = "rect"
# DEFAULT_NODE_SHAPE = "ellipse"
# PRINT_FEATURES = [("Tense",lambda t:t),
#                   ("Determiner",lambda t:"det: "+t["Value"]),
#                   ("Time Value",lambda t:"date: "+t),
#                   ("Negation", lambda t:"negated"),
#                   ("Passive Voice", lambda t:"passive"),
#                   ("Modal",lambda t:"modal: "+ " ".join(t["Value"])),
#                   ("Definite",lambda t:t),
#                   ("Modifier",lambda t:"modifier: "+t)]
# def resetCounter():
#     def __init__(self,text,isPredicate,features,gr,orderText = True,uid=-1):
#     def removeLemma(self):
#     def get_text(self,gr):
#     def addPropogation(self,node):
#     def minIndex(self):
#     def maxIndex(self):
#     def get_original_text(self):
#     def get_sorted_text(self):
#     def __str__(self):
#     def to_conll_like(self):
#     def neighbors(self):
#     def incidents(self):
#     def is_implicit(self):
#     def pos(self):
#     def isConj(self):
#     def is_wh_question(self):
#     def __hash__(self):
#     def makeTopNode(self):
# def getCopular(gr,index,features):
# def getPossesive(gr,index):
# def join(node1,node2,gr):
# def isDefinite(node):
# class Node:


from pygraph.algorithms.sorting import topological_sorting
from pygraph.classes.digraph import digraph
from pygraph.algorithms.accessibility import accessibility
from props.graph_representation.word import NO_INDEX, Word, strip_punctuations
from pygraph.algorithms.traversal import traversal
from pygraph.algorithms.minmax import minimal_spanning_tree, shortest_path
from props.graph_representation import newNode
from operator import itemgetter
import subprocess, math, re, nltk
import cgi
import time
import logging

                         source = source_node)
    return max(d.iteritems(),
               key = itemgetter(1))[0] # Returns the farthest away node

def reverse_graph_edges(graph):
    """
    Returns a reversed version of the input graph.
    I.e., for each edge (u, v) in graph, there will be an edge (v, u) in the
    returned graph.
    The labels aren't changed.
    """
    ret_graph = digraph()

    # Add all nodes to the return graph
    for node in graph.nodes():
        ret_graph.add_node(node)

    # Add reveresed edges to the returned graph
    for (u, v) in graph.edges():
        ret_graph.add_edge((v, u),
                           label = graph.edge_label((u, v)))

    return ret_graph

def merge_nodes(gr, node1, node2):
    if (gr.has_edge((node1, node2))):
        gr.del_edge((node1, node2))
    else:
        gr.del_edge((node2, node1))
        

# Path: props/graph_representation/word.py
# NO_INDEX = -1 # index used in cases where there's no such word in the sentence
# 
# class Word:
#     """
#     word container class, to add the index of the word in addition to the word 
#     
#     @type index: int
#     @var  index: the index of the word within the sentence
#     
#     @type text: string
#     @var  text: the text contained within this word
#     """
#     
#     def __init__(self,index,word):
#         """
#         initialize a word container object
#         """
#         self.index = index
#         self.word = word
#     
#     def to_conll_like(self):
#         return ",".join([str(self.index),self.word])
#     
#     def __str__(self):
#         ret = cgi.escape(self.word)
#         if self.index != NO_INDEX:
#             ret += '<FONT POINT-SIZE="7">[{0}]</FONT>'.format(self.index)
#         return ret
#     
#     def __eq__(self,other_word):
#         return (self.index == other_word.index) and (self.word == other_word.word)
#     
#     def __hash__(self):
#         return self.__str__().__hash__()
# 
# def strip_punctuations(ls):
#     """
#     removes punctuations from beginning and end of the list
#     """
#     puncts = ':.,;\t '
#     sep = "\t"
#     totalElms = len(ls)
#     s = sep.join([x.word for x in ls])
#     ret = ls[totalElms-len(s.lstrip(puncts).split(sep)):len(s.rstrip(puncts).split(sep))]
#     return ret
# 
# Path: props/graph_representation/newNode.py
# COPULA = "SameAs"          # the textual value of a copula node
# PROP = "PROP"          # the textual value of a property node
# RCMOD_PROP = "PROP"    # the textual value of a property for rcmod node
# POSSESSIVE = "have" # the textual value of a possessive node
# APPOSITION = "appos"   # the textual value of an appositio n node
# PREP = "PREP"          # the textual value of a preposition node
# PREP_TYPE = "TYPE"     # the textual value of a preposition node's type
# COND = "COND"          # the textual value of a conditional node
# TIME = "TIME"          # the textual value of a time node
# LOCATION = "LOCATION"  # the textual value of a location node
# CONJUNCTION = "CONJ -" # the textual value of a conjunction node
# ADVERB = "ADV"         # the textual value of a conjunction node
# EXISTENSIAL = "Exists" # the textual value of a conjunction node
# COND_TYPE= PREP_TYPE   # the textual value of a conditional node's type
# RECT_NODE_SHAPE = "rect"
# DEFAULT_NODE_SHAPE = "ellipse"
# PRINT_FEATURES = [("Tense",lambda t:t),
#                   ("Determiner",lambda t:"det: "+t["Value"]),
#                   ("Time Value",lambda t:"date: "+t),
#                   ("Negation", lambda t:"negated"),
#                   ("Passive Voice", lambda t:"passive"),
#                   ("Modal",lambda t:"modal: "+ " ".join(t["Value"])),
#                   ("Definite",lambda t:t),
#                   ("Modifier",lambda t:"modifier: "+t)]
# def resetCounter():
#     def __init__(self,text,isPredicate,features,gr,orderText = True,uid=-1):
#     def removeLemma(self):
#     def get_text(self,gr):
#     def addPropogation(self,node):
#     def minIndex(self):
#     def maxIndex(self):
#     def get_original_text(self):
#     def get_sorted_text(self):
#     def __str__(self):
#     def to_conll_like(self):
#     def neighbors(self):
#     def incidents(self):
#     def is_implicit(self):
#     def pos(self):
#     def isConj(self):
#     def is_wh_question(self):
#     def __hash__(self):
#     def makeTopNode(self):
# def getCopular(gr,index,features):
# def getPossesive(gr,index):
# def join(node1,node2,gr):
# def isDefinite(node):
# class Node:


# Path: props/graph_representation/graph_utils.py
from pygraph.algorithms.sorting import topological_sorting
from pygraph.classes.digraph import digraph
from pygraph.algorithms.accessibility import accessibility
from props.graph_representation.word import NO_INDEX, Word, strip_punctuations
from pygraph.algorithms.traversal import traversal
from pygraph.algorithms.minmax import minimal_spanning_tree, shortest_path
from props.graph_representation import newNode
from operator import itemgetter
import subprocess, math, re, nltk
import cgi
import time
import logging

                         source = source_node)
    return max(d.iteritems(),
               key = itemgetter(1))[0] # Returns the farthest away node

def reverse_graph_edges(graph):
    """
    Returns a reversed version of the input graph.
    I.e., for each edge (u, v) in graph, there will be an edge (v, u) in the
    returned graph.
    The labels aren't changed.
    """
    ret_graph = digraph()

    # Add all nodes to the return graph
    for node in graph.nodes():
        ret_graph.add_node(node)

    # Add reveresed edges to the returned graph
    for (u, v) in graph.edges():
        ret_graph.add_edge((v, u),
                           label = graph.edge_label((u, v)))

    return ret_graph

def merge_nodes(gr, node1, node2):
    if (gr.has_edge((node1, node2))):
        gr.del_edge((node1, node2))
    else:
        gr.del_edge((node2, node1))
        

    new = newNode.join(node1, node2, gr)
