Mercurial > repos > petr-novak > repeatrxplorer

comparison louvain/graph_binary.h @ 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_binary.h
2 // -- graph handling header 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 #ifndef GRAPH_H
18 #define GRAPH_H
19
20 #include <stdlib.h>
21 #include <stdio.h>
22 #include <assert.h>
23 #include <malloc.h>
24 #include <iostream>
25 #include <iomanip>
26 #include <fstream>
27 #include <vector>
28 #include <map>
29 #include <algorithm>
30
31 #define WEIGHTED 0
32 #define UNWEIGHTED 1
33
34 using namespace std;
35
36 class Graph {
37 public:
38 unsigned int nb_nodes;
39 unsigned long nb_links;
40 double total_weight;
41
42 vector<unsigned long> degrees;
43 vector<unsigned int> links;
44 vector<float> weights;
45
46 Graph();
47
48 // binary file format is
49 // 4 bytes for the number of nodes in the graph
50 // 8*(nb_nodes) bytes for the cumulative degree for each node:
51 // deg(0)=degrees[0]
52 // deg(k)=degrees[k]-degrees[k-1]
53 // 4*(sum_degrees) bytes for the links
54 // IF WEIGHTED 4*(sum_degrees) bytes for the weights in a separate file
55 Graph(char *filename, char *filename_w, int type);
56
57 Graph(int nb_nodes, int nb_links, double total_weight, int *degrees, int *links, float *weights);
58
59 void display(void);
60 void display_reverse(void);
61 void display_binary(char *outfile);
62 bool check_symmetry();
63
64
65 // return the number of neighbors (degree) of the node
66 inline unsigned int nb_neighbors(unsigned int node);
67
68 // return the number of self loops of the node
69 inline double nb_selfloops(unsigned int node);
70
71 // return the weighted degree of the node
72 inline double weighted_degree(unsigned int node);
73
74 // return pointers to the first neighbor and first weight of the node
75 inline pair<vector<unsigned int>::iterator, vector<float>::iterator > neighbors(unsigned int node);
76 };
77
78
79 inline unsigned int
80 Graph::nb_neighbors(unsigned int node) {
81 assert(node>=0 && node<nb_nodes);
82
83 if (node==0)
84 return degrees[0];
85 else
86 return degrees[node]-degrees[node-1];
87 }
88
89 inline double
90 Graph::nb_selfloops(unsigned int node) {
91 assert(node>=0 && node<nb_nodes);
92
93 pair<vector<unsigned int>::iterator, vector<float>::iterator > p = neighbors(node);
94 for (unsigned int i=0 ; i<nb_neighbors(node) ; i++) {
95 if (*(p.first+i)==node) {
96 if (weights.size()!=0)
97 return (double)*(p.second+i);
98 else
99 return 1.;
100 }
101 }
102 return 0.;
103 }
104
105 inline double
106 Graph::weighted_degree(unsigned int node) {
107 assert(node>=0 && node<nb_nodes);
108
109 if (weights.size()==0)
110 return (double)nb_neighbors(node);
111 else {
112 pair<vector<unsigned int>::iterator, vector<float>::iterator > p = neighbors(node);
113 double res = 0;
114 for (unsigned int i=0 ; i<nb_neighbors(node) ; i++) {
115 res += (double)*(p.second+i);
116 }
117 return res;
118 }
119 }
120
121 inline pair<vector<unsigned int>::iterator, vector<float>::iterator >
122 Graph::neighbors(unsigned int node) {
123 assert(node>=0 && node<nb_nodes);
124
125 if (node==0)
126 return make_pair(links.begin(), weights.begin());
127 else if (weights.size()!=0)
128 return make_pair(links.begin()+degrees[node-1], weights.begin()+degrees[node-1]);
129 else
130 return make_pair(links.begin()+degrees[node-1], weights.begin());
131 }
132
133
134 #endif // GRAPH_H