Package es.uam.eps.ir.relison.sna.metrics.distance

Class FastDistanceCalculator<U>

java.lang.Object
es.uam.eps.ir.relison.sna.metrics.distance.FastDistanceCalculator<U>
Type Parameters:
U - type of the users.
All Implemented Interfaces:
DistanceCalculator<U>
public class FastDistanceCalculator<U>
extends java.lang.Object
implements DistanceCalculator<U>
Fast version of a distance calculator which just computes the distances between pairs of nodes. Unsupported metrics: node betweenness, edge betweenness, geodesics.

References: M.E.J. Newman. Networks: an introduction (2010)

  • Field Summary

    Fields 
    Modifier and Type Field Description
    private double asl
    The average shortest path length.
    private java.util.Map<U,​java.util.Map<U,​java.lang.Double>> distancesFrom
    Distances map from u to v.
    private java.util.Map<U,​java.util.Map<U,​java.lang.Double>> distancesTo
    Distances map towards the key user.
    private Graph<U> graph
    Graph for which we compute the distances.
    private double infiniteDist
    The number of pairs of users at infinite distance from each other.
    private Communities<U> scc
    Strongly connected components of the network.

  • Constructor Summary

    Constructors 
    Constructor Description
    FastDistanceCalculator()
    Constructor

  • Method Summary

    Modifier and Type Method Description
    boolean computeDistances​(Graph<U> graph)
    Computes the betweenness of a graph.
    double getASL()
    Obtains the average shortest path length, averaged over all the finite distance paths.
    java.util.Map<U,​java.util.Map<U,​java.lang.Double>> getDistances()
    Returns all the distances between different pairs.
    double getDistances​(U orig, U dest)
    Returns the distance between two nodes.
    java.util.Map<U,​java.lang.Double> getDistancesFrom​(U node)
    Return the distances between a node and the rest of nodes in the network.
    java.util.Map<U,​java.lang.Double> getDistancesTo​(U node)
    Returns the distance between the network and an specific node.
    java.util.Map<U,​java.util.Map<U,​java.lang.Double>> getEdgeBetweenness()
    Gets all the values of the edge betweenness.
    java.util.Map<U,​java.lang.Double> getEdgeBetweenness​(U node)
    Returns the edge betweenness of all the adjacent edges to a given node.
    double getEdgeBetweenness​(U orig, U dest)
    Returns the edge betweenness of a single edge.
    java.util.Map<U,​java.util.Map<U,​java.lang.Double>> getGeodesics()
    Returns the number of geodesic paths between different pairs.
    java.util.Map<U,​java.lang.Double> getGeodesics​(U node)
    Return the number of geodesic paths between a node and the rest of nodes in the network.
    double getGeodesics​(U orig, U dest)
    Returns the number of geodesic paths between two nodes.
    double getInfiniteDistances()
    Obtains the number of infinite length pairs.
    java.util.Map<U,​java.lang.Double> getNodeBetweenness()
    Returns the node betweenness for each node in the network.
    double getNodeBetweenness​(U node)
    Gets the value of node betweenness for a single node.
    Communities<U> getSCC()
    Obtains the strongly connected components of the graph.

    Methods inherited from class java.lang.Object

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

  • Field Details

    • graph

      private Graph<U> graph
      Graph for which we compute the distances.

    • distancesFrom

      private java.util.Map<U,​java.util.Map<U,​java.lang.Double>> distancesFrom
      Distances map from u to v.

    • distancesTo

      private java.util.Map<U,​java.util.Map<U,​java.lang.Double>> distancesTo
      Distances map towards the key user.

    • scc

      private Communities<U> scc
      Strongly connected components of the network.

    • asl

      private double asl
      The average shortest path length.

    • infiniteDist

      private double infiniteDist
      The number of pairs of users at infinite distance from each other.

  • Constructor Details

  • Method Details

    • computeDistances

      public boolean computeDistances​(Graph<U> graph)
      Computes the betweenness of a graph.
      Specified by:
      computeDistances in interface DistanceCalculator<U>
      Parameters:
      graph - the graph.
      Returns:
      true if everything went ok.

    • getNodeBetweenness

      public java.util.Map<U,​java.lang.Double> getNodeBetweenness()
      Description copied from interface: DistanceCalculator
      Returns the node betweenness for each node in the network.
      Specified by:
      getNodeBetweenness in interface DistanceCalculator<U>
      Returns:
      a map containing the node betweenness for each node.

    • getNodeBetweenness

      public double getNodeBetweenness​(U node)
      Description copied from interface: DistanceCalculator
      Gets the value of node betweenness for a single node.
      Specified by:
      getNodeBetweenness in interface DistanceCalculator<U>
      Parameters:
      node - the value for the node.
      Returns:
      the node betweenness for that node.

    • getEdgeBetweenness

      public java.util.Map<U,​java.util.Map<U,​java.lang.Double>> getEdgeBetweenness()
      Description copied from interface: DistanceCalculator
      Gets all the values of the edge betweenness.
      Specified by:
      getEdgeBetweenness in interface DistanceCalculator<U>
      Returns:
      the edge betweenness value for each edge.

    • getEdgeBetweenness

      public java.util.Map<U,​java.lang.Double> getEdgeBetweenness​(U node)
      Description copied from interface: DistanceCalculator
      Returns the edge betweenness of all the adjacent edges to a given node.
      Specified by:
      getEdgeBetweenness in interface DistanceCalculator<U>
      Parameters:
      node - The node.
      Returns:
      a map containing the values of edge betweenness for all the adjacent links to the given node.

    • getEdgeBetweenness

      public double getEdgeBetweenness​(U orig, U dest)
      Description copied from interface: DistanceCalculator
      Returns the edge betweenness of a single edge.
      Specified by:
      getEdgeBetweenness in interface DistanceCalculator<U>
      Parameters:
      orig - origin node of the edge.
      dest - destination node of the edge.
      Returns:
      the betweenness if the edge exists, -1.0 if not.

    • getDistances

      public java.util.Map<U,​java.util.Map<U,​java.lang.Double>> getDistances()
      Description copied from interface: DistanceCalculator
      Returns all the distances between different pairs.
      Specified by:
      getDistances in interface DistanceCalculator<U>
      Returns:
      the distances between pairs.

    • getDistancesFrom

      public java.util.Map<U,​java.lang.Double> getDistancesFrom​(U node)
      Description copied from interface: DistanceCalculator
      Return the distances between a node and the rest of nodes in the network.
      Specified by:
      getDistancesFrom in interface DistanceCalculator<U>
      Parameters:
      node - the node.
      Returns:
      a map containing all the distances from the node to the rest of the network.

    • getDistancesTo

      public java.util.Map<U,​java.lang.Double> getDistancesTo​(U node)
      Description copied from interface: DistanceCalculator
      Returns the distance between the network and an specific node.
      Specified by:
      getDistancesTo in interface DistanceCalculator<U>
      Parameters:
      node - the node.
      Returns:
      a map containing all the distances from each vertex in the network to the node.

    • getDistances

      public double getDistances​(U orig, U dest)
      Description copied from interface: DistanceCalculator
      Returns the distance between two nodes.
      Specified by:
      getDistances in interface DistanceCalculator<U>
      Parameters:
      orig - origin node.
      dest - destination node.
      Returns:
      the distance between both nodes. if there is a path between them, +Infinity if not.

    • getGeodesics

      public java.util.Map<U,​java.util.Map<U,​java.lang.Double>> getGeodesics()
      Description copied from interface: DistanceCalculator
      Returns the number of geodesic paths between different pairs.
      Specified by:
      getGeodesics in interface DistanceCalculator<U>
      Returns:
      the distances between pairs.

    • getGeodesics

      public java.util.Map<U,​java.lang.Double> getGeodesics​(U node)
      Description copied from interface: DistanceCalculator
      Return the number of geodesic paths between a node and the rest of nodes in the network.
      Specified by:
      getGeodesics in interface DistanceCalculator<U>
      Parameters:
      node - the node.
      Returns:
      a map containing the number of geodesic paths from the node to the rest of the network.

    • getGeodesics

      public double getGeodesics​(U orig, U dest)
      Description copied from interface: DistanceCalculator
      Returns the number of geodesic paths between two nodes.
      Specified by:
      getGeodesics in interface DistanceCalculator<U>
      Parameters:
      orig - origin node.
      dest - destination node.
      Returns:
      the number of geodesic paths between both nodes if there is a path between them, 0.0 if not.

    • getSCC

      public Communities<U> getSCC()
      Description copied from interface: DistanceCalculator
      Obtains the strongly connected components of the graph.
      Specified by:
      getSCC in interface DistanceCalculator<U>
      Returns:
      the strongly connected components of the graph.

    • getASL

      public double getASL()
      Description copied from interface: DistanceCalculator
      Obtains the average shortest path length, averaged over all the finite distance paths.
      Specified by:
      getASL in interface DistanceCalculator<U>
      Returns:
      the average shortest path length.

    • getInfiniteDistances

      public double getInfiniteDistances()
      Description copied from interface: DistanceCalculator
      Obtains the number of infinite length pairs.
      Specified by:
      getInfiniteDistances in interface DistanceCalculator<U>
      Returns:
      the number of infinite length pairs.