Package com.ensoftcorp.open.commons.algorithms

Class GraphDensity

  • public class GraphDensity
extends java.lang.Object
    A set of utilities for calculating graph density
    Author:
    Ben Holland

    • Method Summary

      All Methods Static Methods Concrete Methods 
      Modifier and Type Method Description
      static double getDensity​(com.ensoftcorp.atlas.core.query.Q graph, boolean directed)
      Calculates Graph Density of a Q, considering all nodes and edges
      static double getDensity​(com.ensoftcorp.atlas.core.query.Q graph, boolean directed, java.lang.String[] nodeTypes, java.lang.String[] edgeTypes)
      Returns the Graph Density of a Q, considering specified nodes and edges

      • Methods inherited from class java.lang.Object

        equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    • Method Detail

      • getDensity

        public static double getDensity​(com.ensoftcorp.atlas.core.query.Q graph,
                                boolean directed)
        Calculates Graph Density of a Q, considering all nodes and edges
        Parameters:
        graph - A Q representing the graph to calculate density for
        directed - A boolean to indicate if the edges should be treated as directed or undirected edges
        Returns:
        graph density calculated as: An undirected graph has no loops and can have at most |N| * (|N| - 1) / 2 edges, so the density of an undirected graph is 2 * |E| / (|N| * (|N| - 1)). A directed graph has no loops and can have at most |N| * (|N| - 1) edges, so the density of a directed graph is |E| / (|N| * (|N| - 1)). Note: N is the number of nodes and E is the number of edges in the graph. Note: A value of 0 would be a sparse graph and a value of 1 is a dense graph. Note: Because of the way the way the Atlas schema is constructed the above assumptions are likely to be violated based on the nodes/edges contained in the graph. Therefore the result of this calculation will likely not be between 0 and 1 as expected, and should be taken with a grain of salt. Reference: http://webwhompers.com/graph-theory.html

      • getDensity

        public static double getDensity​(com.ensoftcorp.atlas.core.query.Q graph,
                                boolean directed,
                                java.lang.String[] nodeTypes,
                                java.lang.String[] edgeTypes)
        Returns the Graph Density of a Q, considering specified nodes and edges
        Parameters:
        graph -
        directed -
        nodeTypes - An array of node type tags, or null for all nodes
        edgeTypes - An array of edge type tags, or null for all edges
        Returns:
        See getDensity method for details