# Source code for strawberryfields.apps.clique

# Copyright 2019 Xanadu Quantum Technologies Inc.

# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at

# Unless required by applicable law or agreed to in writing, software
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
r"""
Tools for users to identify large cliques in graphs.

A clique is a subgraph where all nodes are connected to each other. The maximum clique problem is
to identify the largest clique in a graph. It has been shown that samples from GBS can be used to
select dense subgraphs as a starting seed for heuristic algorithms :cite:banchi2019molecular.

.. seealso::

:ref:apps-clique-tutorial

Algorithm
^^^^^^^^^

This module provides :func:search, a variant of the local search heuristics described in
:cite:pullan2006dynamic and :cite:pullan2006phased. The algorithm proceeds as follows:

#. A small clique in the graph is identified. The initial clique can be a single node, or it can
be obtained by shrinking a random subgraph, for example obtained from GBS.
#. The clique is grown as much as possible by adding nodes connected to all nodes in the clique.
#. When no more growth is possible, a node in the clique is swapped with a node outside of it.

Steps 2-3 are repeated until a pre-determined number of steps have been completed, or until no
more growth or swaps are possible.

Clique growth and swapping
^^^^^^^^^^^^^^^^^^^^^^^^^^

A clique can be grown by evaluating the set :math:C_0 of nodes in the remainder of the graph that
are connected to all nodes in the clique. A single node from :math:C_0 is selected and added to
the clique. This process is repeated until :math:C_0 becomes empty. This is provided with the
:func:grow function.

Searching the local space around a clique can be achieved by swapping a node from the clique with a
node in the remainder of the graph. The first step is to evaluate the set :math:C_1 of nodes in
the remainder of the graph that are connected to *all but one* of the nodes in the current
clique. A swap is then performed by adding the node into the clique and removing the node in the
clique that is not connected to it. This is provided with the :func:swap function.

Whenever the sets :math:C_0 and :math:C_1 used during growth and swapping have more than
one element, there must be a choice of which node to add or swap. The supported choices are:

- Select among candidate nodes uniformly at random;
- Select the candidate node with the greatest degree, settling remaining ties uniformly at random;
- Select the candidate node with the greatest node weight, settling remaining ties uniformly at
random.

Using GBS to find a starting clique
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Samples from GBS correspond to subgraphs that are likely to be dense.
These subgraphs may not be cliques, which is the required input to the :func:search algorithm.
To reconcile this, a subgraph may be shrunk using the :func:shrink function by removing nodes
until the remainder forms a clique. This can be achieved by selecting the node with the lowest
degree relative to the rest of subgraph and removing the node, repeating the process until a
clique is found.
"""
from typing import Union

import networkx as nx
import numpy as np

[docs]def search(
clique: list, graph: nx.Graph, iterations, node_select: Union[str, np.ndarray, list] = "uniform"
) -> list:
"""Local search algorithm for identifying large cliques.

This function implements a version of the local search algorithm given in
:cite:pullan2006dynamic and :cite:pullan2006phased. It proceeds by iteratively applying
phases of greedy growth and plateau search to the input clique subgraph.

**Growth phase**

Growth is achieved using the :func:~.grow function, which repeatedly evaluates the
set :math:C_0 of nodes in the remainder of the graph that are connected to all nodes in the
clique, and selects one candidate node from :math:C_0 to make a larger clique.

**Search phase**

Plateau search is performed with the :func:~.swap function, which evaluates the set
:math:C_1 of nodes in the remainder of the graph that are connected to all but one of the
nodes in the clique. The function then proceeds to select one candidate from :math:C_1 and
swap it with its corresponding node in the clique.

Whenever the sets :math:C_0 and :math:C_1 used during growth and swapping have more than
one element, there must be a choice of which node to add or swap. This choice is specified
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.

**Stopping**

The iterative applications of growth and search are applied until either the specified number
of iterations has been carried out or when a dead end has been reached. The function reaches
a dead end when it is unable to perform any new swaps or growth.

**Example usage:**

>>> graph = nx.lollipop_graph(4, 1)
>>> clique = [3, 4]
>>> search(clique, graph, iterations=10)
[0, 1, 2, 3]

Args:
clique (list[int]): a subgraph specified by a list of nodes; the subgraph must be a clique
graph (nx.Graph): the input graph
iterations (int): number of steps in the algorithm
node_select (str, list or array): method of selecting nodes during swap and growth. Can
be "uniform" (default), "degree", or a NumPy array or list.

Returns:
list[int]: the largest clique found by the algorithm
"""
if iterations < 1:
raise ValueError("Number of iterations must be a positive int")

grown = grow(clique, graph, node_select=node_select)
swapped = swap(grown, graph, node_select=node_select)

iterations -= 1

if set(grown) == set(swapped) or iterations == 0:
return swapped

return search(swapped, graph, iterations, node_select)

[docs]def grow(
clique: list, graph: nx.Graph, node_select: Union[str, np.ndarray, list] = "uniform"
) -> list:
"""Iteratively adds new nodes to the input clique to generate a larger clique.

Each iteration involves calculating the set :math:C_0 (provided by the function
:func:c_0) with respect to the current clique. This set represents the nodes in the rest of
the graph that are connected to all of the nodes in the current clique. Therefore, adding any of
the nodes in :math:C_0 will create a larger clique. This function proceeds by repeatedly
evaluating :math:C_0 and selecting and adding a node from this set to add to the current
clique. Growth is continued until :math:C_0 becomes empty.

Whenever there are multiple nodes within :math:C_0, 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.complete_graph(10)
>>> clique = [0, 1, 2, 3, 4]
>>> grow(clique, graph)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Args:
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 nodes from :math:C_0 during
growth. Can be "uniform" (default), "degree", or a NumPy array or list.

Returns:
list[int]: a new clique subgraph of equal or larger size than the input
"""

if not set(clique).issubset(graph.nodes):
raise ValueError("Input is not a valid subgraph")

if not is_clique(graph.subgraph(clique)):
raise ValueError("Input subgraph is not a clique")

if isinstance(node_select, (list, np.ndarray)):
if len(node_select) != graph.number_of_nodes():
raise ValueError("Number of node weights must match number of nodes")
w = {n: node_select[i] for i, n in enumerate(graph.nodes)}
node_select = "weight"

clique = set(clique)
_c_0 = sorted(c_0(clique, graph))

while _c_0:
if node_select == "uniform":
elif node_select == "degree":
degrees = np.array([graph.degree(n) for n in _c_0])
elif node_select == "weight":
weights = np.array([w[n] for n in _c_0])
else:
raise ValueError("Node selection method not recognized")

_c_0 = sorted(c_0(clique, graph))

return sorted(clique)

[docs]def swap(
clique: list, graph: nx.Graph, node_select: Union[str, np.ndarray, list] = "uniform"
) -> list:
"""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 :math: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 :math:C_1 and corresponding nodes in the clique are provided by the
:func:c_1 function.

Whenever there are multiple nodes within :math: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]

Args:
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 :math:C_1
during swapping. Can be "uniform" (default), "degree", or a NumPy array or list.

Returns:
list[int]: a new clique subgraph of equal size as the input
"""

if not set(clique).issubset(graph.nodes):
raise ValueError("Input is not a valid subgraph")

if not is_clique(graph.subgraph(clique)):
raise ValueError("Input subgraph is not a clique")

if isinstance(node_select, (list, np.ndarray)):
if len(node_select) != graph.number_of_nodes():
raise ValueError("Number of node weights must match number of nodes")
w = {n: node_select[i] for i, n in enumerate(graph.nodes)}
node_select = "weight"

clique = set(clique)
_c_1 = c_1(clique, graph)

if _c_1:
if node_select == "uniform":
swap_index = np.random.choice(len(_c_1))
swap_nodes = _c_1[swap_index]
elif node_select == "degree":
degrees = np.array([graph.degree(n[1]) for n in _c_1])
to_swap_index = np.random.choice(np.where(degrees == degrees.max())[0])
swap_nodes = _c_1[to_swap_index]
elif node_select == "weight":
weights = np.array([w[n[1]] for n in _c_1])
to_swap_index = np.random.choice(np.where(weights == weights.max())[0])
swap_nodes = _c_1[to_swap_index]
else:
raise ValueError("Node selection method not recognized")

clique.remove(swap_nodes[0])

return sorted(clique)

[docs]def shrink(
subgraph: list, graph: nx.Graph, node_select: Union[str, np.ndarray, list] = "uniform"
) -> list:
"""Shrinks an input subgraph until it forms a clique.

Proceeds by removing nodes in the input subgraph one at a time until the result is a clique
that satisfies :func:is_clique. Upon each iteration, this function selects the node with
lowest degree relative to the subgraph and removes it.

In some instances, there may be multiple nodes of minimum degree as candidates to remove from
the subgraph. The method of selecting which of these nodes to remove is specified by the
node_select argument, which can be either:

- "uniform" (default): choose a node from the candidates uniformly at random;
- A list or array: specifying the node weights of the graph, resulting in choosing the node
from the candidates with the lowest weight, settling ties by uniform random choice.

**Example usage:**

>>> graph = nx.barbell_graph(4, 0)
>>> subgraph = [0, 1, 2, 3, 4, 5]
>>> shrink(subgraph, graph)
[0, 1, 2, 3]

Args:
subgraph (list[int]): a subgraph specified by a list of nodes
graph (nx.Graph): the input graph
node_select (str, list or array): method of settling ties when more than one node of
equal degree can be removed. Can be "uniform" (default), or a NumPy array or list.

Returns:
list[int]: a clique of size smaller than or equal to the input subgraph
"""

if not set(subgraph).issubset(graph.nodes):
raise ValueError("Input is not a valid subgraph")

if isinstance(node_select, (list, np.ndarray)):
if len(node_select) != graph.number_of_nodes():
raise ValueError("Number of node weights must match number of nodes")
w = {n: node_select[i] for i, n in enumerate(graph.nodes)}
node_select = "weight"

subgraph = graph.subgraph(subgraph).copy()  # A copy is required to be able to modify the
# structure of the subgraph (https://networkx.github.io/documentation/stable/reference/classes/generated/networkx.Graph.subgraph.html)

while not is_clique(subgraph):
degrees = np.array(subgraph.degree)
degrees_min = np.argwhere(degrees[:, 1] == degrees[:, 1].min()).flatten()

if node_select == "uniform":
to_remove_index = np.random.choice(degrees_min)
elif node_select == "weight":
weights = np.array([w[degrees[n][0]] for n in degrees_min])
to_remove_index = np.random.choice(np.where(weights == weights.min())[0])
else:
raise ValueError("Node selection method not recognized")

to_remove = degrees[to_remove_index][0]
subgraph.remove_node(to_remove)

return sorted(subgraph.nodes())

[docs]def is_clique(graph: nx.Graph) -> bool:
"""Determines if the input graph is a clique. A clique of :math:n nodes has exactly :math:n(
n-1)/2 edges.

**Example usage:**

>>> graph = nx.complete_graph(10)
>>> is_clique(graph)
True

Args:
graph (nx.Graph): the input graph

Returns:
bool: True if input graph is a clique and False otherwise
"""
edges = graph.edges
nodes = graph.order()

return len(edges) == nodes * (nodes - 1) / 2

[docs]def c_0(clique: list, graph: nx.Graph):
"""Generates the set :math:C_0 of nodes that are connected to all nodes in the input
clique subgraph.

The set :math:C_0 is defined in :cite:pullan2006phased and is used to determine nodes
that can be added to the current clique to grow it into a larger one.

**Example usage:**

>>> graph = nx.complete_graph(10)
>>> clique = [0, 1, 2, 3, 4]
>>> c_0(clique, graph)
[5, 6, 7, 8, 9]

Args:
clique (list[int]): a subgraph specified by a list of nodes; the subgraph must be a clique
graph (nx.Graph): the input graph

Returns:
list[int]: a list containing the :math:C_0 nodes for the clique

"""
if not is_clique(graph.subgraph(clique)):
raise ValueError("Input subgraph is not a clique")

clique = set(clique)
c_0_nodes = []
non_clique_nodes = set(graph.nodes) - clique

for i in non_clique_nodes:
if clique.issubset(graph.neighbors(i)):
c_0_nodes.append(i)

return c_0_nodes

[docs]def c_1(clique: list, graph: nx.Graph):
"""Generates the set :math:C_1 of nodes that are connected to all but one of the nodes in
the input clique subgraph.

The set :math:C_1 is defined in :cite:pullan2006phased and is used to determine outside
nodes that can be swapped with clique nodes to create a new clique.

**Example usage:**

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

Args:
clique (list[int]): a subgraph specified by a list of nodes; the subgraph must be a clique
graph (nx.Graph): the input graph

Returns:
list[tuple[int]]: A list of tuples. The first node in the tuple is the node in the clique
and the second node is the outside node it can be swapped with.
"""
if not is_clique(graph.subgraph(clique)):
raise ValueError("Input subgraph is not a clique")

clique = set(clique)
c_1_nodes = []
non_clique_nodes = set(graph.nodes) - clique

for i in non_clique_nodes:
neighbors_in_subgraph = clique.intersection(graph.neighbors(i))

if len(neighbors_in_subgraph) == len(clique) - 1:
to_swap = clique - neighbors_in_subgraph
(i_clique,) = to_swap
c_1_nodes.append((i_clique, i))

return c_1_nodes