search

Qiskit / rustworkx

A high performance Python graph library implemented in Rust.
https://www.rustworkx.org
Apache License 2.0
1.05k stars 146 forks source link

Add new layout methods #438

Open mtreinish opened 3 years ago

mtreinish commented 3 years ago

What is the expected enhancement?

Right now retworkx has several layout methods available: https://qiskit.org/documentation/retworkx/api.html#layout-functions but there are some other common examples (like a planar layout and kamada kawai) missing. We should expand the available layout functions so that they can be leveraged with the drawers. We can look at what networkx offers for this functionality to get some good examples: https://networkx.org/documentation/stable/reference/drawing.html#module-networkx.drawing.layout

enavarro51 commented 2 years ago

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.

Graf_K4_v_rovině svg (1)

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 #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.