Good first issues in retworkx

[mtreinish]

Description

retworkx is a high performance general purpose graph library for python3 written in Rust to take advantage of the performance and safety that Rust provides. It was built as a replacement for Qiskit's previous networkx usage (hence the name) but is designed to provide a high performance general purpose graph library for any python application. The project was originally started to build a faster directed graph to use as the underlying data structure for the DAG at the center of qiskit-terra's transpiler, but it has since grown to cover all the graph usage in Qiskit and other applications. We use retworkx at the core of many of Qiskit's algorithms and functions (including the transpiler) when a graph representation is needed.

The full list of good first issues in retworkx can be found here.

Deliverables

The project is to work through good first issues on retworkx. So ideally pull requests and reviews of others pull requests on retworkx are the deliverable for this project. However, as it is a fairly open ended project to get involved in the development of retworkx the exact deliverables aren't set in stone. In previous iterations mentees have helped opened pull requests to other projects using retworkx along with other related tasks

Mentors details

• Mentor 1
  • Name: Matthew Treinish
  • GitHub ID: mtreinish
  • What they do: Qiskit core developer

Number of mentees

5

Type of mentees

• Mentor *
  • Required:
  • Some experience programming
  • Desire to contribute to an open source project
  • Nice to have:
  • Experience in Python
  • Experience in Rust (this is not expected and can be learned during the mentorship)
  • Experience with graph theory

[enavarro51]

Here are the presentation slides for Checkpoint 1. PlanarLayoutPres.pdf

[HuangJunye]

@enavarro51 Can you please provide your checkpoint 2 updates? Instructions are given in the slack channel.

[enavarro51]

Sorry, @HuangJunye. I put it in https://github.com/Qiskit/retworkx/issues/438, which is the issue I am actually working on.

Add Planar Layout to retworkx

The goal of this PR is to add a planar layout option to the other existing layout options in retworkx using the Rust language. A planar layout should provide better visualization of coupling maps in the gate_map module than existing options.

A planar graph can be displayed in the plane with no edges that intersect except at a node. As an example, a complete 4-node graph is planar since one of the diagonals can be placed outside the square, resulting in no intersecting edges. A complete 5-node graph is not planar.

Creating planar layouts in the general case is a complex problem and has been the subject of research over several decades. The process follows these steps.

1. Determine if the graph is planar. The method used in retworkx is the Left/Right planarity test from Ulrik Brandes: The Left-Right Planarity Test (2009).

2. If the graph is planar, create a planar embedding, which is an intermediate representation of the graph in the plane. The embedding defines the relative positions of the vertices in the plane. The version we are creating is a combinatorial embedding which is defined in terms of the cyclic ordering of the edges to a vertex. This and the following step draw heavily on the existing networkx python code.

3. The final stage is to convert the combinatorial embedding to an actual position list for the nodes in the graph, which can then be displayed using matplotlib or graphviz.

Step 1 has been submitted as PR https://github.com/Qiskit/retworkx/pull/475 by @georgios-ts and is awaiting review. Step 2 is about 60% complete and should be done within the next 2 weeks. Step 3 will follow.

[HuangJunye]

@enavarro51 Can you please upload your final showcase presentation here?

[enavarro51]

Here is the final presentation. PlanarLayoutPres.pptx