# PowerDominationToolbox

## Simple Example and Verification of Install
To verify installation, use the Power Domination Toolbox to find the minimum power domination number of the cycle on 4 vertices.
```python
>>> import networkx as nx
>>> import powerdominationtoolbox as pdt
>>> graph = nx.cycle_graph(4)
>>> pds = pdt.PDT_minpds(graph)
>>> print(pds)
[0]
``` 

## Installing Into Python
The Power Domination Toolbox is a native python module.
Installing python can be done on both [windows]{https://docs.python.org/3/using/windows.html} and [Mac/Linux]{https://docs.python.org/3/using/windows.html} following the official guides.
Installing the Power Domination Toolbox module into your instance of python can be done with pip
```bash
$ python3 -m pip install powerdominationtoolbox
```

## Installing Into CoCalc/Sage
To maintain compatability with SageMath, the Power Domination Toolbox is installable into the Sage environment.
The following will install the Power Domination Toolbox into the Sage environment.
```bash
$ sage -pip install powerdominationtoolbox
```
Graphs must then be converted from Sage Graph objects to NetworkX graph objects.
Once this conversion has been made, the NetworkX graph objects can be used like the examples that follow.
Supposing that ```graph_1``` is a graph made in some Sage way, the conversion process is:
```python
>>> from powerdominationtoolbox.powerdominationtoolbox import sage_to_networkx_graph
>>> converted_graph = sage_to_networkx_graph(graph_1)
<networkx.classes.graph.Graph object at 0x...>
```

For importing this library from witin CoCalc with a free account you must do the following because CoCalc does not allow an outside internet connection with a free account.

1. Download this code as a zip file.
2. Extract the zip file on your local machine.
3. Go to your project in CoCalc and upload the file "powerdominationtoolbox.py".
4. Execute the load command in your sage worksheet.
Note, because the powerdominationtoolbox.py file itself contains prints and figure drawing, CoCalc may display these prints / figures when executing the following command.
```python
>>> load("powerdominationtoolbox.py")
```

## Using the Power Domination Toolbox
The PDT offers functions for various capabilities.
The following is a non-exhaustive list of usefull functions.
The [jupyter notebook within examples](https://github.com/JibJibFlutterhousen/PowerDominationToolbox/blob/main/examples/Power%20Domination%20Toolbox%20(v2).ipynb) shows usage of each function within the Power Domination Toolbox after the explicit code for the function.
1. Zero forcing, ```ZeroForce```
```python
>>> import powerdominationtoolbox as pdt
>>> graph = pdt.ZimGraph()
>>> initial_blue_vertices = ['1', '2', '3']
>>> resultant_blue_vertices = pdt.ZeroForce(graph, initial_blue_vertices)
>>> print(resultant_blue_vertices)
{'5', '8', '2', '6', '3', '1', '7', '4', '9'}
```
2. Domination, ```Dominate```
```python
>>> import powerdominationtoolbox as pdt
>>> graph = pdt.ZimGraph()
>>> initial_blue_vertices = ['1', '2', '3']
>>> resultant_blue_vertices = pdt.Dominate(graph, initial_blue_vertices)
>>> print(resultant_blue_vertices)
{'5', '2', '6', '3', '1', '7'}
```
3. Power domination, ```PowerDominate```
```python
>>> import powerdominationtoolbox as pdt
>>> graph = pdt.ZimGraph()
>>> initial_blue_vertices = ['2', '9']
>>> resultant_blue_vertices = pdt.PowerDominate(graph, initial_blue_vertices)
>>> print(resultant_blue_vertices)
{'5', '8', '2', '6', '10', '3', '1', '11', '9', '4', '7'}
```
4. Determining if a set is a power dominating set, ```isPDS```,
```python
>>> import powerdominationtoolbox as pdt
>>> graph = pdt.ZimGraph()
>>> initial_blue_vertices = ['2']
>>> is_pds = pdt.isPDS(graph, initial_blue_vertices)
>>> print(is_pds)
False
>>> initial_blue_vertices = ['2', '9']
>>> is_pds = pdt.isPDS(graph, initial_blue_vertices)
>>> print(is_pds)
True
```
5. JL-BW, brute force, method for locating a minimum power dominating set, ```JLBW_minpds```
```python
>>> import powerdominationtoolbox as pdt
>>> graph = pdt.ZimGraph()
>>> minimum_power_dominating_set = pdt.JLBW_minpds(graph)
>>> print(resultant_blue_vertices)
['1', '9']
```
6. Brute force, method for locating a minimum power dominating set by way of solving the restricted power domination problem on $G'$ subject to Pref $(G')$, ```PDT_minpds```
```python
>>> import powerdominationtoolbox as pdt
>>> graph = pdt.ZimGraph()
>>> minimum_power_dominating_set = pdt.PDT_minpds(graph)
>>> print(resultant_blue_vertices)
['9', '5']
```
7. Calculating the power domination number of a graph, ```PDT_pdn```
```python
>>> import powerdominationtoolbox as pdt
>>> graph = pdt.ZimGraph()
>>> pdn = pdt.PDT_pdn(graph)
>>> print(pdn)
2
```
8. Locating all power dominating sets of a given size while leveraging parallel computing methods, ```parallel_allpds_of_size```
```python
>>> import powerdominationtoolbox as pdt
>>> graph = pdt.ZimGraph()
>>> pdss = pdt.parallel_allpds_of_size(graph, 4)
>>> print(pdss)
[('1', '2', '5', '9'), ('1', '2', '5', '10'), ('1', '2', '5', '11'), ('1', '2', '3', '9'),...
```

## Datasets
The provided graph datasets are encoded in graph6 format.
For information on this graph format, please see http://users.cecs.anu.edu.au/~bdm/data/formats.txt.
Dataset_1.g6 contains 600, connected, Erdos-Renyi random graphs (100 each on 20, 40, 60, 80, 100, and 120 vertices) with edge probability of 0.05.
Dataset_2.g6 contains 665, connected, Erdos-Renyi random graphs on 80 vertices with edge probability of 0.05.

## Funding
This project was sponsored, in part, by the Air Force Research Laboratory via the Autonomy Technology Research Center and Wright State University.
This research was also supported by Air Force Office of Scientific Research award 23RYCOR004, and is Distribution A under the reference number AFRL-2023-2384 and AFRL-2024-1739.
