DEX 3.0 features: Graph algorithms

Starting today we are going to make a series of posts explaining the most exciting features of the last available version of DEX. We hope that these explanations will give you a hint on the powerful possibilities of DEX. 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.

Let’s start with one of the basic features of DEX 3.0, the graph algorithms.

There is a large literature on graph algorithms studied in the theory of graphs that has been proven to give excellent results extracting information with graphs. DEX 3.0 library offers the following valuable 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.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

For more information about any of these features check the technical documentation at: http://www.sparsity-technologies.com/dex_tutorials.php#dex_javadoc