Cuthill-Mckee Ordering Algorithm for

- Shobhit Chaurasia

25 August 2022 on Firenze room

Shobhit Chaurasia

• Student, Bachelors of Tech. in CSE
• Hindustan College of Science and Technology, Mathura, India
• Participated this year in GSoC
• pgRouting Developer
• Email: 000shobhitchaurasia@gmail.com

Agenda

​

1. My Contributions
2. Usage & Applications
3. Future Scope
4. Conclusion

My Contributions

My Contributions

​

• Added Cuthill-Mckee Ordering Algorithm by the Boost Graph Library to pgRouting.
• Created one function:
• pgr_cuthillMckeeOrdering

Benefits to the community

• Adds more functionality to pgRouting
• Can be integrated with other routing algorithms
• Used to reduce the Bandwidth of the Graphs
• Applications in linear system of

equations, reduce size needed to store sparse matrix, enhancing data locality, etc

Usage & Applications

pgRouting Cuthill-Mckee Ordering

• This algorithm is a part of sparse matrix ordering algorithms:
• decreases the Bandwidth of the Graph.
• it re-order the indices assigned to each vertex.
• Applicable for Undirected Graphs.
• Applications: Linear equations, data locality, size reduction, etc.
• Time complexity : O(m log(m)|V|) where m = max { degree(v) | v in V }.

pgRouting Cuthill-Mckee Ordering

CREATE TABLE edge_table

(

id BIGSERIAL,

source BIGINT,

target BIGINT,

cost FLOAT,

reverse_cost FLOAT

);

INSERT INTO edge_table

(id, source, target, cost, reverse_cost) VALUES

(1, 1, 4, 1, 1), (8, 3, 5, 1, 1),

(2, 1, 6, 1, 1), (9, 4, 6, 1, 1),

(3, 2, 3, 1, 1), (10, 4, 9, 1, 1),

(4, 2, 5, 1, 1), (11, 5, 7, 1, 1),

(5, 2, 7, 1, 1), (12, 6, 7, 1, 1),

(6, 2, 10, 1, 1), (13, 6, 8, 1, 1);

(7, 3, 4, 1, 1), (14, 7, 8, 1, 1);

pgRouting Cuthill-Mckee Ordering

Initial graph (Bandwidth = 8)

Final Graph (New bandwidth = 4)

SELECT * FROM pgr_cuthillMckeeOrdering (

'SELECT * FROM edge_table'

);

​

seq | node seq | node

---------+---------- ----------+----------

1 | 1 6 | 7

2 | 9 7 | 5

3 | 6 8 | 3

4 | 8 9 | 2

5 | 4 10 | 10

(10 rows)

pgRouting Cuthill-Mckee Ordering

Future Scope

What next?

Future Scope

• More functions can be implemented for different use cases from the sparse matrix ordering family:
• minimum degree ordering, sloan ordering, etc
• Bandwidth minimization algorithms for pgRouting will help in computations over large-scale graphs efficiently.

Let’s Wrap Up!

Project:

Source Code:

Documentation:

Wiki Page:

summerofcode.withgoogle.com

GSoC-2022-shobhit162-cuthillMckeeOrdering

To be added soon

github.com/pgRouting/pgrouting/wiki

https://github.com/pgRouting/GSoC-pgRouting

More Information

Website:

GitHub:

Documentation:

Developer’s Doc:

Workshop:

Shobhit Chaurasia: 000shobhitchaurasia@gmail.com

https://pgrouting.org/

https://github.com/pgRouting

https://docs.pgrouting.org/

https://docs.pgrouting.org/doxygen/

https://workshop.pgrouting.org/

Thanks!