graph-analysis-tool/basicstat.cpp at master · tkim-snu/graph-analysis-tool · GitHub

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
#include "basicstat.h"

namespace snu {

	void basicStat(DSGraph& graph, StatResult& result) {
		long long n = graph.id_to_vertex.size();
		long long m = graph.id_to_edge.size();

		result.size = n;
		result.volume = m;
		result.num_vlabel = graph.vlabel_to_class.size();
		result.num_elabel = graph.elabel_to_class.size();
		result.density = (double) m / (n * n); // assume there is loop

		long long max_indegree = 0;
		long long max_outdegree = 0;
		for(auto it = graph.id_to_vertex.begin(); it != graph.id_to_vertex.end(); it++) {
			max_indegree = std::max(max_indegree, it->second->indegree);
			max_outdegree = std::max(max_outdegree, (long long)it->second->edges.size());
		}
		result.max_indegree = max_indegree;
		result.max_outdegree = max_outdegree;

		long long max_vlabel_size = 0;
		for(auto it = graph.vlabel_to_class.begin(); it != graph.vlabel_to_class.end(); it++)
			max_vlabel_size = std::max(max_vlabel_size, (long long)it->second->vertices.size());
		result.max_vlabel_size = max_vlabel_size;

		long long max_elabel_size = 0;
		for(auto it = graph.elabel_to_class.begin(); it != graph.elabel_to_class.end(); it++)
			max_elabel_size = std::max(max_elabel_size, (long long)it->second->edges.size());
		result.max_elabel_size = max_elabel_size;

		long long cycle_count = 0;
		for(auto it = graph.id_to_edge.begin(); it != graph.id_to_edge.end(); it++) {
			Graph::Vid from = it->second->from->id;
			Graph::Vid to = it->second->to->id;
			if(graph.is_connected.count(std::make_pair(to, from)))
				cycle_count++;
		}
		result.reciprocity = (double) cycle_count / m;

		result.negativity = (double) graph.negative_edge_num / m;

		result.basicstat = true;
	}

	void basicStat(USGraph& graph, StatResult& result) {
		long long n = graph.id_to_vertex.size();
		long long m = graph.id_to_edge.size();

		result.size = n; // n
		result.volume = m; // m
		result.num_vlabel = graph.vlabel_to_class.size();
		result.num_elabel = graph.elabel_to_class.size();
		result.density = 2.0 * m / (n * (n + 1)); // assume there is loop
		result.avg_degree = 2.0 * m / n; // 2 * m / n

		long long max_degree = 0;
		for(auto it = graph.id_to_vertex.begin(); it != graph.id_to_vertex.end(); it++)
			max_degree = std::max(max_degree, it->second->indegree); // indegree == outdegree
		result.max_degree = max_degree;

		long long max_vlabel_size = 0;
		for(auto it = graph.vlabel_to_class.begin(); it != graph.vlabel_to_class.end(); it++)
			max_vlabel_size = std::max(max_vlabel_size, (long long)it->second->vertices.size());
		result.max_vlabel_size = max_vlabel_size;

		long long max_elabel_size = 0;
		for(auto it = graph.elabel_to_class.begin(); it != graph.elabel_to_class.end(); it++)
			max_elabel_size = std::max(max_elabel_size, (long long)it->second->edges.size());
		result.max_elabel_size = max_elabel_size;

		result.negativity = (double) graph.negative_edge_num / m;

		result.basicstat = true;
	}
}