• Quantum Photonics
  • Install
  • Interactive
  • Documentation (current)
  • FAQ
  • Support
  • GitHub

Navigation

  • index
  • modules |
  • next |
  • previous |
  • Strawberry Fields 0.18.0-dev documentation »
  • sf.apps »
  • sf.apps.clique »

Using Strawberry Fields

  • Introduction
  • Hardware
  • Circuits
  • Operations
  • States
  • GBS datasets

Development

  • Development guide
  • Research and contribution
  • Release notes

API

  • sf
  • sf.apps
  • sf.api
  • sf.backends
  • sf.compilers
  • sf.circuitdrawer
  • sf.cli
  • sf.configuration
  • sf.decompositions
  • sf.engine
  • sf.io
  • sf.ops
  • sf.parameters
  • sf.program
  • sf.program_utils
  • sf.plot
  • sf.tdm
  • sf.utils
  1. Docs
  2. sf.apps
  3. sf.apps.clique
  4. sf.apps.clique.search
  5. Show on GitHub

sf.apps.clique.search¶

search(clique, graph, iterations, node_select='uniform')[source]¶

Local search algorithm for identifying large cliques.

This function implements a version of the local search algorithm given in [14] and [15]. It proceeds by iteratively applying phases of greedy growth and plateau search to the input clique subgraph.

Growth phase

Growth is achieved using the grow() function, which repeatedly evaluates the set \(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 \(C_0\) to make a larger clique.

Search phase

Plateau search is performed with the swap() function, which evaluates the set \(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 \(C_1\) and swap it with its corresponding node in the clique.

Whenever the sets \(C_0\) and \(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)
>>> graph.add_edge(2, 4)
>>> clique = [3, 4]
>>> search(clique, graph, iterations=10)
[0, 1, 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

  • 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

the largest clique found by the algorithm

Return type

list[int]

code/api/strawberryfields.apps.clique.search
 
Download Python script
 
Download Notebook
 
View on GitHub
Previous
Next

Downloads

code/api/strawberryfields.apps.clique.search
 
Download Python script
 
Download Notebook
 
View on GitHub

Navigation

  • index
  • modules |
  • next |
  • previous |
  • Strawberry Fields 0.18.0-dev documentation »
  • sf.apps »
  • sf.apps.clique »

Xanadu

Located in the heart of downtown Toronto, we've brought together exceptional minds from around the world to build quantum computers that are useful and available to people everywhere.

Strawberry Fields

  • Interactive
  • GitHub
  • Documentation
  • Slack channel
PennyLane

  • Home page
  • GitHub
  • Documentation
  • Discussion forum
  • Twitter
About

  • Home
  • Hardware
  • Software
  • Research
  • Blog
  • About

Stay updated with our newsletter
© Copyright 2019 | Xanadu | All rights reserved
TensorFlow, the TensorFlow logo and any related marks are trademarks of Google Inc.