Mercurial > repos > petrn > repeatexplorer

comparison louvain/main_community.cpp @ 8:3bc73f5dc785 draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Uploaded
author petrn
date Fri, 20 Dec 2019 14:17:59 +0000
parents f6ebec6e235e
children
comparison
equal deleted inserted replaced
7:c56807be3b72 8:3bc73f5dc785
1 // File: main_community.cpp
2 // -- community detection, sample main 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 <stdlib.h>
18 #include <math.h>
19 #include <string>
20 #include <iostream>
21 #include <fstream>
22 #include <sstream>
23 #include <vector>
24 #include <algorithm>
25
26 #include "graph_binary.h"
27 #include "community.h"
28
29 using namespace std;
30
31 char *filename = NULL;
32 char *filename_w = NULL;
33 char *filename_part = NULL;
34 int type = UNWEIGHTED;
35 int nb_pass = 0;
36 double precision = 0.000001;
37 int display_level = -2;
38 int k1 = 16;
39 int seed = 123;
40
41 bool verbose = false;
42
43 void
44 usage(char *prog_name, const char *more) {
45 cerr << more;
46 cerr << "usage: " << prog_name << " input_file [-w weight_file] [-p part_file] [-q epsilon] [-l display_level] [-v] [-h]" << endl << endl;
47 cerr << "input_file: file containing the graph to decompose in communities." << endl;
48 cerr << "-w file\tread the graph as a weighted one (weights are set to 1 otherwise)." << endl;
49 cerr << "-p file\tstart the computation with a given partition instead of the trivial partition." << endl;
50 cerr << "\tfile must contain lines \"node community\"." << endl;
51 cerr << "-q eps\ta given pass stops when the modularity is increased by less than epsilon." << endl;
52 cerr << "-l k\tdisplays the graph of level k rather than the hierachical structure." << endl;
53 cerr << "\tif k=-1 then displays the hierarchical structure rather than the graph at a given level." << endl;
54 cerr << "-v\tverbose mode: gives computation time, information about the hierarchy and modularity." << endl;
55 cerr << "-s\tseed for rundom number generator setting, integer(123 deafault)" << endl;
56 cerr << "-h\tshow this usage message." << endl;
57 exit(0);
58 }
59
60 void
61 parse_args(int argc, char **argv) {
62 if (argc<2)
63 usage(argv[0], "Bad arguments number\n");
64
65 for (int i = 1; i < argc; i++) {
66 if(argv[i][0] == '-') {
67 switch(argv[i][1]) {
68 case 'w':
69 type = WEIGHTED;
70 filename_w = argv[i+1];
71 i++;
72 break;
73 case 'p':
74 filename_part = argv[i+1];
75 i++;
76 break;
77 case 'q':
78 precision = atof(argv[i+1]);
79 i++;
80 break;
81 case 'l':
82 display_level = atoi(argv[i+1]);
83 i++;
84 break;
85 case 's':
86 seed = atoi(argv[i+1]);
87 i++;
88 break;
89 case 'k':
90 k1 = atoi(argv[i+1]);
91 i++;
92 break;
93 case 'v':
94 verbose=true;
95 break;
96 default:
97 usage(argv[0], "Unknown option\n");
98 }
99 } else {
100 if (filename==NULL)
101 filename = argv[i];
102 else
103 usage(argv[0], "More than one filename\n");
104 }
105 }
106 }
107
108 void
109 display_time(const char *str) {
110 time_t rawtime;
111 time ( &rawtime );
112 cerr << str << ": " << ctime (&rawtime);
113 }
114
115 int
116 main(int argc, char **argv) {
117 parse_args(argc, argv);
118 srand(seed);
119 time_t time_begin, time_end;
120 time(&time_begin);
121 if (verbose)
122 display_time("Begin");
123
124 Community c(filename, filename_w, type, -1, precision);
125 if (filename_part!=NULL)
126 c.init_partition(filename_part);
127 Graph g;
128 bool improvement=true;
129 double mod=c.modularity(), new_mod;
130 int level=0;
131
132 do {
133 if (verbose) {
134 cerr << "level " << level << ":\n";
135 display_time(" start computation");
136 cerr << " network size: "
137 << c.g.nb_nodes << " nodes, "
138 << c.g.nb_links << " links, "
139 << c.g.total_weight << " weight." << endl;
140 }
141
142 improvement = c.one_level();
143 new_mod = c.modularity();
144 if (++level==display_level)
145 g.display();
146 if (display_level==-1)
147 c.display_partition();
148 g = c.partition2graph_binary();
149 c = Community(g, -1, precision);
150
151 if (verbose)
152 cerr << " modularity increased from " << mod << " to " << new_mod << endl;
153
154 mod=new_mod;
155 if (verbose)
156 display_time(" end computation");
157
158 if (filename_part!=NULL && level==1) // do at least one more computation if partition is provided
159 improvement=true;
160 } while(improvement);
161
162 time(&time_end);
163 if (verbose) {
164 display_time("End");
165 cerr << "Total duration: " << (time_end-time_begin) << " sec." << endl;
166 }
167 cerr << new_mod << endl;
168 }
169