Class PushPullGossip


  • public class PushPullGossip
    extends java.lang.Object
    Simulates the push-pull gossiping algorithm with a single source on a given undirected graph. The algorithm works in rounds: at each round, some nodes possess an information, and some other do not (at the beginning, the information is possessed by a single node, called the source). At each round, every node x chooses one of its neighbors x'; if x is informed, it communicates the information to x', that thereby becomes informed (push); if x is not informed, it tries to get the information from x', and thereby becomes informed if x' was (pull). The algorithm terminates when a certain fraction θ of the nodes have the information (in the original version, θ=1, which requires the graph to be connected). The algorithm is performed a certain number of times, and the distribution of rounds required for termination is considered.
    Author:
    Paolo Boldi
    • Constructor Summary

      Constructors 
      Constructor Description
      PushPullGossip​(ImmutableGraph g, java.util.Random r, it.unimi.dsi.logging.ProgressLogger pl)
      Creates a new instance for the algorithm execution.
    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      int execution​(int source, double theta)
      Performs an execution of the algorithm with given source and threshold.
      void init​(int source)
      Initializes both informed arrays to the state where only a single source is informed.
      static void main​(java.lang.String[] arg)  
      it.unimi.dsi.stat.SummaryStats simulate​(int source, double theta, int numberExperiments)
      Simulates the algorithm many times on the same graph and returs statistics about the number of iterations required.
      protected int step()
      Performs a step of execution.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Constructor Detail

      • PushPullGossip

        public PushPullGossip​(ImmutableGraph g,
                              java.util.Random r,
                              it.unimi.dsi.logging.ProgressLogger pl)
        Creates a new instance for the algorithm execution.
        Parameters:
        g - the graph on which the algorithm is going to be run.
        pl - the progress logger to be used, if any.
    • Method Detail

      • step

        protected int step()
        Performs a step of execution.
        Returns:
        the number of nodes that have become informed after this step.
      • init

        public void init​(int source)
        Initializes both informed arrays to the state where only a single source is informed.
      • execution

        public int execution​(int source,
                             double theta)
        Performs an execution of the algorithm with given source and threshold.
        Parameters:
        source - the only node that is informed at the beginning.
        theta - the fraction of nodes that need to be informed (the algorithm stops as soon as this many nodes have been informed).
        Returns:
        the number of execution steps performed.
      • simulate

        public it.unimi.dsi.stat.SummaryStats simulate​(int source,
                                                       double theta,
                                                       int numberExperiments)
        Simulates the algorithm many times on the same graph and returs statistics about the number of iterations required.
        Parameters:
        source - the only node that is informed at the beginning of each execution (if negative, it is generated every time at random).
        theta - the fraction of nodes that need to be informed.
        numberExperiments - the number of experiments to be performed.
        Returns:
        a bin containing data about the number of iterations performed during each simulation.
      • main

        public static void main​(java.lang.String[] arg)
                         throws java.io.IOException,
                                com.martiansoftware.jsap.JSAPException,
                                java.lang.IllegalArgumentException,
                                java.lang.ClassNotFoundException,
                                java.lang.IllegalAccessException,
                                java.lang.reflect.InvocationTargetException,
                                java.lang.InstantiationException,
                                java.lang.NoSuchMethodException
        Throws:
        java.io.IOException
        com.martiansoftware.jsap.JSAPException
        java.lang.IllegalArgumentException
        java.lang.ClassNotFoundException
        java.lang.IllegalAccessException
        java.lang.reflect.InvocationTargetException
        java.lang.InstantiationException
        java.lang.NoSuchMethodException