Metadata-Version: 2.4
Name: propflow
Version: 0.1.3
Summary: Highly configurable belief propagation simulator for factor graphs
Author: Or Muller
License-Expression: MIT
Project-URL: Homepage, https://github.com/OrMullerHahitti/Belief-Propagation-Simulator
Project-URL: Repository, https://github.com/OrMullerHahitti/Belief-Propagation-Simulator
Project-URL: Issues, https://github.com/OrMullerHahitti/Belief-Propagation-Simulator/issues
Project-URL: Documentation, https://ormullerhahitti.github.io/Belief-Propagation-Simulator/index.html
Keywords: belief-propagation,factor-graphs,graphical-models,inference,optimization
Classifier: Development Status :: 3 - Alpha
Classifier: Intended Audience :: Science/Research
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3 :: Only
Classifier: Programming Language :: Python :: 3.10
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Classifier: Programming Language :: Python :: 3.13
Classifier: Operating System :: OS Independent
Classifier: Topic :: Scientific/Engineering :: Artificial Intelligence
Classifier: Topic :: Scientific/Engineering :: Mathematics
Classifier: Framework :: Matplotlib
Requires-Python: >=3.10
Description-Content-Type: text/markdown
License-File: LICENSE
Requires-Dist: networkx~=3.4.2
Requires-Dist: numpy~=2.2.1
Requires-Dist: matplotlib~=3.10.0
Requires-Dist: scipy~=1.15.2
Requires-Dist: dash~=2.18.2
Requires-Dist: dash_cytoscape~=1.0.2
Requires-Dist: colorlog~=6.9.0
Requires-Dist: pandas~=2.2.3
Requires-Dist: seaborn~=0.13.2
Requires-Dist: psutil~=7.0.0
Requires-Dist: twine>=6.2.0
Requires-Dist: sphinx>=8.1.3
Requires-Dist: torch>=2.8.0
Requires-Dist: flake8>=7.3.0
Requires-Dist: gunicorn>=23.0.0
Provides-Extra: dev
Requires-Dist: pytest; extra == "dev"
Requires-Dist: pytest-cov; extra == "dev"
Requires-Dist: mypy; extra == "dev"
Requires-Dist: black; extra == "dev"
Requires-Dist: pylint; extra == "dev"
Requires-Dist: jupyter; extra == "dev"
Requires-Dist: build; extra == "dev"
Requires-Dist: twine; extra == "dev"
Requires-Dist: pre-commit; extra == "dev"
Provides-Extra: torch
Requires-Dist: torch>=2.2; extra == "torch"
Dynamic: license-file

# Belief Propagation Simulator - **PropFlow**

**PropFlow** is a Python toolkit for building and experimenting with belief propagation and other distributed constraint optimization (DCOP) algorithms on factor graphs. It was designed for research and education, providing a flexible framework for implementing and testing new policies and engine variants.
## for more comprehensive documentation, please click [here](https://ormullerhahitti.github.io/Belief-Propagation-Simulator/index.html)
## Key Features

- **Belief Propagation Variants**: Simulates a variety of belief propagation algorithms, including Min-Sum, Max-Sum, and Sum-Product.
- **Search-Based DCOP Solvers**: Implements local search algorithms like the Distributed Stochastic Algorithm (DSA) and Maximum Gain Message (MGM).
- **Extensible Policy Framework**: A modular system for applying policies like message damping, factor splitting, and cost reduction to alter the behavior of the core algorithms.
- **Dynamic Graph Construction**: Tools for programmatically creating factor graphs with different topologies (e.g., cycles, random graphs) and custom cost functions.
- **Simulation and Analysis**: A `Simulator` class for running multiple engine configurations in parallel and collecting results for comparison.
- **Debugging and Visualization**: Integrated logging and tools for visualizing factor graphs and analysis results.

## Installation

### Install from PyPI (Recommended)

PropFlow is now available on PyPI! Install it with pip:

```bash
pip install propflow
```

**PyPI Package**: https://pypi.org/project/propflow/

### Install from Source (Development)

For development or to get the latest changes, clone the repository and install in editable mode:

```bash
git clone https://github.com/OrMullerHahitti/Belief-Propagation-Simulator.git
cd Belief-Propagation-Simulator
pip install -e .
```

## Getting Started: A Complete Example

Here's how to create a simple factor graph, run a Min-Sum engine, and get the results.

```python
import numpy as np
from propflow import (
    FactorGraph,
    VariableAgent,
    FactorAgent,
    BPEngine,
    MinSumComputator,
    create_random_int_table,
)

# 1. Define Variables and Factors
var1 = VariableAgent(name="x1", domain=2)
var2 = VariableAgent(name="x2", domain=2)

# Create a factor with a cost table that prefers different assignments
# The cost table is a 2x2 matrix for the two variables, each with a domain of 2.
factor = FactorAgent(
    name="f12",
    domain=2,
    ct_creation_func=create_random_int_table,
    param={"low": 1, "high": 100} # Params for the factory
)

# 2. Create the Factor Graph
# A factor graph connects variables to factors.
edges = {factor: [var1, var2]}
factor_graph = FactorGraph(
    variable_li=[var1, var2],
    factor_li=[factor],
    edges=edges
)

# 3. Initialize and Run the Engine
# The engine orchestrates the message-passing process.
engine = BPEngine(
    factor_graph=factor_graph,
    computator=MinSumComputator() # Use the Min-Sum algorithm
)
engine.run(max_iter=10)

# 4. View the Results
print(f"Final Assignments: {engine.assignments}")
print(f"Final Global Cost: {engine.calculate_global_cost()}")
```

## Advanced Usage

### Search-Based Algorithms

PropFlow also supports local search algorithms for DCOPs.

- **DSA (Distributed Stochastic Algorithm)**: A simple and distributed algorithm where agents make independent, probabilistic decisions.
- **MGM (Maximum Gain Message)**: A coordinated algorithm where only the agent with the maximum potential cost reduction is allowed to change its value.

```python
from propflow.search import DSAEngine, DSAComputator

# Use the same factor_graph from the previous example
dsa_computator = DSAComputator(probability=0.8)
dsa_engine = DSAEngine(factor_graph=factor_graph, computator=dsa_computator)
results = dsa_engine.run(max_iter=50)

print(f"DSA Best Assignment: {results['best_assignment']}")
print(f"DSA Best Cost: {results['best_cost']}")
```

### Policies

You can modify the behavior of an engine by applying different policies. Policies are implemented as specialized engine classes.

- **Damping**: Smooths messages over iterations to prevent oscillations. Use `DampingEngine`.
- **Factor Splitting**: Splits factors into two to alter message flow. Use `SplitEngine`.
- **Cost Reduction**: Applies a one-time discount to costs. Use `CostReductionOnceEngine`.

```python
from propflow import DampingEngine, MinSumComputator

# Apply damping to the standard BP engine
damped_engine = DampingEngine(
    factor_graph=factor_graph,
    computator=MinSumComputator(),
    damping_factor=0.9
)
damped_engine.run(max_iter=20)
print(f"Damped Assignments: {damped_engine.assignments}")
```

### Running Experiments

The `Simulator` class is designed to run experiments comparing multiple engine configurations across one or more graphs.

```python
from propflow import (
    Simulator,
    FGBuilder,
    BPEngine,
    DampingEngine,
    SplitEngine,
    MinSumComputator,
    CTFactory,
)

# 1. Define Engine Configurations
engine_configs = {
    "Standard BP": {"class": BPEngine, "computator": MinSumComputator()},
    "Damped BP": {"class": DampingEngine, "computator": MinSumComputator(), "damping_factor": 0.5},
    "Split Factor BP": {"class": SplitEngine, "computator": MinSumComputator(), "split_factor": 0.6},
}

# 2. Create a list of graphs for the experiment
graphs = [
    FGBuilder.build_cycle_graph(
        num_vars=10,
        domain_size=3,
        ct_factory=CTFactory.random_int.fn,
        ct_params={"low": 0, "high": 100}
    ) for _ in range(5)
]

# 3. Run the simulations in parallel
simulator = Simulator(engine_configs)
results = simulator.run_simulations(graphs, max_iter=100)

# 4. Plot the average cost convergence
simulator.plot_results(verbose=True)
```

## Preliminary Results

> Results for 3 different variants of Min-Sum - regular, dampened, and using damping + splitting for 30 problems each, 90 simulations overall, with each one running 5000 steps (iterations).
> Using the following parameters: only binary constraints, domain size -10, density - 0.25, 50 Variable Nodes (approximately 306 Factor Nodes), and cost table generated from a uniform integer function with range [100, 200].

![image](https://github.com/user-attachments/assets/f9b3c0a6-0059-43a2-9eed-c23b6e06c369)
