Strongly Connected Components (SCC) in D-Graph

[epsi1on]

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: 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

[wo80]

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]

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

[epsi1on]

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...

[wo80]

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

[epsi1on]

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

[epsi1on]

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

[wo80]

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]

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]

I was thinking about making SymbolicColumnStorage public.

I think it is a good idea.

[wo80]

@epsi1on Working on it, see https://github.com/wo80/CSparse.NET/pull/52

[epsi1on]

@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]

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]

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.