Graph Databases features: graph algorithms and how to use them with DEX

There is large literature on graph algorithms studied in the theory of graphs that has been proven to give excellent results extracting information with graphs. In this article we’d like to share a description with examples using DEX 3.0 API of the most relevant graph algorithms.

• Traversal:  You can move through the graph using BFS (breadth first search - starting at the root all its neighbors are explored and so on) or DFS (depth first search - starting at the root and selecting one node neighbors are explored as far as possible along each branch before backtracking). The former methods allow to restrict which node types do you want to visit and which way are the edge types navigable. Use the traversal methods to obtain all the nodes in the graph ordered at your choice.

  BFS example:

  Graph DEXGraph -> Dex graph instance

  long root_node -> valid node identifier from the graph DEXGraph

  long name -> existing attribute indentifier

   

  TraversalBFS t = new TraversalBFS(DEXgraph, root_node);

  while(t.hasNext()) {

  long current_node = t.next();

  string name = dbg.getAttribute(current_node, name);

  system.out.println(name.toString()); }

  t.close();

   

  DFS example: Same as for BFS using method TraversalDFS t = TraversalDFS(DEXgraph, root_node);

  See extended examples at: http://www.sparsity-technologies.com/downloads/javadoc/edu/upc/dama/dex/algorithms/package-summary.html#usage




•  Shortest Path: Having two nodes you can automatically discover which one is the shortest path between them. DEX 3.0 computes the well-known Dijkstra shortest-path algorithm (if there are weights in the edges) and BFS (without weights). It is also possible to restrict which node types do you want to visit and which way are the edge types navigable. In addition also the maximum longitude for the shortest path can be given. Use the shortest path to discover, for instance, the minimum chain of contacts between yourself and the responsible of the company you would like to work with or to discover the fastest way to go to that restaurant from your home.

  Dijkstra example:

  Graph DEXGraph -> Dex graph instance

  long source_node -> valid node identifier from the graph DEXGraph

  long destination_node ->valid node identifier from the graph DEXGraph

   

  SiglePairShortestPathDijkstra sp = new SinglePairShortestPathDijkstra(DEXgraph, source_node, destination_node);

  sp.run();

  double path_size = sp.getCost();

  sp.close();

   

  BFS example: Same as for Dijkstra using method TraversalDFS t = TraversalDFS(DEXgraph, root_node);

  See extended examples at: http://www.sparsity-technologies.com/downloads/javadoc/edu/upc/dama/dex/algorithms/package-summary.html#usage




•  Connectivity: Two algorithms, one for searching strongly connected components using Gabow algorithm and another one for weekly connected algorithms using DFS will help you measuring the connectivity between entities in the graph. Connectivity among entities will give for instance a measure of the communication among the people in your office; if they are more connected information will flow more fluently and quickly.

  Example:

  Graph DEXGraph -> Dex graph

  instanceStrongConnectivityGabow scc = new StrongConnectivityGabow(DEXGraph);

  scc.run();

  ConnectedComponents cc= scc.getConnectedComponents();

  scc.close();

  //Retrieving the number of connected components found.

  long totalCCS = cc.getCount();

   

  See extended examples at: http://www.sparsity-technologies.com/downloads/javadoc/edu/upc/dama/dex/algorithms/package-summary.html#usage

   

This article is the first episode of the series of posts explaining the most exciting features of Graph Databases available at DEX 3.0 with examples of how to use them. You can find these posts at Sparsity Technologies’ blog: http://www.sparsity-technologies.com/events.php.

If some curiosity is left we highly encourage you to try the free download of DEX at http://www.sparsity-technologies.com/dex_downloads.php and test all its features.