Skip to content

Adding New Algorithms

Jump to bottom
Abdullah edited this page Jan 27, 2026 · 29 revisions

Adding New Reordering Algorithms

This guide explains how to add a new vertex reordering algorithm to GraphBrew.

Overview

Adding a new algorithm involves:

  1. Adding an enum value
  2. Implementing the reordering function
  3. Updating the switch statement
  4. (Optional) Adding perceptron weights

Step 1: Add Enum Value

Location

bench/include/gapbs/util.h

Find the Enum

enum ReorderingAlgo {
    ORIGINAL = 0,
    Random = 1,
    Sort = 2,
    HubSort = 3,
    HubCluster = 4,
    DBG = 5,
    HubSortDBG = 6,
    HubClusterDBG = 7,
    RabbitOrder = 8,        // Format: 8:variant (csr/boost, default: csr)
    GOrder = 9,
    COrder = 10,
    RCMOrder = 11,
    GraphBrewOrder = 12,    // Leiden clustering + per-community ordering
    MAP = 13,               // Load reordering from file
    AdaptiveOrder = 14,     // ML-based perceptron selector
    // Leiden algorithms (15-17) - grouped together for easier sweeping
    LeidenOrder = 15,       // Format: 15:resolution (via igraph)
    LeidenDendrogram = 16,  // Format: 16:variant:resolution (dfs/dfshub/dfssize/bfs/hybrid)
    LeidenCSR = 17,         // Format: 17:variant:resolution:iterations:passes (gve/gveopt/dfs/bfs/hubsort/fast/modularity, default: gve)
    // ADD YOUR ALGORITHM HERE
    MyNewOrder = 18,
};

Naming Convention

  • Use PascalCase (e.g., MyNewOrder, LocalitySensitiveOrder)
  • Be descriptive
  • Add comment with brief description

Step 2: Implement the Reordering Function

Function Signature

template <typename NodeID>
pvector<NodeID> MyNewReorder(const CSRGraph<NodeID>& g) {
  // Returns mapping: new_id[old_id] = new_vertex_id
  pvector<NodeID> new_ids(g.num_nodes());
  
  // Your algorithm here
  
  return new_ids;
}

Understanding the Return Value

The function returns a permutation where:

  • new_ids[old_vertex_id] = new vertex ID
  • This is used to relabel vertices

Example: Simple Degree-Based Ordering

template <typename NodeID>
pvector<NodeID> DegreeOrder(const CSRGraph<NodeID>& g) {
  NodeID num_nodes = g.num_nodes();
  pvector<NodeID> new_ids(num_nodes);
  
  // Create (degree, vertex) pairs
  vector<pair<int64_t, NodeID>> degree_pairs(num_nodes);
  #pragma omp parallel for
  for (NodeID n = 0; n < num_nodes; n++) {
    degree_pairs[n] = {g.out_degree(n), n};
  }
  
  // Sort by degree (descending)
  sort(degree_pairs.begin(), degree_pairs.end(), greater<pair<int64_t, NodeID>>());
  
  // Assign new IDs
  #pragma omp parallel for
  for (NodeID i = 0; i < num_nodes; i++) {
    new_ids[degree_pairs[i].second] = i;
  }
  
  return new_ids;
}

Example: Using Community Information

template <typename NodeID>
pvector<NodeID> CommunityAwareOrder(const CSRGraph<NodeID>& g) {
  NodeID num_nodes = g.num_nodes();
  pvector<NodeID> new_ids(num_nodes);
  
  // Detect communities using Leiden
  auto communities = RunLeidenCommunityDetection(g);
  
  // Group vertices by community, then order within
  NodeID next_id = 0;
  for (const auto& community : communities) {
    for (NodeID v : community.members) {
      new_ids[v] = next_id++;
    }
  }
  
  return new_ids;
}

Step 3: Update the Switch Statements

Location

In builder.h, you need to update two switch statements:

1. The GenerateMapping Function

Find the GenerateMapping function and add your case:

void GenerateMapping(CSRGraph<NodeID_, DestID_, invert> &g,
                     pvector<NodeID_> &new_ids,
                     ReorderingAlgo reordering_algo, bool useOutdeg,
                     std::vector<std::string> reordering_options)
{
    switch (reordering_algo)
    {
    case HubSort:
        GenerateHubSortMapping(g, new_ids, useOutdeg);
        break;
    // ... other cases ...
    
    // ADD YOUR CASE HERE
    case MyNewOrder:
        MyNewReorder(g, new_ids);
        break;
    
    default:
        cerr << "Unknown reordering algorithm: " << reordering_algo << endl;
        exit(1);
    }
}

2. The ReorderingAlgoStr Function

Add your algorithm name for display:

const std::string ReorderingAlgoStr(ReorderingAlgo type)
{
    switch (type)
    {
    // ... existing cases ...
    case MyNewOrder:
        return "MyNewOrder";
    default:
        std::cerr << "Unknown Reordering Algorithm type: " << type << std::endl;
        abort();
    }
}

Step 4: Add Algorithm Name Mapping

For Perceptron Weights (in builder.h)

In builder.h, find the name_to_algo map inside ParseWeightsFromJSON and add your algorithm:

static const std::map<std::string, ReorderingAlgo> name_to_algo = {
    {"ORIGINAL", ORIGINAL}, {"HubSort", HubSort}, {"HUBSORT", HubSort},
    // ... existing entries ...
    {"MyNewOrder", MyNewOrder},  // ADD YOUR ALGORITHM HERE
};

For Python Scripts

Edit scripts/lib/utils.py and add to the ALGORITHMS dict:

ALGORITHMS = {
    0: "ORIGINAL",
    # ... existing entries ...
    17: "LeidenCSR",
    18: "MyNewOrder",  # ADD YOUR ALGORITHM HERE
}

Step 5: Add Perceptron Weights (Optional)

If you want AdaptiveOrder to consider your algorithm:

Edit Type Weight Files

When adding a new algorithm, add weights to the type weight files:

# Files to update (in scripts/weights/active/):
scripts/weights/active/type_registry.json    # Contains centroids (no algorithm weights)
scripts/weights/active/type_0.json           # Cluster 0 weights
scripts/weights/active/type_1.json           # Cluster 1 weights
scripts/weights/active/type_N.json           # Additional clusters as needed

Example Entry (add to each type_N.json file)

{
  "MyNewOrder": {
    "bias": 0.5,
    "w_modularity": 0.1,
    "w_log_nodes": 0.0,
    "w_log_edges": 0.0,
    "w_density": 0.0,
    "w_avg_degree": 0.0,
    "w_degree_variance": 0.0,
    "w_hub_concentration": 0.0,
    "w_clustering_coeff": 0.0,
    "w_avg_path_length": 0.0,
    "w_diameter": 0.0,
    "w_community_count": 0.0,
    "w_reorder_time": 0.0,
    "cache_l1_impact": 0.0,
    "cache_l2_impact": 0.0,
    "cache_l3_impact": 0.0,
    "cache_dram_penalty": 0.0,
    "benchmark_weights": {
      "pr": 1.0,
      "bfs": 1.0,
      "cc": 1.0,
      "sssp": 1.0,
      "bc": 1.0
    }
  }
}

Automatic Training

After adding the algorithm, run --fill-weights to train weights from benchmarks:

python3 scripts/graphbrew_experiment.py --fill-weights --graphs small

This will:

  1. Benchmark your algorithm on test graphs
  2. Compute appropriate weights based on performance
  3. Generate per-type weight files automatically

Weight Guidelines

Weight Positive means...
bias Generally preferred (0.3-1.0)
w_modularity Better on modular graphs
w_log_nodes Better on larger graphs
w_density Better on denser graphs
w_hub_concentration Better when hubs dominate

Complete Example: Locality-Sensitive Ordering

1. Add Enum (in util.h)

enum ReorderingAlgo {
    // ...existing...
    LocalitySensitiveOrder = 18,  // Next available ID after LeidenCSR (17)
};

2. Implement Algorithm

// Locality-sensitive ordering: keeps connected vertices close
template <typename NodeID>
pvector<NodeID> LocalitySensitiveReorder(const CSRGraph<NodeID>& g) {
  NodeID num_nodes = g.num_nodes();
  pvector<NodeID> new_ids(num_nodes, -1);
  pvector<bool> visited(num_nodes, false);
  
  NodeID next_id = 0;
  queue<NodeID> frontier;
  
  // Start from highest degree vertex
  NodeID start = 0;
  int64_t max_deg = g.out_degree(0);
  for (NodeID n = 1; n < num_nodes; n++) {
    if (g.out_degree(n) > max_deg) {
      max_deg = g.out_degree(n);
      start = n;
    }
  }
  
  // BFS traversal for locality
  frontier.push(start);
  visited[start] = true;
  
  while (!frontier.empty() || next_id < num_nodes) {
    if (frontier.empty()) {
      // Find unvisited vertex
      for (NodeID n = 0; n < num_nodes; n++) {
        if (!visited[n]) {
          frontier.push(n);
          visited[n] = true;
          break;
        }
      }
    }
    
    NodeID u = frontier.front();
    frontier.pop();
    new_ids[u] = next_id++;
    
    // Add neighbors in degree order
    vector<pair<int64_t, NodeID>> neighbors;
    for (NodeID v : g.out_neigh(u)) {
      if (!visited[v]) {
        neighbors.push_back({g.out_degree(v), v});
      }
    }
    sort(neighbors.rbegin(), neighbors.rend());
    
    for (auto& [deg, v] : neighbors) {
      if (!visited[v]) {
        visited[v] = true;
        frontier.push(v);
      }
    }
  }
  
  return new_ids;
}

3. Add to Switch

case LocalitySensitiveOrder:
  new_ids = LocalitySensitiveReorder(g);
  break;

4. Add Weights

{
  "LocalitySensitiveOrder": {
    "bias": 0.6,
    "w_modularity": 0.15,
    "w_log_nodes": 0.05,
    "w_log_edges": 0.05,
    "w_density": -0.1,
    "w_avg_degree": 0.1,
    "w_degree_variance": 0.1,
    "w_hub_concentration": 0.1
  }
}

5. Add to Python Scripts

Edit scripts/lib/utils.py:

ALGORITHMS = {
    # ... existing ...
    18: "LocalitySensitiveOrder",
}

6. Test

make clean && make all
# Test your new algorithm (ID 18 = next available after existing 0-17)
./bench/bin/pr -f test/graphs/4.el -s -o 18 -n 3

Best Practices

Performance

  1. Use OpenMP: Parallelize where possible

    #pragma omp parallel for
for (NodeID n = 0; n < num_nodes; n++) { ... }

  2. Avoid allocations in loops: Pre-allocate vectors

  3. Cache-friendly access: Process vertices sequentially when possible

Correctness

  1. Return valid permutation: Every vertex must have a new ID
  2. Handle disconnected graphs: Don't assume connectivity
  3. Test with small graphs first: Use test/graphs/4.el

Integration

  1. Consistent naming: Match enum name, function name, JSON key
  2. Document complexity: Add comments about time/space complexity
  3. Add tests: Create test cases for your algorithm

Testing Your Algorithm

Unit Test

# Test on small graph
./bench/bin/pr -f test/graphs/4.el -s -o 18 -n 3

# Verify ordering is valid
./bench/bin/pr -f test/graphs/4.el -s -o 18 -n 1 2>&1 | grep -i error

Performance Test

# Compare with baseline
./bench/bin/pr -f large_graph.el -s -o 0 -n 5   # Baseline
./bench/bin/pr -f large_graph.el -s -o 18 -n 5  # Your algorithm

Memory Test

# Check for leaks
valgrind ./bench/bin/pr -f test/graphs/4.el -s -o 18 -n 1

Debugging Tips

Print Debug Info

template <typename NodeID>
pvector<NodeID> MyNewReorder(const CSRGraph<NodeID>& g) {
  #ifdef DEBUG
  cout << "MyNewReorder: num_nodes=" << g.num_nodes() << endl;
  #endif
  // ...
}

Build with Debug

make clean
make DEBUG=1

Check Permutation Validity

bool ValidPermutation(const pvector<NodeID>& perm, NodeID n) {
  vector<bool> seen(n, false);
  for (NodeID i = 0; i < n; i++) {
    if (perm[i] < 0 || perm[i] >= n || seen[perm[i]]) {
      return false;
    }
    seen[perm[i]] = true;
  }
  return true;
}

Next Steps

← Back to Home | Code Architecture →

Clone this wiki locally