Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Strongly Connected Components (SCC) in D-Graph #17

Closed
epsi1on opened this issue Apr 28, 2019 · 13 comments
Closed

Strongly Connected Components (SCC) in D-Graph #17

epsi1on opened this issue Apr 28, 2019 · 13 comments

Comments

@epsi1on
Copy link
Collaborator

epsi1on commented Apr 28, 2019

Inside Dulmage–Mendelsohn decomposition file there is a section for finding Strongly Connected Components (SCC). Can this code be used to find SCC of a given sparse matrix? how to interpret result?
i need to go through all edges and identify only edges that do connect to different components. eg. in below image:
220px-Scc
need to identify that bc, bf, ef, cg and hg edges are connection between different components.
Is it possible that your code be used for such purpose?
---- edit
All i need is to know how to assign same number to nodes in a single SCC?
Thanks

@epsi1on epsi1on changed the title Strongly Connected Components (SSC) in D-Graph Strongly Connected Components (SCC) in D-Graph Apr 28, 2019
@wo80
Copy link
Owner

wo80 commented Apr 28, 2019

Yes, the SCC algorithm of the Dulmage-Mendelsohn class is general purpose. Actually, finding strongly connected components is doing two depth-first traversals, one of the adjacency graph G(A) and the second of the graph G(A^T). If you are interested, I can copy the relevant pages from "Direct Methods for Sparse Linear Systems" by Tim Davis (section 7.3 Block triangular form on pages 118+).

EDIT: see TestStronglyConnectedComponents.cs

@wo80
Copy link
Owner

wo80 commented Apr 29, 2019

I've moved the SCC code from DulmageMendelsohn to a separate (public) class and will publish an updated nuget package soon.

@epsi1on
Copy link
Collaborator Author

epsi1on commented Apr 30, 2019

Actually I'm going to use it for very large matrix (say 1M nodes with average 1-3 connected edge per node).
Hope it can handle the situation...

Thank you anyways for whole this great library...

@epsi1on epsi1on closed this as completed Apr 30, 2019
@wo80
Copy link
Owner

wo80 commented Apr 30, 2019

Will it be part of BFE.NET? Please let me know how it works. There might be room for optimization.

@epsi1on
Copy link
Collaborator Author

epsi1on commented May 1, 2019

No part of BFE, this is for another project.
I'll check it soon
thanks

@epsi1on
Copy link
Collaborator Author

epsi1on commented May 14, 2019

Worked very well on a 1M+ nodes and avg 2-3 degree per node

@wo80
Copy link
Owner

wo80 commented May 15, 2019

That's great!

I was thinking about making SymbolicColumnStorage public. At the moment, SCC and Dulmage-Mendelsohn allocate new memory when creating the SymbolicColumnStorage and when computing the transposed graph. Making the storage public could eliminate one of the two.

I don't think this would make a big difference in your case (1M nodes with degree 1-3), but for larger or less sparse matrices it might...

@epsi1on
Copy link
Collaborator Author

epsi1on commented May 20, 2019

That's great!

I was thinking about making SymbolicColumnStorage public. At the moment, SCC and Dulmage-Mendelsohn allocate new memory when creating the SymbolicColumnStorage and when computing the transposed graph. Making the storage public could eliminate one of the two.

I don't think this would make a big difference in your case (1M nodes with degree 1-3), but for larger or less sparse matrices it might...

that would be a good decision
In BFE I'm facing with situations that a matrix nonzero member values are updated in each step
Thanks

@epsi1on
Copy link
Collaborator Author

epsi1on commented Sep 14, 2024

I was thinking about making SymbolicColumnStorage public.

I think it is a good idea.

@wo80
Copy link
Owner

wo80 commented Sep 14, 2024

@epsi1on Working on it, see #52

@epsi1on
Copy link
Collaborator Author

epsi1on commented Sep 14, 2024

@epsi1on Working on it, see #52

Thank you.
I think great amount of codes in the library are implementing outstanding algorithms. More the classes are public, more people can use it without copying the source code. Not sure about legal stuff...

@wo80
Copy link
Owner

wo80 commented Sep 15, 2024

I think great amount of codes in the library are implementing outstanding algorithms.

That's true, and of course Tim Davis deserves most of the credit for creating SuiteSparse ;-)

I just published v4.2.0 with public SymbolicColumnStorage class.

@epsi1on
Copy link
Collaborator Author

epsi1on commented Sep 15, 2024

That's true, and of course Tim Davis deserves most of the credit for creating SuiteSparse ;-)

He is definitely great at algorithms, but a little lower great with teaching algorithms.
The [Sergio Pissanetzky] ebook about sparse matrices was much more fluent for me...
I'm trying to hang around sparse matrices for the RREF stuff. I just realized that i not just hate fill-in in sparse matrix factorization, but also hate elimination tree and some other algorithms too! because they are damn hard to understand :))
That is why i like Sergio's ebook more than CXSparse ebook.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants