Metadata-Version: 2.4
Name: kmax-domset
Version: 0.1.0
Summary: K-Max algorithm for computing dominating sets in undirected graphs
Author: Gaurav Rayat
License: MIT License
        
        Copyright (c) 2026 Gaurav Rayat
        
        Permission is hereby granted, free of charge, to any person obtaining a copy
        of this software and associated documentation files (the "Software"), to deal
        in the Software without restriction, including without limitation the rights
        to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
        copies of the Software, and to permit persons to whom the Software is
        furnished to do so, subject to the following conditions:
        
        The above copyright notice and this permission notice shall be included in all
        copies or substantial portions of the Software.
        
        THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
        IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
        FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
        AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
        LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
        OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
        SOFTWARE.
        
Project-URL: Homepage, https://github.com/GauravRayat/kmax-domset
Project-URL: Bug Tracker, https://github.com/GauravRayat/kmax-domset/issues
Keywords: graph theory,dominating set,network analysis,combinatorial optimisation,karci centrality
Classifier: Development Status :: 4 - Beta
Classifier: Intended Audience :: Science/Research
Classifier: Intended Audience :: Education
Classifier: License :: OSI Approved :: MIT License
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.8
Classifier: Programming Language :: Python :: 3.9
Classifier: Programming Language :: Python :: 3.10
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Classifier: Topic :: Scientific/Engineering :: Mathematics
Classifier: Topic :: Scientific/Engineering :: Information Analysis
Requires-Python: >=3.8
Description-Content-Type: text/markdown
License-File: LICENSE
Requires-Dist: networkx>=2.6
Requires-Dist: matplotlib>=3.4
Provides-Extra: dev
Requires-Dist: pytest>=7.0; extra == "dev"
Dynamic: license-file

# kmax-domset

**K-Max algorithm for computing dominating sets in undirected graphs.**

A dominating set *D* of a graph *G = (V, E)* is a subset of vertices such
that every vertex in *V* either belongs to *D* or is adjacent to at least one
vertex in *D*.

This package implements the **K-Max algorithm**, which uses *Karci centrality*
— a measure that combines the node degree in the original graph, its degree in
a K-max spanning tree, and the sizes of fundamental cut-sets — to greedily
select the most structurally important nodes into the dominating set.

---

## Installation

```bash
pip install kmax-domset
```

---

## Quick Start

```python
from kmax_domset import KMaxAlgorithm

# Adjacency matrix: 1 = edge, 0 = no edge
adj = [
    [0, 1, 0, 0, 1],
    [1, 0, 1, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 1, 0, 1],
    [1, 0, 0, 1, 0],
]

algo = KMaxAlgorithm(adj)
D = algo.dominating_set()
print("Dominating set:", sorted(D))   # e.g. [0, 2]
```

---

## Visualisation

```python
algo.visualize(D)                        # spring layout (default)
algo.visualize(D, layout="circular")     # circular layout
algo.visualize(D, layout="kamada")       # Kamada-Kawai layout
algo.visualize(D, layout="spectral")     # spectral layout
```

Red nodes are in the dominating set; blue nodes are dominated neighbours.

---

## Building the adjacency matrix

### Manual (small graphs)

```python
n = 6
adj = [[0] * n for _ in range(n)]

edges = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 0), (0, 3)]
for u, v in edges:
    adj[u][v] = 1
    adj[v][u] = 1
```

### From NetworkX

```python
import networkx as nx
from kmax_domset import KMaxAlgorithm

G = nx.petersen_graph()
n = G.number_of_nodes()
adj = [[0] * n for _ in range(n)]
for u, v in G.edges():
    adj[u][v] = 1
    adj[v][u] = 1

D = KMaxAlgorithm(adj).dominating_set()
print("Dominating set:", sorted(D))
```

---

## API

### `KMaxAlgorithm(adj_matrix)`

| Parameter    | Type                | Description                              |
|-------------|---------------------|------------------------------------------|
| `adj_matrix` | `list[list[int]]`  | Square symmetric adjacency matrix (0/1). |

### `dominating_set() → set[int]`

Returns a set of node indices forming a dominating set.

### `visualize(D=None, layout="spring")`

| Parameter | Type           | Description                                       |
|-----------|----------------|---------------------------------------------------|
| `D`       | `set[int]`     | Dominating set to highlight. Auto-computed if `None`. |
| `layout`  | `str`          | `"spring"` · `"circular"` · `"kamada"` · `"spectral"` |

---

## Algorithm Overview

1. **Phase 1 — K-max spanning tree**: Build a spanning tree (forest for
   disconnected graphs) by greedily selecting the highest-degree unvisited
   node at each step using a max-priority queue.

2. **Phase 2 — Fundamental cut-sets**: For each tree branch (edge), compute
   the size of its fundamental cut-set — the number of graph edges (branches +
   chords) whose removal disconnects the two components formed by removing that
   branch.

3. **Karci centrality**: For each node *v*:  
   `K(v) = deg_G(v) + deg_T(v) + Σ cut_size(e)` for all tree branches *e*
   incident to *v*.

4. **Phase 3 — Greedy selection**: Repeatedly pick the undominated node with
   the highest Karci centrality and add it to the dominating set until all
   nodes are covered.

---

## Requirements

- Python ≥ 3.8
- `networkx >= 2.6`
- `matplotlib >= 3.4`

---

## License

MIT License — see [LICENSE](LICENSE).
