Mercurial > repos > petr-novak > repeatrxplorer

comparison louvain/graph.cpp @ 0:1d1b9e1b2e2f draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Uploaded
author petr-novak
date Thu, 19 Dec 2019 10:24:45 -0500
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:1d1b9e1b2e2f
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