# Graph Partitioning

class qubovert.problems.GraphPartitioning(*args, **kwargs)

GraphPartitioning.

Class to manage converting (Weighted) Graph Partitioning to and from its QUBO and QUSO formluations. Based on the paper “Ising formulations of many NP problems”, hereforth designated [Lucas].

The goal of the Graph Partitioning problem is to partition the verticies of a graph into two equal subsets such that the number of edges (or the total weight of the edges) connecting the two subsets is minimized.

GraphPartitioning inherits some methods and attributes from the Problem class. See `help(qubovert.problems.Problem)`.

Example

```>>> from qubovert.problems import GraphPartitioning
>>> from any_module import qubo_solver
>>> # or you can use my bruteforce solver...
>>> # from qubovert.utils import solve_qubo_bruteforce as qubo_solver
>>> edges = {("a", "b"), ("a", "c"), ("c", "d"),
("b", "c"), ("e", "f"), ("d", "e")}
>>> problem = GraphPartitioning(edges)
>>> Q = problem.to_qubo()
>>> obj, sol = qubo_solver(Q)
>>> solution = problem.convert_solution(sol)
```
```>>> print(solution)
({'a', 'b', 'c'}, {'d', 'e', 'f'})
```
```>>> print(problem.is_solution_valid(solution))
True
```

This is True since the number of vertices in the first partition is equal to the number of vertices in the second partition.

```>>> print(obj)
1
```

This is 1 because there is 1 edge connecting the partitions.

__init__.

The goal of the (Weighted) Graph Partitioning problem is to partition the vertices of a graph into two equal subsets such that the number of edges (or the total weight of the edges) connecting the two subsets is minimized. All naming conventions follow the names in the paper [Lucas].

Parameters

edges (set or dict.) –

If edges is a set, then it must be a set of two element tuples describing the edges of the graph. Ie each tuple is a connection between two vertices. If a tuple has a repeated label (for example, (2, 2)), it will be ignored.

If edges is a dict then the keys must be two element tuples and the values are the weights associated with that edge. If a key has a repeated label (for example, (2, 2)), it will be ignored.

Examples

```>>> edges = {("a", "b"), ("a", "c")}
>>> problem = GraphPartitioning(edges)
```
```>>> edges = {(0, 1), (0, 2)}
>>> problem = GraphPartitioning(edges)
```
```>>> edges = {(0, 1): 2, (1, 2): -1}
>>> problem = GraphPartitioning(edges)
```
property E

A copy of the set of edges of the graph. Updating the copy will not update the instance set.

Returns

E – A copy of the edge set defining the Graph Partitioning problem.

Return type

set of two element tuples.

property V

A copy of the vertex set of the graph. Updating the copy will not update the instance set.

Returns

V – A copy of the set of vertices corresponding to the edge set for the Graph Partitioning problem.

Return type

set.

convert_solution(solution, spin=False)

convert_solution.

Convert the solution to the QUBO or QUSO to the solution to the Graph Partitioning problem.

Parameters
• solution (iterable or dict.) – The QUBO or QUSO solution output. The QUBO solution output is either a list or tuple where indices specify the label of the variable and the element specifies whether it’s 0 or 1 for QUBO (or 1 or -1 for QUSO), or it can be a dictionary that maps the label of the variable to is value.

• spin (bool (optional, defaults to False)) – spin indicates whether `solution` is the solution to the boolean {0, 1} formulation of the problem or the spin {1, -1} formulation of the problem. This parameter usually does not matter, and it will be ignored if possible. The only time it is used is if `solution` contains all 1’s. In this case, it is unclear whether `solution` came from a spin or boolean formulation of the problem, and we will figure it out based on the `spin` parameter.

Returns

res

partition1set.

The first partition of verticies.

partition2set.

The second partition.

Return type

tuple of sets (partition1, partition2)

Example

```>>> edges = {("a", "b"), ("a", "c"), ("c", "d"),
("b", "c"), ("e", "f"), ("d", "e")}
>>> problem = GraphPartitioning(edges)
>>> Q = problem.to_qubo()
>>> obj, sol = solve_qubo(Q)
>>> print(problem.convert_solution(sol))
({'a', 'b', 'c'}, {'d', 'e', 'f'})
```
property degree

degree.

The maximum degree of the graph.

Returns

deg – A copy of the variable of the maximal degree of the graph.

Return type

int.

is_solution_valid(solution, spin=False)

is_solution_valid.

Returns whether or not the proposed solution has an equal number of vertices in each partition. NOTE: this is impossible if the number of edges is odd!

Parameters
• solution (iterable or dict.) – solution can be the output of GraphPartitioning.convert_solution, or the QUBO or QUSO solver output. The QUBO solution output is either a list or tuple where indices specify the label of the variable and the element specifies whether it’s 0 or 1 for QUBO (or 1 or -1 for QUSO), or it can be a dictionary that maps the label of the variable to is value.

• spin (bool (optional, defaults to False)) – spin indicates whether `solution` is the solution to the boolean {0, 1} formulation of the problem or the spin {1, -1} formulation of the problem. This parameter usually does not matter, and it will be ignored if possible. The only time it is used is if `solution` contains all 1’s. In this case, it is unclear whether `solution` came from a spin or boolean formulation of the problem, and we will figure it out based on the `spin` parameter.

Returns

valid – True if the proposed solution is valid, else False.

Return type

boolean.

property num_binary_variables

num_binary_variables.

The number of binary variables that the QUBO and QUSO use.

Returns

num – The number of variables in the QUBO/QUSO formulation.

Return type

integer.

solve_bruteforce(*args, **kwargs)

solve_bruteforce.

Solve the problem bruteforce. THIS SHOULD NOT BE USED FOR LARGE PROBLEMS! This is implemented in the parent `qubovert.utils.Problem` class. Some problems use a lot of slack binary variables for their QUBO/QUSO formulations. If this is the case, then the child class for this problem should override this method with a better bruteforce solver. But, for problems that do not use slack variables, this method will suffice. It converts the problem to QUBO, solves it with `qubovert.utils.solve_qubo_bruteforce`, and then calls and returns `convert_solution`.

Parameters

aruments (arguments and keyword arguments.) – Contains args and kwargs for the `to_qubo` method. Also contains a `all_solutions` boolean flag, which indicates whether or not to return all the solutions, or just the best one found. `all_solutions` defaults to False.

Returns

res – If `all_solutions` is False, then `res` is just the output of the `convert_solution` method. If `all_solutions` is True, then `res` is a list of outputs of the `convert_solution` method, e.g. a converted solution for each solution that the bruteforce solver returns.

Return type

the output or outputs of the `convert_solution` method.

to_pubo(*args, **kwargs)

to_pubo.

Since the model is already degree two, `self.to_pubo` will simply return `qubovert.utils.PUBOMatrix(self.to_qubo(*args, **kwargs))`.

Returns

P – The upper triangular PUBO matrix, a PUBOMatrix object. For most practical purposes, you can use PUBOMatrix in the same way as an ordinary dictionary. For more information, see `help(qubovert.utils.PUBOMatrix)`.

Return type

qubovert.utils.PUBOMatrix object.

to_puso(*args, **kwargs)

to_puso.

Create and return PUSO model representing the problem. Should be implemented in child classes. If this method is not implemented in the child class, then it simply calls `to_pubo` or `to_quso` and converts to a PUSO formulation.

Parameters

arguments (Defined in the child class.) – They should be parameters that define lagrange multipliers or factors in the QUSO model.

Returns

H – For most practical purposes, you can use PUSOMatrix in the same way as an ordinary dictionary. For more information, see `help(qubovert.utils.PUSOMatrix)`.

Return type

qubovert.utils.PUSOMatrix object.

Raises
• RecursionError` if neither to_pubo nor to_puso are define

• in the subclass.

to_qubo(*args, **kwargs)

to_qubo.

Create and return upper triangular QUBO representing the problem. Should be implemented in child classes. If this method is not implemented in the child class, then it simply calls `to_quso` and converts the quso formulation to a QUBO formulation.

Parameters

arguments (Defined in the child class.) – They should be parameters that define lagrange multipliers or factors in the QUBO.

Returns

Q – The upper triangular QUBO matrix, a QUBOMatrix object. For most practical purposes, you can use QUBOMatrix in the same way as an ordinary dictionary. For more information, see `help(qubovert.utils.QUBOMatrix)`.

Return type

qubovert.utils.QUBOMatrix object.

Raises
• RecursionError` if neither to_qubo nor to_quso are define

• in the subclass.

to_quso(A=None, B=1)

to_quso.

Create and return the graph partitioning problem in QUSO form following section 2.2 of [Lucas]. A and B are parameters to enforce constraints.

It is formatted such that the solution to the QUSO formulation is equal to the the total number of edges connecting the two partitions (or the total weight if we are solving weighted partitioning).

Parameters
• A (positive float (optional, defaults to None)) – A enforces the constraints. If it is None, then A will be chosen to enforce hard constraints (equation 10 in [Lucas]). Note that this may not be optimal for a solver, often hard constraints result in unsmooth energy landscapes that are difficult to minimize. Thus it may be useful to play around with the magnitude of this value.

• B (positive float (optional, defaults to 1)) – Constant in front of the objective function to minimize. See section 2.2 of [Lucas].

Returns

L – For most practical purposes, you can use QUSOMatrix in the same way as an ordinary dictionary. For more information, see `help(qubovert.utils.QUSOMatrix)`.

Return type

qubovert.utils.QUSOMatrix object.

Example

```>>> problem = GraphPartitioning({(0, 1), (1, 2), (0, 3)})
>>> L = problem.to_quso()
```
property weights

weights.

Returns a dictionary mapping the edges of the graph to their associated weights.

Returns

weights – Keys are two element tuples, values are numbers.

Return type

dict.