public Graph retainTopKEdgesInGraph()

in src/main/java/com/twitter/sbf/graph/Graph.java [841:901]
46 lines of code
10 McCabe index (conditional complexity)

  public Graph retainTopKEdgesInGraph(int k) {
    //If graph is unweighted, return this object
    if (!this.isWeighted()) {
      return this;
    }
    //Find top-k edges for every vertex using max-heaps, create empty Set for every vertex, and
    //add top-k edges to it
    ArrayList<HashSet<Integer>> topKForVertices = new ArrayList<HashSet<Integer>>();
    for (int vertex = 0; vertex < this.numVertices; vertex++) {
      //Create list of indices of the neighbors in vertex's adjacency list.
      ArrayList<Integer> adjIndexList = new ArrayList<Integer>(this.getDegree(vertex));
      for (int neighborId = 0; neighborId < this.getDegree(vertex); neighborId++) {
        adjIndexList.add(neighborId);
      }
      //sort indices by weights of the edges they correspond to
      float[] wtsOfNeighborsofVertex = this.weights[vertex];
      Collections.sort(adjIndexList,
          (i1, i2) -> (int) Math.signum(wtsOfNeighborsofVertex[i2] - wtsOfNeighborsofVertex[i1]));
      //Create a HashSet containing the top-k edges (neighbors). List contains vertex IDs and not
      //just indices
      HashSet<Integer> topKSet = new HashSet<Integer>();
      int[] vertexNeighbors = this.neighbors[vertex];
      for (int neighbor = 0; neighbor < Math.min(k, this.getDegree(vertex)); neighbor++) {
        topKSet.add(vertexNeighbors[adjIndexList.get(neighbor)]);
      }
      topKForVertices.add(topKSet);
    }
    //Create new adjacency lists and weight lists for creating a new Graph object
    int[][] newAdjLists = new int[this.numVertices][];
    float[][] newWtLists = new float[this.numVertices][];
    //number of edges in new graph. Will initially double count and then divide by two later
    long newNumEdges = 0;
    //Populate using top-k sets computed earlier
    for (int vertex = 0; vertex < this.numVertices; vertex++) {
      //lists for current vertex
      ArrayList<Integer> vertexAdjList = new ArrayList<Integer>();
      ArrayList<Float> vertexWtList = new ArrayList<Float>();
      int[] vertexNeighbors = this.neighbors[vertex];
      for (int oldListIndex = 0; oldListIndex < this.getDegree(vertex); oldListIndex++) {
        int neighborOfVertex = vertexNeighbors[oldListIndex];
        //check if this edge is contained in the top-k of current vertex
        boolean topKinMyList = topKForVertices.get(vertex).contains(neighborOfVertex);
        //check if this edges is contained in the top-k list of the neighbor of the current vertex
        boolean topKinTheirList = topKForVertices.get(neighborOfVertex).contains(vertex);
        if (topKinMyList || topKinTheirList) {
          vertexAdjList.add(neighborOfVertex);
          vertexWtList.add(this.weights[vertex][oldListIndex]);
        }
      }
      //update number of edges
      newNumEdges += vertexAdjList.size();
      //convert ArrayLists to primitive arrays and add to newAdjLists and newWtLists
      newAdjLists[vertex] = new int[vertexAdjList.size()];
      newWtLists[vertex] = new float[vertexAdjList.size()];
      for (int itr = 0; itr < vertexAdjList.size(); itr++) {
        newAdjLists[vertex][itr] = vertexAdjList.get(itr);
        newWtLists[vertex][itr] = vertexWtList.get(itr);
      }
    }
    return new Graph(this.numVertices, newNumEdges / 2, newAdjLists, newWtLists);
  }