mqt.problemsolver.qubo_tools.pathfinder

This module implements the pathfinding functionalities of the qubo_tools.

This, in particular, includes all pathfinding-related cost functions and the specialized QUBO generator for pathfinding problems.

Typical usage example:

```python import mqt.problemsolver.qubo_tools.pathfinder as pf

graph = pf.Graph(5, [(1, 2, 5), (2, 3, 3), (3, 4, 9), (4, 5, 8), (5, 1, 6)]) settings = pf.PathFindingQuboGeneratorSettings(pf.EncodingType.ONE_HOT, 1, 5, True) generator = pf.PathFindingQuboGenerator(pf.MinimizePathLength([1]), graph, settings) generator.add_constraint(pf.PathIsValid([1])) generator.add_constraint(pf.PathContainsVerticesExactlyOnce(graph.all_vertices, [1]))

A = generator.construct_qubo_matrix() print(A) ```

Submodules

Package Contents

class CompositeCostFunction(*parts: tuple[CostFunction, int])[source]

Bases: CostFunction

A composite cost function that is the sum of multiple cost functions.

summands

A list of tuples of cost functions and their weights.

Type:

list[tuple[CostFunction, int]]

summands: list[tuple[CostFunction, int]]
__str__() → str[source]

Returns a string representation of the cost function.

Returns:

A string representation of the cost function.

Return type:

str

get_formula(graph: Graph, settings: PathFindingQuboGeneratorSettings) → sympy.Expr[source]

Translates the cost function into a QUBO expression.

Parameters:
Returns:

An expression representing the cost function as a QUBO function.

Return type:

sp.Expr

get_formula_general(graph: Graph, settings: PathFindingQuboGeneratorSettings, get_variable_function: GetVariableFunction) → sympy.Expr[source]

Returns the QUBO expression for the cost function in the general case.

In the general case, the cost function may access the blackbox function get_variable_function(p, v, i) that returns 1 if vertex v is located at position i in path p and 0 otherwise.

Parameters:
Returns:

An expression representing the cost function as a QUBO function.

Return type:

sp.Expr

class CostFunction[source]

Bases: abc.ABC

An abstract base class for cost functions.

Represents a cost function that can be translated into a QUBO expression.

get_formula(graph: Graph, settings: PathFindingQuboGeneratorSettings) → sympy.Expr[source]

Translates the cost function into a QUBO expression.

Parameters:
Returns:

An expression representing the cost function as a QUBO function.

Return type:

sp.Expr

abstractmethod get_formula_general(graph: Graph, settings: PathFindingQuboGeneratorSettings, get_variable_function: GetVariableFunction) → sympy.Expr[source]

Returns the QUBO expression for the cost function in the general case.

In the general case, the cost function may access the blackbox function get_variable_function(p, v, i) that returns 1 if vertex v is located at position i in path p and 0 otherwise.

Parameters:
Returns:

An expression representing the cost function as a QUBO function.

Return type:

sp.Expr

get_formula_one_hot(graph: Graph, settings: PathFindingQuboGeneratorSettings) → sympy.Expr[source]

Computes the QUBO expression for the cost function for One-Hot encoding.

Parameters:
Returns:

An expression representing the cost function as a QUBO function.

Return type:

sp.Expr

get_formula_domain_wall(graph: Graph, settings: PathFindingQuboGeneratorSettings) → sympy.Expr[source]

Computes the QUBO expression for the cost function for Domain-Wall encoding.

Parameters:
Returns:

An expression representing the cost function as a QUBO function.

Return type:

sp.Expr

get_formula_binary(graph: Graph, settings: PathFindingQuboGeneratorSettings) → sympy.Expr[source]

Computes the QUBO expression for the cost function for Binary encoding.

Parameters:
Returns:

An expression representing the cost function as a QUBO function.

Return type:

sp.Expr

__str__() → str[source]

Returns a string representation of the cost function.

Returns:

A string representation of the cost function.

Return type:

str

class EncodingType[source]

Bases: enum.Enum

The encoding types supported for the QUBO generation.

ONE_HOT = 1
DOMAIN_WALL = 2
BINARY = 3
class MaximizePathLength(path_ids: list[int])[source]

Bases: PathBound

A cost function that penalises paths based on their length.

A lower total weight causes a bigger penalty.

get_formula_general(graph: Graph, settings: PathFindingQuboGeneratorSettings, get_variable_function: GetVariableFunction) → sympy.Expr[source]

Returns the QUBO expression for the cost function in the general case.

In the general case, the cost function may access the blackbox function get_variable_function(p, v, i) that returns 1 if vertex v is located at position i in path p and 0 otherwise.

Parameters:
Returns:

An expression representing the cost function as a QUBO function.

Return type:

sp.Expr

class MinimizePathLength(path_ids: list[int])[source]

Bases: PathBound

A cost function that penalises paths based on their length.

A bigger total weight causes a bigger penalty.

get_formula_general(graph: Graph, settings: PathFindingQuboGeneratorSettings, get_variable_function: GetVariableFunction) → sympy.Expr[source]

Returns the QUBO expression for the cost function in the general case.

In the general case, the cost function may access the blackbox function get_variable_function(p, v, i) that returns 1 if vertex v is located at position i in path p and 0 otherwise.

Parameters:
Returns:

An expression representing the cost function as a QUBO function.

Return type:

sp.Expr

class PathBound(path_ids: list[int])[source]

Bases: CostFunction

An abstract cost function for penalties limited to an individual path.

path_ids

The list of paths to which the cost function applies.

Type:

list[int]

path_ids: list[int]
__str__() → str[source]

Returns a string representation of the cost function.

Returns:

A string representation of the cost function.

Return type:

str

class PathComparison(path_one: int, path_two: int)[source]

Bases: CostFunction

An abstract cost function for penalties that compare two paths.

path_one

The first path.

Type:

int

path_two (int): The second path.

path_one: int
path_two: int
__str__() → str[source]

Returns a string representation of the cost function.

Returns:

A string representation of the cost function.

Return type:

str

class PathContainsEdges(min_occurrences: int, max_occurrences: int, edges: list[tuple[int, int]], path_ids: list[int])[source]

Bases: CostFunction

A cost function that penalises paths that do not contain a given set of edges.

edges

The list of edges subject to the constraint.

Type:

list[tuple[int, int]]

min_occurrences

The minimum number of occurrences of the edges in the path.

Type:

int

max_occurrences

The maximum number of occurrences of the edges in the path.

Type:

int

path_ids

The list of paths to which the cost function applies.

Type:

list[int]

edges: list[tuple[int, int]]
min_occurrences: int
max_occurrences: int
path_ids: list[int]
__str__() → str[source]

Returns a string representation of the cost function.

Returns:

A string representation of the cost function.

Return type:

str

class PathContainsEdgesAtLeastOnce(edges: list[tuple[int, int]], path_ids: list[int])[source]

Bases: PathContainsEdges

A cost function that penalises paths that do not contain a given set of edges at least once.

get_formula_general(graph: Graph, settings: PathFindingQuboGeneratorSettings, get_variable_function: GetVariableFunction) → sympy.Expr[source]

Returns the QUBO expression for the cost function in the general case.

In the general case, the cost function may access the blackbox function get_variable_function(p, v, i) that returns 1 if vertex v is located at position i in path p and 0 otherwise.

Parameters:
Returns:

An expression representing the cost function as a QUBO function.

Return type:

sp.Expr

class PathContainsEdgesAtMostOnce(edges: list[tuple[int, int]], path_ids: list[int])[source]

Bases: PathContainsEdges

A cost function that penalises paths that do not contain a given set of edges at most once.

get_formula_general(graph: Graph, settings: PathFindingQuboGeneratorSettings, get_variable_function: GetVariableFunction) → sympy.Expr[source]

Returns the QUBO expression for the cost function in the general case.

In the general case, the cost function may access the blackbox function get_variable_function(p, v, i) that returns 1 if vertex v is located at position i in path p and 0 otherwise.

Parameters:
Returns:

An expression representing the cost function as a QUBO function.

Return type:

sp.Expr

class PathContainsEdgesExactlyOnce(edges: list[tuple[int, int]], path_ids: list[int])[source]

Bases: PathContainsEdges

A cost function that penalises paths that do not contain a given set of edges exactly once.

get_formula_general(graph: Graph, settings: PathFindingQuboGeneratorSettings, get_variable_function: GetVariableFunction) → sympy.Expr[source]

Returns the QUBO expression for the cost function in the general case.

In the general case, the cost function may access the blackbox function get_variable_function(p, v, i) that returns 1 if vertex v is located at position i in path p and 0 otherwise.

Parameters:
Returns:

An expression representing the cost function as a QUBO function.

Return type:

sp.Expr

class PathContainsVertices(min_occurrences: int, max_occurrences: int, vertex_ids: list[int], path_ids: list[int])[source]

Bases: CostFunction

A cost function that penalises paths that do not contain a given set of vertices.

vertex_ids

The list of vertices subject to the constraint.

Type:

list[int]

min_occurrences

The minimum number of occurrences of the vertices in the path.

Type:

int

max_occurrences

The maximum number of occurrences of the vertices in the path.

Type:

int

path_ids

The list of paths to which the cost function applies.

Type:

list[int]

vertex_ids: list[int]
min_occurrences: int
max_occurrences: int
path_ids: list[int]
__str__() → str[source]

Returns a string representation of the cost function.

Returns:

A string representation of the cost function.

Return type:

str

class PathContainsVerticesAtLeastOnce(vertex_ids: list[int], path_ids: list[int])[source]

Bases: PathContainsVertices

A cost function that penalises paths that do not contain a given set of vertices at least once.

get_formula_general(graph: Graph, settings: PathFindingQuboGeneratorSettings, get_variable_function: GetVariableFunction) → sympy.Expr[source]

Returns the QUBO expression for the cost function in the general case.

In the general case, the cost function may access the blackbox function get_variable_function(p, v, i) that returns 1 if vertex v is located at position i in path p and 0 otherwise.

Parameters:
Returns:

An expression representing the cost function as a QUBO function.

Return type:

sp.Expr

class PathContainsVerticesAtMostOnce(vertex_ids: list[int], path_ids: list[int])[source]

Bases: PathContainsVertices

A cost function that penalises paths that do not contain a given set of vertices at most once.

get_formula_general(graph: Graph, settings: PathFindingQuboGeneratorSettings, get_variable_function: GetVariableFunction) → sympy.Expr[source]

Returns the QUBO expression for the cost function in the general case.

In the general case, the cost function may access the blackbox function get_variable_function(p, v, i) that returns 1 if vertex v is located at position i in path p and 0 otherwise.

Parameters:
Returns:

An expression representing the cost function as a QUBO function.

Return type:

sp.Expr

class PathContainsVerticesExactlyOnce(vertex_ids: list[int], path_ids: list[int])[source]

Bases: PathContainsVertices

A cost function that penalises paths that do not contain a given set of vertices exactly once.

get_formula_general(graph: Graph, settings: PathFindingQuboGeneratorSettings, get_variable_function: GetVariableFunction) → sympy.Expr[source]

Returns the QUBO expression for the cost function in the general case.

In the general case, the cost function may access the blackbox function get_variable_function(p, v, i) that returns 1 if vertex v is located at position i in path p and 0 otherwise.

Parameters:
Returns:

An expression representing the cost function as a QUBO function.

Return type:

sp.Expr

class PathEndsAt(vertex_ids: list[int], path: int)[source]

Bases: CostFunction

A cost function that penalises paths that do not end at a given vertex.

vertex_ids

The list of vertices, one of which must be located at the end of the path.

Type:

list[int]

path

The path index.

Type:

int

vertex_ids: list[int]
path: int
get_formula_general(graph: Graph, settings: PathFindingQuboGeneratorSettings, get_variable_function: GetVariableFunction) → sympy.Expr[source]

Returns the QUBO expression for the cost function in the general case.

In the general case, the cost function may access the blackbox function get_variable_function(p, v, i) that returns 1 if vertex v is located at position i in path p and 0 otherwise.

Parameters:
Returns:

An expression representing the cost function as a QUBO function.

Return type:

sp.Expr

__str__() → str[source]

Returns a string representation of the cost function.

Returns:

A string representation of the cost function.

Return type:

str

class PathIsValid(path_ids: list[int])[source]

Bases: PathBound

A cost function that penalises paths that are not valid for a given encoding.

A path may be invalid if

  • it contains an edge that is not in the graph,

  • it has an assignment incompatible with the encoding:

    • for One-Hot encoding, multiple vertices are assigned to a single position

    • for Domain-Wall encoding, a position bit string is of the form 1…10…1…0

get_formula_general(graph: Graph, settings: PathFindingQuboGeneratorSettings, get_variable_function: GetVariableFunction) → sympy.Expr[source]

Returns the QUBO expression for the cost function in the general case.

In the general case, the cost function may access the blackbox function get_variable_function(p, v, i) that returns 1 if vertex v is located at position i in path p and 0 otherwise.

Parameters:
Returns:

An expression representing the cost function as a QUBO function.

Return type:

sp.Expr

get_formula_one_hot(graph: Graph, settings: PathFindingQuboGeneratorSettings) → sympy.Expr[source]

Computes the QUBO expression for the cost function for One-Hot encoding.

Parameters:
Returns:

An expression representing the cost function as a QUBO function.

Return type:

sp.Expr

get_formula_domain_wall(graph: Graph, settings: PathFindingQuboGeneratorSettings) → sympy.Expr[source]

Computes the QUBO expression for the cost function for Domain-Wall encoding.

Parameters:
Returns:

An expression representing the cost function as a QUBO function.

Return type:

sp.Expr

get_formula_binary(graph: Graph, settings: PathFindingQuboGeneratorSettings) → sympy.Expr[source]

Computes the QUBO expression for the cost function for Binary encoding.

Parameters:
Returns:

An expression representing the cost function as a QUBO function.

Return type:

sp.Expr

class PathPositionIs(position: int, vertex_ids: list[int], path: int)[source]

Bases: CostFunction

A cost function that penalises paths that do not contain a given vertex at a given position.

vertex_ids

The list of vertices, one of which must be located at the given position.

Type:

list[int]

path

The path index.

Type:

int

position

The position index.

Type:

int

vertex_ids: list[int]
path: int
position: int
get_formula_general(graph: Graph, settings: PathFindingQuboGeneratorSettings, get_variable_function: GetVariableFunction) → sympy.Expr[source]

Returns the QUBO expression for the cost function in the general case.

In the general case, the cost function may access the blackbox function get_variable_function(p, v, i) that returns 1 if vertex v is located at position i in path p and 0 otherwise.

Parameters:
Returns:

An expression representing the cost function as a QUBO function.

Return type:

sp.Expr

__str__() → str[source]

Returns a string representation of the cost function.

Returns:

A string representation of the cost function.

Return type:

str

class PathsShareNoEdges(path_one: int, path_two: int)[source]

Bases: PathComparison

A cost function that penalises paths that share edges.

get_formula_general(graph: Graph, settings: PathFindingQuboGeneratorSettings, get_variable_function: GetVariableFunction) → sympy.Expr[source]

Returns the QUBO expression for the cost function in the general case.

In the general case, the cost function may access the blackbox function get_variable_function(p, v, i) that returns 1 if vertex v is located at position i in path p and 0 otherwise.

Parameters:
Returns:

An expression representing the cost function as a QUBO function.

Return type:

sp.Expr

class PathsShareNoVertices(path_one: int, path_two: int)[source]

Bases: PathComparison

A cost function that penalises paths that share vertices.

get_formula_general(graph: Graph, settings: PathFindingQuboGeneratorSettings, get_variable_function: GetVariableFunction) → sympy.Expr[source]

Returns the QUBO expression for the cost function in the general case.

In the general case, the cost function may access the blackbox function get_variable_function(p, v, i) that returns 1 if vertex v is located at position i in path p and 0 otherwise.

Parameters:
Returns:

An expression representing the cost function as a QUBO function.

Return type:

sp.Expr

class PathStartsAt(vertex_ids: list[int], path: int)[source]

Bases: PathPositionIs

A cost function that penalises paths that do not start at a given vertex.

__str__() → str[source]

Returns a string representation of the cost function.

Returns:

A string representation of the cost function.

Return type:

str

class PrecedenceConstraint(pre: int, post: int, path_ids: list[int])[source]

Bases: PathBound

A cost function that penalises paths that do not satisfy a given precedence constraint.

pre

The vertex that must precede post.

Type:

int

post

The vertex that must follow pre.

Type:

int

pre: int
post: int
get_formula_general(graph: Graph, settings: PathFindingQuboGeneratorSettings, get_variable_function: GetVariableFunction) → sympy.Expr[source]

Returns the QUBO expression for the cost function in the general case.

In the general case, the cost function may access the blackbox function get_variable_function(p, v, i) that returns 1 if vertex v is located at position i in path p and 0 otherwise.

Parameters:
Returns:

An expression representing the cost function as a QUBO function.

Return type:

sp.Expr

class Graph(n_vertices: int, edges: list[Edge])[source]

Represents a graph to be used with qubo_tools.

n_vertices

The number of vertices in the graph.

Type:

int

adjacency_matrix

The adjacency matrix of the graph.

Type:

npt.NDArray[np.int_ | np.float64]

all_vertices

A list of all vertices in the graph.

Type:

list[int]

all_edges

A list of all edges in the graph.

Type:

list[tuple[int, int]]

non_edges

A list of all non-edges in the graph.

Type:

list[tuple[int, int]]

n_vertices: int
adjacency_matrix: numpy.typing.NDArray[int_ | numpy.float64]
property all_vertices: list[int]

A list of all vertices in the graph.

property all_edges: list[tuple[int, int]]

A list of all edges in the graph.

property non_edges: list[tuple[int, int]]

A list of all pairs (i, j) that are not edges in the graph.

static read(file: TextIOWrapper) → Graph[source]

Reads a graph from a file.

Parameters:

file (TextIOWrapper) – The file to read the graph from.

Returns:

The graph read from the file.

Return type:

Graph

store(file: TextIOWrapper) → None[source]

Stores the graph in a file.

Parameters:

file (TextIOWrapper) – The file to store the graph in.

static from_adjacency_matrix(adjacency_matrix: numpy.typing.NDArray[int_ | numpy.float64] | list[list[int]] | list[list[float]]) → Graph[source]

Creates a graph from an adjacency matrix.

Parameters:

adjacency_matrix (npt.NDArray[np.int_ | np.float64]) – The adjacency matrix to create the graph from.

Returns:

The graph created from the adjacency matrix.

Return type:

Graph

static deserialize(encoding: str) → Graph[source]

Deserializes a graph from a string.

Parameters:

encoding (str) – The string to deserialize the graph from.

Returns:

The deserialized graph.

Return type:

Graph

serialize() → str[source]

Serializes the graph into a string.

Returns:

The serialized graph as a string.

Return type:

str

__eq__(value: object) → bool[source]

Checks if two graphs are equal.

Parameters:

value (object) – The other graph to compare to.

Returns:

True if the graphs are equal, False otherwise.

Return type:

bool

__hash__() → int[source]

Returns the hash of the graph.

Returns:

The hash of the graph.

Return type:

int

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

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[source]

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[source]

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[source]

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[source]

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[source]

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[source]

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]][source]

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]][source]

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]][source]

Decodes an assignment for Binary encoding.

Parameters:

array – The assignment to decode.

Returns:

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

class PathFindingQuboGeneratorSettings[source]

A dataclass containing the settings for the pathfinding QUBO generator.

encoding_type: EncodingType
n_paths: int
max_path_length: int
loops: bool = False