GeezerVison

The World Wide Web, restored to 800 pixels of glory.

GeezerVison is showing github.com — CFL reachability problem using Kronecker product by Mamontyonok · Pull Request #10 · SparseLinearAlgebra/LAGraph

Conversation

Mamontyonok commented Mar 6, 2026

Copy link

Copy Markdown

The basic version of the CFLR algorithm is based on the Kronecker product

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

Mamontyonok added 2 commits

March 6, 2026 19:22


          init_commit_reachability

4c90003


          Update LAGraph_CFL_Kron.c

gsvgit reviewed

Mar 10, 2026

View reviewed changes

gsvgit left a comment

Copy link

Copy Markdown

Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Add more explanatory comments. For example look at this request

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

Comment thread

experimental/algorithm/LAGraph_CFL_Kron.c Outdated

		GrB_Index nvals_old = 0, nvals_new = 0;
		GrB_Matrix_nvals(&nvals_old, A);
		while (true) {
		GrB_mxm(A, NULL, GrB_LOR, GrB_LOR_LAND_SEMIRING_BOOL, A, A, NULL);

gsvgit Mar 10, 2026

Copy link

Copy Markdown

Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Why not ANY_PAIR?

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

Comment thread

experimental/algorithm/LAGraph_CFL_Kron.c Outdated

		char *msg
		)
		{
		GrB_Matrix M3 = NULL;

gsvgit Mar 10, 2026

Copy link

Copy Markdown

Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Naming. What is M3?

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

Comment thread

experimental/algorithm/LAGraph_CFL_Kron.c Outdated

		GrB_Index r_dim = rsm->state_count;
		GrB_Index kronecker_dim = r_dim * g_dim;

		for (int64_t nt = 0; nt < rsm->nonterminal_count; ++nt) {

gsvgit Mar 10, 2026

Copy link

Copy Markdown

Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

It is hard to realize this loop. We iterate through all non-terminals. Each non-terminal must has related box and this box must has at least one final state. So, it is unclear what exactly we do in this loop.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

gsvgit Mar 10, 2026

Copy link

Copy Markdown

Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Am I right, that you just handle boxes where the same state is both final and start?

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

Mamontyonok Mar 11, 2026

Copy link

Copy Markdown

Author

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

yes, that's it

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

Comment thread

experimental/algorithm/LAGraph_CFL_Kron.c Outdated

		GrB_Matrix_clear(M3);

		for (int64_t t = 0; t < terms_count; ++t) {
		GrB_kronecker(M3, NULL, GrB_LOR, GrB_LAND,

gsvgit Mar 10, 2026

Copy link

Copy Markdown

Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Why not ANY_PAIR?

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

Comment thread

experimental/algorithm/LAGraph_CFL_Kron.c Outdated

		GrB_Matrix_extractTuples_BOOL(i, j, V, &m3_nvals, M3);

		for (GrB_Index k = 0; k < m3_nvals; ++k) {
		GrB_Index s = i[k] / g_dim;

gsvgit Mar 10, 2026

Copy link

Copy Markdown

Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Naming.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

Comment thread

experimental/algorithm/LAGraph_CFL_Kron.c Outdated

		GrB_Index x = i[k] % g_dim;
		GrB_Index y = j[k] % g_dim;

		for (GrB_Index nt = 0; nt < rsm->nonterminal_count; ++nt) {

gsvgit Mar 10, 2026

Copy link

Copy Markdown

Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Can it be done using matrix operations like select or reduce?

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

Mamontyonok added 5 commits

March 11, 2026 17:59


          LOR_LAND -> ANY_PAIR

043d17c


          the_idea_of_extracting_blocks

c1c32f8


          naming

f41e334


          using_the_GrB_LOR_accumulator_replaces_the_need_for_GrB_eWiseAdd

efc0df4


          The_incremental_version_of_the_algorithm

42e490f

gsvgit reviewed

Apr 7, 2026

View reviewed changes

Comment thread

experimental/algorithm/LAGraph_CFL_Kron.c Outdated

		GrB_Matrix_new(&BaseGraph, GrB_BOOL, kronecker_dim, kronecker_dim);
		GrB_Matrix_new(&DeltaM, GrB_BOOL, kronecker_dim, kronecker_dim);

		for (int64_t t = 0; t < terms_count; ++t) {

gsvgit Apr 7, 2026

Copy link

Copy Markdown

Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Забыли почистить код? Что-то тут странное, начинач со строки 91

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

Mamontyonok Apr 7, 2026

Copy link

Copy Markdown

Author

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Да, видимо когда менял код, продублировал этот цикл

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

Comment thread

experimental/algorithm/LAGraph_CFL_Kron.c Outdated


		GrB_Matrix_dup(&CombinedGraph, M_graph);

		transitive_closure_inplace(CombinedGraph);

gsvgit Apr 7, 2026

Copy link

Copy Markdown

Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Если я правильн понимаю, что здесь происходит, то можно иначе пересчитывать транзитивыное замыкание. Пусть TC -- результат замыкания с предыдущей итерации, D -- дельта на этой итерации. Тогда можно посчиать transitive_closure_inplace(TC + D). Должно чуть меньше итераций требовать. Но надо проверять, что будет быстрее.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions


          code_duplication_patch

08de903

homka122 reviewed

Apr 25, 2026

View reviewed changes

Comment thread

experimental/algorithm/LAGraph_CFL_Kron.c Outdated

Comment on lines +68 to +82

		for (int64_t nt = 0; nt < rsm->nonterminal_count; ++nt) {
		GrB_Matrix_new(&outputs[nt], GrB_BOOL, g_dim, g_dim);
		GrB_Matrix_new(&delta_outputs[nt], GrB_BOOL, g_dim, g_dim);

		GrB_Index s = rsm->start_states[nt];
		bool is_final = false;
		GrB_Vector_extractElement_BOOL(&is_final, rsm->final_states[nt], s);

		if (is_final) {
		for (GrB_Index v = 0; v < g_dim; ++v) {
		GrB_Matrix_setElement_BOOL(outputs[nt], true, v, v);
		GrB_Matrix_setElement_BOOL(delta_outputs[nt], true, v, v);
		}
		}
		}

homka122 Apr 25, 2026 •

edited

Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link

Copy Markdown

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Hi, I wanted to add your algo to CFG_Bench, and that piece of code took a lot of time: around 3 seconds to process 1k iterations after 55k/256k iterations had been processed. The processing time increases linearly with the current iteration count.

I think it just adds the identity matrix to the outputs[nt] and delta_outputs[nt] matrices, so this code resolves the task and works in under 1 second on the c_alias init.g graph:

    GrB_Vector v_diag;
    GrB_Vector_new(&v_diag, GrB_BOOL, g_dim);
    GrB_Vector_assign_BOOL(v_diag, GrB_NULL, GrB_NULL, true, GrB_ALL, g_dim, NULL);

    for (int64_t nt = 0; nt < rsm->nonterminal_count; ++nt) {
        GrB_Matrix_new(&outputs[nt], GrB_BOOL, g_dim, g_dim);
        GrB_Matrix_new(&delta_outputs[nt], GrB_BOOL, g_dim, g_dim);

        GrB_Index s = rsm->start_states[nt];
        bool is_final = false;
        GrB_Vector_extractElement_BOOL(&is_final, rsm->final_states[nt], s);

        if (is_final) {
            GrB_Matrix_diag(&outputs[nt], v_diag, 0);
            GrB_Matrix_diag(&delta_outputs[nt], v_diag, 0);
        }
    }
    GrB_free(&v_diag);

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions


          adding_msbfs_version_of_algorithm

6cabf2b

homka122 mentioned this pull request

Oct 10, 2026

Adding a Tensor Algorithm for Finding All Paths in Graphs with Context-Free Grammar Constraints homka122/CFG_bench#41

Merged

Mamontyonok added 2 commits

October 15, 2026 21:45


          update msbfs && refactoring to LAGraph style

baf0462


          update include LAGraphx.h: adding RSM, CFL_Kron

b3ad468

homka122 added a commit that referenced this pull request

Oct 20, 2026


          Feat: update CFL_Kron to the MS-BFS version from #10

8a36ee6

Reviewers

gsvgit

gsvgit left review comments

homka122

homka122 left review comments

Uh oh!

There was an error while loading. Please reload this page.

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

Uh oh!

There was an error while loading. Please reload this page.

3 participants

Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.

You are visitor 01402520 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.

Conversation

Mamontyonok commented Mar 6, 2026

Uh oh!

gsvgit left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

homka122 Apr 25, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Reviewers

Uh oh!

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

homka122 Apr 25, 2026 •

edited

Loading

Uh oh!

There was an error while loading. Please reload this page.