batara666
commented
4 years ago how this going, we want have visjs.org network version of this library
Closed javidhsueh closed 4 years ago
batara666
commented
4 years ago how this going, we want have visjs.org network version of this library
ibgreen
commented
4 years ago FWIW - The graph.gl effort was completed and published as a separate framework with a deck.gl layer pack under https://graph.gl/gatsby/. (I don't think it is being actively maintained though, but could be a good starting point if someone is looking at doing graphs with deck.gl.)
how this going, we want have visjs.org network version of this library
Not quite sure what you mean by that. Do you want deck.gl to duplicate the features of that library, or are you looking for an integration, or?
RFC: Graph Layer
Overview
To support exploring a large graph in the web application, we plan to build a new graph layer with Deck.gl framework. The new graph layer will enable users to render a force-directed layout graph powered by Deck.gl, and all the layout computation will be in the GPU. We also can extend the graph layer with several algorithms, ex: edge-bundling, finding the shortest path, and community detection.
Background
In the past, we've done several prototypes to visualize large graphs with Deck.gl, ex1. All of them use some third-party JS libraries to compute the force-directed layout in the CPU. The basic force-directed layout is to simulate the spring model and compute the position of nodes on each frame until the layout is stable enough. However, it's challenging to compute the layout for a large graph in most web applications due to the computation speed and limited memory in browsers. When the number of nodes/edges increases, the performance of the application will significantly drop. It becomes a bottleneck to render a large graph in web application in modern web browsers.
Target Use Cases
Force-directed layout
To render an animated force-directed graph with interactive speed, the key is to leverage the GPGPU computation power through GLSL shaders. We can implement a GPU-accelerated force-directed layout algorithm. The CPU will only do the minimum of the work on the graph and perform most computations in the GPU.
Edge bundling
Graphs depicted as node-link diagrams are widely used to show relationships between entities. However, node-link diagrams comprised of a large number of nodes and edges often suffer from visual clutter. The use of edge bundling remedies this and reveals high-level edge patterns. To bundle edges in an intuitive way without requiring a control mesh or hierarchy, we can implement the self-organizing approach that edges are modeled as flexible springs that can attract each other while node positions remain fixed. A force-directed technique is used to calculate the bundling.
Binary arrow data support
Load graph data in binary arrow format. Users can pass the binary arrow data into the GPU directly, and compute the attributes of nodes/edges in the GPU without any CPU involvement.
Shortest path
Finding the shortest path between two nodes is a very common graph theory problem. For example, given a number of cities with highways connecting them, find the shortest path from New York to Chicago. It's also often used in SNA (Social Network Analysis) to calculate betweenness centrality among others. Usually, people with the strongest bonds tend to communicate through the shortest path. A GPU-accelerated Dijkstra's shortest path algorithm can be implemented in the graph layer to find the path between two nodes in the graph.
Proposal
Start to use "Transform" from luma.gl to experiment with several graph algorithms:
To Do List