GraphHelpers.h

Go to the documentation of this file.

/*
 * This file belongs to the Galois project, a C++ library for exploiting
 * parallelism. The code is being released under the terms of the 3-Clause BSD
 * License (a copy is located in LICENSE.txt at the top-level directory).
 *
 * Copyright (C) 2018, The University of Texas at Austin. All rights reserved.
 * UNIVERSITY EXPRESSLY DISCLAIMS ANY AND ALL WARRANTIES CONCERNING THIS
 * SOFTWARE AND DOCUMENTATION, INCLUDING ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR ANY PARTICULAR PURPOSE, NON-INFRINGEMENT AND WARRANTIES OF
 * PERFORMANCE, AND ANY WARRANTY THAT MIGHT OTHERWISE ARISE FROM COURSE OF
 * DEALING OR USAGE OF TRADE.  NO WARRANTY IS EITHER EXPRESS OR IMPLIED WITH
 * RESPECT TO THE USE OF THE SOFTWARE OR DOCUMENTATION. Under no circumstances
 * shall University be liable for incidental, special, indirect, direct or
 * consequential damages or loss of profits, interruption of business, or
 * related expenses which may arise from use of Software or Documentation,
 * including but not limited to those resulting from defects in Software and/or
 * Documentation, or loss or inaccuracy of data of any kind.
 */

#pragma once

#include <cassert>
#include <vector>

#include <boost/iterator/counting_iterator.hpp>

#include "galois/config.h"
#include "galois/gIO.h"

namespace galois {
namespace graphs {

namespace internal {
// Note: "inline" may be required if PrefixSumType is exactly the same type
// in 2 different translation units; otherwise it should be fine
template <typename PrefixSumType>
size_t findIndexPrefixSum(size_t nodeWeight, size_t edgeWeight,
                          size_t targetWeight, uint64_t lb, uint64_t ub,
                          PrefixSumType& edgePrefixSum, uint64_t edgeOffset,
                          uint64_t nodeOffset) {
  assert(nodeWeight != 0 || edgeWeight != 0);

  while (lb < ub) {
    size_t mid = lb + (ub - lb) / 2;
    size_t num_edges;

    if ((mid + nodeOffset) != 0) {
      num_edges = edgePrefixSum[mid - 1 + nodeOffset] - edgeOffset;
    } else {
      num_edges = 0;
    }

    size_t weight = num_edges * edgeWeight + mid * nodeWeight;

    if (weight < targetWeight) {
      lb = mid + 1;
    } else if (weight >= targetWeight) {
      ub = mid;
    }
  }

  return lb;
}

uint32_t determine_block_division(uint32_t numDivisions,
                                  std::vector<unsigned>& scaleFactor);

} // end namespace internal

// Note: "inline" may be required if PrefixSumType is exactly the same type
// in 2 different translation units; otherwise it should be fine
// If inline is used, then apparently you cannot use typedefs, so get rid
// of those if the need arises.
template <typename PrefixSumType, typename NodeType = uint64_t>
auto divideNodesBinarySearch(
    NodeType numNodes, uint64_t numEdges, size_t nodeWeight, size_t edgeWeight,
    size_t id, size_t total, PrefixSumType& edgePrefixSum,
    std::vector<unsigned> scaleFactor = std::vector<unsigned>(),
    uint64_t edgeOffset = 0, uint64_t nodeOffset = 0) {
  typedef boost::counting_iterator<NodeType> iterator;
  typedef boost::counting_iterator<uint64_t> edge_iterator;
  typedef std::pair<iterator, iterator> NodeRange;
  typedef std::pair<edge_iterator, edge_iterator> EdgeRange;
  typedef std::pair<NodeRange, EdgeRange> GraphRange;

  // numNodes = 0 corner case
  if (numNodes == 0) {
    return GraphRange(NodeRange(iterator(0), iterator(0)),
                      EdgeRange(edge_iterator(0), edge_iterator(0)));
  }

  assert(nodeWeight != 0 || edgeWeight != 0);
  assert(total >= 1);
  assert(id < total);

  // weight of all data
  uint64_t weight = numNodes * nodeWeight + (numEdges + 1) * edgeWeight;
  // determine the number of blocks to divide among total divisions + setup the
  // scale factor vector if necessary
  uint32_t numBlocks = internal::determine_block_division(total, scaleFactor);
  // weight of a block (one block for each division by default; if scale
  // factor specifies something different, then use that instead)
  uint64_t blockWeight = (weight + numBlocks - 1) / numBlocks;
  // galois::gDebug("weight ", weight, " numblock ", numBlocks, " blockwegith ",
  //               blockWeight);

  // lower and upper blocks that this division should use determined
  // using scaleFactor
  uint32_t blockLower;
  if (id != 0) {
    blockLower = scaleFactor[id - 1];
  } else {
    blockLower = 0;
  }

  uint32_t blockUpper = scaleFactor[id];

  assert(blockLower <= blockUpper);
  // galois::gDebug("Unit ", id, " block ", blockLower, " to ",
  //               blockUpper, "; ", blockLower * blockWeight, " ",
  //               blockUpper * blockWeight);

  uint64_t nodesLower;
  // use prefix sum to find node bounds
  if (blockLower == 0) {
    nodesLower = 0;
  } else {
    nodesLower = internal::findIndexPrefixSum(
        nodeWeight, edgeWeight, blockWeight * blockLower, 0, numNodes,
        edgePrefixSum, edgeOffset, nodeOffset);
  }

  uint64_t nodesUpper;
  nodesUpper = internal::findIndexPrefixSum(
      nodeWeight, edgeWeight, blockWeight * blockUpper, nodesLower, numNodes,
      edgePrefixSum, edgeOffset, nodeOffset);

  // get the edges bounds using node lower/upper bounds
  uint64_t edgesLower = numEdges;
  uint64_t edgesUpper = numEdges;

  if (nodesLower != nodesUpper) {
    if ((nodesLower + nodeOffset) != 0) {
      edgesLower = edgePrefixSum[nodesLower - 1 + nodeOffset] - edgeOffset;
    } else {
      edgesLower = 0;
    }

    edgesUpper = edgePrefixSum[nodesUpper - 1 + nodeOffset] - edgeOffset;
  }

  // galois::gDebug("Unit ", id, " nodes ", nodesLower, " to ",
  //               nodesUpper, " edges ", edgesLower, " ",
  //               edgesUpper);

  return GraphRange(
      NodeRange(iterator(nodesLower), iterator(nodesUpper)),
      EdgeRange(edge_iterator(edgesLower), edge_iterator(edgesUpper)));
}

// second internal namespace
namespace internal {

bool unitRangeCornerCaseHandle(uint32_t unitsToSplit, uint32_t beginNode,
                               uint32_t endNode,
                               std::vector<uint32_t>& returnRanges);

template <typename GraphTy>
void determineUnitRangesLoopGraph(GraphTy& graph, uint32_t unitsToSplit,
                                  uint32_t beginNode, uint32_t endNode,
                                  std::vector<uint32_t>& returnRanges,
                                  uint32_t nodeAlpha) {
  assert(beginNode != endNode);

  uint32_t numNodesInRange = endNode - beginNode;
  uint64_t numEdgesInRange =
      graph.edge_end(endNode - 1) - graph.edge_begin(beginNode);
  uint64_t edgeOffset = *graph.edge_begin(beginNode);

  returnRanges[0] = beginNode;
  std::vector<unsigned int> dummyScaleFactor;

  for (uint32_t i = 0; i < unitsToSplit; i++) {
    // determine division for unit i
    auto nodeSplits =
        divideNodesBinarySearch<GraphTy, uint32_t>(
            numNodesInRange, numEdgesInRange, nodeAlpha, 1, i, unitsToSplit,
            graph, dummyScaleFactor, edgeOffset, beginNode)
            .first;

    // i.e. if there are actually assigned nodes
    if (nodeSplits.first != nodeSplits.second) {
      if (i != 0) {
        assert(returnRanges[i] == *(nodeSplits.first) + beginNode);
      } else { // i == 0
        assert(returnRanges[i] == beginNode);
      }
      returnRanges[i + 1] = *(nodeSplits.second) + beginNode;
    } else {
      // unit assinged no nodes, copy last one
      returnRanges[i + 1] = returnRanges[i];
    }

    galois::gDebug("LoopGraph Unit ", i, " gets nodes ", returnRanges[i],
                   " to ", returnRanges[i + 1], ", num edges is ",
                   graph.edge_end(returnRanges[i + 1] - 1) -
                       graph.edge_begin(returnRanges[i]));
  }
}

template <typename VectorTy>
void determineUnitRangesLoopPrefixSum(VectorTy& prefixSum,
                                      uint32_t unitsToSplit, uint32_t beginNode,
                                      uint32_t endNode,
                                      std::vector<uint32_t>& returnRanges,
                                      uint32_t nodeAlpha) {
  assert(beginNode != endNode);

  uint32_t numNodesInRange = endNode - beginNode;

  uint64_t numEdgesInRange;
  uint64_t edgeOffset;
  if (beginNode != 0) {
    numEdgesInRange = prefixSum[endNode - 1] - prefixSum[beginNode - 1];
    edgeOffset      = prefixSum[beginNode - 1];
  } else {
    numEdgesInRange = prefixSum[endNode - 1];
    edgeOffset      = 0;
  }

  returnRanges[0] = beginNode;
  std::vector<unsigned int> dummyScaleFactor;

  for (uint32_t i = 0; i < unitsToSplit; i++) {
    // determine division for unit i
    auto nodeSplits =
        divideNodesBinarySearch<VectorTy, uint32_t>(
            numNodesInRange, numEdgesInRange, nodeAlpha, 1, i, unitsToSplit,
            prefixSum, dummyScaleFactor, edgeOffset, beginNode)
            .first;

    // i.e. if there are actually assigned nodes
    if (nodeSplits.first != nodeSplits.second) {
      if (i != 0) {
        assert(returnRanges[i] == *(nodeSplits.first) + beginNode);
      } else { // i == 0
        assert(returnRanges[i] == beginNode);
      }
      returnRanges[i + 1] = *(nodeSplits.second) + beginNode;
    } else {
      // unit assinged no nodes
      returnRanges[i + 1] = returnRanges[i];
    }

    galois::gDebug("Unit ", i, " gets nodes ", returnRanges[i], " to ",
                   returnRanges[i + 1]);
  }
}

void unitRangeSanity(uint32_t unitsToSplit, uint32_t beginNode,
                     uint32_t endNode, std::vector<uint32_t>& returnRanges);

} // namespace internal

template <typename GraphTy>
std::vector<uint32_t> determineUnitRangesFromGraph(GraphTy& graph,
                                                   uint32_t unitsToSplit,
                                                   uint32_t nodeAlpha = 0) {
  uint32_t totalNodes = graph.size();

  std::vector<uint32_t> returnRanges;
  returnRanges.resize(unitsToSplit + 1);

  // check corner cases
  if (internal::unitRangeCornerCaseHandle(unitsToSplit, 0, totalNodes,
                                          returnRanges)) {
    return returnRanges;
  }

  // no corner cases: onto main loop over nodes that determines
  // node ranges
  internal::determineUnitRangesLoopGraph(graph, unitsToSplit, 0, totalNodes,
                                         returnRanges, nodeAlpha);

  internal::unitRangeSanity(unitsToSplit, 0, totalNodes, returnRanges);

  return returnRanges;
}

template <typename GraphTy>
std::vector<uint32_t>
determineUnitRangesFromGraph(GraphTy& graph, uint32_t unitsToSplit,
                             uint32_t beginNode, uint32_t endNode,
                             uint32_t nodeAlpha = 0) {
  std::vector<uint32_t> returnRanges;
  returnRanges.resize(unitsToSplit + 1);

  if (internal::unitRangeCornerCaseHandle(unitsToSplit, beginNode, endNode,
                                          returnRanges)) {
    return returnRanges;
  }

  // no corner cases: onto main loop over nodes that determines
  // node ranges
  internal::determineUnitRangesLoopGraph(graph, unitsToSplit, beginNode,
                                         endNode, returnRanges, nodeAlpha);

  internal::unitRangeSanity(unitsToSplit, beginNode, endNode, returnRanges);

  return returnRanges;
}

template <typename VectorTy>
std::vector<uint32_t> determineUnitRangesFromPrefixSum(uint32_t unitsToSplit,
                                                       VectorTy& edgePrefixSum,
                                                       uint32_t nodeAlpha = 0) {
  assert(unitsToSplit > 0);

  std::vector<uint32_t> nodeRanges;
  nodeRanges.resize(unitsToSplit + 1);

  nodeRanges[0] = 0;

  uint32_t numNodes = edgePrefixSum.size();
  // handle corner case TODO there are better ways to do this, i.e. call helper
  if (numNodes == 0) {
    nodeRanges[0] = 0;

    for (uint32_t i = 0; i < unitsToSplit; i++) {
      nodeRanges[i + 1] = 0;
    }
    return nodeRanges;
  }

  uint64_t numEdges = edgePrefixSum[numNodes - 1];

  for (uint32_t i = 0; i < unitsToSplit; i++) {
    auto nodeSplits =
        divideNodesBinarySearch<VectorTy, uint32_t>(
            numNodes, numEdges, nodeAlpha, 1, i, unitsToSplit, edgePrefixSum)
            .first;

    // i.e. if there are actually assigned nodes
    if (nodeSplits.first != nodeSplits.second) {
      if (i != 0) {
        assert(nodeRanges[i] == *(nodeSplits.first));
      } else { // i == 0
        assert(nodeRanges[i] == 0);
      }
      nodeRanges[i + 1] = *(nodeSplits.second);
    } else {
      // unit assinged no nodes
      nodeRanges[i + 1] = nodeRanges[i];
    }

    galois::gDebug("Unit ", i, " gets nodes ", nodeRanges[i], " to ",
                   nodeRanges[i + 1]);
  }

  return nodeRanges;
}

template <typename VectorTy>
std::vector<uint32_t>
determineUnitRangesFromPrefixSum(uint32_t unitsToSplit, VectorTy& edgePrefixSum,
                                 uint32_t beginNode, uint32_t endNode,
                                 uint32_t nodeAlpha = 0) {
  std::vector<uint32_t> returnRanges;
  returnRanges.resize(unitsToSplit + 1);

  if (internal::unitRangeCornerCaseHandle(unitsToSplit, beginNode, endNode,
                                          returnRanges)) {
    return returnRanges;
  }

  // no corner cases: onto main loop over nodes that determines
  // node ranges
  internal::determineUnitRangesLoopPrefixSum(
      edgePrefixSum, unitsToSplit, beginNode, endNode, returnRanges, nodeAlpha);

  internal::unitRangeSanity(unitsToSplit, beginNode, endNode, returnRanges);

  return returnRanges;
}

} // end namespace graphs
} // end namespace galois