|
0
|
1 // File: graph.cpp
|
|
|
2 // -- simple graph handling source file
|
|
|
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 "graph.h"
|
|
|
18
|
|
|
19 using namespace std;
|
|
|
20
|
|
|
21 Graph::Graph(char *filename, int type) {
|
|
|
22 ifstream finput;
|
|
|
23 finput.open(filename,fstream::in);
|
|
|
24
|
|
|
25 int nb_links=0;
|
|
|
26
|
|
|
27 while (!finput.eof()) {
|
|
|
28 unsigned int src, dest;
|
|
|
29 double weight=1.;
|
|
|
30
|
|
|
31 if (type==WEIGHTED) {
|
|
|
32 finput >> src >> dest >> weight;
|
|
|
33 } else {
|
|
|
34 finput >> src >> dest;
|
|
|
35 }
|
|
|
36
|
|
|
37 if (finput) {
|
|
|
38 if (links.size()<=max(src,dest)+1) {
|
|
|
39 links.resize(max(src,dest)+1);
|
|
|
40 }
|
|
|
41
|
|
|
42 links[src].push_back(make_pair(dest,weight));
|
|
|
43 if (src!=dest)
|
|
|
44 links[dest].push_back(make_pair(src,weight));
|
|
|
45
|
|
|
46 nb_links++;
|
|
|
47 }
|
|
|
48 }
|
|
|
49
|
|
|
50 finput.close();
|
|
|
51 }
|
|
|
52
|
|
|
53 void
|
|
|
54 Graph::renumber(int type) {
|
|
|
55 vector<int> linked(links.size(),-1);
|
|
|
56 vector<int> renum(links.size(),-1);
|
|
|
57 int nb=0;
|
|
|
58
|
|
|
59 for (unsigned int i=0 ; i<links.size() ; i++) {
|
|
|
60 for (unsigned int j=0 ; j<links[i].size() ; j++) {
|
|
|
61 linked[i]=1;
|
|
|
62 linked[links[i][j].first]=1;
|
|
|
63 }
|
|
|
64 }
|
|
|
65
|
|
|
66 for (unsigned int i=0 ; i<links.size() ; i++) {
|
|
|
67 if (linked[i]==1)
|
|
|
68 renum[i]=nb++;
|
|
|
69 }
|
|
|
70
|
|
|
71 for (unsigned int i=0 ; i<links.size() ; i++) {
|
|
|
72 if (linked[i]==1) {
|
|
|
73 for (unsigned int j=0 ; j<links[i].size() ; j++) {
|
|
|
74 links[i][j].first = renum[links[i][j].first];
|
|
|
75 }
|
|
|
76 links[renum[i]]=links[i];
|
|
|
77 }
|
|
|
78 }
|
|
|
79 links.resize(nb);
|
|
|
80 }
|
|
|
81
|
|
|
82 void
|
|
|
83 Graph::clean(int type) {
|
|
|
84 for (unsigned int i=0 ; i<links.size() ; i++) {
|
|
|
85 map<int, float> m;
|
|
|
86 map<int, float>::iterator it;
|
|
|
87
|
|
|
88 for (unsigned int j=0 ; j<links[i].size() ; j++) {
|
|
|
89 it = m.find(links[i][j].first);
|
|
|
90 if (it==m.end())
|
|
|
91 m.insert(make_pair(links[i][j].first, links[i][j].second));
|
|
|
92 else if (type==WEIGHTED)
|
|
|
93 it->second+=links[i][j].second;
|
|
|
94 }
|
|
|
95
|
|
|
96 vector<pair<int,float> > v;
|
|
|
97 for (it = m.begin() ; it!=m.end() ; it++)
|
|
|
98 v.push_back(*it);
|
|
|
99 links[i].clear();
|
|
|
100 links[i]=v;
|
|
|
101 }
|
|
|
102 }
|
|
|
103
|
|
|
104 void
|
|
|
105 Graph::display(int type) {
|
|
|
106 for (unsigned int i=0 ; i<links.size() ; i++) {
|
|
|
107 for (unsigned int j=0 ; j<links[i].size() ; j++) {
|
|
|
108 int dest = links[i][j].first;
|
|
|
109 float weight = links[i][j].second;
|
|
|
110 if (type==WEIGHTED)
|
|
|
111 cout << i << " " << dest << " " << weight << endl;
|
|
|
112 else
|
|
|
113 cout << i << " " << dest << endl;
|
|
|
114 }
|
|
|
115 }
|
|
|
116 }
|
|
|
117
|
|
|
118 void
|
|
|
119 Graph::display_binary(char *filename, char *filename_w, int type) {
|
|
|
120 ofstream foutput;
|
|
|
121 foutput.open(filename, fstream::out | fstream::binary);
|
|
|
122
|
|
|
123 unsigned int s = links.size();
|
|
|
124
|
|
|
125 // outputs number of nodes
|
|
|
126 foutput.write((char *)(&s),4);
|
|
|
127
|
|
|
128 // outputs cumulative degree sequence
|
|
|
129 long tot=0;
|
|
|
130 for (unsigned int i=0 ; i<s ; i++) {
|
|
|
131 tot+=(long)links[i].size();
|
|
|
132 foutput.write((char *)(&tot),8);
|
|
|
133 }
|
|
|
134
|
|
|
135 // outputs links
|
|
|
136 for (unsigned int i=0 ; i<s ; i++) {
|
|
|
137 for (unsigned int j=0 ; j<links[i].size() ; j++) {
|
|
|
138 int dest = links[i][j].first;
|
|
|
139 foutput.write((char *)(&dest),4);
|
|
|
140 }
|
|
|
141 }
|
|
|
142 foutput.close();
|
|
|
143
|
|
|
144 // outputs weights in a separate file
|
|
|
145 if (type==WEIGHTED) {
|
|
|
146 ofstream foutput_w;
|
|
|
147 foutput_w.open(filename_w,fstream::out | fstream::binary);
|
|
|
148 for (unsigned int i=0 ; i<s ; i++) {
|
|
|
149 for (unsigned int j=0 ; j<links[i].size() ; j++) {
|
|
|
150 float weight = links[i][j].second;
|
|
|
151 foutput_w.write((char *)(&weight),4);
|
|
|
152 }
|
|
|
153 }
|
|
|
154 foutput_w.close();
|
|
|
155 }
|
|
|
156 }
|
|
|
157
|
