sf.apps.clique.swap¶

swap(clique, graph, node_select='uniform')[source]

If possible, generates a new clique by swapping a node in the input clique with a node outside the clique.

Proceeds by calculating the set $$C_1$$ of nodes in the rest of the graph that are connected to all but one of the nodes in the clique. If this set is not empty, this function randomly picks a node and swaps it with the corresponding node in the clique that is not connected to it. The set $$C_1$$ and corresponding nodes in the clique are provided by the c_1() function.

Whenever there are multiple nodes within $$C_1$$, one must choose which node to add to the growing clique. This function allows a method of choosing nodes to be set with the node_select argument, which can be any of the following:

• "uniform" (default): choose a node from the candidates uniformly at random;

• "degree": choose the node from the candidates with the greatest degree, settling ties by uniform random choice;

• A list or array: specifying the node weights of the graph, resulting in choosing the node from the candidates with the greatest weight, settling ties by uniform random choice.

Example usage:

>>> graph = nx.wheel_graph(5)
>>> graph.remove_edge(0, 4)
>>> clique = [0, 1, 2]
>>> swap(clique, graph)
[0, 2, 3]

Parameters
• clique (list[int]) – a subgraph specified by a list of nodes; the subgraph must be a clique

• graph (nx.Graph) – the input graph

• node_select (str, list or array) – method of selecting incoming nodes from $$C_1$$ during swapping. Can be "uniform" (default), "degree", or a NumPy array or list.

Returns

a new clique subgraph of equal size as the input

Return type

list[int]

Contents

Using Strawberry Fields

Development

API