Skip to content
GSQL Graph Algorithms
Shell
Branch: master
Clone or download
Latest commit 940cf85 Sep 25, 2019
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
algorithms fix install Sep 24, 2019
tests update Aug 1, 2019
LICENSE Update LICENSE Jun 5, 2019
README.algorithms Update README.algorithms Sep 12, 2019

README.algorithms

README for GSQL Algorithm Library
9/12/19

The GSQL Graph Algorithm Library is a collection of high-performance GSQL queries,
each of which implements a standard graph algorithm. Each algorithm is ready to be
installed and used, either as a stand-alone query or as a building block of a larger
analytics application.GSQL running on the TigerGraph platform is particularly
well-suited for graph algorithms:

* Turing-complete with full support for imperative and procedural programming,
 ideal for algorithmic computation.

* Parallel and Distributed Processing, enabling computations on larger graphs.

* User-Extensible.
  Because the algorithms are written in standard GSQL and compiled by the user,
  they are easy to modify and customize.

* Open-Source. Users can study the GSQL implementations to learn by
  example, and they can develop and submit additions to the library.


Compatibility
-----------------
v1.2 compatible with TG2.4 or higher
v1.1 compatible with TG2.4 or higher

Library Structure
-----------------

You can download the library from github:
https://github.com/tigergraph/gsql-graph-algorithms

The library contains two main sections: Algorithms and Tests.

The Algorithms folder contains template algorithms and scripts to help you customize
and install them. There are two folders:
	templates/
		 contains template algorithms with some placeholder code
		and markers which need to be acted on by the installation script.

	examples/
		contains GSQL queries generated from the templates by the installation script.

The Tests folder contains small sample graphs that you can use to experiment with the
algorithms. In our online documentation, we use the test graphs to show you the expected
result for each algorithm. The graphs are small enough that you can manually calculate
and sometimes intuitively see what the answers should be.

Get Started
-----------
If you want to use one of the test graphs, load it before installing the algorithms:
See the README.test file in the tests folder


* Install Algorithms:
1) You should create a graph schema in GSQL first.
2) Change into the algorithms folder.
3) Run a installation script, i.e.,
   bash install.sh
   and answer the questions.

More detailed documentation and examples are available on the web at
https://docs.tigergraph.com/graph-algorithm-library



List of GSQL Graph Algorithms
-----------------------------
as of Sept 5, 2019
Compatible with TigerGraph version 2.1.8 or higher

closeness_cent                  Closeness Centrality
conn_comp                       Connected Component Detection
scc				Strongly Connected Component Detection
label_prop                      Label Propagation Method for Community Detection
louvain_parallel                Parallel Louvain Modularity Method with Refinement for Community Detection
pageRank                        PageRank measurement of relative influence of each vertex
pageRank_wt                     Weighted PageRank
pageRank_pers                   Personalized PageRank
shortest_ss_no_wt               Single-Source Shortest Paths without weight
shortest_ss_pos_wt              Single-Source Shortest Paths with positive weight
shortest_ss_any_wt              Single-Source Shortest Paths
mst                             Minimum Spanning Tree (MST)
cycle_detection                 Rocha–Thatte algorithm for cycle detection
tri_count                       Count all the triangles, memory effient
tri_count_fast                  Count all the triangles, faster but using more memory
cosine_nbor_ss                  Cosine Similarity from a single vertex
cosine_nbor_ap                  Cosine Similarity for each pair of vertices
jaccard_nbor_ss                 Jaccard Similarity from a single vertex
jaccard_nbor_ap                 Jaccard Similarity for each pair of vertices
knn_cosine_ss			k-Nearest Neighbor classification, using Cosine Similarity, single source
knn_cosine_all			k-Nearest Neighbor classification, using Cosine Similarity, batch
knn_cosine_cv			Cross validation for k-Nearest Neighbor, using Cosine Similarity

Each of the above  may be available as 2 or 3 related queries
For example:

pageRank.gsql - base version. Results are provided as JSON output.
		Not persisted to the graph database.

pageRank_file.gsql - Results are in CSV format to a file.
		Not persisted to the graph database.

pageRank_attr.gsql - Results are written to vertex or edge attributes
		which the user specifies.


You can’t perform that action at this time.