How to use DEX algorithm package

The latest version of DEX includes the helpful algorithm package that give more high-level operations to the API.

Here you can find the list of algorithms explained including examples of use for the Java and .NET APIs:

Traversals algorithms
To traverse a graph is to visit the nodes included in the graph. You can choose between DFS or BFS techniques.

DFS (depth first search) is a technique were the nodes are visited starting at the root and selecting one of the neighbors’ nodes which are explored as far as possible along each branch before backtracking.

BFS (breadth first search) is a technique were the nodes are visited starting at the root which all its neighbors are explored and so on.

For both techniques you can restrict the visit by a certain type of nodes or only navigating through a certain type of edges.

Java example:

System.out.println("Traversal BFS");
// Create a new BFS traversal from the node "startingNode"
TraversalBFS bfs = new TraversalBFS(sess, startingNode);
// Allow the use of all the node types
bfs.addAllNodeTypes();
// Allow the use of all the edge types but only in outgoing direction
bfs.addAllEdgeTypes(EdgesDirection.Outgoing);
// Limit the depth to 3 hops from the starting node
bfs.setMaximumHops(3);
// Get the nodes
while (bfs.hasNext())
{
long nodeid = bfs.next();
int depth = bfs.getCurrentDepth();
System.out.println("Node "+nodeid+" at depth "+depth+".");
}
// Close the traversal
bfs.close();

The same with the TraversalDFS method.

.Net example:

System.Console.WriteLine("Traversal BFS");
// Create a new BFS traversal from the node "startingNode"
TraversalBFS bfs = new TraversalBFS(sess, startingNode);
// Allow the use of all the node types
bfs.AddAllNodeTypes();
// Allow the use of all the edge types but only in outgoing direction
bfs.AddAllEdgeTypes(EdgesDirection.Outgoing);
// Limit the depth to 3 hops from the starting node
bfs.SetMaximumHops(3);
// Get the nodes
while (bfs.HasNext())
{
long nodeid = bfs.Next();
int depth = bfs.GetCurrentDepth();
System.Console.WriteLine("Node "+nodeid+" at depth "+depth+".");
}
// Close the traversal
bfs.Close();

The same with the TraversalDFS method.

Find shortest path algorithms
Find the shortest way to travel from one node to another. The APIs offer two techniques BFS or Dijkstra. Dijkstra is the one to use if you have weights, that matter in the path retrieval, in the edges whileas BFS is the one to use otherwise.

Java example:

System.out.println("SinglePairShortestPath BFS");
// Create a new unweighted shortest path from "startingNode" to "endingNode"
SinglePairShortestPathBFS spBFS = new SinglePairShortestPathBFS(sess, startingNode, endingNode);
// Allow the use of all the edge types in Any direction
spBFS.addAllEdgeTypes(EdgesDirection.Any);
// Allow the use of all the node types
spBFS.addAllNodeTypes();
// Calculate the shortest path
spBFS.run();
// Check the path if it exists
if (spBFS.exists())
{
// Get the total path cost
System.out.println("A shortest path exists with cost: "+spBFS.getCost()+".");
// Get the path
OIDList pathAsNodes = spBFS.getPathAsNodes();
OIDListIterator pathIt = pathAsNodes.iterator();
while (pathIt.hasNext())
{
long nodeid = pathIt.next();
System.out.println("Node: "+nodeid);
}
}
else
{
System.out.println("No path found");
}
// Close the shortest path
spBFS.close();

Analogously the Dijkstra method.

.Net example:

System.Console.WriteLine("SinglePairShortestPath BFS");
// Create a new unweighted shortest path from "startingNode" to "endingNode"
SinglePairShortestPathBFS spBFS = new SinglePairShortestPathBFS(sess, startingNode, endingNode);
// Allow the use of all the edge types in Any direction
spBFS.AddAllEdgeTypes(EdgesDirection.Any);
// Allow the use of all the node types
spBFS.AddAllNodeTypes();
// Calculate the shortest path
spBFS.Run();
// Check the path if it exists
if (spBFS.Exists())
{
// Get the total path cost
System.Console.WriteLine("A shortest path exists with cost: "+spBFS.GetCost()+".");
// Get the path
OIDList pathAsNodes = spBFS.GetPathAsNodes();
OIDListIterator pathIt = pathAsNodes.Iterator();
while (pathIt.HasNext())
{
long nodeid = pathIt.Next();
System.Console.WriteLine("Node: "+nodeid);
}
}
else
{
System.Console.WriteLine("No path found");
}
// Close the shortest path
spBFS.Close();

Analogously the Dijkstra method.

Connected components algorithms
Connectivity shows in which degree a group of nodes are connected to each other. With DEX you can find strongy connected components using Gabow technique or weakly connected components using DFS technique.

Java example:

System.out.println("Weak Connectivity DFS");
// Create a new WeakConnectivityDFS
WeakConnectivityDFS weakConnDFS = new WeakConnectivityDFS(sess);
// Allow the user of all the edge types
weakConnDFS.addAllEdgeTypes();
// Allow the use of all the node types
weakConnDFS.addAllNodeTypes();
// Don't set a materialized attribute
// Calculate the weakly connected components
weakConnDFS.run();
// Get the connected components
ConnectedComponents weakCC = weakConnDFS.getConnectedComponents();
long numWeakComponents = weakCC.getCount();
System.out.println("Weakly connnected componennts: "+numWeakComponents);
for (long ii = 0; ii < weakCC.getCount(); ii++)
{
Objects ccNodes = weakCC.getNodes(ii);
long numNodes = ccNodes.count();
System.out.println("Connected component "+ii+" has "+numNodes+" nodes.");
ccNodes.close();
}
// Close the connected components
weakCC.close();
// Close the WeakConnectivityDFS
weakConnDFS.close();

Analogously the StrongConnectivityGabow method.

.Net example:

System.Console.WriteLine("Weak Connectivity DFS");
// Create a new WeakConnectivityDFS
WeakConnectivityDFS weakConnDFS = new WeakConnectivityDFS(sess);
// Allow the user of all the edge types
weakConnDFS.AddAllEdgeTypes();
// Allow the use of all the node types
weakConnDFS.AddAllNodeTypes();
// Don't set a materialized attribute
// Calculate the weakly connected components
weakConnDFS.Run();
// Get the connected components
ConnectedComponents weakCC = weakConnDFS.GetConnectedComponents();
long numWeakComponents = weakCC.GetCount();
System.Console.WriteLine("Weakly connnected componennts: "+numWeakComponents);
for (long ii = 0; ii < weakCC.GetCount(); ii++)
{
Objects ccNodes = weakCC.GetNodes(ii);
long numNodes = ccNodes.Count();
System.Console.WriteLine("Connected component "+ii+" has "+numNodes+" nodes.");
ccNodes.Close();
}
// Close the connected components
weakCC.Close();
// Close the WeakConnectivityDFS
weakConnDFS.Close();

Analogously the StrongConnectivityGabow method.

Finally do not forget to include the package when using the former methods! by adding:

Java:
import com.sparsity.dex.algorithms.*;

.Net:
using com.sparsity.dex.algorithms;

This entry was posted in DEX, Documentation and tagged , , , , , , , , , , , , , , , , , , . Bookmark the permalink.

2 Responses to How to use DEX algorithm package

  1. Jose Gregorio Piñero says:

    I’m having troubles using TraversalDFS (I’m using DEX on java). I can create the graph successfully and then i use TraversalDFS and it works fine but when i try to close the session i’m getting this error:

    Exception in thread “main” java.lang.RuntimeException: Session data still active when closing
    at com.sparsity.dexjavawrapJNI.delete_dex_gdb_Session(Native Method)
    at com.sparsity.dex.gdb.Session.delete(Session.java:32)
    at com.sparsity.dex.gdb.Session.close(Session.java:40)

    I checked everything many times and i thing the code is fine because i use exactly the same code changing TraversalDFS by TraversalBFS and it works fine.

    Please i need help

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>