Algorithms

Implementations of graph-theory algorithms on the D-Wave system and other binary quadratic model samplers.

Canonicalization

canonical_chimera_labeling(G[, t])

Returns a mapping from the labels of G to chimera-indexed labeling.

Clique

A clique in an undirected graph G = (V, E) is a subset of the vertex set such that for every two vertices in C there exists an edge connecting the two.

maximum_clique(G[, sampler, lagrange])	Returns an approximate maximum clique.
clique_number(G[, sampler, lagrange])	Returns the number of vertices in the maximum clique of a graph.
is_clique(G, clique_nodes)	Determines whether the given nodes form a clique.

Coloring

Graph coloring is the problem of assigning a color to the vertices of a graph in a way that no adjacent vertices have the same color.

Example

The map-coloring problem is to assign a color to each region of a map (represented by a vertex on a graph) such that any two regions sharing a border (represented by an edge of the graph) have different colors.

Fig. 206 Coloring a map of Canada with four colors.

is_vertex_coloring(G, coloring)	Determines whether the given coloring is a vertex coloring of graph G.
min_vertex_color(G[, sampler, chromatic_lb, ...])	Returns an approximate minimum vertex coloring.
min_vertex_color_qubo(G[, chromatic_lb, ...])	Return a QUBO with ground states corresponding to a minimum vertex coloring.
vertex_color(G, colors[, sampler])	Returns an approximate vertex coloring.
vertex_color_qubo(G, colors)	Return the QUBO with ground states corresponding to a vertex coloring.

Cover

Vertex covering is the problem of finding a set of vertices such that all the edges of the graph are incident to at least one of the vertices in the set.

Fig. 207 Cover for a Chimera unit cell: the nodes of both the blue set of vertices (the horizontal tile of the Chimera unit cell) and the red set (vertical tile) connect to all 16 edges of the graph.

is_vertex_cover(G, vertex_cover)	Determines whether the given set of vertices is a vertex cover of graph G.
min_weighted_vertex_cover(G[, weight, ...])	Returns an approximate minimum weighted vertex cover.
min_vertex_cover(G[, sampler, lagrange])	Returns an approximate minimum vertex cover.

Elimination Ordering

Many algorithms for NP-hard problems are exponential in treewidth. However, finding a lower bound on treewidth is in itself NP-complete. [Gog2004] describes a branch-and-bound algorithm for computing the treewidth of an undirected graph by searching in the space of perfect elimination ordering of vertices of the graph.

A clique of a graph is a fully-connected subset of vertices; that is, every pair of vertices in the clique share an edge. A simplicial vertex is one whose neighborhood induces a clique. A perfect elimination ordering is an ordering of vertices \(1..n\) such that any vertex \(i\) is simplicial for the subset of vertices \(i..n\).

chimera_elimination_order(m[, n, t, coordinates])	Provides a variable elimination order for a Chimera graph.
elimination_order_width(G, order)	Calculates the width of the tree decomposition induced by a variable elimination order.
is_almost_simplicial(G, n)	Determines whether a node n in G is almost simplicial.
is_simplicial(G, n)	Determines whether a node n in G is simplicial.
max_cardinality_heuristic(G)	Computes an upper bound on the treewidth of graph G based on the max-cardinality heuristic for the elimination ordering.
minor_min_width(G)	Computes a lower bound for the treewidth of graph G.
min_fill_heuristic(G)	Computes an upper bound on the treewidth of graph G based on the min-fill heuristic for the elimination ordering.
min_width_heuristic(G)	Computes an upper bound on the treewidth of graph G based on the min-width heuristic for the elimination ordering.
pegasus_elimination_order(n[, coordinates])	Provides a variable elimination order for the Pegasus graph.
treewidth_branch_and_bound(G[, ...])	Computes the treewidth of graph G and a corresponding perfect elimination ordering.

Markov Networks

sample_markov_network(MN[, sampler, ...])	Samples from a markov network using the provided sampler.
markov_network_bqm(MN)	Construct a binary quadratic model for a markov network.

Matching

A matching is a subset of graph edges in which no vertex occurs more than once.

Fig. 208 A matching for a Chimera unit cell: no vertex is incident to more than one edge in the set of blue edges

matching_bqm(G)	Find a binary quadratic model for the graph's matchings.
maximal_matching_bqm(G[, lagrange])	Find a binary quadratic model for the graph's maximal matchings.
min_maximal_matching_bqm(G[, ...])	Find a binary quadratic model for the graph's minimum maximal matchings.
min_maximal_matching(G[, sampler])	Returns an approximate minimum maximal matching.

Maximum Cut

A maximum cut is a subset of a graph’s vertices such that the number of edges between this subset and the remaining vertices is as large as possible.

Fig. 209 Maximum cut for a Chimera unit cell: the blue line around the subset of nodes {4, 5, 6, 7} cuts 16 edges; adding or removing a node decreases the number of edges between the two complementary subsets of the graph.

maximum_cut(G[, sampler])	Returns an approximate maximum cut.
weighted_maximum_cut(G[, sampler])	Returns an approximate weighted maximum cut.

Independent Set

An independent set is a set of a graph’s vertices with no edge connecting any of its member pairs.

Fig. 210 Independent sets for a Chimera unit cell: the nodes of both the blue set of vertices (the horizontal tile of the Chimera unit cell) and the red set (vertical tile) are independent sets of the graph, with no blue node adjacent to another blue node and likewise for red nodes.

maximum_weighted_independent_set(G[, ...])	Returns an approximate maximum weighted independent set.
maximum_independent_set(G[, sampler, lagrange])	Returns an approximate maximum independent set.
is_independent_set(G, indep_nodes)	Determines whether the given nodes form an independent set.

Helper Functions

maximum_weighted_independent_set_qubo(G[, ...])

Return the QUBO with ground states corresponding to a maximum weighted independent set.

Partitioning

A k-partition consists of k disjoint and equally sized subsets of a graph’s vertices such that the total number of edges between nodes in distinct subsets is as small as possible.

Fig. 211 A 2-partition for a simple graph: the nodes in blue are in the ‘0’ subset, and the nodes in red are in the ‘1’ subset. There are no other arrangements with fewer edges between two equally sized subsets.

partition(G[, num_partitions, sampler])

Returns an approximate k-partition of G.

Social

A signed social network graph is a graph whose signed edges represent friendly/hostile interactions between vertices.

Fig. 212 A signed social graph for three nodes, where Eve and Bob are friendly with each other and hostile to Alice. This network is balanced because it can be cleanly divided into two subsets, {Bob, Eve} and {Alice}, with friendly relations within each subset and only hostile relations between the subsets.

structural_imbalance(S[, sampler])	Returns an approximate set of frustrated edges and a bicoloring.
structural_imbalance_ising(S)	Construct the Ising problem to calculate the structural imbalance of a signed social network.

Traveling Salesperson

A traveling salesperson route is an ordering of the vertices in a complete weighted graph.

Fig. 213 A traveling salesperson route of [2, 1, 0, 3].

traveling_salesperson(G[, sampler, ...])	Returns an approximate minimum traveling salesperson route.
traveling_salesperson_qubo(G[, lagrange, ...])	Return the QUBO with ground states corresponding to a minimum TSP route.