Connected components algorithms with Java

[DEX graphdb]

Since 4.5 DEX includes connected components algorithms for Java (see old blog announcement: http://sparsity-technologies.com/blog/?p=540).

Here is an example of use for Java API:

First, remember to include in your code the algorithms package by adding:

import com.sparsity.dex.algorithms.ConnectedComponents;
import com.sparsity.dex.algorithms.WeakConnectivityDFS;
import com.sparsity.dex.algorithms.StrongConnectivityGabow;

We assume here, that you already have a created db with nodes and edges included.

If you would like to indentify weak connected components, DFS is your algorithm:

        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();

Otherwise, if you want to retrieve strong connected components you should use Gabow instead (More info http://en.wikipedia.org/wiki/Cheriyan%E2%80%93Mehlhorn/Gabow_algorithm):

        System.out.println("Strong Connectivity Gabow");
        // Create a new StrongConnectivityGabow
        StrongConnectivityGabow strongConnGabow = new StrongConnectivityGabow(sess);
        // Allow the user of all the edge types in outgoing direction
        strongConnGabow.addAllEdgeTypes(EdgesDirection.Outgoing);
        // Allow the use of all the node types
        strongConnGabow.addAllNodeTypes();
        // Don't set a materialized attribute
   // Calculate the weakly connected components
        strongConnGabow.run();
   // Get the connected components
        ConnectedComponents strongCC = strongConnGabow.getConnectedComponents();
        long numStrongComponents = strongCC.getCount();
        System.out.println("Strongly connnected componennts: "+numStrongComponents);
        for (long ii = 0; ii < strongCC.getCount(); ii++)
        {
            Objects ccNodes = strongCC.getNodes(ii);
            long numNodes = ccNodes.count();
            System.out.println("Connected component "+ii+" has "+numNodes+" nodes.");
            ccNodes.close();
        }
   // Close the connected components
        strongCC.close();
        // Close the StrongConnectivityGabow
        strongConnGabow.close();