Metadata-Version: 2.4
Name: connected-k-center
Version: 0.2.1
Summary: Implementations of algorithms for connected k-center on path graphs.
License: MIT
License-File: LICENSE
Author: Lukas Drexler
Author-email: lukas.drexler@hhu.de
Requires-Python: >=3.10,<4.0
Classifier: License :: OSI Approved :: MIT License
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.10
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Classifier: Programming Language :: Python :: 3.13
Classifier: Programming Language :: Python :: 3.14
Requires-Dist: numpy (>=1.26.4,<2.0.0)
Requires-Dist: scikit-learn (>=1.6.1,<2.0.0)
Description-Content-Type: text/markdown

[![Build Status](https://github.com/algo-hhu/connected-k-center/actions/workflows/mypy-flake-test.yml/badge.svg)](https://github.com/algo-hhu/connected-k-center/actions)
[![License: MIT](https://img.shields.io/badge/License-MIT-yellow.svg)](https://opensource.org/licenses/MIT)
[![Supported Python version](https://img.shields.io/badge/python-3.10+-blue.svg)](https://www.python.org/downloads/release/python-3100/)
[![Stable Version](https://img.shields.io/pypi/v/connected-k-center?label=stable)](https://pypi.org/project/connected-k-center/)


# Connected Path Graph Clustering

A library for algorithms for the connected k-center problem (as described in [1]). In this problem setting, the input consists of a point set $P$ and a desired number of centers $k$, along with a *connectivity graph* $G = (P,E)$. The goal is to partition $P$ into (at most) $k$ *clusters* $C_1, \ldots, C_k$, such that, for every $i$, the subgraph of $G$ induced by $C_i$ is connected.

As of now, only an algorithm for path graphs is implemented. A path graph is a graph whose connected components are simple paths. This algorithm was developed by Johanna Hillebrand and implemented by Julius Mann.


### References
[1] Drexler, L., Eube, J., Luo, K., Reineccius, D., Röglin, H., Schmidt, M., & Wargalla, J. (2024). Connected k-center and k-diameter clustering. Algorithmica, 86(11), 3425-3464.

## Installation

```bash
pip install connected_k_center
```

## Usage

The estimator expects a number $k$ of desired clusters and (optionally) a string that specifies the metric. Possible values are "rmse" (default), "euclidean" and "manhattan".

The fit method expects two arguments: A 2d numpy array of dimension $n\times d$ (where n is the number points and d the dimension they live in), and a numpy array of integers, specifying connected component IDs. If there is only one connected component, this argument can be omitted. 

```python
from connected_k_center import PathCKC

X = [
    [0., 1.,
    [1., 0.],
    [2., 1.],
    [1., 1.],
    [2., 0.],
    [3., 1.],
]

cids = [0,0,0,0,0,0]

pckc = PathCKC(n_clusters=2, metric="euclidean")
pckc.fit(X, cids)

print(pckc.optimal_radius_) # 1.4142135623730951
print(pckc.cluster_centers_indices_) # [1,5]
print(pckc.labels_) # [1,1,1,1,1,5]
```

The package also provides a `read_instance` method, that expects a path to a csv file where each line contains the coordinates of a point, and the order of the points determines the ordering along the path. A new connected component is indicated by a blank line. It returns a tuple (X, cids).

```python
from connected_k_center import PathKCK, read_instance

(X, cids) = read_instance("path/to/csv")

pckc = PathCKC(n_clusters=2, metric="euclidean")
pckc.fit(X, cids)

print(pckc.optimal_radius_) # 1.4142135623730951
print(pckc.cluster_centers_indices_) # [1,5]
print(pckc.labels_) # [1,1,1,1,1,5]

```


## Development

Install [poetry](https://python-poetry.org/docs/#installation)
```bash
curl -sSL https://install.python-poetry.org | python3 -
```

Install clang
```bash
sudo apt-get install clang
```

Set clang variables
```bash
export CXX=/usr/bin/clang++
export CC=/usr/bin/clang
```

Install the package
```bash
poetry install
```

If the installation does not work and you do not see the C++ output, you can build the package to see the stack trace
```bash
poetry build
```

Run the tests
```bash
poetry run python -m unittest discover tests -v
```

