#!/usr/bin/python

import sys, time, random
from networkx import *

#algorithm config
verbose = False
maxk=1000

#####################
#print digraph stats#
#####################

def distats(D):
    outmax = 0
    inmax = 0
    for node in nodes(D):
        outmax = max(D.out_degree(node),outmax) 
        inmax = max(D.in_degree(node),inmax) 
    #print "#n, m, delta_out,delta_in,wcc"
    print len(nodes(D)),len(edges(D)),outmax,inmax,nx.number_connected_components(D.to_undirected())

#print graph stats
def stats(G):
    deg = 0
    for node in nodes(G):
        deg = max(G.degree(node),deg)
    #print "#n, m, delta,cc"
    print len(nodes(G)),len(edges(G)), deg, nx.number_connected_components(G)

#print both stats
def bothstats(D,G):
    if verbose:
        distats(D);
        stats(G);
######################
#building the graphs #
######################

def buildDiGraph(filen):
    D = DiGraph();
    for line in filen:
        tabs = line.split();
        a = tabs[0]
        b = tabs[1].strip()
        D.add_node(a)
        D.add_node(b)
        D.add_edge(a,b)
    return D

def buildGraph(filen,D):
    G = Graph();
    for line in filen:
        tabs = line.split();
        a = tabs[0]
        b = tabs[1].strip()
        if a in nodes(D) and b in nodes(D):
            G.add_node(a)
            G.add_node(b)
            G.add_edge(a,b)
    return G

#################################
#     utility functions         # 
#################################

#remove those vertices from D that are not in G
def uselessNodes(D,G):
    success=False
    for node in nodes(D):
        if not node in nodes(G):
            D.remove_node(node)
            success=True
    for node in nodes(G):
        if not node in nodes(D):
            G.remove_node(node)
            success=True
    return success

#removal of vertex in both graphs
def consistent_removal(D,G,u):
    G.remove_node(u)
    D.remove_node(u)

#elapsed_time_string
def elapsed(start):
    return str(time.time()-start)

#elapsed_time_string
def too_long(start,timeout):
    return (time.time()-start)>timeout

#################################
#general data reduction routines#
#################################

def dreduce(D,G,exhaustive):
    reduced=False
    success=True 
    while (success):
        success=False;
        #rule 0:identify nodes which are only in one of the graphs
        #if uselessNodes(D,G):
        #    return True
        
        #rule 1: if two vertices are in different connected components of G, then one can remove the edge in D
        if G.order()>0:
            gconn = is_connected(G)
        else: gconn=True
        if not gconn:
            for u in nodes(D):
                ccu = nx.node_connected_component(G, u)
                for v in D.neighbors(u):
                    if v != u and not v in ccu:
                        reduced=True
                        D.remove_edge(u,v)
                        if exhaustive: success=True

        #rule 2: if two vertices are in different weakly connected components of D, then one can remove the edge in G
        Dun = Graph(D)
        if Dun.order()>0 and not nx.is_connected(Dun): # check makes sense only if D has several weakly connected components
            for u in nodes(G):
                wccu = nx.node_connected_component(Dun, u)
                for v in G.neighbors(u):
                    if v != u and not v in wccu:
                        reduced=True
                        G.remove_edge(u,v)
                        if exhaustive: success=True
            
        #rule 3: remove isolated vertices in G or D
        for u in nodes(G):
            if G.degree(u)==0 or (D.out_degree(u)==0 and D.in_degree(u)==0):
                reduced=True
                consistent_removal(D,G,u)

    return reduced


#################################
# (u,v)  data reduction routines#
#################################

def proper(D,G,u,v):
    if (v in nodes(D) and v in nodes(G) and  
        u in nodes(D) and u in nodes(G)):
        if nx.has_path(D,u,v) and nx.has_path(G,u,v):
            return True
    return False

#returns true if a reduction took place
def dreduceuv(D,G,u,v):
    reduced=False
    ureach=nx.single_source_shortest_path_length(D,u)

    for w in nodes(D):
         if not w in ureach:
             reduced=True
             consistent_removal(D,G,w)
             if w==u: print "Bad"
             if w==v or w==u:return True 

    reachv=nx.single_source_shortest_path_length(D.reverse(),v)
    
    for w in nodes(D):
        if not w in reachv:
            reduced=True
            consistent_removal(D,G,w)
            if w==v: print "Bad"
            if w==v or w==u:return True 

    Dstar = D.to_undirected() 
    # #apoints = set(nx.articulation_points(Dstar))
    # #print len(apoints)
    # #print apoints
    for w in nodes(G):
         Dc = D.copy()
         if w in nodes(Dc) and w != u and w != v:
             Dc.remove_node(w)
             for x in nodes(Dc):
                 if (not nx.has_path(Dc,u,x)) and (not nx.has_path(Dc,x,v)):
                     consistent_removal(D,G,x)
                     reduced=True
    return reduced


###################################
#  reduction with upper bound k   #
###################################

def dreducekuv(D,G,u,v,k):
    success=False

    distu=nx.single_source_shortest_path_length(G,u,k)
    distv=nx.single_source_shortest_path_length(G,v,k)
    #print distu
    
    for w in nodes(D):
        if (not w in distu) or (not w in distv) :
            consistent_removal(D,G,w)
            if w==v or w==u:return True 
            success=True

    distu=nx.single_source_shortest_path_length(D,u,k)
    distv=nx.single_source_shortest_path_length(D.reverse(),v,k)
                
            
    for w in nodes(D):            
        if not w in distu or not w in distv or (distu[w]+distv[w]>k):
            consistent_removal(D,G,w)
            if w==v or w==u:return True 
            success=True

            
    return success

###################################
# exhaustive application routines #
###################################

#returns False if instance is not proper anymore (u or v removed or they cannot reach each other)
def exreduce(D,G,u,v,exhaustive):
    success=True
    while(success):
        success=False
        if not proper(D,G,u,v):
            bothstats(D,G)
            return False
        elif dreduce(D,G,exhaustive):
            success=True; continue
        elif dreduceuv(D,G,u,v):
            success=True; continue
    bothstats(D,G)
    return True


#k is the number of edges in the path
def exkreduce(D,G,u,v,k,exhaustive):
    success=True
    #first reduction for k, other rules have been already applied when method is called
    dreducekuv(D,G,u,v,k)
    while(success):
        success = False
        if not proper(D,G,u,v):
            bothstats(D,G)
            return False
        elif dreduce(D,G,exhaustive):
            success=True; continue
        elif dreduceuv(D,G,u,v):
            success=True; continue
        elif dreducekuv(D,G,u,v,k):
            success=True; continue
    bothstats(D,G)
    return True