Algorithms
OneSparse leverages the SuiteSparse GraphBLAS library and the
LAGraph suite of graph algorithms and integrates them with
Postgres. Using SuiteSparse's state of the art Sparse Linear
Algebra Just-In-Time (JIT) compiled kernels, OneSparse can leverage
CPUs, GPUs, and any future architectures without you having to
re-target your code.
The algorithms shown here come from the LAGraph library, they are
already complete and well tested implementations of common graph
algorithms. The algorithms shown here are just the beginning,
there are many more to come, including versions that leverage CUDA
GPUs.
Example Graphs
To show off the algorithms we will need some sample graphs. There
are multiple ways to construct graphs in OneSparse.
From a Matrix Market file
The SuiteSparse Matrix Collection
contains many graphs of all different shapes and sizes and
publishes them in the Matrix Market format. The "karate" graph
shown here is a common test graph for documentation purposes.
Let's load the graph into a materialized view to make its use from
SQL very easy:
create materialized view karate as select mmread ( '/home/postgres/onesparse/demo/karate.mtx' ) as graph ;
select draw ( triu ( graph ),
reduce_cols ( cast_to ( graph , 'int32' )),
false , false , true , 0.5 , 'The Karate Graph' )
as draw_source from karate \gset
%3
The Karate Graph
0
0 : 16
1
1 : 9
0--1
2
2 : 10
0--2
3
3 : 6
0--3
4
4 : 3
0--4
5
5 : 4
0--5
6
6 : 4
0--6
7
7 : 4
0--7
8
8 : 5
0--8
10
10 : 3
0--10
11
11 : 1
0--11
12
12 : 2
0--12
13
13 : 5
0--13
17
17 : 2
0--17
19
19 : 3
0--19
21
21 : 2
0--21
31
31 : 6
0--31
1--2
1--3
1--7
1--13
1--17
1--19
1--21
30
30 : 4
1--30
2--3
2--7
2--8
9
9 : 2
2--9
2--13
27
27 : 4
2--27
28
28 : 3
2--28
32
32 : 12
2--32
3--7
3--12
3--13
4--6
4--10
5--6
5--10
16
16 : 2
5--16
6--16
8--30
8--32
33
33 : 17
8--33
9--33
13--33
14
14 : 2
14--32
14--33
15
15 : 2
15--32
15--33
18
18 : 2
18--32
18--33
19--33
20
20 : 2
20--32
20--33
22
22 : 2
22--32
22--33
23
23 : 5
25
25 : 3
23--25
23--27
29
29 : 4
23--29
23--32
23--33
24
24 : 3
24--25
24--27
24--31
25--31
26
26 : 2
26--29
26--33
27--33
28--31
28--33
29--32
29--33
30--32
30--33
31--32
31--33
32--33
Matrix Aggregation
Graph an be constructed by aggregating an adjacency matrix with
matrix_agg:
create table edge_data (
i bigint ,
j bigint ,
v integer
);
insert into edge_data (i, j, v) values (1, 2, 3), (1, 3, 4), (2, 3, 1), (3, 1, 8);
create materialized view edge_data_view as
select matrix_agg(i, j, v) as graph from edge_data;
select draw(triu(graph),
reduce_cols(one(graph)),
false, true, true, 0.5)
as draw_source from edge_data_view \gset
%3
1
1 : 2
2
2 : 1
1->2
3
3 : 1
1->3
2->3
SQL Queries
Random Graphs
We'll use some random weighted graphs for demonstration purposes as
well, one directed and one undirected.
create materialized view rgraph as select triu ( random_matrix ( 8 , 8 , 28 , 1 , 10 , false , 0.22 ), 1 ) > 0 as graph ;
create materialized view urgraph as select random_matrix(8, 8, 28, 1, 10, true, 0.22) > 0 as graph;
select draw(triu(graph), reduce_cols(one(graph)), true, true, true, 0.5, 'Random Weighted Directed Graph') as col_a_source from rgraph \gset
select draw(triu(graph), reduce_cols(one(graph)), true, false, true, 0.5, 'Random Weighted Undirected Graph') as col_b_source from urgraph \gset
%3
Random Weighted Directed Graph
0
0 : 3
3
3 : 3
0->3
7
6
6 : 1
0->6
3
7
7
0->7
9
1
1 : 4
2
2 : 2
1->2
3
5
5 : 2
1->5
4
1->6
7
1->7
10
2->5
9
2->7
10
4
4 : 1
3->4
5
3->5
6
3->7
7
4->7
5
5->6
2
5->7
9
6->7
1
%3
Random Weighted Undirected Graph
0
0 : 6
1
1 : 5
0--1
4
2
2 : 5
0--2
9
3
3 : 4
0--3
7
5
5 : 7
0--5
1
6
6 : 4
0--6
1
7
7 : 7
0--7
5
1--2
3
1--5
4
1--6
3
1--7
10
4
4 : 4
2--4
8
2--5
4
2--7
10
3--4
7
3--5
9
3--7
9
4--5
8
4--7
5
5--6
2
5--7
9
6--7
1
Level BFS
Level BFS exposes the depth of each vertex starting from a
given source vertex using the breadth-first search algorithm.
See https://en.wikipedia.org/wiki/Breadth-first_search for details.
select draw ( triu ( graph ), ( select level from bfs ( graph , 1 )), false , false , true , 0.5 ) as col_a_source from karate \gset
select draw ( triu ( graph ), ( select level from bfs ( graph , 1 )), false , false , true , 0.5 ) as col_b_source from urgraph \gset
%3
0
0 : 1
1
1 : 0
0--1
2
2 : 1
0--2
3
3 : 1
0--3
4
4 : 2
0--4
5
5 : 2
0--5
6
6 : 2
0--6
7
7 : 1
0--7
8
8 : 2
0--8
10
10 : 2
0--10
11
11 : 2
0--11
12
12 : 2
0--12
13
13 : 1
0--13
17
17 : 1
0--17
19
19 : 1
0--19
21
21 : 1
0--21
31
31 : 2
0--31
1--2
1--3
1--7
1--13
1--17
1--19
1--21
30
30 : 1
1--30
2--3
2--7
2--8
9
9 : 2
2--9
2--13
27
27 : 2
2--27
28
28 : 2
2--28
32
32 : 2
2--32
3--7
3--12
3--13
4--6
4--10
5--6
5--10
16
16 : 3
5--16
6--16
8--30
8--32
33
33 : 2
8--33
9--33
13--33
14
14 : 3
14--32
14--33
15
15 : 3
15--32
15--33
18
18 : 3
18--32
18--33
19--33
20
20 : 3
20--32
20--33
22
22 : 3
22--32
22--33
23
23 : 3
25
25 : 3
23--25
23--27
29
29 : 3
23--29
23--32
23--33
24
24 : 3
24--25
24--27
24--31
25--31
26
26 : 3
26--29
26--33
27--33
28--31
28--33
29--32
29--33
30--32
30--33
31--32
31--33
32--33
%3
0
0 : 1
1
1 : 0
0--1
2
2 : 1
0--2
3
3 : 2
0--3
5
5 : 1
0--5
6
6 : 1
0--6
7
7 : 1
0--7
1--2
1--5
1--6
1--7
4
4 : 2
2--4
2--5
2--7
3--4
3--5
3--7
4--5
4--7
5--6
5--7
6--7
Parent BFS
Parent BFS returns the predecessor of each vertex in the
BFS tree rooted at the chosen source. It is also based on
https://en.wikipedia.org/wiki/Breadth-first_search .
select draw ( triu ( graph ), ( select parent from bfs ( graph , 1 )), false , false , true , 0.5 ) as col_a_source from karate \gset
select draw ( triu ( graph ), ( select parent from bfs ( graph , 1 )), false , false , true , 0.5 ) as col_b_source from urgraph \gset
%3
0
0 : 1
1
1 : 1
0--1
2
2 : 1
0--2
3
3 : 1
0--3
4
4 : 0
0--4
5
5 : 0
0--5
6
6 : 0
0--6
7
7 : 1
0--7
8
8 : 0
0--8
10
10 : 0
0--10
11
11 : 0
0--11
12
12 : 0
0--12
13
13 : 1
0--13
17
17 : 1
0--17
19
19 : 1
0--19
21
21 : 1
0--21
31
31 : 0
0--31
1--2
1--3
1--7
1--13
1--17
1--19
1--21
30
30 : 1
1--30
2--3
2--7
2--8
9
9 : 2
2--9
2--13
27
27 : 2
2--27
28
28 : 2
2--28
32
32 : 2
2--32
3--7
3--12
3--13
4--6
4--10
5--6
5--10
16
16 : 5
5--16
6--16
8--30
8--32
33
33 : 13
8--33
9--33
13--33
14
14 : 32
14--32
14--33
15
15 : 32
15--32
15--33
18
18 : 32
18--32
18--33
19--33
20
20 : 32
20--32
20--33
22
22 : 32
22--32
22--33
23
23 : 27
25
25 : 31
23--25
23--27
29
29 : 32
23--29
23--32
23--33
24
24 : 27
24--25
24--27
24--31
25--31
26
26 : 33
26--29
26--33
27--33
28--31
28--33
29--32
29--33
30--32
30--33
31--32
31--33
32--33
%3
0
0 : 1
1
1 : 1
0--1
2
2 : 1
0--2
3
3 : 0
0--3
5
5 : 1
0--5
6
6 : 1
0--6
7
7 : 1
0--7
1--2
1--5
1--6
1--7
4
4 : 2
2--4
2--5
2--7
3--4
3--5
3--7
4--5
4--7
5--6
5--7
6--7
Benchmarks
Single Source Shortest Path
select draw ( triu ( graph ), sssp ( graph , 1 :: bigint , 1 ), true , true , true , 0.5 ) as col_a_source from rgraph \gset
select draw ( triu ( graph ), sssp ( graph , 1 :: bigint , 1 ), true , false , true , 0.5 ) as col_b_source from urgraph \gset
%3
0
0 : 2147
3
3 : 2147
0->3
7
6
6 : 6
0->6
3
7
7 : 7
0->7
9
1
1 : 0
2
2 : 3
1->2
3
5
5 : 4
1->5
4
1->6
7
1->7
10
2->5
9
2->7
10
4
4 : 2147
3->4
5
3->5
6
3->7
7
4->7
5
5->6
2
5->7
9
6->7
1
%3
0
0 : 4
1
1 : 0
0--1
4
2
2 : 3
0--2
9
3
3 : 11
0--3
7
5
5 : 4
0--5
1
6
6 : 3
0--6
1
7
7 : 4
0--7
5
1--2
3
1--5
4
1--6
3
1--7
10
4
4 : 9
2--4
8
2--5
4
2--7
10
3--4
7
3--5
9
3--7
9
4--5
8
4--7
5
5--6
2
5--7
9
6--7
1
Benchmarks
Page Rank
PageRank assigns an importance score to each vertex based on link structure.
For details see https://en.wikipedia.org/wiki/PageRank .
select draw ( triu ( graph ), pagerank ( graph ) * 100 , false , false , true , 0.5 ) as draw_source from karate \gset
%3
0
0 : 9.69
1
1 : 5.28
0--1
2
2 : 5.70
0--2
3
3 : 3.58
0--3
4
4 : 2.19
0--4
5
5 : 2.91
0--5
6
6 : 2.91
0--6
7
7 : 2.44
0--7
8
8 : 2.97
0--8
10
10 : 2.19
0--10
11
11 : 0.95
0--11
12
12 : 1.46
0--12
13
13 : 2.95
0--13
17
17 : 1.45
0--17
19
19 : 1.96
0--19
21
21 : 1.45
0--21
31
31 : 3.71
0--31
1--2
1--3
1--7
1--13
1--17
1--19
1--21
30
30 : 2.45
1--30
2--3
2--7
2--8
9
9 : 1.43
2--9
2--13
27
27 : 2.56
2--27
28
28 : 1.95
2--28
32
32 : 7.16
2--32
3--7
3--12
3--13
4--6
4--10
5--6
5--10
16
16 : 1.67
5--16
6--16
8--30
8--32
33
33 : 10.0
8--33
9--33
13--33
14
14 : 1.45
14--32
14--33
15
15 : 1.45
15--32
15--33
18
18 : 1.45
18--32
18--33
19--33
20
20 : 1.45
20--32
20--33
22
22 : 1.45
22--32
22--33
23
23 : 3.15
25
25 : 2.10
23--25
23--27
29
29 : 2.62
23--29
23--32
23--33
24
24 : 2.10
24--25
24--27
24--31
25--31
26
26 : 1.50
26--29
26--33
27--33
28--31
28--33
29--32
29--33
30--32
30--33
31--32
31--33
32--33
Benchmarks
Triangle Centrality
Triangle centrality counts the number of triangles incident to each vertex.
This measure relates to the clustering coefficient
https://en.wikipedia.org/wiki/Clustering_coefficient .
select draw ( triu ( graph ), triangle_centrality ( graph ) * 10 , false , false , true , 0.5 ) as draw_source from karate \gset
%3
0
0 : 6.74
1
1 : 5.55
0--1
2
2 : 6.44
0--2
3
3 : 4.74
0--3
4
4 : 1.85
0--4
5
5 : 2.00
0--5
6
6 : 2.00
0--6
7
7 : 4.22
0--7
8
8 : 4.81
0--8
10
10 : 1.85
0--10
11
11 : 4.00
0--11
12
12 : 2.14
0--12
13
13 : 7.55
0--13
17
17 : 2.29
0--17
19
19 : 5.62
0--19
21
21 : 2.29
0--21
31
31 : 6.51
0--31
1--2
1--3
1--7
1--13
1--17
1--19
1--21
30
30 : 5.33
1--30
2--3
2--7
2--8
9
9 : 5.77
2--9
2--13
27
27 : 4.14
2--27
28
28 : 3.85
2--28
32
32 : 4.66
2--32
3--7
3--12
3--13
4--6
4--10
5--6
5--10
16
16 : 0.51
5--16
6--16
8--30
8--32
33
33 : 5.62
8--33
9--33
13--33
14
14 : 2.14
14--32
14--33
15
15 : 2.14
15--32
15--33
18
18 : 2.14
18--32
18--33
19--33
20
20 : 2.14
20--32
20--33
22
22 : 2.14
22--32
22--33
23
23 : 2.96
25
25 : 1.25
23--25
23--27
29
29 : 2.74
23--29
23--32
23--33
24
24 : 0.59
24--25
24--27
24--31
25--31
26
26 : 1.48
26--29
26--33
27--33
28--31
28--33
29--32
29--33
30--32
30--33
31--32
31--33
32--33
Benchmarks
Betweeness Centrality
Betweenness centrality measures how often a vertex appears on shortest paths between others.
https://en.wikipedia.org/wiki/Betweenness_centrality .
select draw ( triu ( graph ), betweenness ( graph , ARRAY [ 1 , 32 ] :: bigint []), false , false , true , 0.5 ) as draw_source from karate \gset
%3
0
0 : 17.2
1
1 : 0.80
0--1
2
2 : 13.6
0--2
3
3 : 0.75
0--3
4
4 : 0.00
0--4
5
5 : 1.00
0--5
6
6 : 1.00
0--6
7
7 : 0.00
0--7
8
8 : 2.98
0--8
10
10 : 0.00
0--10
11
11 : 0.00
0--11
12
12 : 0.00
0--12
13
13 : 2.03
0--13
17
17 : 0.00
0--17
19
19 : 2.03
0--19
21
21 : 0.00
0--21
31
31 : 6.31
0--31
1--2
1--3
1--7
1--13
1--17
1--19
1--21
30
30 : 5.13
1--30
2--3
2--7
2--8
9
9 : 0.00
2--9
2--13
27
27 : 0.66
2--27
28
28 : 0.00
2--28
32
32 : 2.73
2--32
3--7
3--12
3--13
4--6
4--10
5--6
5--10
16
16 : 0.00
5--16
6--16
8--30
8--32
33
33 : 8.26
8--33
9--33
13--33
14
14 : 0.00
14--32
14--33
15
15 : 0.00
15--32
15--33
18
18 : 0.00
18--32
18--33
19--33
20
20 : 0.00
20--32
20--33
22
22 : 0.00
22--32
22--33
23
23 : 0.83
25
25 : 0.00
23--25
23--27
29
29 : 0.50
23--29
23--32
23--33
24
24 : 0.00
24--25
24--27
24--31
25--31
26
26 : 0.00
26--29
26--33
27--33
28--31
28--33
29--32
29--33
30--32
30--33
31--32
31--33
32--33
Benchmarks
Square Clustering
Calculates the square clustering coefficient for each vertex.
https://en.wikipedia.org/wiki/Clustering_coefficient .
select draw ( triu ( graph ), square_clustering ( graph ), false , false , true , 0.5 ) as draw_source from karate \gset
%3
0
0 : 0.09
1
1 : 0.17
0--1
2
2 : 0.12
0--2
3
3 : 0.21
0--3
4
4 : 0.12
0--4
5
5 : 0.09
0--5
6
6 : 0.09
0--6
7
7 : 0.30
0--7
8
8 : 0.15
0--8
10
10 : 0.12
0--10
12
12 : 0.28
0--12
13
13 : 0.19
0--13
17
17 : 0.40
0--17
19
19 : 0.16
0--19
21
21 : 0.40
0--21
31
31 : 0.09
0--31
11
11
0--11
1--2
1--3
1--7
1--13
1--17
1--19
1--21
30
30 : 0.18
1--30
2--3
2--7
2--8
9
9 : 0.25
2--9
2--13
27
27 : 0.12
2--27
28
28 : 0.16
2--28
32
32 : 0.14
2--32
3--7
3--12
3--13
4--6
4--10
5--6
5--10
16
16 : 0.33
5--16
6--16
8--30
8--32
33
33 : 0.12
8--33
9--33
13--33
14
14 : 0.56
14--32
14--33
15
15 : 0.56
15--32
15--33
18
18 : 0.56
18--32
18--33
19--33
20
20 : 0.56
20--32
20--33
22
22 : 0.56
22--32
22--33
23
23 : 0.15
25
25 : 0.17
23--25
23--27
29
29 : 0.18
23--29
23--32
23--33
24
24 : 0.12
24--25
24--27
24--31
25--31
26
26 : 0.13
26--29
26--33
27--33
28--31
28--33
29--32
29--33
30--32
30--33
31--32
31--33
32--33
