import networkx as nx

class sub_path:
    ''' Helper class to represents sub-path into the graph.
        Contains information about path (subpath)
    '''
    def __init__(self):
        self._p = []
        self._visited = False

class SemGraph:
    '''This class is the wrapper for networkx.Graph class
       Implements some operations for weighting the edges
       or/and nodes in the graph. Some operations which
       are not implemented in networkx package.
    '''

    def __init__(self):
        self._g = None

    def G(self):
        '''Returns actually graph @see self._g'''
        return self._g

    def build_graph(self):
        '''General methon which can be reimplemented.
           This method build the graph'''
        self._g = nx.Graph()
        self._g.add_path(['1', '2',  '5',  '9', '12'])
        self._g.add_path(['1', '4',  '8', '11', '12'])
        self._g.add_path(['1', '3',  '6', '10', '12'])
        self._g.add_path(['1', '3',  '6', '9', '12'])
        self._g.add_path(['1', '3',  '7', '10', '12'])
        self._g.add_path(['5', '6',  '3',  '7', '8'])
        self._g.add_path(['5', '6', '10', ' 7', '8'])

    def modify_nodes_weight(self, nmod, w):
        '''For given list of nodes @see nmod modifies 
           its weight to the given @see w value'''
        for n in nmod:
            if self._g.has_node(n):
                nghb = self._g.neighbors(n)
                self._g.remove_node(n)
                self._g.add_node(n, weight = w)
                for nb in nghb:
                    self._g.add_edge(n, nb)
    
    def modify_edge_weight(self, e, w):
        '''For given edge @see e in the grap @see self._g 
           modify weight to the given value @see w. 

           @param e is the tuple which means that between e[0] and e[1]
                    exists the edge i the graph @see self._g
        '''
        self._g.remove_edge(e[0], e[1])
        self._g.add_edge(e[0], e[1], weight = w)

    def weight_all_edges(self, __func__):
        '''Weight all edges from graph @see self._g with given 
           function @see __func__. This function should take as
           their arguments:
                fst-node, scnd-node
        '''
        for e in self._g.edges():
            eweight = __func__(e)
            self.modify_edge_weight(e, eweight)

    def weight_all_nodes(self, w):
        '''For all nodes in the graph @see self._g set the value (weight)
           equal as given @see w'''
        self.modify_nodes_weight(self._g.nodes(), w)

    def all_minimal_subgraphs(self, nodes):
        '''Returns all minimal subgraphs which can be build from 
           nodes @see nodes. One minimal subgraph contains all
           nodes which are give in the list @see nodes'''

        # pobieram wszystkie minimalne sciezki
        checked = dict()
        for f in nodes:
            for t in nodes:
                mn = min(f, t)
                mx = max(f, t)
                if f != t and not checked.has_key((mn, mx)):
                    checked[(mn, mx)] = self.all_mincost_paths(f, t)

        # sprawdzam zawieranie sie sciezek
        ready_paths = dict()
        for k1, pths1 in checked.iteritems():
            for k2, pths2 in checked.iteritems():
                if k1 != k2 and pths1 != pths2:
                    # w1 = pths1[0]
                    # w2 = pths2[0]
                    for p1 in pths1[1]:
                        for p2 in pths2[1]:
                            s_p = p1
                            s_k = k1
                            l_p = p2
                            l_k = k2
                            if len(p1) > len(p2):
                                s_p = p2
                                s_k = k2
                                l_p = p1
                                l_k = k1
                            # XXX TODO tutaj trzena wywalic warunek ;)
                            if s_p[0] not in l_p or True:
                                if not ready_paths.has_key(s_k):
                                    ready_paths[s_k] = []
                                if not s_p in ready_paths[s_k]:
                                    ready_paths[s_k].append(s_p)

        # sortuje sciezki wg pokrycia sciezek wezlami z grafu
        # te, ktore sa gesciej pokryte, sa wyzej....
        sorted_paths = self._sort_paths_by_nodes_coverage(ready_paths, nodes)
        
        # wybieram z nich tylko wartosci... nie uwzgledniam teraz wag, 
        # bo mam posortowane wg wag zatem robiac sciezke musze sprawdzac 
        # czy moge juz dojsc od wezla "A" do wezla "B" i jestli tak, 
        # to nie dodaje juz aktualnie anallizowanej sciezki
        r_g = []
        for k, p in sorted_paths:
            r_g.append(p.values())
            print k, p
        return self._all_subpaths(r_g)

    def _all_subpaths(self, resg):
        res_ps = []
        for l in resg:
            print l
            for pths in l:
                sub_paths = []
                for i, p in enumerate(pths):
                    sp = sub_path()
                    sp._visited = False
                    sp._p = p
                    sub_paths.append(sp)
                res_ps.append(sub_paths)

        return [None]

    def all_mincost_paths(self, f, t):
        '''Returns list of all minimal cost paths from node @see f
           to node @see t in the graph @see self._g'''
        minpaths = []
        mincost = self._g.number_of_nodes() * \
                  self._g.number_of_nodes()
        for p in nx.all_simple_paths(self._g, f, t):
            pcost = self._path_cost(p)
            if pcost < mincost:
                mincost = pcost
                minpaths = [p]
            elif pcost == mincost:
                minpaths.append(p)
        return [mincost, minpaths]

    def _nodes_weight_sum(self, e):
        '''Helper function which returns sum of weight of given edge'''
        return self._g.node[e[0]]['weight'] + \
               self._g.node[e[1]]['weight']

    def _path_cost(self, path):
        '''Calculate path cost based on the weight of the nodes. 
           The returned value is the sum of the weights of nodes 
           in the given @see path'''
        c = 0.0
        for n in path:
            c += self._g.node[n]['weight']
        return c

    def _sort_paths_by_nodes_coverage(self, paths, nodes):
        '''Returns the dictionary with wp as key and value is the list 
           of path with the wp. Where wp is defined as:
           
                 path size (num. of nodes into the path)
           wp = -----------------------------------------
                  num. of nodes from text into the path
        '''
        s_paths = dict()
        for nds, path in paths.iteritems():
            wp = (len(path[0]) / (0.0 + self._same_nodes(path[0], nodes)))
            # wp = ((0.0 + self._same_nodes(path[0], nodes)) / len(path[0]))
            if not s_paths.has_key(wp):
                s_paths[wp] = dict()
            if not s_paths[wp].has_key(nds):
                s_paths[wp][nds] = []
            s_paths[wp][nds].extend(path)
        s_paths = sorted(s_paths.items(), key=lambda t: t[0])
        return s_paths

    def _same_nodes(self, n1, n2):
        '''Returns number of same nodes in the n1 and n2'''
        c = 0
        for n in n1:
            if n in n2:
                c += 1
        return c

def main():
    # te wezly (pojecia SUMO), ktore wystapily w tekscie
    in_text = ['1', '5', '6', '7',  '8', '12']
    print 'In text', in_text

    # 1. buduje graf G - w domysle z SUMO
    g = SemGraph()
    g.build_graph()

    # 2. inicializuje graf wagami. Wszystkie wezly 
    #    maja wage rowna liczbie wezlow grafu G
    g.weight_all_nodes(1.0 * len(g.G().nodes()))

    # 3. tym wezlom, ktore wystapily w tekscie przypisuje wartosc (wage) 1
    g.modify_nodes_weight(in_text, 1.0)

    # 4. dokonuje wazenia wszystkich krawedzi. Waga krawedzi 
    #    rowna jest sumiw wag wezlow tworzacych dana krawedz
    g.weight_all_edges(g._nodes_weight_sum)

    # #########################################################################
    # print 'in text:', in_text
    # print 'edges  :', g.G().edges(data=True)
    # print 'nodes  :', g.G().nodes(data=True)
    # print(nx.dijkstra_path(g.G(), '1', '12'))
    # print(nx.bidirectional_dijkstra(g.G(), '1', '12')[1])
    # print 50 * '-'
    # print(nx.center(g.G()))
    # print 50 * '-'

    # znajduje wszystkie mozliwe minimalne podgrafy zawierajace pojecia z tekstu
    g_sgraphs = g.all_minimal_subgraphs(in_text)
    for gs in g_sgraphs:
        if not gs:
            continue
        print gs


if __name__ == '__main__':
    main()

exit(1)

print(nx.dijkstra_path(g, '1', '12'))
print(nx.bidirectional_dijkstra(g, '1', '12'))

d = dict()
for i in g.nodes():
    if i in in_text:
        d[i] = 1.0 / len(in_text)
    else:
        d[i] = 0.0
    print d[i]
print nx.pagerank(g, personalization = d)
