CompleteRecursiveClustering_v1.py

# Updated 21-Mar-2018 14:27
import sys
import json
import random
import networkx as nx
import time

def clustering(M,n,m):

    # Set recursion limit
    sys.setrecursionlimit(m)

    row=[0 for i in range(n)]
    col=[0 for i in range(n)]

    clusters=[]
    C=[]

    for i in range(n):
        inspect_row(i,M,C,row,col)

        if (len(C) is not 0):
            clusters.append(C)
            C=[]
    return clusters

def inspect_row(i,M,C,row,col,jj=None):

    #scroll row
    for j in range(row[i],len(M)):
        if j!=jj:
            #print (i,j)
            #print " ",M[i][j]
            if M[i][j]==1:
                row[i]=j+1
                C.append((i,j))
                M[i][j]=0
                #scroll column
                for ii in range(col[j],len(M)):
                    if ii!=i:
                        #print (ii,j)
                        if M[ii][j]==1:
                            col[j]=ii+1
                            C.append((ii,j))
                            M[ii][j]=0
                            inspect_row(ii,M,C,row,col,j)

def my_has_path(G, source, target):

    try:
        sp = nx.shortest_path(G, source, target)
    except nx.NetworkXNoPath:
        return []
    return sp

def myeccentricity(G, v=None, sp=None):

    order=G.order()

    e={}
    for n in G.nbunch_iter(v):
        if sp is None:
            length=nx.single_source_shortest_path_length(G,n)
            L = len(length)
        else:
            try:
                length=sp[n]
                L = len(length)
            except TypeError:
                raise nx.NetworkXError('Format of "sp" is invalid.')

        e[n]=max(length.values())

    if v in G:
        return e[v]
    else:
        return e

def mydiameter(G, e=None):

    if e is None:
        e=myeccentricity(G)
    return max(e.values())


if __name__ == "__main__":

    try:
        # Sanity check
        if len(sys.argv)!=3:
            sys.stderr.write("usage: %s graphml_file [sampling_rate] [monitored nodes list]\n"%sys.argv[0])
            exit()

        try:
            # Rate
            rate=int(sys.argv[2])

            if rate<0 or rate>100:
                sys.stderr.write("Sampling rate must be [0,100]\n")
                exit()

        except ValueError:
            # List of monitored nodes
            rate=-1
            try:
                input_list=json.loads(sys.argv[2])
            except ValueError:
                sys.stderr.write("Wrong list format")
                exit()

        # Import graph
        graph=nx.read_graphml(sys.argv[1],str)

        print("Graph %s has %d physical nodes with %d physical edges"
              % (graph.name, nx.number_of_nodes(graph), nx.number_of_edges(graph)))

        n_nodes=nx.number_of_nodes(graph)
        n_edges=nx.number_of_edges(graph)

        # Adapt to networkx version
        if float(nx.__version__)>=2.0:
            edges_iter=graph.edges
            nodes_iter=graph.nodes
        else:
            edges_iter=graph.edges_iter
            nodes_iter=graph.nodes_iter

        # Node labels
        geolabels=['' for i in range(n_nodes)]
        for node in nodes_iter(data=True):
            geolabels[int(node[0])]=node[1]['label']

        # Setup input and output interfaces
        # Setup external links
        in_interfaces={}
        out_interfaces={}
        Enodes=[]
        Eedges=[]
        n=0

        for edge in edges_iter(data=True):
            x=int(edge[0])
            y=int(edge[1])

            if x not in out_interfaces:
                out_interfaces[x]={}
            if y not in out_interfaces:
                out_interfaces[y]={}
            if x not in in_interfaces:
                in_interfaces[x]={}
            if y not in in_interfaces:
                in_interfaces[y]={}

            n0=(n,x,y,"out")
            n1=(n+1,y,x,"out")
            n2=(n+2,x,y,"in")
            n3=(n+3,y,x,"in")
            out_interfaces[x][y]=n0
            out_interfaces[y][x]=n1
            in_interfaces[x][y]=n2
            in_interfaces[y][x]=n3
            Enodes.extend([n0,n1,n2,n3])
            Eedges.extend([(n0,n3),(n1,n2)])
            n+=4

        # Setup internal links
        for node in in_interfaces:
            for intf1 in in_interfaces[node]:
                in_intf=in_interfaces[node][intf1]
                for intf2 in out_interfaces[node]:
                    out_intf=out_interfaces[node][intf2]
                    Eedges.append((in_intf,out_intf))

        # Extended graph
        extended_graph=nx.DiGraph()
        extended_graph.add_nodes_from(Enodes)
        extended_graph.add_edges_from(Eedges)

        print ("Extended graph: %d nodes, %d edges" %(len(Enodes),len(Eedges)))

        # Set seed for reproducibility
        #random.seed(0)

        if (rate>=0):
            Mnodes = random.sample(Enodes,((len(Enodes)*rate)/100))
        else:
            Mnodes = []
            for e in Enodes:
                for i in input_list:
                    if i[0]==e[1] and i[1]==e[2] and i[2]==e[3]:
                        Mnodes.append(e)

        #print "Mnodes",Mnodes

        # Monitored graph
        monitored_graph=nx.DiGraph()
        monitored_graph.add_nodes_from(Mnodes)

        find_monitored_edges_start = time.time()
        # Save all the links in the extended graph
        # with a monitored node as one extremity
        links_to_mnodes={}

        for edge in extended_graph.edges():
        #for edge in extended_graph.edges_iter(): # nx version < 2.0
            if edge[0] in Mnodes: 

                if edge[0] not in links_to_mnodes:
                    links_to_mnodes[edge[0]]={"in":[],"out":[]}

                links_to_mnodes[edge[0]]["out"].append(edge)

            if edge[1] in Mnodes:

                if edge[1] not in links_to_mnodes:
                    links_to_mnodes[edge[1]]={"in":[],"out":[]}

                links_to_mnodes[edge[1]]["in"].append(edge)

        # Remove from the Extended graph all to monitored nodes
        extended_graph.remove_nodes_from(Mnodes)

        # Add edges to the monitored graph
        MEdges_to_EPath={}
        for n in monitored_graph.nodes():
            for d in monitored_graph.nodes():

                if(n!=d):

                    # Add the 2 monitored nodes to the pruned extended graph
                    extended_graph.add_node(n)
                    extended_graph.add_node(d)

                    for link in links_to_mnodes[n]["in"]:
                        if link[0] not in Mnodes or link[0]==d:
                            extended_graph.add_edge(link[0],link[1])

                    for link in links_to_mnodes[n]["out"]:
                        if link[1] not in Mnodes or link[1]==d:
                            extended_graph.add_edge(link[0],link[1])

                    for link in links_to_mnodes[d]["in"]:
                        if link[0] not in Mnodes or link[0]==n:
                            extended_graph.add_edge(link[0],link[1])

                    for link in links_to_mnodes[d]["out"]:
                        if link[1] not in Mnodes or link[1]==n:
                            extended_graph.add_edge(link[0],link[1])

                    path= my_has_path(extended_graph,n,d)

                    if (len(path)>0):

                        monitored_graph.add_edge(n,d)
                        MEdges_to_EPath[(n[0],d[0])]=path

                    extended_graph.remove_node(n)
                    extended_graph.remove_node(d)

        find_monitored_edges_time = time.time() - find_monitored_edges_start
        print "Time to find edges in the monitored network: "+str(find_monitored_edges_time)+" sec."

        print ("Monitored graph: %d nodes, %d edges"
              %(len(monitored_graph.nodes()),len(monitored_graph.edges())))
        
        # Extended graph node index -> Monitored graph node with incremental index
        # (because the clustering algorithm needs an incremental node)
        extended_to_monitored={}
        monitored_to_extended={}
        i=0
        for old_node in Mnodes:
            extended_to_monitored[old_node[0]]=i
            monitored_to_extended[i]=old_node
            i+=1

        incremental_edges=[]
        for edge in monitored_graph.edges():
            incremental_edges.append((extended_to_monitored[edge[0][0]],extended_to_monitored[edge[1][0]]))

        # Build adjacency matrix
        M=[[0 for i in range(len(monitored_graph.nodes()))] for k in range(len(monitored_graph.nodes()))]

        for edge in incremental_edges:
            M[edge[0]][edge[1]]=1

        # Clustering
        clustering_start = time.time()
        clusters=clustering(M, len(monitored_graph.nodes()),len(incremental_edges))
        clustering_time = time.time()-clustering_start
        print "Clustering time: "+str(clustering_time)+" sec."

        # Dump clusters
        dump=[]

        for cl in clusters:
            labeled_cl=[]
            raw_cl=[]
            for edge in cl:
                src=monitored_to_extended[edge[0]]
                dst=monitored_to_extended[edge[1]]

                src_label="%s-%s-%s"%(geolabels[src[1]],geolabels[src[2]],src[3])
                dst_label="%s-%s-%s"%(geolabels[dst[1]],geolabels[dst[2]],dst[3])
                labeled_cl.append("(%s,%s),"%(src_label,dst_label))
                raw_cl.append((src,dst))
            dump.append({"raw":raw_cl,"labeled":labeled_cl,"size":len(cl)})

        nx.write_graphml(monitored_graph, "Monitored.graphml")

        with open('clusters.json', 'w') as cfile:
            json.dump(dump, cfile, indent=4)

        print "Clusters: %d"%len(clusters)

        # Get Stats

        # Compute Diameter for Extended Graph and Monitored Graph

        cluster_id=0
        info_clusters=[]

        for clu in clusters:
            info_cluster={}
            #print "Cluster : ",clu,"Len : ",len(clu)
            info_cluster['id']=cluster_id
            Edges_cluster_ext=[]
            Edges_cluster=[]
            All_paths=[]

            for edg in clu:
                Edges_cluster.append(edg)

                src_idx=monitored_to_extended[edg[0]][0]
                dst_idx=monitored_to_extended[edg[1]][0]

                Edges_cluster_ext.append( (src_idx,dst_idx) )

                path = MEdges_to_EPath [ (src_idx,dst_idx) ]
                All_paths.append(path)

            # Build cluster extended graph
            cluster_extended_graph=nx.DiGraph()
            for path in All_paths:
                cluster_extended_graph.add_path(path)

            print ("Cluster in the Extended  Graph: %d nodes, %d edges"
              %(len(cluster_extended_graph.nodes()),len(cluster_extended_graph.edges())))

            info_cluster['num_extended_nodes']=len(cluster_extended_graph.nodes())
            info_cluster['num_extended_edges']=len(cluster_extended_graph.edges())

            diameter1  = mydiameter(cluster_extended_graph)
            print 'Diameter in the Extended Graph : ', diameter1
            info_cluster['extended_diameter']=diameter1

            # Build cluster monitored graph
            cluster_monitored_graph=nx.DiGraph()
            cluster_monitored_graph.add_edges_from(Edges_cluster)

            print ("Cluster in the Monitored Graph: %d nodes, %d edges"
              %(len(cluster_monitored_graph.nodes()),len(cluster_monitored_graph.edges())))

            info_cluster['num_monitored_nodes']=len(cluster_monitored_graph.nodes())
            info_cluster['num_monitored_edges']=len(cluster_monitored_graph.edges())

            diameter2  = mydiameter(cluster_monitored_graph)
            print 'Diameter in the Monitored Graph : ', diameter2
            info_cluster['monitored_diameter']=diameter2

            print "Dictionary of Cluster: ",info_cluster
            info_clusters.append(info_cluster)

            # DEBUG
            if len(cluster_extended_graph.nodes()) < len(cluster_monitored_graph.nodes()):
                sys.stderr.write("All_paths : %s\n\n"%All_paths)
                print "---- ERROR ----"
                sys.stderr.write("Edge_cluster : %s\n\n"%Edges_cluster)
                sys.stderr.write("Monitored to EXt : %s\n\n"%monitored_to_extended)
                sys.stderr.write("Ext to Monit : %s\n\n"%extended_to_monitored)
                sys.stderr.write("-----EDges M: %s\n\n"%cluster_monitored_graph.edges())
                sys.stderr.write("-----EDges E: %s\n\n"%cluster_extended_graph.edges())


            cluster_id+=1


        #print "Informations about Clusters: ",info_clusters
        data=[]
        
          
        if type(sys.argv[2]) is int:{

            data.append({"topology":str(sys.argv[1]),"rate":int(sys.argv[2]),"num_clusters":len(clusters),"info_clusters":info_clusters,"Monitored_graph_nodes":len(monitored_graph.nodes()),"Monitored_graph_edges":len(monitored_graph.edges()),"Extended_graph_nodes":len(Enodes),"Extended_graph_edges":len(Eedges),"Monitored_edges_time":find_monitored_edges_time,"Clustering_time":clustering_time})
        }
        elif type(sys.argv[2]) is str: {
            data.append({"topology":str(sys.argv[1]),"nodes":str(sys.argv[2]),"num_clusters":len(clusters),"info_clusters":info_clusters,"Monitored_graph_nodes":len(monitored_graph.nodes()),"Monitored_graph_edges":len(monitored_graph.edges()),"Extended_graph_nodes":len(Enodes),"Extended_graph_edges":len(Eedges),"Monitored_edges_time":find_monitored_edges_time,"Clustering_time":clustering_time})

          }  

        with open('totclusters.json', 'w') as tcfile:
            json.dump(data, tcfile, indent=4)

    except RuntimeError as e:
        sys.stderr.write(str(e)+"\n")
        exit(1)