App.java

package iwocs;

import java.io.BufferedWriter;
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStream;
import java.util.HashMap;
import java.util.List;
import java.util.Map.Entry;

import org.graphstream.algorithm.Toolkit;
import org.graphstream.graph.BreadthFirstIterator;
import org.graphstream.graph.Graph;
import org.graphstream.graph.Node;
import org.graphstream.graph.implementations.SingleGraph;
import org.graphstream.stream.file.FileSource;
import org.graphstream.stream.file.FileSourceEdge;

/**
 * App which purpose is to experiment on a real life scaled
 * interaction network (scientific collaboration).
 */
public class App {
  public static void main(String[] args) {
    Graph g = getNerdsGraph();

    int nb_nodes = g.getNodeCount();
    int nb_links = g.getEdgeCount();

    System.out.format("N: %d\nL: %d\n<k>: %.3f\n<C>: %.3f\nConnected: %b\n<d>: %.3f\n",
      nb_nodes,
      nb_links,
      Toolkit.averageDegree(g),
      Toolkit.averageClusteringCoefficient(g),
      Toolkit.isConnected(g),
      calculateMeanDistanceFromSample(g, 1000)
    );

    exportHashMapDistribution(calculateDistancesDistributionFromSample(g, 1000), "distance_distrib");
  }

  /**
   * Export the distribution in a simple x\ty file.
   * 
   * @param distribution the map to write in the file.
   * @param destFile the path to the file in which we'll write the distribution.
   */
  private static void exportHashMapDistribution(HashMap<Integer, Double> distribution, String destFile) {
    try(BufferedWriter w = new BufferedWriter(new FileWriter(new File(destFile)))) {
      for(Entry<?, ?> entry : distribution.entrySet())
        w.write(String.format("%d\t\t%f\n", entry.getKey(), entry.getValue()));
    } catch(Exception e) {
      e.printStackTrace();
    }
  }

  /**
   * Calculate a mean distance from a sample of nodes from a given graph.
   * 
   * @param g the graph to analyse.
   * @param sampleSize number of nodes to include in the analysis.
   * @return mean distance calculated from the sample.
   */
  public static double calculateMeanDistanceFromSample(Graph g, int sampleSize) {
    List<Node> sampleNodes = Toolkit.randomNodeSet(g, sampleSize);

    double meanSum = 0;

    for(Node n : sampleNodes) {
      System.out.format("\r(%d/%d)", sampleNodes.indexOf(n), sampleSize);
      double localSum = 0;
      int nbVisited;
      BreadthFirstIterator<Node> iter = (BreadthFirstIterator<Node>)n.getBreadthFirstIterator();

      for(nbVisited = 0; iter.hasNext(); nbVisited++)
        localSum += iter.getDepthOf(iter.next());

      meanSum += localSum / nbVisited;
    }

    System.out.println();
    return meanSum / sampleSize;
  }

  /**
   * Creates a distribution of distances from a random set of nodes from a given
   * graph of a given size.
   * 
   * @param g the graph to analyse.
   * @param sampleSize number of nodes to analyse.
   * @return the distribution calculated.
   */
  public static HashMap<Integer, Double> calculateDistancesDistributionFromSample(Graph g, int sampleSize) {
    List<Node> sampleNodes = Toolkit.randomNodeSet(g, sampleSize);

    HashMap<Integer, Double> distribution = new HashMap<>();

    int i = 0;

    for(Node n : sampleNodes) {
      System.out.format("\r(%d/%d)", ++i, sampleSize);
      BreadthFirstIterator<Node> iter = (BreadthFirstIterator<Node>)n.getBreadthFirstIterator();

      while(iter.hasNext()) {
        int depth = iter.getDepthOf(iter.next());
        Double depthCount = distribution.get(depth);

        if(depthCount == null)
          distribution.put(depth, 1.0);
        else
          distribution.put(depth, depthCount + 1);
      }
    }

    System.out.println();

    Double totalMeasures = distribution.values().stream().reduce(0.0, Double::sum);

    distribution.forEach((k, v) -> distribution.put(k, v / totalMeasures));

    return distribution;
  }

  /**
   * Export degrees distribution of a graph to a given file.
   * 
   * @param g the graph from which we get the degree distribution.
   * @param destFile the path to the file in which the distribution will be written.
   * @param normalized if the values of the distribution will be normalized or not.
   */
  public static void exportDegreeDistribution(Graph g, String destFile, boolean normalized) {
    int[] degreesDistribution = Toolkit.degreeDistribution(g);
    double[] convertedDistribution = new double[degreesDistribution.length];
  
    for(int i=0; i < degreesDistribution.length; i++)
      convertedDistribution[i] = normalized ? 
        (double)degreesDistribution[i] / g.getNodeCount() :
        (double)degreesDistribution[i];

    try(BufferedWriter w = new BufferedWriter(new FileWriter(new File(destFile)))) {
      for(int i=0; i < convertedDistribution.length; i++)
        if(convertedDistribution[i] != 0)
          w.write(String.format("%d\t%f\n", i, convertedDistribution[i]));
    } catch(Exception e) {
      e.printStackTrace();
    }
  }

  public static Graph getNerdsGraph() {
    Graph g = new SingleGraph("nerds");
    
    FileSource fs = new FileSourceEdge();

    fs.addSink(g);

    try {
      InputStream stream = App.class.getClassLoader().getResourceAsStream("nerds.txt");
      fs.readAll(stream);
    } catch (IOException e) {
      e.printStackTrace();
    }

    return g;
  }
}