File: graph.h

package info (click to toggle)
socnetv 0.90-3
  • links: PTS, VCS
  • area: main
  • in suites: wheezy
  • size: 2,028 kB
  • sloc: cpp: 12,953; makefile: 75
file content (377 lines) | stat: -rwxr-xr-x 16,316 bytes parent folder | download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
/***************************************************************************
 SocNetV: Social Networks Visualizer 
 version: 0.90
 Written in Qt 4.4
 
                         graph.h  -  description
                             -------------------
    copyright            : (C) 2005-2010 by Dimitris B. Kalamaras
    email                : dimitris.kalamaras@gmail.com
 ***************************************************************************/

/*******************************************************************************
*     This program is free software: you can redistribute it and/or modify     *
*     it under the terms of the GNU General Public License as published by     *
*     the Free Software Foundation, either version 3 of the License, or        *
*     (at your option) any later version.                                      *
*                                                                              *
*     This program is distributed in the hope that it will be useful,          *
*     but WITHOUT ANY WARRANTY; without even the implied warranty of           *
*     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the            *
*     GNU General Public License for more details.                             *
*                                                                              *
*     You should have received a copy of the GNU General Public License        *
*     along with this program.  If not, see <http://www.gnu.org/licenses/>.    *
********************************************************************************/

#ifndef GRAPH_H
#define GRAPH_H


#include <QObject>
#include <QList>
#include <QHash>
#include <QTextStream>

#include <stack>  //FYI: stack is a wrapper around <deque> in C++, see: www.cplusplus.com/reference/stl/stack
#include <map>
	
#include "vertex.h"
#include "matrix.h"
#include "parser.h"
#include "webcrawler.h"

using namespace std;

class QPointF;
class QDateTime;

/**	This is the main class for a Graph, used in conjuction with Vertex, Parser and Matrix objects.
	
	Graph class has the interface and the various network algorithms 
	Vertex class holds each vertex data (colors, strings, statistics, etc)
	Matrix class holds the adjacency matrix of the network.
	Parser class loads files of networks.	
*/

typedef QList<Vertex*> Vertices;
typedef map<long int,long int> imap_i;
typedef map<int,float> imap_f;
typedef QHash <QString, int> hash_si;


class Graph:  public QObject{
	Q_OBJECT

public slots:
	/** Slots to signals from Parser */
	void createVertex(	int i, int size, QString nodeColor, 
						QString numColor, int numSize, 
						QString label, QString lColor, int lSize, 
						QPointF p, QString nodeShape, bool signalMW
						);//Main vertex creation call
						
	void setFileType(int, QString, int,int, bool);	
	void removeDummyNode(int);
	
	/** Slots to signals from GraphicsWidget and Parser*/
	void createEdge (int, int, float, QString, int, bool, bool);	//GW and Parser.
	void createEdge (int, int, float, int, bool, bool);		//GW
	void createEdge (int, int);					//WebCrawler
	void nodeMovement(int state, int type, int cW, int cH);		//Called by MW to start movement

	void slotSetEdgeVisibility( int, int, bool);
	
	//auxiliary createVertex functions
	void createVertex(int i, QPointF p); 				//Called by GW
	void createVertex(int i, int canvasWidth, int canvasHeight); 	//Called by MW
	void createVertex(QString label, int i) ; 			//Called by WebCrawler
	
	/** Slots to signals from MainWindow */
	void setCanvasDimensions(int w, int h);
	void filterOrphanVertices ( bool );		//Called by MW to filter orphan vertices
	void filterEdgesByWeight (float, bool);		//Called by MW to filter edges over/under a weight
	
	void webCrawl( QString, int, int, bool);	//Called by MW to start a web crawler...
	
signals:
	/** Signals to MainWindow */
	void updateProgressDialog(int );
	void graphChanged();					//call to update MW widgets
	void selectedVertex(int);				//notifies MW who is the selected node

	void signalFileType (int, QString, int,int, bool);	//notifies MW what we have loaded.
	void statusMessage (QString message);			//updates statusbar message
		
	/** Signals to GraphicsWidget */
	void drawNode( int ,int,  QString, QString, int, QString, QString, int, QPointF, QString, bool, bool, bool);	//call GW to draw a node
	
	void eraseNode (long int);						//erase node from GW
	void drawEdge(int, int, float, bool, bool, QString, bool);	//call GW to draw an edge
	void eraseEdge(int, int);					//emited from removeEdge() to GW to clear the edge item.
	void setEdgeVisibility ( int, int, bool);			// emitted from each Vertex
	void setVertexVisibility(long int, bool);		//notifies GW to disable a node
	void drawEdgeReciprocal(int, int);				//call GW to draw the edge as symmetric one
	void addBackgrCircle(int, int, int);				//call GW to draw a circular layout line somewhere.
	void addBackgrHLine (int);					//call GW to draw a horizontal layout line somewhere.
	void moveNode(int, int, int);

	
public: 	
	/* INIT AND CLEAR*/
	Graph(); 			//Creates a new graph.
	void clear();			//Clears m_graph 
	~Graph();			//destroy object

	void setSocNetV_Version (QString ver) { VERSION = ver; }
		
	void setShowLabels(bool toggle);
	void setShowNumbersInsideNodes(bool toggle);

	/*FILES (READ AND WRITE)*/
	bool loadGraph ( QString, bool,	int maxWidth, int maxHeight, int format, int two_sm_mode);	//Our almost universal network loader. :)
	
	bool saveGraph( QString fileName, int fileType, 
						QString networkName, int maxWidth, int maxHeight 
				);
	bool saveGraphToPajekFormat (QString fileName,QString networkName,  int maxWidth, int maxHeight);
	bool saveGraphToAdjacencyFormat (QString fileName, int maxWidth, int maxHeight);
	bool saveGraphToDotFormat (QString fileName, QString networkName, int maxWidth, int maxHeight);
	bool saveGraphToGraphMLFormat (QString fileName,QString networkName,  int maxWidth, int maxHeight);

	/* VERTICES */
	int lastVertexNumber();				//Returns the number of the last vertex
	int firstVertexNumber();			//Returns the number of the first vertex

	int hasVertex(long int );		//Checks if a vertex exists
	int hasVertex(QString);				//Checks if a vertex with a label exists
	void removeVertex (long int );			//removes given vertex from m_graph

	void setInitVertexSize (long int); 			//Changes the init size used in new vertices.
	void setVertexSize(long int v, int );		//Changes the size.of vertex v

	
	void setInitVertexShape (QString); 		//Changes the init shape used in new vertices.
	void setVertexShape(int v, QString shape); 	//Changes the shape.of vertex v 
	QString shape(int v);				//returns the shape of this vertex

	void setInitVertexColor (QString color);  	//Changes the init color used in new vertices
	void setVertexColor(long int v, QString color); 	//Changes the color.of vertex v


	void setInitVertexNumberColor ( QString color);	//Changes the init number color in new vertices  
	void setInitVertexNumberSize (int size);	//Changes the init number size in new vertices
	
	void setInitVertexLabelSize(int newSize);	//Changes the init size of new vertices labels
	void setVertexLabelSize(int v, int newSize);	//Changes the size of a vertex label
	
	void setInitVertexLabelColor(QString color);	//Changes the init color used by all new vertices' labels
	void setVertexLabel(int v, QString label); 	//Changes the label.of vertex v
	void setVertexLabelColor(int v1, QString color);  
	QString label(int);			


	void updateVertCoords(int v, int x, int y);	 //Updates vertex v with coords x,y

	int vertices() ;				//Returns the sum of vertices inside m_graph

	int edgesFrom (int i) ;				//Returns the number of edges starting from v1 (outDegree)
	int edgesTo (int i) ;				//Returns the number of edges ending to v1 (inDegree)

	int verticesWithOutEdges();			//Returns the sum of vertices having outEdges
	int verticesWithInEdges();			//Returns the sum of vertices having inEdges
	int verticesWithReciprocalEdges();		//Returns the sum of vertices having reciprocal edges


	/* EDGES */
	float hasEdge (int v1, int v2);			//Checks if edge between v1 and v2 exists. Returns weight or -1
	void removeEdge (int v1, int v2);		//removes the edge between v1 and v2
	
 
	void setEdgeWeight (int v1, int v2, float w); 	//Sets the edge weight between v1 and v2
	void setInitEdgeColor(QString);

	void setEdgeColor(long int s, long int t, QString color);	//Changes the color of edge (s,t).
	QString edgeColor (long int s, long int t); 		//Returns the edgeColor
	 
	int totalEdges ();				//Returns the sum of edges inside m_graph

	float density();				//Returns ratio of present edges to total possible edges.

	bool symmetricEdge(int v1, int v2);		//Returns TRUE if (v1, v2) is symmetric.
	bool isSymmetric();				//Returns TRUE if symmetricAdjacencyMatrix=TRUE
	void symmetrize();				//Symmetrize all edges so that the network is undirected.

	void createAdjacencyMatrix(bool);
	void invertAdjacencyMatrix();


	/* PRINT OUT TO FILES*/
	
	void writeDataSetToFile(QString );			// Writes a known dataset to a file.
	void writeAdjacencyMatrixTo(QTextStream& os);	 		//Exports the adjacency matrix to a given textstream
	void writeAdjacencyMatrix(const char*, const char*);		//Writes the adjacency matrix to a given file.

	void writeInvertAdjacencyMatrix(const char*,  const char*);
	void writeDistanceMatrix(const char*, const char*, const char*);//Writes the distance matrix to a file
	friend QTextStream& operator <<  (QTextStream& os, Graph& m);  	//

	void writeCentralityInDegree(const QString, bool);		//Writes the in-degree centralities to a file
	void writeCentralityOutDegree(const QString, const bool);	//Writes the out-degree centralities to a file
	void writeCentralityCloseness(const QString, const bool);	//Writes the closeness centralities to a file
	void writeCentralityBetweeness(const QString, const bool);	//Writes the betweeness centralities to a file
	void writeCentralityGraph(const QString, const bool);		//Writes the Graph centralities to a file
	void writeCentralityPower(const QString, const bool);		//Writes the Power centralities to a file
	void writeCentralityStress(const QString, const bool);		//Writes the Stress centralities to a file	
	void writeCentralityEccentricity(const QString, const bool);	//Writes the Eccentr centralities to a file
	void writeCentralityInformation(const QString);			//Writes the Information centralities to a file

	void writeNumberOfCliques(const QString fileName, const bool considerWeights);
	
	void writeClusteringCoefficient(const QString, const bool);	//Writes the clustering coefficients to a file

	void writeTriadCensus(const QString, const bool);		//Writes the triad census to a file	
	

	/* DISTANCES & CENTRALITIES */
	int distance( int, int);		//Returns the geodesic distance between two vertices
	int diameter();				//Returns the diameter of the graph (maximum shortest path).
	float averageGraphDistance();		//Returns the average shortest path length (average geodesic).

	void createDistanceMatrix(bool);	//Creates the distance matrix and calculates the centralities, if bool is true.

	void centralityInDegree(bool);		//Calculates the inDegree centrality of each vertex
	void centralityOutDegree(bool);		//Calculates the outDegree centrality of each vertex

	void centralityInformation();

	float numberOfTriples(int v1); 		//Returns the number of triples at vertex v1
	float numberOfCliques(int v1);		//Calculates the number of cliques (triangles) of vertex v1
	float numberOfCliques();		//Calculates the number of cliques (triangles) of the whole graph
	float clusteringCoefficient(int v1);	
	float clusteringCoefficient ();
	
	bool triadCensus();
	void examine_MAN_label(int, int, int, Vertex*,  Vertex*, Vertex* );
//	void eccentr_JordanCenter(); 				// TODO


	/* LAYOUTS */
	void layoutRandom(double maxWidth, double maxHeight);
	void layoutRadialCentrality(double x0, double y0, double maxRadius, int CentralityType);
	void layoutLayeredCentrality(double maxWidth, double maxHeight, int CentralityType);
	void layoutForceDirectedSpringEmbedder(bool dynamicMovement);
	void layoutForceDirectedFruchtermanReingold(bool dynamicMovement);

	/**RANDOM NETWORKS*/
	void createRandomNetErdos 
			(int, double);				//Creates a uniform random network
	
	void createRandomNetRingLattice
			(int, int, double, double, double); 	//Creates a ring lattice network
				
	void createSameDegreeRandomNetwork
			(int, int); 				//Creates a random network with the same degree in all nodes
				
	void createRandomNetSmallWorld 
			(int, int, double, double, double, double); 	//Creates a small world network
				
	int factorial (int);				// for  (n 2)p edges calculation


	/*  index stores the real position of each vertex inside m_graph. It starts at zero (0).
	    We need to know the place of a vertex inside m_graph after adding or removing many vertices */
	imap_i index;

	// Stores the number of vertices at distance n from a given vertex
	imap_i sizeOfNthOrderNeighborhood;

	/* maps have O(logN) lookup complexity */
	/* Consider using tr1::hashmap which has O(1) lookup, but this is not ISO C++ yet :(   */




protected: 

	void timerEvent(QTimerEvent *event);			// Called from nodeMovement when a timerEvent occurs
private:

	/** List of pointers to the vertices. A vertex stores all the info: links, colours, etc */
	Vertices m_graph;			

	Parser parser;			//file loader threaded class.

	WebCrawler crawler; 
	
	/** private member functions */

	void addVertex (
						int v1, int val, int size, QString color, 
						QString numColor, int numSize, 
						QString label, QString labelColor, int labelSize, 
						QPointF p, QString shape
					);			// adds a vertex to m_graph
						
	void addEdge (int v1, int v2, float w, QString color, int reciprocal); 		//adds an edge between v1 and v2, weight w, colored

	/** methods used by createDistanceMatrix()  */
	void BFS(int, bool);									//Breadth-first search 
	void minmax(float C, Vertex *v, float &max, float &min, int &maxNode, int &minNode) ;	//helper
	void resolveClasses(float C, hash_si &discreteClasses, int &classes);			//helper
	void resolveClasses(float C, hash_si &discreteClasses, int &classes, int name);  	//helper

	/** used in resolveClasses and createDistanceMatrix() */
	hash_si discreteIDCs, discreteODCs, discreteCCs, discreteBCs, discreteSCs, discreteGCs, discreteECs, discretePCs, discreteICs;
	
	int *eccentricities;
	bool calculatedIDC, calculatedODC, calculatedCentralities, dynamicMovement;
	
	QList<int>  triadTypeFreqs; 	//stores triad type frequencies
	Matrix  TM, DM, sumM, invAM, AM, invM;
	stack<int> Stack;

	float meanDegree, varianceDegree;
	float minIDC, maxIDC, sumIDC, groupIDC;
	float minODC, maxODC, sumODC, groupODC;
	float minCC, maxCC, nomCC, denomCC, sumCC, groupCC, maxIndexCC;
	float minBC, maxBC, nomBC, denomBC, sumBC, groupBC, maxIndexBC;
	float minGC, maxGC, nomGC, denomGC, sumGC, groupGC, maxIndexGC;
	float minPC, maxPC, sumPC, groupPC, maxIndexPC;
	float minSC, maxSC, nomSC, denomSC, sumSC, groupSC, maxIndexSC;
	float minEC, maxEC, nomEC, denomEC, sumEC, groupEC, maxIndexEC;
	float minIC, maxIC, nomIC, denomIC, sumIC, groupIC, maxIndexIC;
	float minCLC, maxCLC, averageCLC, averageIC;
	int maxNodeCLC, minNodeCLC;
	int classesIDC, maxNodeIDC, minNodeIDC;
	int classesODC, maxNodeODC, minNodeODC;
	int classesCC, maxNodeCC, minNodeCC;
	int classesBC, maxNodeBC, minNodeBC;
	int classesGC, maxNodeGC, minNodeGC;
	int classesPC, maxNodePC, minNodePC;
	int classesSC, maxNodeSC, minNodeSC;
	int classesEC, maxNodeEC, minNodeEC;
	int classesIC, maxNodeIC, minNodeIC;
	int sizeOfComponent;

	/** General & initialisation variables */

	long int m_totalEdges, m_totalVertices, graphDiameter, initVertexSize;
	int initVertexLabelSize, initVertexNumberSize;

	int isolatedVertices;
	float averGraphDistance, nonZeroDistancesCounter;
	int outEdgesVert, inEdgesVert, reciprocalEdgesVert;
	int timerId,  layoutType, canvasWidth, canvasHeight;
	
	bool order, initShowLabels, initNumbersInsideNodes;
	bool adjacencyMatrixCreated, symmetricAdjacencyMatrix, graphModified, distanceMatrixCreated;
	bool m_undirected;

	QString VERSION, networkName, initEdgeColor, initVertexColor, initVertexNumberColor, initVertexLabelColor, initVertexShape;
	
	QDateTime actualDateTime;
};

#endif