mqt.problemsolver.qubo_tools.pathfinder.pathfinder

This module is responsible for the pathfinding version of the QuboGenerator.

Module Contents

class PathFindingQuboGeneratorSettings

A dataclass containing the settings for the pathfinding QUBO generator.

encoding_type: EncodingType

n_paths: int

max_path_length: int

loops: bool = False

class PathFindingQuboGenerator(objective_function: CostFunction | None, graph: Graph, settings: PathFindingQuboGeneratorSettings)

Bases: mqt.problemsolver.qubo_tools.QuboGenerator

A class for generating QUBOs for pathfinding problems.

Extends the QuboGenerator class with methods for generating QUBOs for pathfinding problems.

graph

The graph on which the pathfinding problem is defined.

settings

The settings for the QUBO generator.

graph: Graph

settings: PathFindingQuboGeneratorSettings

static suggest_encoding(json_string: str, graph: Graph) → EncodingType

Suggests an encoding type for a given pathfinding problem.

The suggestion is based on the number of binary variables required for a specific problem.

Parameters:

• json_string – A JSON string describing the pathfinding problem.

• graph – The graph on which the pathfinding problem is defined.

Returns:

The suggested encoding type.

static from_json(json_string: str, graph: Graph) → PathFindingQuboGenerator

Creates a PathFindingQuboGenerator object from its JSON format.

Parameters:

• json_string – The JSON string describing the pathfinding problem.

• graph – The graph on which the pathfinding problem is defined.

Returns:

The constructed QUBO generator.

add_constraint(constraint: CostFunction, weight: float | None = None) → PathFindingQuboGenerator

Add a pathfinding constraint to the QUBO generator.

Parameters:

• constraint – The constraint to be added.

• weight – The desired weight of the constraint. Defaults to None.

Returns:

The current instance of the QUBO generator.

add_constraint_if_exists(constraint: CostFunction | None, weight: float | None = None) → PathFindingQuboGenerator

Add a pathfinding constraint to the QUBO generator.

Parameters:

• constraint – The constraint to be added.

• weight – The desired weight of the constraint. Defaults to None.

Returns:

The current instance of the QUBO generator.

get_variable_index(variable: sympy.Expr) → int

For a given variable, returns its index in the QUBO matrix.

Parameters:

variable – The variable to investigate.

Returns:

The index of the variable.

decode_bit_array(_array: list[int]) → Any

Given an assignment, decodes it into a meaningful result. May be extended by subclasses.

Parameters:

_array – The binary assignment.

Returns:

The decoded result as a (set of) path(s).

decode_bit_array_domain_wall(array: list[int]) → list[list[int]]

Decodes an assignment for domain_wall encoding.

Parameters:

array – The assignment to decode.

Returns:

The decoded assignment as a (set of) path(s).

decode_bit_array_one_hot(array: list[int]) → list[list[int]]

Decodes an assignment for One-Hot encoding.

Parameters:

array – The assignment to decode.

Returns:

The decoded assignment as a (set of) path(s).

decode_bit_array_binary(array: list[int]) → list[list[int]]

Decodes an assignment for Binary encoding.

Parameters:

array – The assignment to decode.

Returns:

The decoded assignment as a (set of) path(s).