Hello @cvvergara
I’m writing to clarify pgRouting’s needs around sparse matrix ordering algorithms and propose a potential GSoC 2025 project.
The 2022 GSoC added pgr_cuthillMckeeOrdering. From the documentation, it appears to be experimental. Is it still needed in the current pgRouting scenario?
Would enhancing the existing CM implementation be valuable?
Also would implementing Sloan Ordering (Boost Graph Library: Sloan Ordering - 1.78.0) be a priority? Sloan can be used for profile/wavefront reduction in irregular graphs. Moreover, both reverse CM and direct ordering from Sloan can be implemented together.
For GSoC 2025, I want to propose:
If not already covered, enhancing pgr_reverseCuthillMckeeOrdering using BGL’s reversed CM and pgr_sloanOrdering to optimize sparse matrix computations.
Could this align with pgRouting’s goals and feasibility? I’d appreciate your guidance on refining this idea.
Regards,
Bipasha Gayary
Indian Institute of Technology Roorkee
Hello
The function pgr_cuthillMckeeOrdering is still in experimental, because we need more unit tests or users feedback to move it forward to proposed. That one can not be taken for GSoC.
We do not have pgr_reverseCuthillMckeeOrdering.
CM = centimeters? (try not to use acronyms, unless they are well known, because for non English native speaker we are always guessing)
Sloan ordering is ok for you to take.
If you want to code more than one function make it 375 hours, in the standard coding period.
None of our mentors is available for more time.
And you mention:
“Sloan can be used for profile/wavefront reduction in irregular graphs”
Also:
“Moreover, both reverse CM and direct ordering from Sloan can be implemented together.” Where CM is any of these
That gives me the impression that:
- reverse CM is one algorithm
- direct ordering from Sloan is another algorithm
and they can be implemented together with Sloan
So that gives many options where you can choose from.
Please choose at most two.
Regards