CFPQ_PyAlgo package

[vivalerievich]

Hi @IlyaEp, @gsvgit, @KutuevVladimir and all interested!

I think it's time to put all the algorithms into a single package.

I wrote a little plan for what to do and suggest to do all tasks using pull requests to the package branch.

I will be glad to discuss all the details here!

[gsvgit]

Hi. Good idea.

I think, first, we should fix user-friendly names of algorithms. Such names as 'TensorPathNew' or 'TensorSimpleAlgo' are terrible. I guess, the task 'Provide a clear and comprehensible name' is exactly about it.

Second, we should fix the list of algorithms. For example, what is the reason to have Brut and Opt for multiple source CFPQ? I guess we should publish only the final versions of the algorithms. All intermediate results/implementations should be internal.

It is not clear how to select a backend for the algorithm. I guess we can provide multiple backends (SuiteSparse/pygraphblas, pyspbla) for each algorithm.

[gsvgit]

• MatrixAllPairsReachability
• TensorAllPairsReachability
• MatrixMultipleSourceReachability
• TensorMultipleSourceReachability
• MatrixAllPairsSinglePath
• MatrixAllPairsAllPaths
• MatrixMultipleSourcesSinglePath
• MatrixMultipleSourcesAllPaths
• TensorMultipleSourcesSubgraph
• TensorMultipleSourceSinglePath
• TensorMultipleSourceAllPaths

Anything else?

Can we implement different versions of matrix algorithms using the common scheme parametrized by semiring?

[vivalerievich]

+1 for these names

[vivalerievich]

I'm not sure about this approach. Are there really so many semirings that can be used in algorithms that it would be better to make a parameter for them than a new function?

[gsvgit]

All three classes of matrix-based algorithms (reachability, single path, all paths) should be (at least in theory) one algorithm parameterized by three different semirings. So, we should implement all-pairs and multiple-sources algorithms parametrized by semirings. I guess, @rustam-azimov can provide more details.

[rustam-azimov]

Yes. It is true for index creation. The only question is about path extraction algorithms, They are different for single path and all path query semantics.

[vivalerievich]

I think we can discuss the package structure in this thread.

I would suggest the following package structure.

cfpq_pyalgo
├── pygraphblas
│   ├── algorithms - directory where all algorithms are implemented using pygraphblas
│   │   ├─── ...
├── pyspbla
│   ├── algorithms - directory where all algorithms are implemented using pysbla
│   │   ├─── ...

But I still do not understand where to put all the auxiliary (dependent and not dependent on the backend) classes. What do you think?

[gsvgit]

Well

1. Can we use pyformlang directly for manipulations with grammars?
2. Seems, that a specific graph loader is required to convert a graph to boolean matrices. Isn't it?

[vivalerievich]

1. As I imagine - yes. But @IlyaEp or @rustam-azimov can better tell about this.
2. I think we can add a graphs submodule to a specific backend.

   cfpq_pyalgo
   ├── pygraphblas
   │   ├── algorithms - directory where all algorithms are implemented using pygraphblas
   │   │   ├─── ...
   │   ├── graphs - directory where all graph classes are implemented using pygraphblas
   │   │   ├─── ...
   ├── pyspbla
   │   ├── algorithms - directory where all algorithms are implemented using pysbla
   │   │   ├─── ...
   │   ├── graphs - directory where all graph classes are implemented using pysbla
   │   │   ├─── ...
   

[gsvgit]

Are graphs helpers implementation-specific? I guess, there is a common part. For example, file reading.

[vivalerievich]

For example, BooleanMatrixGraph uses pygraphblas matrices for pygraphblas backend-specific algorithms and pysbpla matrices for pysbla backend-specific algorithms.

[gsvgit]

Well, I see.

[vivalerievich]

Another interesting question: should we use "well-known" parameter types for functions, such as

def matrix_all_pairs_reachability(graph: networkx.MultiDiGraph, grammar: pyformlang.CFG):
    ...

or use types defined in package, such as

def matrix_all_pairs_reachability(graph: BooleanMatrixGraph, grammar: CNF):
    ...

?

[gsvgit]

Can you describe the pros and cons of these approaches? I think that the second way is better because

1. It clearly specify what exactly the algorithm expects as input.
2. It allows us to separate converters. If we want, we can provide converters from the most popular graph formats to boolean matrices. The same for grammars.

[vivalerievich]

I agree, it's better to convert from the most popular graph formats. This makes it possible to more accurately implement the algorithms themselves and all the necessary preparations.