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

Navigation

  • index
  • modules |
  • next |
  • previous |
  • Strawberry Fields 0.23.0 documentation »
  • sf.apps »
  • sf.apps.subgraph »

Using Strawberry Fields

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

Development

  • Development guide
  • Migration guides
  • Research and contribution
  • Release notes

API

  • sf
  • sf.apps
  • sf.backends
  • sf.compilers
  • sf.circuitdrawer
  • 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.subgraph
  4. sf.apps.subgraph.search
  5. Show on GitHub

sf.apps.subgraph.search¶

search(subgraphs, graph, min_size, max_size, max_count=10, node_select='uniform')[source]¶

Search for dense subgraphs within an input size range.

For each subgraph from subgraphs, this function resizes using resize() to the input range specified by min_size and max_size, resulting in a range of differently sized subgraphs. This function loops over all elements of subgraphs and keeps track of the max_count number of densest subgraphs identified for each size.

In both growth and shrink phases of resize(), there may be multiple candidate nodes with equal degree to add to or remove from the subgraph. The method of selecting the node 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 highest weight (when growing) and lowest weight (when shrinking), settling remaining ties by uniform random choice.

Example usage:

>>> s = data.Planted()
>>> g = nx.Graph(s.adj)
>>> s = sample.postselect(s, 16, 30)
>>> s = sample.to_subgraphs(s, g)
>>> search(s, g, 8, 9, max_count=3)
{9: [(0.9722222222222222, [21, 22, 23, 24, 25, 26, 27, 28, 29]),
  (0.9722222222222222, [20, 21, 22, 24, 25, 26, 27, 28, 29]),
  (0.9444444444444444, [20, 21, 22, 23, 24, 25, 26, 27, 29])],
 8: [(1.0, [21, 22, 24, 25, 26, 27, 28, 29]),
  (1.0, [21, 22, 23, 24, 25, 26, 27, 28]),
  (1.0, [20, 21, 22, 24, 25, 26, 27, 29])]}
Parameters
  • subgraphs (list[list[int]]) – a list of subgraphs specified by their nodes

  • graph (nx.Graph) – the input graph

  • min_size (int) – minimum size to search for dense subgraphs

  • max_size (int) – maximum size to search for dense subgraphs

  • max_count (int) – maximum number of densest subgraphs to keep track of for each size

  • node_select (str, list or array) – method of settling ties when more than one node of equal degree can be added/removed. Can be "uniform" (default), or a NumPy array or list containing node weights.

Returns

a dictionary of different sizes, each containing a list of densest subgraphs reported as a tuple of subgraph density and subgraph nodes, sorted in non-increasing order of density

Return type

dict[int, list[tuple[float, list[int]]]]

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

Contents

Using Strawberry Fields

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

Development

  • Development guide
  • Migration guides
  • Research and contribution
  • Release notes

API

  • sf
  • sf.apps
    • sf.apps.clique
    • sf.apps.data
    • sf.apps.plot
    • sf.apps.points
    • sf.apps.qchem
    • sf.apps.sample
    • sf.apps.similarity
    • sf.apps.subgraph
      • Algorithm
      • Subgraph resizing
    • sf.apps.train
  • sf.backends
  • sf.compilers
  • sf.circuitdrawer
  • sf.decompositions
  • sf.engine
  • sf.io
  • sf.ops
  • sf.parameters
  • sf.program
  • sf.program_utils
  • sf.plot
  • sf.tdm
  • sf.utils

Navigation

  • index
  • modules |
  • next |
  • previous |
  • Strawberry Fields 0.23.0 documentation »
  • sf.apps »
  • sf.apps.subgraph »

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.

PennyLane

  • Home
  • Documentation
  • Forum
  • GitHub
  • Slack
  • Twitter
Strawberry Fields

  • Home
  • Documentation
  • GitHub
  • Slack
About

  • Home
  • About
  • Hardware
  • Research
  • Cloud
  • Blog

Stay updated with our newsletter
Copyright © 2022 Xanadu Quantum Technologies
TensorFlow, the TensorFlow logo, and any related marks are trademarks of Google Inc.