|
0
|
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
|
