# UCSD Prim-Dijkstra Revisited

``` shell
Usage: ./pd_rev -h
    ------------------------------------------------------
      UCSD Prim-Dijkstra Revisited
      coded by Kwangsoo Han and Sriram Venkatesh
    ------------------------------------------------------
    -v       verbose mode (1 - 4)
    -a1      alpha for PD (default: 0.3)
    -a2      alpha for PD-II (default: 0.45)
    -bu      enable PD-II (default: off)
    -m1      Upperbound of max pathlength degradation in DAS wirelength minimization
             (default: 1.1 --> allow 10% max PL degradation for WL optimization)
    -f       input file with pointset
    -hv      enable HoVW Steinerization and Detour-Aware Steinerization (default off)
```

Sample input file: test.in

``` text
Net FE_OFN298734_n20421 10 (Net NetName NumOfTerminals)
0 10672450 199765 (Index x_loc y_loc, index 0 is root)
1 10769055 425415
2 10861105 425270
3 10734350 308990
4 10762195 340095
5 10741025 374295
6 10844360 425415
7 10862030 415010
8 10724765 254415
9 10745900 326235
```

## Example runs:
1. run Prim-Dijkstra with alpha = 0.3
``` shell
./pd_rev -f ./test.in -a1 0.3
```

2. run Prim-Dijkstra with alpha = 0.3 and PD-II with alpha = 0.45
``` shell
./pd_rev -f ./test.in -a1 0.3 -bu 1 -a2 0.45
```

3. run Prim-Dijkstra with alpha = 0.3 and PD-II with alpha = 0.45 and HVW Steinerization and DAS
``` shell
./pd_rev -f ./test.in -a1 0.3 -bu 1 -a2 0.45 -hv 1
```

## External references

-   C. J. Alpert, W.-K. Chow, K. Han, A. B. Kahng, Z. Li, D. Liu and
    S. Venkatesh, "Prim-Dijkstra Revisited: Achieving Superior Timing-driven
    Routing Trees", Proc. ACM/IEEE Intl. Symp. on Physical Design, 2018,
    pp. 10-17.


## Authors

- Kwangsoo Han
- Andrew B. Kahng
- Sriram Venkatesh

Contact: kwhan@ucsd.edu, abk@ucsd.edu, srvenkat@ucsd.edu

Affiliation: Computer Science and Engineering Department, UC San Diego,
             La Jolla, CA 92093-0404, USA

## License

BSD 3-Clause License. See [LICENSE](LICENSE) file.