|
0
|
1 // File: graph_binary.cpp
|
|
|
2 // -- graph handling source
|
|
|
3 //-----------------------------------------------------------------------------
|
|
|
4 // Community detection
|
|
|
5 // Based on the article "Fast unfolding of community hierarchies in large networks"
|
|
|
6 // Copyright (C) 2008 V. Blondel, J.-L. Guillaume, R. Lambiotte, E. Lefebvre
|
|
|
7 //
|
|
|
8 // This program must not be distributed without agreement of the above mentionned authors.
|
|
|
9 //-----------------------------------------------------------------------------
|
|
|
10 // Author : E. Lefebvre, adapted by J.-L. Guillaume
|
|
|
11 // Email : jean-loup.guillaume@lip6.fr
|
|
|
12 // Location : Paris, France
|
|
|
13 // Time : February 2008
|
|
|
14 //-----------------------------------------------------------------------------
|
|
|
15 // see readme.txt for more details
|
|
|
16
|
|
|
17 #include <sys/mman.h>
|
|
|
18 #include <fstream>
|
|
|
19 #include "graph_binary.h"
|
|
|
20 #include "math.h"
|
|
|
21
|
|
|
22 Graph::Graph() {
|
|
|
23 nb_nodes = 0;
|
|
|
24 nb_links = 0;
|
|
|
25 total_weight = 0;
|
|
|
26 }
|
|
|
27
|
|
|
28 Graph::Graph(char *filename, char *filename_w, int type) {
|
|
|
29 ifstream finput;
|
|
|
30 finput.open(filename,fstream::in | fstream::binary);
|
|
|
31
|
|
|
32 // Read number of nodes on 4 bytes
|
|
|
33 finput.read((char *)&nb_nodes, 4);
|
|
|
34 assert(finput.rdstate() == ios::goodbit);
|
|
|
35
|
|
|
36 // Read cumulative degree sequence: 8 bytes for each node
|
|
|
37 // cum_degree[0]=degree(0); cum_degree[1]=degree(0)+degree(1), etc.
|
|
|
38 degrees.resize(nb_nodes);
|
|
|
39 finput.read((char *)°rees[0], nb_nodes*8);
|
|
|
40
|
|
|
41 // Read links: 4 bytes for each link (each link is counted twice)
|
|
|
42 nb_links=degrees[nb_nodes-1];
|
|
|
43 links.resize(nb_links);
|
|
|
44 finput.read((char *)(&links[0]), (long)nb_links*4);
|
|
|
45
|
|
|
46 // IF WEIGHTED : read weights: 4 bytes for each link (each link is counted twice)
|
|
|
47 weights.resize(0);
|
|
|
48 total_weight=0;
|
|
|
49 if (type==WEIGHTED) {
|
|
|
50 ifstream finput_w;
|
|
|
51 finput_w.open(filename_w,fstream::in | fstream::binary);
|
|
|
52 weights.resize(nb_links);
|
|
|
53 finput_w.read((char *)&weights[0], (long)nb_links*4);
|
|
|
54 }
|
|
|
55
|
|
|
56 // Compute total weight
|
|
|
57 for (unsigned int i=0 ; i<nb_nodes ; i++) {
|
|
|
58 total_weight += (double)weighted_degree(i);
|
|
|
59 }
|
|
|
60 }
|
|
|
61
|
|
|
62 Graph::Graph(int n, int m, double t, int *d, int *l, float *w) {
|
|
|
63 /* nb_nodes = n;
|
|
|
64 nb_links = m;
|
|
|
65 total_weight = t;
|
|
|
66 degrees = d;
|
|
|
67 links = l;
|
|
|
68 weights = w;*/
|
|
|
69 }
|
|
|
70
|
|
|
71
|
|
|
72 void
|
|
|
73 Graph::display() {
|
|
|
74 /* for (unsigned int node=0 ; node<nb_nodes ; node++) {
|
|
|
75 pair<vector<unsigned int>::iterator, vector<float>::iterator > p = neighbors(node);
|
|
|
76 for (unsigned int i=0 ; i<nb_neighbors(node) ; i++) {
|
|
|
77 if (node<=*(p.first+i)) {
|
|
|
78 if (weights.size()!=0)
|
|
|
79 cout << node << " " << *(p.first+i) << " " << *(p.second+i) << endl;
|
|
|
80 else
|
|
|
81 cout << node << " " << *(p.first+i) << endl;
|
|
|
82 }
|
|
|
83 }
|
|
|
84 }*/
|
|
|
85 for (unsigned int node=0 ; node<nb_nodes ; node++) {
|
|
|
86 pair<vector<unsigned int>::iterator, vector<float>::iterator > p = neighbors(node);
|
|
|
87 cout << node << ":" ;
|
|
|
88 for (unsigned int i=0 ; i<nb_neighbors(node) ; i++) {
|
|
|
89 if (true) {
|
|
|
90 if (weights.size()!=0)
|
|
|
91 cout << " (" << *(p.first+i) << " " << *(p.second+i) << ")";
|
|
|
92 else
|
|
|
93 cout << " " << *(p.first+i);
|
|
|
94 }
|
|
|
95 }
|
|
|
96 cout << endl;
|
|
|
97 }
|
|
|
98 }
|
|
|
99
|
|
|
100 void
|
|
|
101 Graph::display_reverse() {
|
|
|
102 for (unsigned int node=0 ; node<nb_nodes ; node++) {
|
|
|
103 pair<vector<unsigned int>::iterator, vector<float>::iterator > p = neighbors(node);
|
|
|
104 for (unsigned int i=0 ; i<nb_neighbors(node) ; i++) {
|
|
|
105 if (node>*(p.first+i)) {
|
|
|
106 if (weights.size()!=0)
|
|
|
107 cout << *(p.first+i) << " " << node << " " << *(p.second+i) << endl;
|
|
|
108 else
|
|
|
109 cout << *(p.first+i) << " " << node << endl;
|
|
|
110 }
|
|
|
111 }
|
|
|
112 }
|
|
|
113 }
|
|
|
114
|
|
|
115
|
|
|
116 bool
|
|
|
117 Graph::check_symmetry() {
|
|
|
118 int error=0;
|
|
|
119 for (unsigned int node=0 ; node<nb_nodes ; node++) {
|
|
|
120 pair<vector<unsigned int>::iterator, vector<float>::iterator > p = neighbors(node);
|
|
|
121 for (unsigned int i=0 ; i<nb_neighbors(node) ; i++) {
|
|
|
122 unsigned int neigh = *(p.first+i);
|
|
|
123 float weight = *(p.second+i);
|
|
|
124
|
|
|
125 pair<vector<unsigned int>::iterator, vector<float>::iterator > p_neigh = neighbors(neigh);
|
|
|
126 for (unsigned int j=0 ; j<nb_neighbors(neigh) ; j++) {
|
|
|
127 unsigned int neigh_neigh = *(p_neigh.first+j);
|
|
|
128 float neigh_weight = *(p_neigh.second+j);
|
|
|
129
|
|
|
130 if (node==neigh_neigh && weight!=neigh_weight) {
|
|
|
131 cout << node << " " << neigh << " " << weight << " " << neigh_weight << endl;
|
|
|
132 if (error++==10)
|
|
|
133 exit(0);
|
|
|
134 }
|
|
|
135 }
|
|
|
136 }
|
|
|
137 }
|
|
|
138 return (error==0);
|
|
|
139 }
|
|
|
140
|
|
|
141
|
|
|
142 void
|
|
|
143 Graph::display_binary(char *outfile) {
|
|
|
144 ofstream foutput;
|
|
|
145 foutput.open(outfile ,fstream::out | fstream::binary);
|
|
|
146
|
|
|
147 foutput.write((char *)(&nb_nodes),4);
|
|
|
148 foutput.write((char *)(°rees[0]),4*nb_nodes);
|
|
|
149 foutput.write((char *)(&links[0]),8*nb_links);
|
|
|
150 }
|
