Repository

Active List Management

Overview

The active list is a core data structure in the FIM algorithm. It tracks which vertices need to be updated because their field values may change (haven't converged yet) or because they may be affected by newly updated neighbors.

Active List Interface

All active list implementations must support these operations:

  • init_active_list(::Type{T}, length) — Create an empty active list of given length.
  • reset_active_list!(active_list) — Clear the active list.
  • make_vertex_active!(active_list, vertex) — Mark a vertex as active.
  • make_vertex_inactive!(active_list, vertex) — Mark a vertex as inactive.
  • isactive_condition(active_list) — Check if any vertices are active.
  • get_active_vertex(active_list) — Get the next active vertex to process.

Built-in Implementations

BitVector

using FastIterativeMethod

# Create a BitVector-based active list
active_list = init_active_list(BitVector, n_vertices)

# Use it
reset_active_list!(active_list)
make_vertex_active!(active_list, v1)
make_vertex_active!(active_list, v2)

while isactive_condition(active_list)
    v = get_active_vertex(active_list)
    # Process vertex v
end

Pros:

  • Simple and lightweight
  • Minimal memory overhead

Cons:

  • get_active_vertex returns argmax, which is O(n)
  • May iterate over the full BitVector multiple times

UniqueVector

using FastIterativeMethod

# Create a UniqueVector-based active list
active_list = init_active_list(UniqueVector{Vector{Int}}, n_vertices)

# Use it (identical interface to BitVector)
reset_active_list!(active_list)
make_vertex_active!(active_list, v1)
make_vertex_active!(active_list, v2)

while isactive_condition(active_list)
    v = get_active_vertex(active_list)
    # Process vertex v
end

Pros:

  • get_active_vertex is O(1): just returns the first element
  • Maintains ordered list of unique active vertices

Cons:

  • Slightly higher memory overhead (stores vertex indices)
  • make_vertex_inactive! requires deletion, which can be O(n)

Choosing an Active List

Use BitVector if:

  • Your problem has few vertices or the active list is small.
  • Memory is extremely constrained.
  • Simple code is preferred over performance.

Use UniqueVector if:

  • Your problem has many vertices.
  • Most vertices are inactive at any given time.
  • Performance is critical.

Custom Active List Implementations

You can create your own active list type by implementing the interface:

struct MyActiveList
    # Your data structure
end

function FastIterativeMethod.init_active_list(::Type{MyActiveList}, length::Int)
    # Return an empty active list
end

function FastIterativeMethod.reset_active_list!(al::MyActiveList)
    # Clear the active list
end

function FastIterativeMethod.make_vertex_active!(al::MyActiveList, vertex::Int)
    # Mark vertex as active
end

# ... etc for other interface functions

This allows you to experiment with different strategies, such as:

  • Priority queue — Process lowest Φ values first.
  • Spatial hashing — Group active vertices by region for better cache locality.