<commit_before>/*******************************************************************************
GPU OPTIMIZED MONTE CARLO (GOMC) 2.70
Copyright (C) 2018  GOMC Group
A copy of the GNU General Public License can be found in the COPYRIGHT.txt
along with this program, also can be found at <http://www.gnu.org/licenses/>.
********************************************************************************/
#include "FloydWarshallCycle.h"

FloydWarshallCycle::FloydWarshallCycle(int numNodes)
{
  // Confirm that the number of nodes is greater than zero
  assert(numNodes > 0);

  // Store the size of the graph in numberOfNodes
  numberOfNodes = numNodes;

  // Resize both graph and next vectors to the size of N*N
  graph.resize(numberOfNodes);
  for (int i = 0; i < numberOfNodes; i++)
    graph[i].resize(numberOfNodes);
  next.resize(numberOfNodes);
  for (int i = 0; i < numberOfNodes; i++)
    next[i].resize(numberOfNodes);

  // double check
  assert((int) graph.size() == numberOfNodes);
}


FloydWarshallCycle::~FloydWarshallCycle()
{
}

void FloydWarshallCycle::AddEdge(int src, int dest)
{
  // make sure src and dest are valid node IDs
  assert(src >= 0);
  assert(src < numberOfNodes);
  assert(dest >= 0);
  assert(dest < numberOfNodes);

  std::vector<int> temp;
  temp.push_back(src);
  temp.push_back(dest);
  connections.push_back(temp);
}

std::vector<int> FloydWarshallCycle::GetShortestCycle(int src)
{
  // check src value
  assert(src >= 0);
  assert(src < numberOfNodes);

  std::vector< std::vector<int> > paths;
  std::vector<int> allEdgesIncludingSrc = getConnectionsFor(src);
  for (int i = 0; i < (int) allEdgesIncludingSrc.size(); i++) {
    setDefaults();
    setValues(allEdgesIncludingSrc[i]);
    floydWarshall();
    paths.push_back(getPath(allEdgesIncludingSrc[i]));
  }
  return findMinimumPath(paths);
}

std::vector< std::vector<int> > FloydWarshallCycle::GetAllUniqueCycles()
{
  // check number of nodes
  assert(numberOfNodes >= 0);

  std::vector< std::vector<int> > allCycles;
  for (int i = 0; i < numberOfNodes; i++) {
    allCycles.push_back(GetShortestCycle(i));
  }
  return getUniqueVectors(allCycles);
}

std::vector< std::vector<int> > FloydWarshallCycle::GetAllCommonCycles()
{
  std::vector< std::vector<int> > uniqueCycles = GetAllUniqueCycles();
  std::vector< std::vector<int> > commons;
  int len = uniqueCycles.size();
  std::vector<bool> visited(len, false);

  for (int i = 0; i < len; i++) {
    if (!visited[i]) {
      std::vector<int> combined(uniqueCycles[i]);
      visited[i] = true;
      for (int j = i + 1; j < len; j++) {
        if (haveCommonElements(combined, uniqueCycles[j])) {
          combined = returnCombinedSet(combined, uniqueCycles[j]);
          visited[j] = true;
        }
      }
      commons.push_back(combined);
    }
  }

  return commons;
}

void FloydWarshallCycle::floydWarshall()
{
  for (int k = 0; k < numberOfNodes; k++) {
    for (int i = 0; i < numberOfNodes; i++) {
      for (int j = 0; j < numberOfNodes; j++) {
        if (graph[i][j] > graph[i][k] + graph[k][j]) {
          graph[i][j] = graph[i][k] + graph[k][j];
          next[i][j] = next[i][k];
        }
      }
    }
  }
}

std::vector<int> FloydWarshallCycle::getPath(int src, int dest)
{
  // make sure src and dest are valid node IDs
  assert(src >= 0);
  assert(src < numberOfNodes);
  assert(dest >= 0);
  assert(dest < numberOfNodes);

  std::vector<int> path;
  if (next[src][dest] == -1)
    return path;
  path.push_back(src);
  while (src != dest) {
    src = next[src][dest];
    path.push_back(src);
  }
  return path;
}

std::vector<int> FloydWarshallCycle::getPath(int connectionIndex)
{
  int src = connections[connectionIndex][0];
  int dest = connections[connectionIndex][1];
  std::vector<int> path;
  if (next[src][dest] == -1)
    return path;
  path.push_back(src);
  while (src != dest) {
    src = next[src][dest];
    path.push_back(src);
  }
  return path;
}

void FloydWarshallCycle::setDefaults()
{
  for (int i = 0; i < numberOfNodes; i++)
    for (int j = 0; j < numberOfNodes; j++) {
      graph[i][j] = 10000;
      next[i][j] = -1;
    }
}

void FloydWarshallCycle::setValues(int exceptThisOne)<commit_msg>Fix the initial value for FloydWarshall class, per L.S. suggestion<commit_after>/*******************************************************************************
GPU OPTIMIZED MONTE CARLO (GOMC) 2.70
Copyright (C) 2018  GOMC Group
A copy of the GNU General Public License can be found in the COPYRIGHT.txt
along with this program, also can be found at <http://www.gnu.org/licenses/>.
********************************************************************************/
#include "FloydWarshallCycle.h"

FloydWarshallCycle::FloydWarshallCycle(int numNodes)
{
  // Confirm that the number of nodes is greater than zero
  assert(numNodes > 0);

  // Store the size of the graph in numberOfNodes
  numberOfNodes = numNodes;

  // Resize both graph and next vectors to the size of N*N
  graph.resize(numberOfNodes);
  for (int i = 0; i < numberOfNodes; i++)
    graph[i].resize(numberOfNodes);
  next.resize(numberOfNodes);
  for (int i = 0; i < numberOfNodes; i++)
    next[i].resize(numberOfNodes);

  // double check
  assert((int) graph.size() == numberOfNodes);
}


FloydWarshallCycle::~FloydWarshallCycle()
{
}

void FloydWarshallCycle::AddEdge(int src, int dest)
{
  // make sure src and dest are valid node IDs
  assert(src >= 0);
  assert(src < numberOfNodes);
  assert(dest >= 0);
  assert(dest < numberOfNodes);

  std::vector<int> temp;
  temp.push_back(src);
  temp.push_back(dest);
  connections.push_back(temp);
}

std::vector<int> FloydWarshallCycle::GetShortestCycle(int src)
{
  // check src value
  assert(src >= 0);
  assert(src < numberOfNodes);

  std::vector< std::vector<int> > paths;
  std::vector<int> allEdgesIncludingSrc = getConnectionsFor(src);
  for (int i = 0; i < (int) allEdgesIncludingSrc.size(); i++) {
    setDefaults();
    setValues(allEdgesIncludingSrc[i]);
    floydWarshall();
    paths.push_back(getPath(allEdgesIncludingSrc[i]));
  }
  return findMinimumPath(paths);
}

std::vector< std::vector<int> > FloydWarshallCycle::GetAllUniqueCycles()
{
  // check number of nodes
  assert(numberOfNodes >= 0);

  std::vector< std::vector<int> > allCycles;
  for (int i = 0; i < numberOfNodes; i++) {
    allCycles.push_back(GetShortestCycle(i));
  }
  return getUniqueVectors(allCycles);
}

std::vector< std::vector<int> > FloydWarshallCycle::GetAllCommonCycles()
{
  std::vector< std::vector<int> > uniqueCycles = GetAllUniqueCycles();
  std::vector< std::vector<int> > commons;
  int len = uniqueCycles.size();
  std::vector<bool> visited(len, false);

  for (int i = 0; i < len; i++) {
    if (!visited[i]) {
      std::vector<int> combined(uniqueCycles[i]);
      visited[i] = true;
      for (int j = i + 1; j < len; j++) {
        if (haveCommonElements(combined, uniqueCycles[j])) {
          combined = returnCombinedSet(combined, uniqueCycles[j]);
          visited[j] = true;
        }
      }
      commons.push_back(combined);
    }
  }

  return commons;
}

void FloydWarshallCycle::floydWarshall()
{
  for (int k = 0; k < numberOfNodes; k++) {
    for (int i = 0; i < numberOfNodes; i++) {
      for (int j = 0; j < numberOfNodes; j++) {
        if (graph[i][j] > graph[i][k] + graph[k][j]) {
          graph[i][j] = graph[i][k] + graph[k][j];
          next[i][j] = next[i][k];
        }
      }
    }
  }
}

std::vector<int> FloydWarshallCycle::getPath(int src, int dest)
{
  // make sure src and dest are valid node IDs
  assert(src >= 0);
  assert(src < numberOfNodes);
  assert(dest >= 0);
  assert(dest < numberOfNodes);

  std::vector<int> path;
  if (next[src][dest] == -1)
    return path;
  path.push_back(src);
  while (src != dest) {
    src = next[src][dest];
    path.push_back(src);
  }
  return path;
}

std::vector<int> FloydWarshallCycle::getPath(int connectionIndex)
{
  int src = connections[connectionIndex][0];
  int dest = connections[connectionIndex][1];
  std::vector<int> path;
  if (next[src][dest] == -1)
    return path;
  path.push_back(src);
  while (src != dest) {
    src = next[src][dest];
    path.push_back(src);
  }
  return path;
}

void FloydWarshallCycle::setDefaults()
{
  for (int i = 0; i < numberOfNodes; i++) {
    for (int j = 0; j < numberOfNodes; j++) {
      graph[i][j] = 10000;
      next[i][j] = -1;
    }
    graph[i][i] = 0;
    next[i][i] = i;
  }
}

void FloydWarshallCycle::setValues(int exceptThisOne)
{'fraction_non_alphanumeric': 0.18698517298187808, 'fraction_numerical': 0.00835490703694987, 'mean_word_length': 3.8676975945017182, 'pattern_counts': {'":': 0, '<': 79, '<?xml version=': 0, '>': 63, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6480941', 'n_tokens_mistral': 3100, 'n_tokens_neox': 2944, 'n_words': 696}