QuEraComputing / UnitDiskMapping.jl

Reduce several arbitrary-connectivity optimization problems into maximum independent set problems on a grid
https://github.com/QuEraComputing/UnitDiskMapping.jl
Other
16 stars 3 forks source link

The new Unit disk map #2

Closed GiggleLiu closed 2 years ago

GiggleLiu commented 2 years ago

Grid mapping

@minhthin1028 This is the latest mapping with constant overhead factor 4. Now the petersen graph has only 39 rows and 38 columns.

image

Rules

Cross{false}
⋅ ⋅ ● ⋅ ⋅ 
● ● ◉ ● ● 
⋅ ⋅ ● ⋅ ⋅ 
⋅ ⋅ ● ⋅ ⋅ 
    ↓
⋅ ⋅ ● ⋅ ⋅ 
● ● ● ● ● 
⋅ ● ● ● ⋅ 
⋅ ⋅ ● ⋅ ⋅ 
Cross{true}
⋅ ● ⋅ 
◆ ◉ ● 
⋅ ◆ ⋅ 
  ↓
⋅ ● ⋅ 
● ● ● 
⋅ ● ⋅ 
TShape{true}
⋅ ● ⋅ ⋅ 
⋅ ● ⋅ ⋅ 
◆ ● ⋅ ⋅ 
⋅ ◆ ⋅ ⋅ 
   ↓
⋅ ● ⋅ ⋅ 
⋅ ⋅ ● ⋅ 
● ⋅ ● ⋅ 
⋅ ● ⋅ ⋅ 
TShape{false}
⋅ ● ⋅ ⋅ 
⋅ ● ⋅ ⋅ 
● ● ⋅ ⋅ 
⋅ ● ⋅ ⋅ 
⋅ ● ⋅ ⋅ 
   ↓
⋅ ● ⋅ ⋅ 
⋅ ⋅ ● ⋅ 
● ⋅ ● ⋅ 
⋅ ⋅ ● ⋅ 
⋅ ● ⋅ ⋅ 
Turn
⋅ ● ⋅ ⋅ 
⋅ ● ⋅ ⋅ 
⋅ ● ● ● 
⋅ ⋅ ⋅ ⋅ 
   ↓
⋅ ● ⋅ ⋅ 
⋅ ⋅ ● ⋅ 
⋅ ⋅ ⋅ ● 
⋅ ⋅ ⋅ ⋅ 

julia> for s in (Cross{false}(), Cross{true}(), TShape{true}(), TShape{false}(), Turn()) println(typeof(s)); println(s); println() end
Cross{false}
⋅ ⋅ ● ⋅ ⋅ 
● ● ◉ ● ● 
⋅ ⋅ ● ⋅ ⋅ 
⋅ ⋅ ● ⋅ ⋅ 
    ↓
⋅ ⋅ ● ⋅ ⋅ 
● ● ● ● ● 
⋅ ● ● ● ⋅ 
⋅ ⋅ ● ⋅ ⋅ 

Cross{true}
⋅ ● ⋅ 
◆ ◉ ● 
⋅ ◆ ⋅ 
  ↓
⋅ ● ⋅ 
● ● ● 
⋅ ● ⋅ 

TShape{true}
⋅ ● ⋅ ⋅ 
⋅ ● ⋅ ⋅ 
◆ ● ⋅ ⋅ 
⋅ ◆ ⋅ ⋅ 
   ↓
⋅ ● ⋅ ⋅ 
⋅ ⋅ ● ⋅ 
● ⋅ ● ⋅ 
⋅ ● ⋅ ⋅ 

TShape{false}
⋅ ● ⋅ ⋅ 
⋅ ● ⋅ ⋅ 
● ● ⋅ ⋅ 
⋅ ● ⋅ ⋅ 
⋅ ● ⋅ ⋅ 
   ↓
⋅ ● ⋅ ⋅ 
⋅ ⋅ ● ⋅ 
● ⋅ ● ⋅ 
⋅ ⋅ ● ⋅ 
⋅ ● ⋅ ⋅ 

Turn
⋅ ● ⋅ ⋅ 
⋅ ● ⋅ ⋅ 
⋅ ● ● ● 
⋅ ⋅ ⋅ ⋅ 
   ↓
⋅ ● ⋅ ⋅ 
⋅ ⋅ ● ⋅ 
⋅ ⋅ ⋅ ● 
⋅ ⋅ ⋅ ⋅