---
# System prepended metadata

title: CFPQ_PyAlgo

---

# CFPQ_PyAlgo

## Требования

1. Каждый алгоритм ( аля `MatrixAllPairsReachability` ) представляет из себя отдельную функцию ( `def matrix_all_pairs_reachability()` )
2. Поддерживать различные backend'ы
    * `scipy.sparse`
    * `pygraphblas`
    * `pysbla`
3. Фиксировать алгоритм в виде функции в библиотеке

## [Структура проекта](https://github.com/JetBrains-Research/CFPQ_PyAlgo/discussions/29#discussioncomment-1237981)

- cfpq_pyalgo
    - pygraphblas
        - algorithms
        - graphs
        - grammars
        - tests
    - pysbla
    - scipy

## Задачи

### Подготовка репозитория

- [x] Подготовить ветку

- [x] pre-commit & black

- [x] Continuous Integration

- [ ] Documentation Deployment

### Класс BooleanMatrixGraph

- [x] Разработать API для BooleanMatrixGraph:

```python=
from pygraphblas import Matrix, BOOL

class BooleanMatrixGraph:
    def __init__(self):
        self._matrices: Dict[str, Matrix] = dict()
        self._matrices_size: int = 0
        
    def __getitem__(self, label: str):
        if label not in self._matrices:
            raise KeyError(f"{label}")
        return self._matrices[label]
    
    def __setitem__(self, label: str, matrix: Matrix):
        self._matrices[label] = matrix
        
    @classmethod
    def from_nx_graph(cls, g: nx.MultiDiGraph):
        """
        
        Parameters
        ----------
        
        g: g.edge["label"] -- строка, которая метка
        """
        
        graph = BooleanMatrixGraph()
        graph._matrices_size = g.number_of_nodes()
        
        for u, v, edge in g.edges(data=True):
            if edge["label"] not in self._matrices:
                self._matrices[edge["label"]] = Matrix.sparse(BOOL, self._matrices_size, self._matrices_size)
            graph[edge["label"]][u, v] = True
```

- [x] Реализовать BooleanMatrixGraph

- [ ] Написать документацию для BooleanMatrixGraph

- [x] Написать `unit-tests` для BooleanMatrixGraph

- [ ] Написать `Jupyter Notebook Tutorial` для BooleanMatrixGraph

### Класс WCNF

- [x] Разработать API для WCNF (Weak Chomsky Normal Form):

```python=
class WCNF:
    def __init__(self, cfg: CFG):
        self._cfg: CFG = cfg
        self._cnf: CFG = cfg.to_normal_form()
        
        # WCNF
        self.start_symbol: Variable = cfg.start_symbol
        
        # [Variable -> Epsilon]
        self.epsilon_productions: List[Production] = [] 
        
        # [Variable -> Terminal]
        self.unary_productions: List[Production] = [] 

        # [Variable -> Variable Variable]
        self.binary_productions: List[Production] = []
        
        #
        self.variables: List[Variable] = []
        
        #
        self.terminals: List[Terminal] = []
        
        # строить поля из cfg
        
        ## сначала проверить cfg уже в WCNF?
        
        ## иначе построить из cfg WCNF
        
    def contains(self, word: str):
        return self._cfg.contains(word)
        
# wcnf = WCNF(cfg)
```

- [x] Реализовать WCNF

- [x] Написать документацию для WCNF

- [x] Написать `unit-tests` для WCNF

- [ ] Написать `Jupyter Notebook Tutorial` для WCNF

### Функция matrix_all_pairs_reachability

- [x] Разработать API для matrix_all_pairs_reachability:

```python=
# внешний API
def matrix_all_pairs_reachability(graph: nx.MultiDiGraph, grammar: CFG) -> List[Tuple[int, int]]:
    # prepare WCNF
    wcnf = WCNF(grammar)
    
    # prepare BooleanMatrixGraph
    matrix_graph = BooleanMatrixGraph.from_nx_graph(graph)
    
    res = _matrix_all_pairs_reachability(matrix_graph, wcnf)
    
    return res[wcnf.start_symbol].to_lists()  # convert to list of pairs

# внутренний API
def _matrix_all_pairs_reachability(graph: BooleanMatrixGraph, grammar: WCNF) -> BooleanMatrixGraph:
    # без эффекта !
    t = BooleanMatrixGraph(graph._matrices_size)
    
    # 0. Variable -> Epsilon добавляем в матрицы на диагональ единички 
    # 1. Variable -> Terminal добавляем в матрицы единички
    # 2. Транзитивное замыкание над матрицами по нетерминалам
```

- [ ] Реализовать matrix_all_pairs_reachability

- [ ] Написать документацию для matrix_all_pairs_reachability

- [ ] Написать `unit-tests` для matrix_all_pairs_reachability

- [ ] Написать `Jupyter Notebook Tutorial` для matrix_all_pairs_reachability

### Класс RSA

- [ ] Разработать API для RSA (Recursive State Automaton): **Решили отказаться от BooleanMatrixAutomaton**

- [ ] Реализовать RSA

- [ ] Написать документацию для RSA

- [ ] Написать `unit-tests` для RSA

- [ ] Написать `Jupyter Notebook Tutorial` для RSA

### Функция tensor_all_pairs_reachability

- [ ] Разработать API для tensor_all_pairs_reachability:

```python=
def tensor_all_pairs_reachability(graph: nx.MultiDiGraph, grammar: RSM):
    t = BooleanMatrixGraph.from_nx(graph)
    rsa = BooleanMatrixGraph.from_rsm(rsm)
    ...
    kron += rsa[label].kronecker(t[label])
    ...
    for nonterminal in rsm...nonterminals:
        for fin_state in rsm[]

```

- [ ] Реализовать tensor_all_pairs_reachability

- [ ] Написать документацию для tensor_all_pairs_reachability

- [ ] Написать `unit-tests` для tensor_all_pairs_reachability

- [ ] Написать `Jupyter Notebook Tutorial` для tensor_all_pairs_reachability

## CFPQ_PyAlgo 1.0.0

- [ ] PyGraphBLAS
    - [ ] matrix_all_pairs_reachability
        - [ ] Код
        - [ ] Документация
        - [ ] Тетрадка
        - [ ] Бенчмарки
    - [ ] tensor_all_pairs_reachability
        - [ ] Код
        - [ ] Документация
        - [ ] Тетрадка
        - [ ] Бенчмарки

## CFPQ_PyAlgo 1.1.0 ?

- [ ] PyCuBool
    - [ ] matrix_all_pairs_reachability
        - [ ] Код
        - [ ] Документация
        - [ ] Тетрадка
        - [ ] Бенчмарки
    - [ ] tensor_all_pairs_reachability
        - [ ] Код
        - [ ] Документация
        - [ ] Тетрадка
        - [ ] Бенчмарки