Skip to content

quast_decisiontree.problems.classes.max_cut

quast_decisiontree.problems.classes.max_cut

MaxCut problem framework

logger module-attribute 

logger = logging.getLogger('dt_logger')

MaxCut

Bases: OptimizationProblem

class representing an instance of the MaxCut problem

Source code in src/quast_decisiontree/problems/classes/max_cut.py 
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
class MaxCut(OptimizationProblem):
    """class representing an instance of the MaxCut problem"""

    direct_encoding_modes = ("QUBO",)
    alias = ["wMaxCut", "MaximumCut", "weightedMaxCut", "weightedMaximumCut"]
    weight_tol = 1e-5

    def __init__(self, input_data: Any) -> None:
        """Constructs a MaxCut instance from a NetworkX graph or adjacency matrix.

        Args:
            input_data: A NetworkX graph (optionally with edge weights) or a
                square numpy array representing an adjacency/weight matrix.
        """
        if isinstance(input_data, nx.Graph):
            self.graph = input_data
        else:
            self.graph = nx.from_numpy_array(np.asarray(input_data))
        self.adjacency_matrix = nx.to_numpy_array(self.graph)
        self.positions = None

    @classmethod
    def from_dict(cls, problem_dict: Mapping) -> "MaxCut":
        """attempts to construct a MaxCut instance from the data

        Dictionary keys:
        "edges" - a list of edges, with integers labelling the nodes. Single edges will be either a
                pair (resulting in an unweighted Maxcut problem), or 3-tuples (u, v, weight). All
                edges should be weighted or all unweighted.
        All other dictionary keys are ignored.

        Returns:
        (Weighted) Maxcut instance.
        """
        edges = problem_dict.get("edges")
        if edges is None:
            raise InvalidProblemDictError(
                "Problem dictionary specifying MaxCut contains no edge data."
            )
        if not edges:
            raise InvalidProblemDictError(
                "Edge list is empty; cannot construct a MaxCut instance."
            )

        shape = functions.list_shape(edges)
        if shape == 2:
            return cls(nx.Graph(edges))
        if shape == 3:
            graph = nx.Graph()
            graph.add_weighted_edges_from(edges)
            return cls(graph)
        raise InvalidProblemDictError("Edge list doesn't have the correct format.")

    def to_dict(self) -> dict:
        """Converts the MaxCut instance into a problem dictionary.

        Returns:
            dict: The resulting dictionary will be of the form
                {"problem_class": "MaxCut", "edges" : edges} where the edges
                are given as either 2- or 3-tuples of the underlying graph.
        """
        if nx.is_weighted(self.graph):
            problem_class = "wMaxCut"
            edges = list(self.graph.edges(data="weight"))
        else:
            problem_class = "MaxCut"
            edges = list(self.graph.edges())

        return {"problem_class": problem_class, "edges": edges}

    def __eq__(self, other: object) -> bool:
        """checks whether two given MaxCut instances are equivalent, e.g. they are isomorphic
        including (if existent) their edge weights
        """
        if not isinstance(other, MaxCut):
            return NotImplemented
        return nx.is_isomorphic(
            self.graph, other.graph, edge_match=lambda x, y: _edge_match(x, y, self.weight_tol)
        )

    @classmethod
    def create_random_instance(
        cls,
        size: int,
        *,
        graph_type: str = "er",
        graph_params: Any = None,
        weighted: bool = True,
        seed: Any = None,
        rand_type: str = "uniform",
        rand_params: Any = None,
    ):
        """create a random MaxCut instance of the specified graph type. If weighted, the weights
        are drawn from the specified distribution.

        Parameters:
        size: how many vertices the graph will have
        graph_type: the graph type to generate. Currently supported are "regular", "er"
        for Erdös-Renyi and "complete"
        graph_params: a dict of properties specifying the graph_type. These are the format
        and defaults:
            "regular" : {"degree": 3}
            "er" : {"probability": 0.5}
            "3-regular" : {}
            "complete" : {}
        weighted: if true, random weights drawn from the chosen distribution are added to the edges
        seed: A random seed. Two independent streams are spawned from it, one for the graph
            topology and one for the edge weights, so the two are decorrelated but jointly
            reproducible.
        rand_type: what distribution to draw the edge weights from. Currently, normal and uniform
        are supported.
        rand_params: the parameters directly passed to the random distribution (default ones will
        be used if None)
            "uniform": A (low, high) tuple. Default is (0,1)
            "normal": A (mean, standard_deviation) tuple. Default is (0,1)
        """
        if rand_type.lower() not in ["uniform", "normal"]:
            logger.warning(f"Unknown rand_type {rand_type!r}, defaulting to uniform.")
            rand_type = "uniform"

        weight_seed, graph_seed_source = np.random.SeedSequence(seed).spawn(2)
        graph_seed = int(graph_seed_source.generate_state(1)[0])

        if weighted:
            weight_rng = rd.default_rng(weight_seed)
            if rand_params is None:
                rand_params = (0, 1)
            if rand_type == "uniform":
                randfun = weight_rng.uniform
            else:
                randfun = weight_rng.normal

        allowed_graph_types = ["3-regular", "regular", "er", "complete"]

        if graph_type.lower() not in allowed_graph_types:
            raise ValueError(
                f"Graph type {graph_type!r} is not supported. Supported types:"
                f" {allowed_graph_types}."
            )

        if graph_params is None:
            graph_params = {}
        if graph_type.lower() in ["regular", "3-regular"]:
            if "degree" in graph_params and graph_type.lower() == "regular":
                degree = graph_params["degree"]
            else:
                degree = 3
            rand_graph = nx.random_regular_graph(degree, size, seed=graph_seed)

        elif graph_type.lower() == "er":
            prob = graph_params.get("probability", 0.5)
            rand_graph = nx.fast_gnp_random_graph(size, prob, seed=graph_seed)

        elif graph_type.lower() == "complete":
            rand_graph = nx.complete_graph(size)

        if weighted:
            for u, v in rand_graph.edges():
                rand_graph[u][v]["weight"] = randfun(*rand_params)

        ins = cls(rand_graph)
        # add positions so it can later be displayed using Plotly
        spring_layout_positions = nx.spring_layout(rand_graph)
        coordinate_list = []
        for i, _ in enumerate(spring_layout_positions):
            coordinate_list.append(spring_layout_positions[i])

        ins.positions = coordinate_list

        return ins

    @classmethod
    def is_feasible(cls, solution_string: str) -> bool:
        """all solution strings are feasible for MaxCut!"""
        return True

    def _as_partition(self, result: Sequence) -> set:
        """normalizes a solution into the set of nodes on one side of the cut

        Accepts either a collection of node labels or a bitstring whose i-th
        character selects the i-th node (in graph node order).
        """
        if isinstance(result, str):
            return {
                node for node, bit in zip(self.graph.nodes(), result, strict=False) if bit == "1"
            }
        return set(result)

    def display(self) -> go.Figure:
        """displays the underlying graph including edge weights

        Returns a colormap figure indicating the mapping between edge weights and colours
        """
        if self.positions is None:
            raise AttributeError(
                "The display function cannot be called when the attribute positions is not"
                " specified"
            )

        completelist = list(self.graph.edges(data="weight", default=1))
        edges = list(zip(*list(zip(*completelist, strict=False))[:2], strict=False))
        weights = list(zip(*completelist, strict=False))[2]

        weight_array = np.asarray(weights, dtype=float)
        span = weight_array.max() - weight_array.min()
        if span > 0:
            normalized_weights = (weight_array - weight_array.min()) / span
        else:
            normalized_weights = np.zeros_like(weight_array)

        cmap = colormaps["plasma"]

        edge_scatters = []
        for i, edge in enumerate(edges):
            edge_x = []
            edge_y = []

            x1, y1 = self.positions[edge[0]]
            x2, y2 = self.positions[edge[1]]
            edge_x.append(x1)
            edge_x.append(x2)
            edge_x.append(None)
            edge_y.append(y1)
            edge_y.append(y2)
            edge_y.append(None)

            edge_trace = go.Scatter(
                cliponaxis=True,
                x=edge_x,
                y=edge_y,
                line=dict(width=2, color=functions.to_rgb(color=cmap(normalized_weights[i]))),
                hoverinfo="skip",
                mode="lines",
            )

            edge_scatters.append(edge_trace)

        node_x = []
        node_y = []
        node_text = []

        for i, pos in enumerate(self.positions):
            x, y = pos
            node_x.append(x)
            node_y.append(y)
            node_text.append(str(i))

        sort_order = np.argsort(weight_array)
        sorted_weights = weight_array[sort_order]
        sorted_normalized = normalized_weights[sort_order]

        legend = dict(
            type="scatter",
            x=node_x,
            y=node_y,
            mode="markers",
            hoverinfo="skip",
            marker=dict(
                color=sorted_weights,
                colorscale=[functions.to_rgb(cmap(value)) for value in sorted_normalized],
                size=14,
                colorbar=dict(thickness=20),
            ),
        )

        node_trace = go.Scatter(
            x=node_x,
            y=node_y,
            mode="markers+text",
            hoverinfo="x+y",
            marker=dict(color="LightSkyBlue", size=30, line_width=2),
            text=node_text,
        )

        fig = go.Figure(
            data=edge_scatters + [legend, node_trace],
            layout=go.Layout(
                plot_bgcolor="#FFF",
                showlegend=False,
                hovermode="closest",
                margin=dict(b=20, l=5, r=5, t=40),
                xaxis=dict(showgrid=False, zeroline=False, showticklabels=False),
                yaxis=dict(showgrid=False, zeroline=False, showticklabels=False),
            ),
        )

        for i, edge in enumerate(edges):
            x1, y1 = self.positions[edge[0]]
            x2, y2 = self.positions[edge[1]]
            fig.add_annotation(
                x=(min(x1, x2) + ((max(x1, x2) - min(x1, x2)) / 2)),
                y=(min(y1, y2) + ((max(y1, y2) - min(y1, y2)) / 2)),
                text=str(weights[i]),
            )

        return fig

    def display_solution(self, result: Sequence) -> None:
        """displays a solution (partition) to maxcut. The result is specified by a subset of
        vertices
        """
        partition = self._as_partition(result)
        node_color = ["#179c7d" if node in partition else "#F58220" for node in self.graph.nodes()]

        nx.draw_networkx(
            self.graph,
            edge_cmap=colormaps["plasma"],
            node_color=node_color,
        )

    def evaluate_objective(self, result: Sequence) -> float:
        """returns the cut value of a proposed result (a node subset or bitstring)"""
        partition = self._as_partition(result)
        total_cut = 0
        for u, v, weight in self.graph.edges(data="weight", default=1):
            if (u in partition) != (v in partition):
                total_cut += weight
        return total_cut

    def formulate_qubo(self, scaling_factor: float = 1) -> tuple[float, np.ndarray]:
        """formulates the MaxCut qubo."""
        offset = 0  # no offset for maxcut, qubo value is the negative of the cut value
        return (
            offset,
            -scaling_factor * nx.laplacian_matrix(self.graph, weight="weight").toarray(),
        )

    def formulate_problem(
        self, mode: str = "QUBO", scaling_factor: float = 1
    ) -> tuple[float, np.ndarray]:
        """returns offset and qubo tensor for the MaxCut instance"""
        if not isinstance(mode, str):
            raise TypeError(f"Mode argument must be string, not {type(mode)}.")

        if mode.lower() == "qubo":
            return self.formulate_qubo(scaling_factor)

        supported_modes = [s.lower() for s in self.direct_encoding_modes]
        raise ValueError(f"Mode {mode!r} isn't supported, choose from {supported_modes}.")

direct_encoding_modes class-attribute instance-attribute 

direct_encoding_modes = ('QUBO',)

alias class-attribute instance-attribute 

alias = [
    "wMaxCut",
    "MaximumCut",
    "weightedMaxCut",
    "weightedMaximumCut",
]

weight_tol class-attribute instance-attribute 

weight_tol = 1e-05

graph instance-attribute 

graph = input_data

adjacency_matrix instance-attribute 

adjacency_matrix = nx.to_numpy_array(self.graph)

positions instance-attribute 

positions = None

__init__ 

__init__(input_data)

Constructs a MaxCut instance from a NetworkX graph or adjacency matrix.

Parameters:

Name Type Description Default
input_data Any

A NetworkX graph (optionally with edge weights) or a square numpy array representing an adjacency/weight matrix.

 required
Source code in src/quast_decisiontree/problems/classes/max_cut.py 
39
40
41
42
43
44
45
46
47
48
49
50
51
def __init__(self, input_data: Any) -> None:
    """Constructs a MaxCut instance from a NetworkX graph or adjacency matrix.

    Args:
        input_data: A NetworkX graph (optionally with edge weights) or a
            square numpy array representing an adjacency/weight matrix.
    """
    if isinstance(input_data, nx.Graph):
        self.graph = input_data
    else:
        self.graph = nx.from_numpy_array(np.asarray(input_data))
    self.adjacency_matrix = nx.to_numpy_array(self.graph)
    self.positions = None

from_dict classmethod 

from_dict(problem_dict)

attempts to construct a MaxCut instance from the data

Dictionary keys: "edges" - a list of edges, with integers labelling the nodes. Single edges will be either a pair (resulting in an unweighted Maxcut problem), or 3-tuples (u, v, weight). All edges should be weighted or all unweighted. All other dictionary keys are ignored.

Returns: (Weighted) Maxcut instance.

Source code in src/quast_decisiontree/problems/classes/max_cut.py 
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
@classmethod
def from_dict(cls, problem_dict: Mapping) -> "MaxCut":
    """attempts to construct a MaxCut instance from the data

    Dictionary keys:
    "edges" - a list of edges, with integers labelling the nodes. Single edges will be either a
            pair (resulting in an unweighted Maxcut problem), or 3-tuples (u, v, weight). All
            edges should be weighted or all unweighted.
    All other dictionary keys are ignored.

    Returns:
    (Weighted) Maxcut instance.
    """
    edges = problem_dict.get("edges")
    if edges is None:
        raise InvalidProblemDictError(
            "Problem dictionary specifying MaxCut contains no edge data."
        )
    if not edges:
        raise InvalidProblemDictError(
            "Edge list is empty; cannot construct a MaxCut instance."
        )

    shape = functions.list_shape(edges)
    if shape == 2:
        return cls(nx.Graph(edges))
    if shape == 3:
        graph = nx.Graph()
        graph.add_weighted_edges_from(edges)
        return cls(graph)
    raise InvalidProblemDictError("Edge list doesn't have the correct format.")

to_dict 

to_dict()

Converts the MaxCut instance into a problem dictionary.

Returns:

Name Type Description
dict dict

The resulting dictionary will be of the form {"problem_class": "MaxCut", "edges" : edges} where the edges are given as either 2- or 3-tuples of the underlying graph.
Source code in src/quast_decisiontree/problems/classes/max_cut.py 
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
def to_dict(self) -> dict:
    """Converts the MaxCut instance into a problem dictionary.

    Returns:
        dict: The resulting dictionary will be of the form
            {"problem_class": "MaxCut", "edges" : edges} where the edges
            are given as either 2- or 3-tuples of the underlying graph.
    """
    if nx.is_weighted(self.graph):
        problem_class = "wMaxCut"
        edges = list(self.graph.edges(data="weight"))
    else:
        problem_class = "MaxCut"
        edges = list(self.graph.edges())

    return {"problem_class": problem_class, "edges": edges}

__eq__ 

__eq__(other)

checks whether two given MaxCut instances are equivalent, e.g. they are isomorphic including (if existent) their edge weights

Source code in src/quast_decisiontree/problems/classes/max_cut.py 
102
103
104
105
106
107
108
109
110
def __eq__(self, other: object) -> bool:
    """checks whether two given MaxCut instances are equivalent, e.g. they are isomorphic
    including (if existent) their edge weights
    """
    if not isinstance(other, MaxCut):
        return NotImplemented
    return nx.is_isomorphic(
        self.graph, other.graph, edge_match=lambda x, y: _edge_match(x, y, self.weight_tol)
    )

create_random_instance classmethod 

create_random_instance(
    size,
    *,
    graph_type="er",
    graph_params=None,
    weighted=True,
    seed=None,
    rand_type="uniform",
    rand_params=None,
)

create a random MaxCut instance of the specified graph type. If weighted, the weights are drawn from the specified distribution.

Parameters: size: how many vertices the graph will have graph_type: the graph type to generate. Currently supported are "regular", "er" for Erdös-Renyi and "complete" graph_params: a dict of properties specifying the graph_type. These are the format and defaults: "regular" : {"degree": 3} "er" : {"probability": 0.5} "3-regular" : {} "complete" : {} weighted: if true, random weights drawn from the chosen distribution are added to the edges seed: A random seed. Two independent streams are spawned from it, one for the graph topology and one for the edge weights, so the two are decorrelated but jointly reproducible. rand_type: what distribution to draw the edge weights from. Currently, normal and uniform are supported. rand_params: the parameters directly passed to the random distribution (default ones will be used if None) "uniform": A (low, high) tuple. Default is (0,1) "normal": A (mean, standard_deviation) tuple. Default is (0,1)

Source code in src/quast_decisiontree/problems/classes/max_cut.py 
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
@classmethod
def create_random_instance(
    cls,
    size: int,
    *,
    graph_type: str = "er",
    graph_params: Any = None,
    weighted: bool = True,
    seed: Any = None,
    rand_type: str = "uniform",
    rand_params: Any = None,
):
    """create a random MaxCut instance of the specified graph type. If weighted, the weights
    are drawn from the specified distribution.

    Parameters:
    size: how many vertices the graph will have
    graph_type: the graph type to generate. Currently supported are "regular", "er"
    for Erdös-Renyi and "complete"
    graph_params: a dict of properties specifying the graph_type. These are the format
    and defaults:
        "regular" : {"degree": 3}
        "er" : {"probability": 0.5}
        "3-regular" : {}
        "complete" : {}
    weighted: if true, random weights drawn from the chosen distribution are added to the edges
    seed: A random seed. Two independent streams are spawned from it, one for the graph
        topology and one for the edge weights, so the two are decorrelated but jointly
        reproducible.
    rand_type: what distribution to draw the edge weights from. Currently, normal and uniform
    are supported.
    rand_params: the parameters directly passed to the random distribution (default ones will
    be used if None)
        "uniform": A (low, high) tuple. Default is (0,1)
        "normal": A (mean, standard_deviation) tuple. Default is (0,1)
    """
    if rand_type.lower() not in ["uniform", "normal"]:
        logger.warning(f"Unknown rand_type {rand_type!r}, defaulting to uniform.")
        rand_type = "uniform"

    weight_seed, graph_seed_source = np.random.SeedSequence(seed).spawn(2)
    graph_seed = int(graph_seed_source.generate_state(1)[0])

    if weighted:
        weight_rng = rd.default_rng(weight_seed)
        if rand_params is None:
            rand_params = (0, 1)
        if rand_type == "uniform":
            randfun = weight_rng.uniform
        else:
            randfun = weight_rng.normal

    allowed_graph_types = ["3-regular", "regular", "er", "complete"]

    if graph_type.lower() not in allowed_graph_types:
        raise ValueError(
            f"Graph type {graph_type!r} is not supported. Supported types:"
            f" {allowed_graph_types}."
        )

    if graph_params is None:
        graph_params = {}
    if graph_type.lower() in ["regular", "3-regular"]:
        if "degree" in graph_params and graph_type.lower() == "regular":
            degree = graph_params["degree"]
        else:
            degree = 3
        rand_graph = nx.random_regular_graph(degree, size, seed=graph_seed)

    elif graph_type.lower() == "er":
        prob = graph_params.get("probability", 0.5)
        rand_graph = nx.fast_gnp_random_graph(size, prob, seed=graph_seed)

    elif graph_type.lower() == "complete":
        rand_graph = nx.complete_graph(size)

    if weighted:
        for u, v in rand_graph.edges():
            rand_graph[u][v]["weight"] = randfun(*rand_params)

    ins = cls(rand_graph)
    # add positions so it can later be displayed using Plotly
    spring_layout_positions = nx.spring_layout(rand_graph)
    coordinate_list = []
    for i, _ in enumerate(spring_layout_positions):
        coordinate_list.append(spring_layout_positions[i])

    ins.positions = coordinate_list

    return ins

is_feasible classmethod 

is_feasible(solution_string)

all solution strings are feasible for MaxCut!

Source code in src/quast_decisiontree/problems/classes/max_cut.py 
203
204
205
206
@classmethod
def is_feasible(cls, solution_string: str) -> bool:
    """all solution strings are feasible for MaxCut!"""
    return True

display 

display()

displays the underlying graph including edge weights

Returns a colormap figure indicating the mapping between edge weights and colours

Source code in src/quast_decisiontree/problems/classes/max_cut.py 
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
def display(self) -> go.Figure:
    """displays the underlying graph including edge weights

    Returns a colormap figure indicating the mapping between edge weights and colours
    """
    if self.positions is None:
        raise AttributeError(
            "The display function cannot be called when the attribute positions is not"
            " specified"
        )

    completelist = list(self.graph.edges(data="weight", default=1))
    edges = list(zip(*list(zip(*completelist, strict=False))[:2], strict=False))
    weights = list(zip(*completelist, strict=False))[2]

    weight_array = np.asarray(weights, dtype=float)
    span = weight_array.max() - weight_array.min()
    if span > 0:
        normalized_weights = (weight_array - weight_array.min()) / span
    else:
        normalized_weights = np.zeros_like(weight_array)

    cmap = colormaps["plasma"]

    edge_scatters = []
    for i, edge in enumerate(edges):
        edge_x = []
        edge_y = []

        x1, y1 = self.positions[edge[0]]
        x2, y2 = self.positions[edge[1]]
        edge_x.append(x1)
        edge_x.append(x2)
        edge_x.append(None)
        edge_y.append(y1)
        edge_y.append(y2)
        edge_y.append(None)

        edge_trace = go.Scatter(
            cliponaxis=True,
            x=edge_x,
            y=edge_y,
            line=dict(width=2, color=functions.to_rgb(color=cmap(normalized_weights[i]))),
            hoverinfo="skip",
            mode="lines",
        )

        edge_scatters.append(edge_trace)

    node_x = []
    node_y = []
    node_text = []

    for i, pos in enumerate(self.positions):
        x, y = pos
        node_x.append(x)
        node_y.append(y)
        node_text.append(str(i))

    sort_order = np.argsort(weight_array)
    sorted_weights = weight_array[sort_order]
    sorted_normalized = normalized_weights[sort_order]

    legend = dict(
        type="scatter",
        x=node_x,
        y=node_y,
        mode="markers",
        hoverinfo="skip",
        marker=dict(
            color=sorted_weights,
            colorscale=[functions.to_rgb(cmap(value)) for value in sorted_normalized],
            size=14,
            colorbar=dict(thickness=20),
        ),
    )

    node_trace = go.Scatter(
        x=node_x,
        y=node_y,
        mode="markers+text",
        hoverinfo="x+y",
        marker=dict(color="LightSkyBlue", size=30, line_width=2),
        text=node_text,
    )

    fig = go.Figure(
        data=edge_scatters + [legend, node_trace],
        layout=go.Layout(
            plot_bgcolor="#FFF",
            showlegend=False,
            hovermode="closest",
            margin=dict(b=20, l=5, r=5, t=40),
            xaxis=dict(showgrid=False, zeroline=False, showticklabels=False),
            yaxis=dict(showgrid=False, zeroline=False, showticklabels=False),
        ),
    )

    for i, edge in enumerate(edges):
        x1, y1 = self.positions[edge[0]]
        x2, y2 = self.positions[edge[1]]
        fig.add_annotation(
            x=(min(x1, x2) + ((max(x1, x2) - min(x1, x2)) / 2)),
            y=(min(y1, y2) + ((max(y1, y2) - min(y1, y2)) / 2)),
            text=str(weights[i]),
        )

    return fig

display_solution 

display_solution(result)

displays a solution (partition) to maxcut. The result is specified by a subset of vertices

Source code in src/quast_decisiontree/problems/classes/max_cut.py 
329
330
331
332
333
334
335
336
337
338
339
340
def display_solution(self, result: Sequence) -> None:
    """displays a solution (partition) to maxcut. The result is specified by a subset of
    vertices
    """
    partition = self._as_partition(result)
    node_color = ["#179c7d" if node in partition else "#F58220" for node in self.graph.nodes()]

    nx.draw_networkx(
        self.graph,
        edge_cmap=colormaps["plasma"],
        node_color=node_color,
    )

evaluate_objective 

evaluate_objective(result)

returns the cut value of a proposed result (a node subset or bitstring)

Source code in src/quast_decisiontree/problems/classes/max_cut.py 
342
343
344
345
346
347
348
349
def evaluate_objective(self, result: Sequence) -> float:
    """returns the cut value of a proposed result (a node subset or bitstring)"""
    partition = self._as_partition(result)
    total_cut = 0
    for u, v, weight in self.graph.edges(data="weight", default=1):
        if (u in partition) != (v in partition):
            total_cut += weight
    return total_cut

formulate_qubo 

formulate_qubo(scaling_factor=1)

formulates the MaxCut qubo.

Source code in src/quast_decisiontree/problems/classes/max_cut.py 
351
352
353
354
355
356
357
def formulate_qubo(self, scaling_factor: float = 1) -> tuple[float, np.ndarray]:
    """formulates the MaxCut qubo."""
    offset = 0  # no offset for maxcut, qubo value is the negative of the cut value
    return (
        offset,
        -scaling_factor * nx.laplacian_matrix(self.graph, weight="weight").toarray(),
    )

formulate_problem 

formulate_problem(mode='QUBO', scaling_factor=1)

returns offset and qubo tensor for the MaxCut instance

Source code in src/quast_decisiontree/problems/classes/max_cut.py 
359
360
361
362
363
364
365
366
367
368
369
370
def formulate_problem(
    self, mode: str = "QUBO", scaling_factor: float = 1
) -> tuple[float, np.ndarray]:
    """returns offset and qubo tensor for the MaxCut instance"""
    if not isinstance(mode, str):
        raise TypeError(f"Mode argument must be string, not {type(mode)}.")

    if mode.lower() == "qubo":
        return self.formulate_qubo(scaling_factor)

    supported_modes = [s.lower() for s in self.direct_encoding_modes]
    raise ValueError(f"Mode {mode!r} isn't supported, choose from {supported_modes}.")