Skip to content

Latest commit

 

History

History
39 lines (31 loc) · 1.23 KB

README.md

File metadata and controls

39 lines (31 loc) · 1.23 KB
Raw

Graph Computing

Graph representation

To save memory as much as possible, and keep find the Vertex by O(1)

Based on Vertex and Edge

Edge List

  • Graph_Map_EL ——> Map<K, Vertex> vertices, Map<K, List> edges.

CSR

  • Graph_Map_CSR --> List vertices. List<List edges, Map<K, Integer> dictV

Based on K,V

Adjacency List

  • Graph_CSR_EL_Map --> Map<K, Integer> dict_V; Map<Integer, List> targets;
  • Graph_CSR_EL_List --> Map<K, Integer> dict_V; List<List> targets;

CSR

  • Graph_CSR_GC_Brother --> Map<K, Integer> dict_V; List<List<byte[]>> targets; List csr;
    i = csr[dict_V[sid]]
    targets[i][0] = dict_V[tid] - dict_V[sid]
    targets[i][j] = SUB(dict_V[tid] - targets[i][k]) - dict_V[sid], k in [0, j)
  • Graph_CSR_GC --> Map<K, Integer> dict_V; List<List< byte[]>> targets;

Struc2vec

Struc2vec implemented by Java and Graph_Map_CSR

A* search Algorithm

A* is a modification of Dijkstra’s Algorithm that is optimized for a single destination.
Dijkstra’s Algorithm can find paths to all locations;
A* finds paths to one location, or the closest of several locations.
It prioritizes paths that seem to be leading closer to a goal.