graph.h
Go to the documentation of this file.
1 /***************************************************************************
2  SocNetV: Social Network Visualizer
3  version: 2.2
4  Written in Qt
5 
6  graph.h - description
7  -------------------
8  copyright : (C) 2005-2017 by Dimitris B. Kalamaras
9  project site : http://socnetv.org
10 
11  ***************************************************************************/
12 
13 /*******************************************************************************
14 * This program is free software: you can redistribute it and/or modify *
15 * it under the terms of the GNU General Public License as published by *
16 * the Free Software Foundation, either version 3 of the License, or *
17 * (at your option) any later version. *
18 * *
19 * This program is distributed in the hope that it will be useful, *
20 * but WITHOUT ANY WARRANTY; without even the implied warranty of *
21 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
22 * GNU General Public License for more details. *
23 * *
24 * You should have received a copy of the GNU General Public License *
25 * along with this program. If not, see <http://www.gnu.org/licenses/>. *
26 ********************************************************************************/
27 
28 #ifndef GRAPH_H
29 #define GRAPH_H
30 
31 
32 #include <QObject>
33 #include <QDateTime> // used in exporting centrality files
34 #include <QList>
35 #include <QHash>
36 #include <QTextStream>
37 #include <QThread>
38 //FYI: stack is a wrapper around <deque> in C++, see: www.cplusplus.com/reference/stl/stack
39 #include <stack>
40 #include <map>
41 
42 #include "vertex.h"
43 #include "matrix.h"
44 #include "parser.h"
45 #include "webcrawler.h"
46 
47 using namespace std;
48 
49 static const int EDGE_DIRECTED = 0;
50 static const int EDGE_DIRECTED_OPPOSITE_EXISTS = 1;
51 static const int EDGE_RECIPROCAL_UNDIRECTED = 2;
52 
53 static const int FILE_GRAPHML = 1; // .GRAPHML .XML
54 static const int FILE_PAJEK = 2; // .PAJ .NET
55 static const int FILE_ADJACENCY = 3; // .ADJ .CSV .SM
56 static const int FILE_GRAPHVIZ = 4; // .DOT
57 static const int FILE_UCINET = 5; // .DL .DAT
58 static const int FILE_GML = 6; // .GML
59 static const int FILE_EDGELIST_WEIGHTED = 7; // .CSV, .TXT, .LIST, LST, WLST
60 static const int FILE_EDGELIST_SIMPLE = 8; // .CSV, .TXT, .LIST, LST
61 static const int FILE_TWOMODE = 9; // .2SM .AFF
62 static const int FILE_UNRECOGNIZED =-1; // UNRECOGNIZED FILE FORMAT
63 
64 
65 static const int GRAPH_CHANGED_NONE = 0;
66 static const int GRAPH_CHANGED_MINOR_OPTIONS = 1;
67 static const int GRAPH_CHANGED_VERTICES_METADATA = 2;
68 static const int GRAPH_CHANGED_EDGES_METADATA = 3;
69 static const int GRAPH_CHANGED_POSITIONS = 4;
70 static const int GRAPH_CHANGED_VERTICES = 11;
71 static const int GRAPH_CHANGED_EDGES = 12;
72 static const int GRAPH_CHANGED_VERTICES_AND_EDGES = 13;
73 static const int GRAPH_CHANGED_NEW = 14;
74 
75 static const int CLUSTERING_SINGLE_LINKAGE = 0; //"single-link" or minimum
76 static const int CLUSTERING_COMPLETE_LINKAGE = 1; // "complete-link or maximum
77 static const int CLUSTERING_AVERAGE_LINKAGE = 2;
78 
79 static const int SUBGRAPH_CLIQUE = 1;
80 static const int SUBGRAPH_STAR = 2;
81 static const int SUBGRAPH_CYCLE = 3;
82 static const int SUBGRAPH_LINE = 4;
83 
84 static const int MATRIX_ADJACENCY = 1;
85 static const int MATRIX_DISTANCES = 2;
86 static const int MATRIX_DEGREE = 3;
87 static const int MATRIX_LAPLACIAN = 4;
88 static const int MATRIX_ADJACENCY_INVERSE = 5;
89 static const int MATRIX_GEODESICS = 6;
90 static const int MATRIX_REACHABILITY = 7;
91 static const int MATRIX_ADJACENCY_TRANSPOSE = 8;
92 static const int MATRIX_COCITATION = 9;
93 static const int MATRIX_DISTANCES_EUCLIDEAN = 12;
94 static const int MATRIX_DISTANCES_MANHATTAN= 13;
95 static const int MATRIX_DISTANCES_JACCARD= 14;
96 static const int MATRIX_DISTANCES_HAMMING= 15;
97 static const int MATRIX_DISTANCES_CHEBYSHEV= 16;
98 
99 
100 class QPointF;
101 
102 
103 
104 typedef QList<Vertex*> Vertices;
105 typedef QHash <QString, int> H_StrToInt;
106 typedef QHash <long int, long int> H_Int;
107 typedef QPair <float, bool> pair_f_b;
108 typedef QPair <int, pair_f_b > rel_w_bool;
109 typedef QHash < int, rel_w_bool > H_edges;
110 typedef QHash<QString, bool> H_StrToBool;
111 typedef QList<int> L_int;
112 typedef QVector<int> V_int;
113 typedef QVector<QString> V_str;
114 
115 
116 
117 struct ClickedEdge {
118  int v1;
119  int v2;
120 };
121 
122 
123 
124 typedef pair<int, int> SelectedEdge;
125 
126 
128 {
129 public:
130  int target;
131  int distance;
132 
133  GraphDistance(int t, int dist)
134  : target(t), distance(dist)
135  {
136 
137  }
138 };
139 
140 
141 // implement a min-priority queue
143  public:
145  {
146  if (t1.distance == t2.distance)
147  return t1.target > t2.target;
148  return t1.distance > t2.distance; //minimum priority
149  // Returns true if t1 is closer than t2
150  // else
151  }
152 };
153 
154 
192 class Graph: public QObject{
193  Q_OBJECT
197 
198 public slots:
199 
200  int relationCurrent();
201  QString relationCurrentName() const;
202  void relationCurrentRename(const QString &newName, const bool &notifyMW=false);
203 
205  void vertexCreate(const int &num, const int &size, const QString &nodeColor,
206  const QString &numColor, const int &numSize,
207  const QString &label, const QString &lColor,
208  const int &labelSize, const QPointF &p, const QString &nodeShape,
209  const bool &signalMW
210  );//Main vertex creation call
211 
212  void graphFileLoaded(const int &fileType,
213  const QString &fName=QString::null,
214  const QString &netName=QString::null,
215  const int &totalNodes=0,
216  const int &totalLinks=0,
217  const bool &undirected=false,
218  const QString &message=QString::null);
219 
220  void vertexRemoveDummyNode(int);
221  void graphLoadedTerminateParserThreads (QString reason);
222 
224  void edgeCreate (const int &v1, const int &v2, const float &weight,
225  const QString &color ,
226  const int &type=0,
227  const bool &drawArrows=true, const bool &bezier=false,
228  const QString &label=QString::null,
229  const bool &signalMW=true);
230  void edgeCreateWebCrawler (const int &source, const int &target);
231 
232  void edgeVisibilitySet(int relation, int, int, bool);
233 
234  //auxiliary vertexCreate functions
235  void vertexCreateAtPos(const QPointF &p);
236  void vertexCreateAtPosRandom(const bool &signalMW=false);
237  void vertexCreateAtPosRandomWithLabel(const int &i,
238  const QString &label,
239  const bool &signalMW=false) ;
242  void relationSet(int index=RAND_MAX, const bool notifyMW=true);
243  void relationNext();
244  void relationPrev();
245  void canvasSizeSet(const int w, const int h);
246  double canvasMaxRadius() const;
247  float canvasMinDimension() const;
248  double canvasVisibleX(const double &x) const ;
249  double canvasVisibleY(const double &y) const ;
250  double canvasRandomX() const;
251  double canvasRandomY() const;
252  void vertexIsolateFilter ( bool ); //Called by MW to filter orphan vertices
253  void vertexClickedSet(const int &v);
254  void edgeClickedSet(const int &v1, const int &v2) ;
255  void edgeFilterByWeight (float, bool); //Called by MW to filter edges over/under a weight
256  void edgeFilterByRelation(int relation, bool status);
257  void edgeFilterUnilateral(const bool &toggle);
258  void webCrawl(QString, int, int, bool extLinks, bool intLinks); //Called by MW to start a web crawler...
259 
260  QString htmlEscaped (QString str) const;
261 
262 signals:
264  void updateProgressDialog(int );
265  void signalGraphModified(const int &graphStatus,
266  const bool &undirected,
267  const int &vertices,
268  const int &edges,
269  const float &density);
270 
271  void signalGraphLoaded (const int &fileType,
272  const QString &fileName=QString::null,
273  const QString &netName=QString::null,
274  const int &totalNodes=0,
275  const int &totalLinks=0,
276  const QString &message=QString::null
277  );
278  void signalGraphSaved(const int &status);
279 
280  void statusMessage (const QString &message);
281  void signalDatasetDescription(QString);
282  void signalNodeSizesByOutDegree(bool);
283  void signalNodeSizesByInDegree(bool);
284  void signalNodeClickedInfo(const int &number=0,
285  const QPointF &p=QPointF(),
286  const QString &label=QString::null,
287  const int &inDegree=0,
288  const int &outDegree=0,
289  const float &clc=0);
290  void signalEdgeClickedInfo (const long int &v1=0,
291  const long int &v2=0,
292  const float &weight=0,
293  const bool &undirected=false);
294  void signalRelationAddToMW(const QString &newRelation, const bool &changeRelation=true);
295  void signalRelationsClear();
296  void signalRelationRenamedToMW(const QString newRelName);
297  void signalRelationChangedToGW(int);
298  void signalRelationChangedToMW(const int &relIndex=RAND_MAX);
299  void signalSelectionChanged(const int &selectedVertices,
300  const int &selectedEdges);
301 
303  void drawNode( const int &num, const int &size, const QString &nodeShape,
304  const QString &nodeColor,
305  const bool &showNumbers,const bool &numbersInside,
306  const QString &numberColor, const int &numSize,
307  const int &numDistance,
308  const bool &showLabels, const QString &label,
309  const QString &labelColor, const int &labelSize,
310  const int &labelDistance,
311  const QPointF &p
312  );
313 
314  void eraseNode (long int); //erase node from GW
315  //call GW to draw an edge
316  void drawEdge ( const int &v1, const int &v2, const float &weight,
317  const QString &label="",
318  const QString &color="black",
319  const int &type=0, const bool arrows=true,
320  const bool &bezier=false, const bool &weightNumbers=false);
321  void eraseEdge(const long int &, const long int &); //emited from edgeRemove() to GW to clear the edge item.
322  void setEdgeVisibility (int, int, int, bool); // emitted from each Vertex
323  void setVertexVisibility(long int, bool); //notifies GW to disable a node
324  void setNodePos(const int &, const qreal &, const qreal &);
325  void setNodeSize(const long int &v, const int &size);
326  void setNodeShape(const long int v, const QString &shape);
327  void setNodeColor(const long int v, const QString &color);
328  void setNodeLabel(long int, QString);
329  void setNodeNumberSize(const long int &, const int &);
330  void setNodeNumberDistance(const long int &, const int &);
331  void setNodeLabelSize(const long int &, const int &);
332  void setNodeLabelColor(const long int &, const QString &color);
333  void setNodeLabelDistance(const long int &, const int &);
334 
335  void setEdgeWeight (const long int &v1, const long int &v2, const float &weight);
336  void setEdgeUndirected(const long int &v1, const long int &v2, const float &weight);
337  void setEdgeColor(const long int &v1,
338  const long int &v2,
339  const QString &color);
340  void setEdgeLabel (const long int &v1,
341  const long int &v2,
342  const QString &label);
343  void addGuideCircle(const double&, const double&, const double&);
344  void addGuideHLine (const double&y0);
345 
346 
347 
348 
350  void operateSpider();
351 
352 
353 public:
354  /* INIT AND CLEAR*/
355  Graph();
356  void clear();
357  ~Graph(); //destroy object
358 
359  void setSocNetV_Version (QString ver) { VERSION = ver; }
360 
361 
362  /*FILES (READ AND WRITE)*/
363  QString graphName() const;
364  void graphLoad (const QString m_fileName, const QString m_codecName,
365  const bool m_showLabels,
366  const int format,
367  const int two_sm_mode,
368  const QString delimiter=QString::null);
369 
370  void graphSave(const QString &fileName,
371  const int &fileType,
372  const bool &saveEdgeWeights=true);
373  bool graphSaveToPajekFormat (const QString &fileName,
374  QString networkName="",
375  int maxWidth=0, int maxHeight=0);
376  bool graphSaveToAdjacencyFormat (const QString &fileName,
377  const bool &saveEdgeWeights=true);
378 
379  bool graphSaveToGraphMLFormat (const QString &fileName,
380  QString networkName="",
381  int maxWidth=0, int maxHeight=0);
382  bool graphSaveToDotFormat (QString fileName);
383  int graphFileFormat() const;
384  bool graphFileFormatExportSupported(const int &fileFormat) const;
385 
386  QString graphMatrixTypeToString(const int &matrixType) const;
387  int graphMatrixStrToType(const QString &matrix) const;
388 
389  QString graphMetricTypeToString(const int &metricType) const;
390  int graphMetricStrToType(const QString &metricStr) const;
391 
392  QString graphClusteringMethodTypeToString(const int &methodType) const;
393  int graphClusteringMethodStrToType(const QString &method) const;
394 
395  /* RELATIONS */
396  int relations();
397  void relationsClear();
398  void relationAdd(const QString &relName, const bool &changeRelation=false);
399 
400  /* VERTICES */
401  int vertexNumberMax();
402  int vertexNumberMin();
403 
404  int vertexDegreeOut(int);
405  int vertexDegreeIn(int);
406  QList<int> vertexNeighborhoodList(const int &v1);
407 
408  bool vertexIsolated(const long int &v1) const;
409 
410  int vertexExists(const long int &v1 );
411  int vertexExists(const QString &label);
412  void vertexRemove (long int );
413 
414  void vertexSizeInit (const long int);
415  void vertexSizeSet(const long int &v, const int &newsize );
416  void vertexSizeAllSet(const int newsize);
417  int vertexSize(const long int &v);
418 
419  void vertexShapeInit (const QString);
420  void vertexShapeSet(const int v, const QString shape);
421  void vertexShapeAllSet(const QString shape);
422  QString vertexShape(const int &v);
423 
424  void vertexColorInit (const QString &color);
425  void vertexColorSet(const long &v, const QString &color);
426  void vertexColorAllSet(const QString &color);
427  QColor vertexColor(const long int &v);
428 
429  void vertexNumberColorInit ( QString color);
430  void vertexNumberSizeInit (const int &size);
431  void vertexNumberSizeSet(const long int &v, const int &newsize );
432  void vertexNumberSizeSetAll (const int &size);
433  void vertexNumberDistanceInit (const int &distance);
434  void vertexNumberDistanceSet(const long int &v, const int &newDistance );
435  void vertexNumberDistanceSetAll (const int &newDistance);
436  void vertexNumbersInsideNodesSet(bool toggle);
437  void vertexNumbersVisibilitySet(bool toggle);
438 
439  void vertexLabelsVisibilitySet(bool toggle);
440  void vertexLabelSizeInit(int newSize);
441  void vertexLabelSizeSet(const long int &v, const int &newsize );
442  void vertexLabelSizeAllSet (const int &);
443  void vertexLabelColorInit(QString color);
444  void vertexLabelSet(int v, QString label);
445  void vertexLabelColorSet(int v1, QString color);
446  void vertexLabelColorAllSet(const QString &color);
447  QString vertexLabel(const long int &v1);
448  void vertexLabelDistanceInit (const int &distance);
449  void vertexLabelDistanceSet(const long int &v, const int &newDistance );
450  void vertexLabelDistanceAllSet (const int &newDistance);
451 
452  void vertexPosSet(const int &v, const int &x, const int &y);
453  QPointF vertexPos(const int &v1);
454  int vertexClicked() const;
455 
456  int vertices(const bool dropIsolates=false, const bool countAll=false) ;
457 
458  int vertexEdgesOutbound (int i) ;
459  int vertexEdgesInbound (int i) ;
460 
461  int verticesWithOutboundEdges();
462  int verticesWithInboundEdges();
463  int verticesWithReciprocalEdges();
464 
465  QList<int> verticesListIsolated();
466  QList<int> verticesList();
467  QSet<int> verticesSet();
468 
469 
470 
471  void verticesCreateSubgraph(QList<int> vList,
472  const int &type = SUBGRAPH_CLIQUE,
473  const int &center = 0);
474 
475 
476  qreal graphDistanceEuclidean(const QPointF &a, const QPointF &b);
477  qreal graphDistanceEuclidean(const QPointF &a);
478  int sign(const qreal &D);
479 
480  qreal layoutForceDirected_F_rep(const QString model, const qreal &dist,
481  const qreal &optimalDistance) ;
482  qreal layoutForceDirected_F_att(const QString model, const qreal &dist,
483  const qreal &optimalDistance) ;
484 
485  void layoutForceDirected_Eades_moveNodes(const qreal &c4);
486  void layoutForceDirected_FR_moveNodes(const qreal &temperature) ;
487 
488  qreal layoutForceDirected_FR_temperature(const int iteration) const;
489  qreal computeOptimalDistance(const int &Vertices);
490  void compute_angles( const QPointF &Delta,
491  const qreal &dist,
492  qreal &angle1,
493  qreal &angle2,
494  qreal &degrees1,
495  qreal &degrees2 );
496 
497  /* EDGES */
498  int edgesEnabled();
499  ClickedEdge edgeClicked();
500  float edgeExists(const long &v1, const long &v2, const bool &undirected=false);
501 
502  void edgeRemove (const long int &v1, const long int &v2,
503  const bool &removeOpposite=false);
504  bool edgeSymmetric(const long &v1, const long &v2);
505  void edgeUndirectedSet(const long int &v1, const long int &v2, const float &w);
506 
507  void edgeWeightSet (const long int &v1, const long int &v2,
508  const float &w,
509  const bool &undirected=false);
510  float edgeWeight(const long int &v1, const long int &v2) const;
511  void edgeWeightNumbersVisibilitySet (const bool &toggle);
512 
513  void edgeLabelSet(const long int &v1, const long int &v2, const QString &label);
514  QString edgeLabel (const long int &v1, const long int &v2) const;
515  void edgeLabelsVisibilitySet (const bool &toggle);
516 
517  void edgeColorInit(const QString &);
518  void edgeColorSet(const long int &v1, const long int &v2, const QString &color);
519  QString edgeColor (const long int &v1, const long int &v2);
520  bool edgeColorAllSet(const QString &color, const int &threshold=RAND_MAX);
521 
522  //GRAPH methods
523  void graphModifiedSet(const int &graphNewStatus, const bool&signalMW=true);
524  bool graphModified() const ;
525  bool graphSaved() const;
526  bool graphLoaded() const;
527 
528  void graphSelectionChanged(const QList<int> &selectedVertices,
529  const QList<SelectedEdge> &selectedEdges);
530 
531  QList<int> graphSelectedVertices() const;
532  int graphSelectedVerticesCount() const;
533  int graphSelectedVerticesMin() const;
534  int graphSelectedVerticesMax() const;
535 
536  QList<SelectedEdge> graphSelectedEdges() const;
537  int graphSelectedEdgesCount() const;
538 
539  int graphGeodesics();
540 
541  float graphDensity();
542  bool graphWeighted();
543 
544  bool graphSymmetric();
545  void graphSymmetrize();
546  void graphSymmetrizeStrongTies(const bool &allRelations=false);
547 
548  void graphCocitation();
549 
550  void graphUndirectedSet(const bool &toggle, const bool &signalMW=true);
551  bool graphUndirected();
552 
553  void graphMatrixAdjacencyCreate(const bool dropIsolates=false,
554  const bool considerWeights=true,
555  const bool inverseWeights=false,
556  const bool symmetrize=false );
557 
558  bool graphMatrixAdjacencyInvert(const QString &method="lu");
559 
560 
561  void graphMatrixSimilarityMatchingCreate(Matrix &AM,
562  Matrix &SEM,
563  const int &measure=METRIC_SIMPLE_MATCHING,
564  const QString &varLocation="Rows",
565  const bool &diagonal=false,
566  const bool &considerWeights=true);
567 
568  void graphMatrixSimilarityPearsonCreate (Matrix &AM,
569  Matrix &PCC,
570  const QString &varLocation="Rows",
571  const bool &diagonal=false);
572 
573  void graphMatrixDissimilaritiesCreate(Matrix &INPUT_MATRIX,
574  Matrix &DSM,
575  const int &metric,
576  const QString &varLocation,
577  const bool &diagonal,
578  const bool &considerWeights);
579 
580  /* REPORT EXPORTS */
581 
582  void writeDataSetToFile(const QString dir, const QString );
583 
584  void writeMatrixAdjacencyTo(QTextStream& os,
585  const bool &saveEdgeWeights=true);
586 
587  void writeMatrix(const QString &fileName,
588  const int &matrix=MATRIX_ADJACENCY,
589  const bool &considerWeights=true,
590  const bool &inverseWeights=false,
591  const bool &dropIsolates=false,
592  const QString &varLocation="Rows",
593  const bool &simpler=false);
594 
595  void writeMatrixAdjacency(const QString fileName,
596  const bool &markDiag=true);
597  void writeMatrixAdjacencyPlot(const QString fileName,
598  const bool &simpler=false);
599 
600  void writeMatrixAdjacencyInvert(const QString &filename,
601  const QString &method);
602 
603  void writeMatrixLaplacianPlainText(const QString &filename);
604  void writeMatrixDegreeText(const QString &filename);
605 
606  void writeMatrixDistancesPlainText(const QString &fn,
607  const bool &considerWeights,
608  const bool &inverseWeights,
609  const bool &dropIsolates);
610 
611  void writeMatrixNumberOfGeodesicsPlainText(const QString &fn,
612  const bool &considerWeights,
613  const bool &inverseWeights);
614 
615  void writeMatrixDissimilarities(const QString fileName,
616  const QString &metricStr,
617  const QString &varLocation,
618  const bool &diagonal,
619  const bool &considerWeights) ;
620 
621  void writeMatrixSimilarityMatchingPlain(const QString fileName,
622  const int &measure=METRIC_SIMPLE_MATCHING,
623  const QString &matrix = "adjacency",
624  const QString &varLocation="rows",
625  const bool &diagonal=false,
626  const bool &considerWeights=true);
627 
628  void writeMatrixSimilarityMatching(const QString fileName,
629  const QString &measure="Simple",
630  const QString &matrix = "adjacency",
631  const QString &varLocation="rows",
632  const bool &diagonal=false,
633  const bool &considerWeights=true);
634 
635 
636  void writeMatrixSimilarityPearson(const QString fileName,
637  const bool considerWeights,
638  const QString &matrix = "adjacency",
639  const QString &varLocation="rows",
640  const bool &diagonal=false);
641 
642  void writeMatrixSimilarityPearsonPlainText(const QString fileName,
643  const bool considerWeights,
644  const QString &matrix = "adjacency",
645  const QString &varLocation="rows",
646  const bool &diagonal=false);
647 
648  void writeEccentricity(const QString, const bool considerWeights,
649  const bool inverseWeights, const bool dropIsolates);
650 
651  // friend QTextStream& operator << (QTextStream& os, Graph& m);
652 
653  void writeCentralityDegree(const QString,
654  const bool weights,
655  const bool dropIsolates);
656  void writeCentralityCloseness(const QString,
657  const bool weights,
658  const bool inverseWeights,
659  const bool dropIsolates);
660  void writeCentralityClosenessInfluenceRange(const QString,
661  const bool weights,
662  const bool inverseWeights,
663  const bool dropIsolates);
664  void writeCentralityBetweenness(const QString,
665  const bool weights,
666  const bool inverseWeights,
667  const bool dropIsolates);
668  void writeCentralityPower(const QString,
669  const bool weigths,
670  const bool inverseWeights,
671  const bool dropIsolates);
672  void writeCentralityStress(const QString,
673  const bool weigths,
674  const bool inverseWeights,
675  const bool dropIsolates);
676  void writeCentralityEccentricity(const QString,
677  const bool weigths,
678  const bool inverseWeights,
679  const bool dropIsolates);
680  void writeCentralityInformation(const QString,
681  const bool weigths,
682  const bool inverseWeights);
683  void writeCentralityEigenvector(const QString,
684  const bool &weigths=true,
685  const bool &inverseWeights = false,
686  const bool &dropIsolates=false);
687  void writePrestigeDegree(const QString, const bool weights,
688  const bool dropIsolates);
689  void writePrestigeProximity(const QString, const bool weights,
690  const bool inverseWeights,
691  const bool dropIsolates);
692  void writePrestigePageRank(const QString, const bool Isolates=false);
693 
694 
695  void writeClusteringHierarchical(const QString &fileName,
696  const QString &matrix = "Adjancency",
697  const QString &metric = "Manhattan",
698  const QString &method = "Complete",
699  const bool &diagonal = false,
700  const bool &dendrogram = false,
701  const bool &considerWeights=true,
702  const bool &inverseWeights=false,
703  const bool &dropIsolates=false);
704 
705  void writeClusteringHierarchicalResultsToStream(QTextStream& outText,
706  const int N,
707  const bool &dendrogram = false);
708 
709  void writeCliqueCensus(
710  const QString fileName, const bool considerWeights
711  );
712 
713  void writeClusteringCoefficient(const QString, const bool);
714 
715  void writeTriadCensus(const QString, const bool);
716 
717 
718 
719 
720 
721 
722  /* DISTANCES, CENTRALITIES & PROMINENCE MEASURES */
723  int graphDistanceGeodesic(const int, const int,
724  const bool considerWeights, const bool inverseWeights);
725  int graphDiameter(const bool considerWeights, const bool inverseWeights);
726  float graphDistanceGeodesicAverage(const bool considerWeights,
727  const bool inverseWeights, const bool dropIsolates);
728  int graphConnectedness(const bool updateProgress=false) ;
729 
730  void graphMatrixDistancesCreate(const bool &computeCentralities=false,
731  const bool &considerWeights=false,
732  const bool &inverseWeights=true,
733  const bool &dropIsolates=false);
734  void centralityDegree(const bool &weights=true,
735  const bool &dropIsolates=false);
736  void centralityInformation(const bool considerWeights=false,
737  const bool inverseWeights=false);
738  void centralityEigenvector(const bool &considerWeights=false,
739  const bool &inverseWeights=false,
740  const bool &dropIsolates=false);
741  void centralityClosenessIR(const bool considerWeights=false,
742  const bool inverseWeights=false,
743  const bool dropIsolates=false);
744 
745  void prestigeDegree(const bool &weights, const bool &dropIsolates=false);
746  void prestigePageRank(const bool &dropIsolates=false);
747  void prestigeProximity(const bool considerWeights=false,
748  const bool inverseWeights=false,
749  const bool dropIsolates=false);
750 
751  /* REACHABILTY AND WALKS */
752  int walksBetween(int v1, int v2,int length);
753  void graphWalksMatrixCreate(const int &vertices=0, const int &length=0,
754  const bool &updateProgress=false);
755  void writeWalksTotalMatrixPlainText(const QString &fn);
756  void writeWalksOfLengthMatrixPlainText(const QString &fn, const int &length);
757  void writeMatrixWalks (const QString &fn,
758  const int &length=0,
759  const bool &simpler=false);
760  int reachable(const int &v1, const int &v2) ;
761  QList<int> vertexinfluenceRange(int v1);
762  QList<int> vertexinfluenceDomain(int v2);
763 
764  void writeReachabilityMatrixPlainText(const QString &fn, const bool &dropIsolates=false);
765 
766 
767  float numberOfTriples(int v1);
768 
769  /* CLIQUES, CLUSTERING, TRIADS */
770  void graphCliques(QSet<int> R=QSet<int>(), QSet<int> P=QSet<int>(), QSet<int> X=QSet<int>() );
771  void graphCliqueAdd (const QList<int> &clique);
772  int graphCliquesContaining(const int &actor, const int &size=0);
773  int graphCliquesOfSize(const int &size );
774 
775  void graphClusteringHierarchical(Matrix &STR_EQUIV,
776  const int &metric,
777  const int &method,
778  const bool &diagonal=false,
779  const bool &diagram=false,
780  const bool &considerWeights=true,
781  const bool &inverseWeights=false,
782  const bool &dropIsolates=false);
783  float clusteringCoefficientLocal(const long int &v1);
784  float clusteringCoefficient (const bool updateProgress=false);
785 
786  bool graphTriadCensus();
787  void triadType_examine_MAN_label(int, int, int, Vertex*, Vertex*, Vertex* );
788  // void eccentr_JordanCenter(); // TODO
789 
790 
791 
792  /* LAYOUTS */
793 
794  void layoutRandom();
795 
796  void layoutCircularRandom(double x0, double y0, double maxRadius);
797 
798  void layoutCircularByProminenceIndex(double x0, double y0, double maxRadius,
799  int type, const bool considerWeights,
800  const bool inverseWeights,
801  const bool dropIsolates);
802 
803  void layoutLevelByProminenceIndex(double maxWidth, double maxHeight, int type,
804  const bool considerWeights,
805  const bool inverseWeights,
806  const bool dropIsolates);
807 
808  void layoutVerticesSizeByProminenceIndex(int index,
809  const bool considerWeights,
810  const bool inverseWeights,
811  const bool dropIsolates);
812 
813  void layoutForceDirectedSpringEmbedder(const int maxIterations);
814 
815  void layoutForceDirectedFruchtermanReingold(const int maxIterations);
816 
817  void layoutForceDirectedKamadaKawai(const int maxIterations);
818 
819  /* CRAWLER */
820  void webCrawlTerminateThreads (QString reason);
821 
823  void randomizeThings();
824 
825  void randomNetErdosCreate ( const int &vert,
826  const QString &model,
827  const int &edges,
828  const float &eprob,
829  const QString &mode,
830  const bool &diag);
831 
832  void randomNetRingLatticeCreate (const int &vert, const int &degree,
833  const bool updateProgress=false);
834 
835  void randomNetRegularCreate (const int &vert,
836  const int &degree,
837  const QString &mode,
838  const bool &diag);
839 
840  void randomNetScaleFreeCreate (const int &n,
841  const int &power,
842  const int &m0,
843  const int &m,
844  const float &alpha,
845  const QString &mode);
846 
847  void randomNetSmallWorldCreate(const int &vert, const int &degree,
848  const double &beta, const QString &mode);
849 
850  int factorial (int);
851 
852 
859 
860  // Stores the number of vertices at distance n from a given vertex
862 
863  /* maps have O(logN) lookup complexity */
864  /* Consider using tr1::hashmap which has O(1) lookup, but this is not ISO C++ yet :( */
865 
866 
867 protected:
868  // Called from nodeMovement when a timerEvent occurs
869  void timerEvent(QTimerEvent *event);
870 
871 
872 private:
873 
878  Vertices m_graph;
879 
880  Parser *file_parser; //file loader threaded class.
881 
884 
886  void vertexAdd ( const int &v1, const int &val, const int &size,
887  const QString &color, const QString &numColor,
888  const int &numSize, const QString &label,
889  const QString &labelColor, const int &labelSize,
890  const QPointF &p, const QString &shape );
891 
892  void edgeAdd (const int &v1, const int &v2, const float &weight,
893  const int &type,
894  const QString &label,
895  const QString &color
896  );
897 
899  void BFS(const int &s, const bool &computeCentralities=false,
900  const bool &dropIsolates=false);
901  void dijkstra(const int &s, const bool &computeCentralities=false,
902  const bool &inverseWeights=false,
903  const bool &dropIsolates=false);
904  void minmax(
905  float C, Vertex *v, float &max, float &min,
906  int &maxNode, int &minNode
907  ) ;
908  void resolveClasses (float C, H_StrToInt &discreteClasses, int &classes);
909  void resolveClasses (
910  float C, H_StrToInt &discreteClasses,
911  int &classes, int name
912  );
913 
914 
915  QList<QString> m_relationsList;
916  QList<int> triadTypeFreqs; //stores triad type frequencies
917  QList<int> m_isolatedVerticesList,m_verticesList, m_graphFileFormatExportSupported;
918  QSet<int> m_verticesSet;
919  QList<SelectedEdge> m_selectedEdges;
920  QList<int> m_selectedVertices;
921  QHash <int, int> influenceRanges, influenceDomains;
922  QHash <int, int> m_vertexPairsNotConnected;
924 
925  QMap <int, L_int > m_cliques;
926 
927  QList <float> m_clusteringLevel;
928  QMap <int, V_int> m_clustersPerSequence;
929 
930 
931  QMap<QString, V_int> m_clustersByName;
932  QMap<int, V_str> m_clusterPairNamesPerSeq;
933 
934  Matrix TM, DM, sumM, invAM, AM, invM;
935  Matrix XM, XSM, XRM, CLQM;
936 
937  stack<int> Stack;
938 
940  H_StrToInt discreteDPs, discreteSDCs, discreteCCs, discreteBCs, discreteSCs;
941  H_StrToInt discreteIRCCs, discreteECs, discreteEccentricities;
942  H_StrToInt discretePCs, discreteICs, discretePRPs, discretePPs, discreteEVCs;
943 
944  int m_precision, m_fieldWidth, m_curRelation, m_fileFormat, m_vertexClicked;
946  float edgeWeightTemp, edgeReverseWeightTemp;
947  float meanSDC, varianceSDC;
948  float meanSCC, varianceSCC;
949  float meanIRCC, varianceIRCC;
950  float meanSBC, varianceSBC;
951  float meanSSC, varianceSSC;
952  float meanEC, varianceEC;
953  float meanSPC, varianceSPC;
954  float meanIC, varianceIC;
955  float meanEVC, varianceEVC;
956  float meanSDP, varianceSDP;
957  float meanPP, variancePP;
958  float meanPRP, variancePRP;
959  float minEccentricity, maxEccentricity, sumEccentricity;
960  float minSDP, maxSDP, sumDP, sumSDP, groupDP;
961  float minSDC, maxSDC, sumDC, sumSDC, groupDC;
962  float minSCC, maxSCC, nomSCC, denomSCC, sumCC, sumSCC, groupCC, maxIndexCC;
963  float minIRCC, maxIRCC, nomIRCC, denomIRCC, sumIRCC, groupIRCC;
964  float minSBC, maxSBC, nomSBC, denomSBC, sumBC, sumSBC, groupSBC, maxIndexBC;
965  float minSPC, maxSPC, nomSPC, denomSPC, t_sumIC, sumSPC, groupSPC, maxIndexPC;
966  float minSSC, maxSSC, sumSC, sumSSC, groupSC, maxIndexSC;
967  float minEC, maxEC, nomEC, denomEC, sumEC, groupEC, maxIndexEC;
968  float minIC, maxIC, nomIC, denomIC, sumIC, maxIndexIC;
969  float minEVC, maxEVC, nomEVC, denomEVC, sumEVC, sumSEVC, groupEVC;
970  float minPRP, maxPRP, nomPRC, denomPRC, sumPC, t_sumPRP, sumPRP;
971  float minPP, maxPP, nomPP, denomPP, sumPP, groupPP;
972 
973  float minCLC, maxCLC, averageCLC,varianceCLC, d_factor;
974  int maxNodeCLC, minNodeCLC;
975  int classesSDP, maxNodeDP, minNodeDP;
976  int classesSDC, maxNodeSDC, minNodeSDC;
977  int classesSCC, maxNodeSCC, minNodeSCC;
978  int classesIRCC, maxNodeIRCC, minNodeIRCC;
979  int classesSBC, maxNodeSBC, minNodeSBC;
980  int classesSPC, maxNodeSPC, minNodeSPC;
981  int classesSSC, maxNodeSSC, minNodeSSC;
982  int classesEC, maxNodeEC, minNodeEC;
983  int classesEccentricity, maxNodeEccentricity, minNodeEccentricity;
984  int classesIC, maxNodeIC, minNodeIC;
985  int classesPRP, maxNodePRP, minNodePRP;
986  int classesPP, maxNodePP, minNodePP;
987  int classesEVC, maxNodeEVC, minNodeEVC;
989 
993  long int m_totalVertices, m_totalEdges, m_graphDiameter, initVertexSize;
994  int initVertexLabelSize, initVertexNumberSize;
995  int initVertexNumberDistance, initVertexLabelDistance;
996  bool order, initVertexLabelsVisibility,initVertexNumbersVisibility;
997  bool initVertexNumberInside, initEdgeWeightNumbers, initEdgeLabels;
998  float m_graphAverageDistance, m_graphGeodesicsCount;
1001  int outboundEdgesVert, inboundEdgesVert, reciprocalEdgesVert;
1002  int timerId, canvasWidth, canvasHeight;
1004  bool calculatedVertices, calculatedVerticesList, calculatedVerticesSet;
1005  bool calculatedAdjacencyMatrix, calculatedDistances, calculatedCentralities;
1008  bool calculatedDP, calculatedDC, calculatedPP;
1009  bool calculatedIRCC, calculatedIC, calculatedPRP;
1011  bool calculatedGraphSymmetry, calculatedGraphDensity, calculatedGraphWeighted;
1012  bool m_undirected, m_symmetric, m_isWeighted;
1013 
1014  QString VERSION, fileName, m_graphName, initEdgeColor, initVertexColor,
1015  initVertexNumberColor, initVertexLabelColor, initVertexShape;
1016  QString htmlHead, htmlHeadLight, htmlEnd;
1017 
1018  QDateTime actualDateTime;
1019 };
1020 
1021 #endif
1022 
static const int CLUSTERING_SINGLE_LINKAGE
Definition: graph.h:75
static const int MATRIX_REACHABILITY
Definition: graph.h:90
int minNodeCLC
Definition: graph.h:974
Definition: webcrawler.h:67
static const int GRAPH_CHANGED_VERTICES_METADATA
Definition: graph.h:67
static const int FILE_TWOMODE
Definition: graph.h:61
WebCrawler_Parser * wc_parser
Definition: graph.h:882
QList< Vertex * > Vertices
Definition: graph.h:100
QList< int > triadTypeFreqs
Definition: graph.h:916
float t_sumIC
Definition: graph.h:965
static const int FILE_UNRECOGNIZED
Definition: graph.h:62
GraphDistance(int t, int dist)
Definition: graph.h:133
int minNodeDP
Definition: graph.h:975
static const int MATRIX_DISTANCES
Definition: graph.h:85
static const int SUBGRAPH_CLIQUE
Definition: graph.h:79
WebCrawler_Spider * wc_spider
Definition: graph.h:883
bool calculatedIsolates
Definition: graph.h:1006
int distance
Definition: graph.h:131
static const int MATRIX_DISTANCES_JACCARD
Definition: graph.h:95
static const int FILE_PAJEK
Definition: graph.h:54
bool calculatedGraphWeighted
Definition: graph.h:1011
static const int GRAPH_CHANGED_NEW
Definition: graph.h:73
The Graph class This is the main class for a Graph, used in conjuction with Vertex, Parser and Matrix objects. Graph class methods are the interface to various analysis 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.
Definition: graph.h:192
QList< int > m_verticesList
Definition: graph.h:917
QHash< QString, int > H_StrToInt
Definition: graph.h:105
Definition: graph.h:142
float varianceIC
Definition: graph.h:954
float varianceSDP
Definition: graph.h:956
QVector< int > V_int
Definition: graph.h:112
QList< int > m_selectedVertices
Definition: graph.h:920
float sumIRCC
Definition: graph.h:963
static const int GRAPH_CHANGED_EDGES
Definition: graph.h:71
H_StrToInt discretePRPs
Definition: graph.h:942
QThread wc_spiderThread
Definition: graph.h:196
static const int FILE_UCINET
Definition: graph.h:57
float sumSDC
Definition: graph.h:961
static const int SUBGRAPH_CYCLE
Definition: graph.h:81
float variancePP
Definition: graph.h:957
int minNodePRP
Definition: graph.h:985
float varianceSPC
Definition: graph.h:953
int v2
Definition: graph.h:119
Vertices m_graph
Definition: graph.h:878
static const int FILE_GRAPHVIZ
Definition: graph.h:56
float variancePRP
Definition: graph.h:958
QString htmlHeadLight
Definition: graph.h:1016
bool calculatedTriad
Definition: graph.h:1010
static const int GRAPH_CHANGED_VERTICES
Definition: graph.h:70
QString VERSION
Definition: graph.h:1014
QThread file_parserThread
Definition: graph.h:194
Definition: graph.h:117
H_StrToInt discreteIRCCs
Definition: graph.h:941
QPair< int, pair_f_b > rel_w_bool
Definition: graph.h:108
static const int EDGE_DIRECTED
Definition: graph.h:49
bool calculatedDistances
Definition: graph.h:1005
float t_sumPRP
Definition: graph.h:970
int minNodeSSC
Definition: graph.h:981
bool order
Definition: graph.h:996
QDateTime actualDateTime
Definition: graph.h:1018
bool calculatedVerticesSet
Definition: graph.h:1004
QList< QString > m_relationsList
Definition: graph.h:915
Definition: webcrawler.h:40
static const int MATRIX_DEGREE
Definition: graph.h:86
Parser * file_parser
Definition: graph.h:880
float varianceCLC
Definition: graph.h:973
static const int MATRIX_GEODESICS
Definition: graph.h:89
static const int GRAPH_CHANGED_EDGES_METADATA
Definition: graph.h:68
H_StrToInt discreteSDCs
Definition: graph.h:940
int minNodeEC
Definition: graph.h:982
int minNodeSCC
Definition: graph.h:977
QPair< float, bool > pair_f_b
Definition: graph.h:107
stack< int > Stack
Definition: graph.h:937
float varianceEC
Definition: graph.h:952
int sizeOfComponent
Definition: graph.h:988
float sumSDP
Definition: graph.h:960
int target
Definition: graph.h:130
static const int FILE_EDGELIST_SIMPLE
Definition: graph.h:60
QHash< QString, bool > H_StrToBool
Definition: graph.h:110
static const int FILE_ADJACENCY
Definition: graph.h:55
pair< int, int > SelectedEdge
Definition: graph.h:124
float sumSCC
Definition: graph.h:962
static const int MATRIX_LAPLACIAN
Definition: graph.h:87
ClickedEdge m_clickedEdge
Definition: graph.h:945
int minNodeSDC
Definition: graph.h:976
QHash< int, int > influenceRanges
Definition: graph.h:921
Definition: graph.h:127
float m_graphGeodesicsCount
Definition: graph.h:998
H_Int sizeOfNthOrderNeighborhood
Definition: graph.h:861
static const QString VERSION
Definition: mainwindow.h:54
void setSocNetV_Version(QString ver)
Definition: graph.h:359
long int m_totalVertices
Definition: graph.h:993
static const int SUBGRAPH_STAR
Definition: graph.h:80
float varianceSSC
Definition: graph.h:951
static const int MATRIX_DISTANCES_EUCLIDEAN
Definition: graph.h:93
static const int FILE_GML
Definition: graph.h:58
static const int SUBGRAPH_LINE
Definition: graph.h:82
bool initVertexNumberInside
Definition: graph.h:997
int minNodeIC
Definition: graph.h:984
QList< int > L_int
Definition: graph.h:111
float sumPP
Definition: graph.h:971
static const int GRAPH_CHANGED_NONE
Definition: graph.h:65
QSet< int > m_verticesSet
Definition: graph.h:918
float sumIC
Definition: graph.h:968
static const int CLUSTERING_COMPLETE_LINKAGE
Definition: graph.h:76
int minNodeEVC
Definition: graph.h:987
float varianceSDC
Definition: graph.h:947
static const int MATRIX_COCITATION
Definition: graph.h:92
float varianceIRCC
Definition: graph.h:949
QHash< int, int > m_vertexPairsNotConnected
Definition: graph.h:922
static const int CLUSTERING_AVERAGE_LINKAGE
Definition: graph.h:77
Definition: matrix.h:128
int graphModifiedFlag
Definition: graph.h:992
Matrix TM
Definition: graph.h:934
int minNodeSBC
Definition: graph.h:979
int reciprocalEdgesVert
Definition: graph.h:1001
int minNodeEccentricity
Definition: graph.h:983
static const int FILE_EDGELIST_WEIGHTED
Definition: graph.h:59
float sumEC
Definition: graph.h:967
static const int MATRIX_DISTANCES_CHEBYSHEV
Definition: graph.h:97
static const int FILE_GRAPHML
Definition: graph.h:53
QList< SelectedEdge > m_selectedEdges
Definition: graph.h:919
float varianceSCC
Definition: graph.h:948
float sumEccentricity
Definition: graph.h:959
QHash< long int, long int > H_Int
Definition: graph.h:106
bool calculatedPP
Definition: graph.h:1008
int initVertexNumberSize
Definition: graph.h:994
float sumSBC
Definition: graph.h:964
bool calculatedPRP
Definition: graph.h:1009
bool operator()(GraphDistance &t1, GraphDistance &t2)
Definition: graph.h:144
QVector< QString > V_str
Definition: graph.h:113
QMap< QString, V_int > m_clustersByName
Definition: graph.h:931
QMap< int, V_str > m_clusterPairNamesPerSeq
Definition: graph.h:932
static const int GRAPH_CHANGED_MINOR_OPTIONS
Definition: graph.h:66
float edgeWeightTemp
Definition: graph.h:946
int v1
Definition: graph.h:118
float sumSSC
Definition: graph.h:966
int m_vertexClicked
Definition: graph.h:944
int minNodeSPC
Definition: graph.h:980
int minNodePP
Definition: graph.h:986
float sumSEVC
Definition: graph.h:969
static const int MATRIX_DISTANCES_HAMMING
Definition: graph.h:96
QThread wc_parserThread
Definition: graph.h:195
int minNodeIRCC
Definition: graph.h:978
QMap< int, L_int > m_cliques
Definition: graph.h:925
int m_graphConnectedness
Definition: graph.h:1000
QHash< int, rel_w_bool > H_edges
Definition: graph.h:109
float varianceSBC
Definition: graph.h:950
Matrix XSM
Definition: graph.h:935
static const int MATRIX_DISTANCES_MANHATTAN
Definition: graph.h:94
static const int MATRIX_ADJACENCY
Definition: graph.h:84
QList< float > m_clusteringLevel
Definition: graph.h:927
float m_graphDensity
Definition: graph.h:999
static const int GRAPH_CHANGED_VERTICES_AND_EDGES
Definition: graph.h:72
static const int MATRIX_ADJACENCY_INVERSE
Definition: graph.h:88
static const int EDGE_DIRECTED_OPPOSITE_EXISTS
Definition: graph.h:50
static const int MATRIX_ADJACENCY_TRANSPOSE
Definition: graph.h:91
H_Int index
Definition: graph.h:858
bool calculatedEdges
Definition: graph.h:1003
int timerId
Definition: graph.h:1002
int initVertexNumberDistance
Definition: graph.h:995
static const int EDGE_RECIPROCAL_UNDIRECTED
Definition: graph.h:51
The Parser class Main class for network file parsing and loading Supports GraphML, Pajek, Adjacency, Graphviz, UCINET, EdgeLists etc.
Definition: parser.h:78
QMap< int, V_int > m_clustersPerSequence
Definition: graph.h:928
float varianceEVC
Definition: graph.h:955
bool calculatedEVC
Definition: graph.h:1007
static const int GRAPH_CHANGED_POSITIONS
Definition: graph.h:69
QHash< int, int > m_vertexPairsUnilaterallyConnected
Definition: graph.h:923
Definition: vertex.h:52
static const int METRIC_SIMPLE_MATCHING
Definition: matrix.h:51
bool m_undirected
Definition: graph.h:1012