test_sf_cuthill_mckee.cc

Go to the documentation of this file.

// SPDX-FileCopyrightText: Copyright (c) NumeriCor GmbH
// SPDX-License-Identifier: Apache-2.0
 
#include "SF_numbering.h"
#include "basics.h"
 
#include <iostream>
#include <string>
#include <vector>
 
namespace {
 
using SF::vector;
using perm_map = hashmap::unordered_map<SF_int, SF_int>;
 
int failures = 0;
 
void check(bool ok, const std::string& what)
{
  if (!ok) {
    std::cerr << "FAILED: " << what << '\n';
    failures++;
  }
}
 
void make_graph(const std::vector<std::vector<SF_int>>& adj,
                vector<SF_int>& cnt, vector<SF_int>& dsp, vector<SF_int>& con)
{
  cnt.resize(adj.size());
  for (size_t i = 0; i < adj.size(); i++) {
    cnt[i] = SF_int(adj[i].size());
    for (const SF_int c : adj[i]) con.push_back(c);
  }
  SF::dsp_from_cnt(cnt, dsp);
}
 
bool is_permutation(const perm_map& old2new, size_t n)
{
  if (old2new.size() != n) return false;
 
  std::vector<bool> seen(n, false);
  for (size_t i = 0; i < n; i++) {
    const SF_int key = SF_int(i);
    if (!old2new.count(key)) return false;
    const SF_int val = old2new.at(key);
    if (val < 0 || size_t(val) >= n || seen[val]) return false;
    seen[val] = true;
  }
  return true;
}
 
std::vector<std::vector<SF_int>> path_graph(size_t n)
{
  std::vector<std::vector<SF_int>> adj(n);
  for (size_t i = 0; i < n; i++) {
    if (i > 0) adj[i].push_back(SF_int(i - 1));
    adj[i].push_back(SF_int(i));
    if (i + 1 < n) adj[i].push_back(SF_int(i + 1));
  }
  return adj;
}
 
void test_path_reverse()
{
  const size_t n = 5;
  vector<SF_int> cnt, dsp, con;
  perm_map old2new;
  make_graph(path_graph(n), cnt, dsp, con);
 
  SF::reindex_cuthill_mckee(cnt, dsp, con, true, old2new);
 
  check(is_permutation(old2new, n), "path graph, reverse: result is a permutation");
  // seeded at node 0, a chain is traversed in order, so reversing maps i to n-1-i
  for (size_t i = 0; i < n; i++)
    check(old2new.at(SF_int(i)) == SF_int(n - 1 - i), "path graph, reverse: expected index");
}
 
void test_path_forward()
{
  const size_t n = 5;
  vector<SF_int> cnt, dsp, con;
  perm_map old2new;
  make_graph(path_graph(n), cnt, dsp, con);
 
  SF::reindex_cuthill_mckee(cnt, dsp, con, false, old2new);
 
  check(is_permutation(old2new, n), "path graph, forward: result is a permutation");
  for (size_t i = 0; i < n; i++)
    check(old2new.at(SF_int(i)) == SF_int(i), "path graph, forward: expected index");
}
 
void test_empty_graph()
{
  vector<SF_int> cnt, dsp, con;
  perm_map old2new;
 
  SF::reindex_cuthill_mckee(cnt, dsp, con, true, old2new);
 
  check(old2new.empty(), "empty graph: no indices produced");
}
 
void test_disconnected_components()
{
  const size_t n = 4;
  std::vector<std::vector<SF_int>> adj(n);
  adj[0].push_back(1); adj[1].push_back(0);
  adj[2].push_back(3); adj[3].push_back(2);
 
  vector<SF_int> cnt, dsp, con;
  perm_map old2new;
  make_graph(adj, cnt, dsp, con);
 
  SF::reindex_cuthill_mckee(cnt, dsp, con, true, old2new);
 
  check(is_permutation(old2new, n), "disconnected components: result is a permutation");
}
 
void test_isolated_node()
{
  const size_t n = 4;
  std::vector<std::vector<SF_int>> adj(n);
  adj[0].push_back(0); adj[0].push_back(1);
  adj[1].push_back(0); adj[1].push_back(1);
  // node 2 is isolated
  adj[3].push_back(3);
 
  vector<SF_int> cnt, dsp, con;
  perm_map old2new;
  make_graph(adj, cnt, dsp, con);
 
  SF::reindex_cuthill_mckee(cnt, dsp, con, true, old2new);
 
  check(is_permutation(old2new, n), "isolated node: result is a permutation");
}
 
}  // namespace
 
int main()
{
  test_path_reverse();
  test_path_forward();
  test_empty_graph();
  test_disconnected_components();
  test_isolated_node();
 
  return failures ? 1 : 0;
}