Model

class Model[source]

Bases: object

Graph problem modeling and solving class for Critical Node Problems.

The Model class provides a unified interface for:

  • Building undirected graph instances by adding nodes and edges

  • Configuring solver parameters (search strategy, crossover operator, population settings)

  • Executing the memetic algorithm to solve CNP and DCNP problems

  • Retrieving solutions with associated statistics

The class internally manages a ProblemData object that is passed to the C++ solver backend. This ProblemData can be created from the model’s internal representation or provided directly via from_data().

Examples

Create a simple graph and solve the CNP problem:

>>> from pycnp import Model
>>> from pycnp.stop import MaxIterations
>>>
>>> model = Model()
>>> for i in range(10):
...     model.add_node(i)
>>> model.add_edge(0, 1)
>>> model.add_edge(1, 2)
>>> model.add_edge(2, 3)
>>>
>>> result = model.solve(
...     problem_type="CNP",
...     budget=2,
...     stopping_criterion=MaxIterations(100),
...     seed=42
... )
>>> print(f"Removed nodes: {result.best_solution}")
add_node(node: int) → None[source]

Add a node to the graph.

If the node already exists in the graph, this method has no effect. The adjacency list is automatically expanded to accommodate the new node ID.

Parameters:

node (int) – The ID of the node to add. Must be a non-negative integer.

add_edge(u: int, v: int) → None[source]

Add an undirected edge between two nodes.

If either endpoint does not exist, it will be automatically added to the graph. Adding the same edge multiple times has no additional effect (edges are stored as sets).

Parameters:

  • u (int) – The ID of the first endpoint.

  • v (int) – The ID of the second endpoint.

static from_data(problem_data: ProblemData) → Model[source]

Create a Model instance from an existing ProblemData object.

This factory method is useful when working with ProblemData obtained from external sources (e.g., file I/O via pycnp.read()). The created model holds a reference to the provided ProblemData.

Parameters:

problem_data (ProblemData) – The ProblemData object to wrap.

Returns:

A new Model instance that wraps the provided ProblemData.

Return type:

Model

Examples

>>> from pycnp import read, Model
>>> problem_data = read("graph.txt")
>>> model = Model.from_data(problem_data)
property problem_data: ProblemData

Get the ProblemData object for visualization.

Creates the ProblemData from the model’s graph representation if it doesn’t exist yet.

Returns:

The ProblemData object representing the graph.

Return type:

ProblemData

solve(problem_type: str, budget: int, stopping_criterion: StoppingCriterion, seed: int = 0, memetic_search_params: MemeticSearchParams | None = None, variable_population_params: VariablePopulationParams | None = None, hop_distance: int = DEFAULT_HOP_DISTANCE, display_interval: float = DEFAULT_DISPLAY_INTERVAL, display: bool = True, collect_stats: bool = True) → Result[source]

Solve the Critical Node Problem defined by this model.

This method executes the memetic algorithm to find a set of nodes to remove that minimizes connectivity while respecting the budget constraint.

Parameters:

  • problem_type (str) – The type of problem to solve. Either "CNP" for the standard Critical Node Problem or "DCNP" for the Distance-based variant.

  • budget (int) – The maximum number of nodes that can be removed. Must be non-negative and not exceed the total number of nodes.

  • stopping_criterion (StoppingCriterion) – The criterion used to determine when to stop the search. Common options include MaxIterations, MaxRuntime, or NoImprovement.

  • seed (int, default=0) – Random seed for reproducibility. The same seed will produce the same results when all other parameters are identical.

  • memetic_search_params (MemeticSearchParams, optional) – Configuration for the memetic algorithm. If None, default values are used. See MemeticSearchParams for options.

  • variable_population_params (VariablePopulationParams, optional) – Configuration for adaptive population sizing. If None, default values are used. See VariablePopulationParams for details.

  • hop_distance (int, default=DEFAULT_HOP_DISTANCE) – The hop distance limit for DCNP problems. Ignored for CNP. Two nodes are considered connected only if within this distance.

  • display_interval (float, default=DEFAULT_DISPLAY_INTERVAL) – Time interval (in seconds) between progress updates when display=True.

  • display (bool, default=True) – Whether to print progress information during the search.

  • collect_stats (bool, default=True) – Whether to collect detailed iteration-by-iteration statistics.

Returns:

A Result object containing the best solution found, its objective value, runtime statistics, and optionally iteration statistics if collect_stats=True.

Return type:

Result

Raises:

ValueError – If budget exceeds the number of nodes or if problem_type is invalid.

Examples

Solve a CNP problem with a time limit:

>>> from pycnp import Model
>>> from pycnp.stop import MaxRuntime
>>>
>>> model = Model()
>>> # ... build graph ...
>>> result = model.solve(
...     problem_type="CNP",
...     budget=5,
...     stopping_criterion=MaxRuntime(60),  # 60 seconds
...     seed=42
... )
>>> print(f"Objective: {result.best_obj_value}")