graph.pyx 13.5 KB
Newer Older
Fize Jacques's avatar
Fize Jacques committed
1 2 3 4 5 6 7 8 9 10
from libcpp.map cimport map
from libcpp.utility cimport pair
from libcpp.string  cimport string
from libcpp.vector  cimport vector
import numpy as np
cimport numpy as np
import networkx as nx

cdef class Graph:

Fize Jacques's avatar
Fize Jacques committed
11 12 13 14 15 16 17 18
    def __init__(self,G, node_attr_key="",edge_attr_key=""):
        self.nx_g=G

        #GRAPH PROPERTY INIT
        self.is_directed = G.is_directed()
        self.is_multi = G.is_multigraph()
        self.is_node_attr=(True if node_attr_key else False)
        self.is_edge_attr=(True if edge_attr_key else False)
Fize Jacques's avatar
Fize Jacques committed
19
        
Fize Jacques's avatar
Fize Jacques committed
20 21
        if len(G) == 0:
            return
Fize Jacques's avatar
Fize Jacques committed
22
        
Fize Jacques's avatar
Fize Jacques committed
23 24 25 26 27 28 29 30 31 32 33 34 35 36
        a,b=list(zip(*list(G.nodes(data=True))))
        self.nodes_list,self.attr_nodes=list(a),list(b)
        if G.number_of_edges()>0:
            e1,e2,d=zip(*list(G.edges(data=True)))
            self.attr_edges=list(d)
            self.edges_list=list(zip(e1,e2))
        else:
            self.edges_list=[]
            self.attr_edges=[]

        if self.is_node_attr:
            self.node_attr_key = node_attr_key
            self.nodes_attr_list = [attr_dict[node_attr_key] for attr_dict in self.attr_nodes]
            self.unique_node_attr_vals=set(self.nodes_attr_list)
Fize Jacques's avatar
Fize Jacques committed
37
        
Fize Jacques's avatar
Fize Jacques committed
38 39 40 41
        if self.is_edge_attr:
            self.edge_attr_key = edge_attr_key
            self.edges_attr_list = [attr_dict[edge_attr_key] for attr_dict in self.attr_edges]
            self.unique_edge_attr_vals=set(self.edges_attr_list)
Fize Jacques's avatar
Fize Jacques committed
42

Fize Jacques's avatar
Fize Jacques committed
43 44 45 46 47 48 49 50 51 52
        # NODE Information init
        #######################
        
        self.nodes_hash=[self.hash_node_attr(node,self.nodes_attr_list[ix]) if self.is_node_attr else self.hash_node(node) for ix, node in enumerate(self.nodes_list) ]
        self.nodes_hash_set=set(self.nodes_hash)
        self.nodes_idx={node:ix for ix, node in enumerate(self.nodes_list)}
        self.nodes_weight=[attr_dict["weight"] if "weight" in attr_dict else 1 for attr_dict in self.attr_nodes]
        degree_all=[]
        degree_in=[]
        degree_out=[]
Fize Jacques's avatar
Fize Jacques committed
53 54 55 56

        degree_all_weighted=[]
        degree_in_weighted=[]
        degree_out_weighted=[]
Fize Jacques's avatar
Fize Jacques committed
57 58
        if self.is_edge_attr:
            self.degree_per_attr={attr_v:{n:{"in":0,"out":0} for n in self.nodes_list} for attr_v in self.unique_edge_attr_vals}
Fize Jacques's avatar
Fize Jacques committed
59
            self.degree_per_attr_weighted={attr_v:{n:{"in":0,"out":0} for n in self.nodes_list} for attr_v in self.unique_edge_attr_vals}
Fize Jacques's avatar
Fize Jacques committed
60
        # Retrieving Degree Information
61
        self.edges_of_nodes={}
Fize Jacques's avatar
Fize Jacques committed
62
        for n in self.nodes_list:
63
            self.edges_of_nodes[n]=[self.hash_edge_attr(e1,e2,attr_dict[self.edge_attr_key]) if self.is_edge_attr else self.hash_edge(e1,e2) for e1,e2,attr_dict in G.edges(n,data=True)]
Fize Jacques's avatar
Fize Jacques committed
64
            degree_all.append(G.degree(n))
Fize Jacques's avatar
Fize Jacques committed
65
            degree_all_weighted.append(G.degree(n,weight="weight"))
Fize Jacques's avatar
Fize Jacques committed
66 67
            if self.is_directed:
                degree_in.append(G.in_degree(n))
Fize Jacques's avatar
Fize Jacques committed
68
                degree_in_weighted.append(G.in_degree(n,weight="weight"))
Fize Jacques's avatar
Fize Jacques committed
69
                degree_out.append(G.out_degree(n))
Fize Jacques's avatar
Fize Jacques committed
70
                degree_out_weighted.append(G.out_degree(n))
Fize Jacques's avatar
Fize Jacques committed
71 72
            else:
                degree_in.append(degree_all[-1])
Fize Jacques's avatar
Fize Jacques committed
73
                degree_in_weighted.append(degree_all_weighted[-1])
Fize Jacques's avatar
Fize Jacques committed
74
                degree_out.append(degree_all[-1])
Fize Jacques's avatar
Fize Jacques committed
75
                degree_out_weighted.append(degree_all_weighted[-1])
Fize Jacques's avatar
Fize Jacques committed
76 77 78 79 80 81
            if self.is_edge_attr:
                if self.is_directed:
                    in_edge=list(G.in_edges(n,data=True))
                    out_edge=list(G.in_edges(n,data=True))
                    for n1,n2,attr_dict in in_edge:
                        self.degree_per_attr[attr_dict[self.edge_attr_key]][n]["in"]+=1
Fize Jacques's avatar
Fize Jacques committed
82
                        self.degree_per_attr_weighted[attr_dict[self.edge_attr_key]][n]["in"]+=1*(attr_dict["weight"] if "weight" in attr_dict else 1 )
Fize Jacques's avatar
Fize Jacques committed
83 84 85
        
                    for n1,n2,attr_dict in out_edge:
                        self.degree_per_attr[attr_dict[self.edge_attr_key]][n]["out"]+=1
Fize Jacques's avatar
Fize Jacques committed
86
                        self.degree_per_attr_weighted[attr_dict[self.edge_attr_key]][n]["out"]+=1*(attr_dict["weight"] if "weight" in attr_dict else 1 )
Fize Jacques's avatar
Fize Jacques committed
87 88 89 90 91 92
    
                else:
                    edges=G.edges(n,data=True)
                    for n1,n2,attr_dict in edges:
                        self.degree_per_attr[attr_dict[self.edge_attr_key]][n]["in"]+=1
                        self.degree_per_attr[attr_dict[self.edge_attr_key]][n]["out"]+=1
Fize Jacques's avatar
Fize Jacques committed
93 94 95
                        self.degree_per_attr_weighted[attr_dict[self.edge_attr_key]][n]["in"]+=1*(attr_dict["weight"] if "weight" in attr_dict else 1 )
                        self.degree_per_attr_weighted[attr_dict[self.edge_attr_key]][n]["out"]+=1*(attr_dict["weight"] if "weight" in attr_dict else 1 )
        
Fize Jacques's avatar
Fize Jacques committed
96 97 98 99 100
        
        self.nodes_degree=np.array(degree_all)
        self.nodes_degree_in=np.array(degree_in)
        self.nodes_degree_out=np.array(degree_out)

Fize Jacques's avatar
Fize Jacques committed
101 102 103 104
        self.nodes_degree_weighted=np.array(degree_all_weighted)
        self.nodes_degree_in_weighted=np.array(degree_in_weighted)
        self.nodes_degree_out_weighted=np.array(degree_out_weighted)

Fize Jacques's avatar
Fize Jacques committed
105 106 107 108 109
        # EDGE INFO INIT
        #################
        
        self.edges_hash=[]
        self.edges_hash_map = {}
Fize Jacques's avatar
Fize Jacques committed
110
        self.edges_hash_idx = {}
Fize Jacques's avatar
Fize Jacques committed
111 112 113
        for ix, ed in enumerate(self.edges_list):
            e1,e2=ed
            if not e1 in self.edges_hash_map:self.edges_hash_map[e1]={}
Fize Jacques's avatar
Fize Jacques committed
114 115
            
            hash_=self.hash_edge_attr(e1,e2,self.edges_attr_list[ix]) if self.is_edge_attr else self.hash_edge(e1,e2)
Fize Jacques's avatar
Fize Jacques committed
116
            if self.is_multi and self.is_edge_attr:
Fize Jacques's avatar
Fize Jacques committed
117 118 119 120 121 122
                if not e2 in self.edges_hash_map[e1]:self.edges_hash_map[e1][e2]={}
                self.edges_hash_map[e1][e2][self.edges_attr_list[ix]]=hash_
            else:
                self.edges_hash_map[e1][e2]=hash_
            self.edges_hash_idx[hash_]=ix 
            self.edges_hash.append(hash_) 
Fize Jacques's avatar
Fize Jacques committed
123
        self.edges_hash_set=set(self.edges_hash)
Fize Jacques's avatar
Fize Jacques committed
124

Fize Jacques's avatar
Fize Jacques committed
125 126
        self.edges_weight={}
        for e1,e2,attr_dict in list(G.edges(data=True)):
Fize Jacques's avatar
Fize Jacques committed
127
            print(e1,e2,attr_dict)
Fize Jacques's avatar
Fize Jacques committed
128 129
            hash_=self.hash_edge_attr(e1,e2,attr_dict[self.edge_attr_key]) if self.is_edge_attr else self.hash_edge(e1,e2)
            self.edges_weight[hash_]=attr_dict["weight"] if "weight" in attr_dict else 1 
Fize Jacques's avatar
Fize Jacques committed
130 131 132 133
        
        self.number_of_edges = len(self.edges_list)
        self.number_of_nodes = len(self.nodes_list)
        
Fize Jacques's avatar
Fize Jacques committed
134 135 136 137 138 139 140 141 142
        if self.is_edge_attr and self.number_of_edges >0:
            self.number_of_edges_per_attr={attr:0 for attr in self.unique_edge_attr_vals}
            for _,_,attr_dict in list(G.edges(data=True)):
                self.number_of_edges_per_attr[attr_dict[self.edge_attr_key]]+=1
        
        if self.is_node_attr and self.number_of_nodes >0:
            self.number_of_nodes_per_attr={attr:0 for attr in self.unique_node_attr_vals}
            for _,attr_dict in list(G.nodes(data=True)):
                self.number_of_nodes_per_attr[attr_dict[self.node_attr_key]]+=1
Fize Jacques's avatar
Fize Jacques committed
143 144

    
Fize Jacques's avatar
Fize Jacques committed
145 146 147 148 149
    # HASH FUNCTION
    cpdef str hash_node(self,str n1):
        return "{0}".format(n1)

    cpdef str hash_edge(self,str n1,str n2):
Fize Jacques's avatar
Fize Jacques committed
150
        return "_".join(sorted([n1,n2]))
Fize Jacques's avatar
Fize Jacques committed
151 152 153 154 155 156

    cpdef str hash_node_attr(self,str n1, str attr_value):
        return "_".join(sorted([n1,attr_value]))

    cpdef str hash_edge_attr(self,str n1,str n2, str attr_value):
        return "_".join([n1,n2,attr_value])
Fize Jacques's avatar
Fize Jacques committed
157 158
    
    ## EXIST FUNCTION
Fize Jacques's avatar
Fize Jacques committed
159
    cpdef bint has_node(self,str n_id):
Fize Jacques's avatar
Fize Jacques committed
160 161 162 163
        if n_id in self.nodes_list:
            return True
        return False

Fize Jacques's avatar
Fize Jacques committed
164
    cpdef bint has_edge(self,str n_id1,str n_id2):
Fize Jacques's avatar
Fize Jacques committed
165
        if self.is_directed:
166
            if n_id1 in self.edges_hash_map and n_id2 in self.edges_hash_map[n_id1]:
Fize Jacques's avatar
Fize Jacques committed
167 168
                return True
        else:
169
            if n_id1 in self.edges_hash_map and n_id2 in self.edges_hash_map[n_id1]:
Fize Jacques's avatar
Fize Jacques committed
170
                return True
171
            if n_id2 in self.edges_hash_map and n_id1 in self.edges_hash_map[n_id2]:
Fize Jacques's avatar
Fize Jacques committed
172 173
                return True
        return False
Fize Jacques's avatar
Fize Jacques committed
174 175

    ## LEN FUNCTION
Fize Jacques's avatar
Fize Jacques committed
176
    cpdef int size_node_intersect(self,Graph G):
Fize Jacques's avatar
Fize Jacques committed
177
        return len(self.nodes_hash_set.intersection(G.nodes_hash_set))
Fize Jacques's avatar
Fize Jacques committed
178
    cpdef int size_node_union(self,Graph G):
Fize Jacques's avatar
Fize Jacques committed
179
        return len(self.nodes_hash_set.union(G.nodes_hash_set))
Fize Jacques's avatar
Fize Jacques committed
180 181
    
    cpdef int size_edge_intersect(self,Graph G):
Fize Jacques's avatar
Fize Jacques committed
182
        return len(self.edges_hash_set.intersection(G.edges_hash_set))
Fize Jacques's avatar
Fize Jacques committed
183
    cpdef int size_edge_union(self,Graph G):
Fize Jacques's avatar
Fize Jacques committed
184 185 186
        return len(self.edges_hash_set.union(G.edges_hash_set))
    
        ## GETTER
Fize Jacques's avatar
Fize Jacques committed
187 188 189 190
    
    def get_nx(self):
        return self.nx_g

Fize Jacques's avatar
Fize Jacques committed
191 192
    def nodes(self,data=False):
        if data:
Fize Jacques's avatar
Fize Jacques committed
193
            return self.nodes_list,self.attr_nodes
Fize Jacques's avatar
Fize Jacques committed
194 195 196 197 198 199
        else:
            return self.nodes_list
        
    
    def edges(self,data=False):
        if data:
Fize Jacques's avatar
Fize Jacques committed
200
            return self.edges_list,self.attr_edges
Fize Jacques's avatar
Fize Jacques committed
201 202
        else:
            return self.edges_list
Fize Jacques's avatar
Fize Jacques committed
203
    
204
    cpdef list get_edges_ed(self,str e1,str e2):
Fize Jacques's avatar
Fize Jacques committed
205 206 207 208 209
        if self.is_edge_attr:
            hashes=self.edges_hash_map[e1][e2]
            return [(e1,e2,self.edges_attr_list[self.edges_hash_idx[hash_]])for hash_ in hashes]
        else:
            return [(e1,e2,None)]
210
            
211 212
    cpdef list get_edges_no(self,str n):
        return self.edges_of_nodes[n]
Fize Jacques's avatar
Fize Jacques committed
213

Fize Jacques's avatar
Fize Jacques committed
214 215 216 217 218 219 220 221 222 223 224
    cpdef dict get_edge_attr(self,edge_hash):
        return self.edges_attr_list[self.edges_hash_idx[edge_hash]]
    
    cpdef dict get_node_attr(self, node_hash):
        return self.edges_attr_list[self.edges_hash_idx[node_hash]]

    cpdef dict get_edge_attrs(self,edge_hash):
        return self.attr_edges[self.edges_hash_idx[edge_hash]]
    
    cpdef dict get_node_attrs(self, node_hash):
        return self.attr_nodes[self.edges_hash_idx[node_hash]]
Fize Jacques's avatar
Fize Jacques committed
225

Fize Jacques's avatar
Fize Jacques committed
226 227 228
    cpdef set get_edges_hash(self):
        return self.edges_hash_set

Fize Jacques's avatar
Fize Jacques committed
229 230 231 232 233 234 235 236 237 238
    cpdef set get_nodes_hash(self):
        return self.nodes_hash_set

    cpdef str get_node_key(self):
        return self.node_attr_key
        
    cpdef str get_egde_key(self):
        return self.edge_attr_key
    #####

Fize Jacques's avatar
Fize Jacques committed
239
    cpdef long size(self):
Fize Jacques's avatar
Fize Jacques committed
240
        return self.number_of_nodes
Fize Jacques's avatar
Fize Jacques committed
241 242 243
    
    cpdef int size_attr(self, attr_val):
        return self.number_of_nodes_per_attr[attr_val]
Fize Jacques's avatar
Fize Jacques committed
244

Fize Jacques's avatar
Fize Jacques committed
245
    cpdef long density(self):
Fize Jacques's avatar
Fize Jacques committed
246
        return self.number_of_edges
Fize Jacques's avatar
Fize Jacques committed
247 248 249
    
    cpdef int density_attr(self, str attr_val):
        return self.number_of_edges_per_attr[attr_val]
Fize Jacques's avatar
Fize Jacques committed
250

Fize Jacques's avatar
Fize Jacques committed
251 252 253
    cpdef int degree(self,str n_id, bint weight=False):
        if weight:
            return self.nodes_degree_weighted[self.nodes_idx[n_id]]
Fize Jacques's avatar
Fize Jacques committed
254
        return self.nodes_degree[self.nodes_idx[n_id]]
Fize Jacques's avatar
Fize Jacques committed
255
    
Fize Jacques's avatar
Fize Jacques committed
256 257 258
    cpdef int in_degree(self,str n_id, bint weight=False):
        if weight:
            return self.nodes_degree_in_weighted[self.nodes_idx[n_id]]
Fize Jacques's avatar
Fize Jacques committed
259 260
        return self.nodes_degree_in[self.nodes_idx[n_id]]
    
Fize Jacques's avatar
Fize Jacques committed
261 262 263
    cpdef int out_degree(self,str n_id, bint weight=False):
        if weight:
            return self.nodes_degree_out_weighted[self.nodes_idx[n_id]]
Fize Jacques's avatar
Fize Jacques committed
264 265
        return self.nodes_degree_out[self.nodes_idx[n_id]]

Fize Jacques's avatar
Fize Jacques committed
266
    cpdef int in_degree_attr(self,str n_id,str attr_val, bint weight=False):
Fize Jacques's avatar
Fize Jacques committed
267 268
        if not self.is_edge_attr and not self.is_directed:
            raise AttributeError("No edge attribute have been defined")
Fize Jacques's avatar
Fize Jacques committed
269 270
        if weight:
            return self.degree_per_attr_weighted[attr_val][n_id]["in"]
Fize Jacques's avatar
Fize Jacques committed
271 272
        return self.degree_per_attr[attr_val][n_id]["in"]

Fize Jacques's avatar
Fize Jacques committed
273
    cpdef int out_degree_attr(self,str n_id,str attr_val, bint weight=False):
Fize Jacques's avatar
Fize Jacques committed
274 275
        if not self.is_edge_attr and not self.is_directed:
            raise AttributeError("No edge attribute have been defined")
Fize Jacques's avatar
Fize Jacques committed
276 277
        if weight:
            return self.degree_per_attr_weighted[attr_val][n_id]["out"]
Fize Jacques's avatar
Fize Jacques committed
278 279
        return self.degree_per_attr[attr_val][n_id]["out"]

Fize Jacques's avatar
Fize Jacques committed
280
    cpdef int degree_attr(self,str n_id,str attr_val, bint weight=False):
Fize Jacques's avatar
Fize Jacques committed
281 282
        if not self.is_edge_attr:
            raise AttributeError("No edge attribute have been defined")
Fize Jacques's avatar
Fize Jacques committed
283 284 285 286 287 288
        if not self.is_directed:
            if weight:
                return self.degree_per_attr_weighted[attr_val][n_id]["out"]
            return self.degree_per_attr[attr_val][n_id]["out"]
        if weight:
            return self.degree_per_attr_weighted[attr_val][n_id]["in"] + self.degree_per_attr_weighted[attr_val][n_id]["out"]
Fize Jacques's avatar
Fize Jacques committed
289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337
        return self.degree_per_attr[attr_val][n_id]["out"] + self.degree_per_attr[attr_val][n_id]["in"]
    
    #GRAPH SETTER
    def add_node(self,str id_,**kwargs):
        if not self.node_attr_key in kwargs:
            print("Node not added because information lacks")
            return self
        if id_ in self.nodes_idx:
            print("Already in G")
            return self
        G=self.nx_g.copy()
        G.add_node(id_,**kwargs)
        return Graph(G,self.node_attr_key,self.edge_attr_key)
    
    
    def add_edge(self,str n1,str n2,**kwargs):
        G=self.nx_g.copy()
        G.add_edge(n1,n2,**kwargs)
        return Graph(G,self.node_attr_key,self.edge_attr_key)
    
    def remove_node(self,str id_):
        if not id_ in self.nodes_idx:
            print("Already removed in G")
            return self
        G=self.nx_g.copy()
        G.remove_node(id_)
        return Graph(G,self.node_attr_key,self.edge_attr_key)
    
    def remove_edge(self,str n1,str n2,**kwargs):
        G=self.nx_g.copy()
        edges=G.edges([n1,n2],data=True)
        if len(edges) == 0:
            return self
        elif len(edges)<2:
            G.remove_edge(n1,n2)
        else:
            if not self.edge_attr_key in kwargs:
                for i in range(len(edges)):
                    G.remove_edge(n1,n2,i)
            else:
                key,val,i=self.edge_attr_key, kwargs[self.edge_attr_key],0
                for e1,ed2,attr_dict in edges:
                    if attr_dict[key] == val:
                        G.remove_edge(n1,n2,i)
                        break
                    i+=1
                    
        return Graph(G,self.node_attr_key,self.edge_attr_key)

338