.. index:: single: Ordering Family ; pgr_cuthillMckeeOrdering single: pgr_cuthillMckeeOrdering
pgr_cuthillMckeeOrdering — Returns the reverse Cuthill-Mckee ordering of an undirected
graphs
Availability
- Version 3.4.0
- New experimental function.
In numerical linear algebra, the Cuthill-McKee algorithm (CM), named after Elizabeth Cuthill and James McKee, is an algorithm to permute a sparse matrix that has a symmetric sparsity pattern into a band matrix form with a small bandwidth.
The vertices are basically assigned a breadth-first search order, except that at each step, the adjacent vertices are placed in the queue in order of increasing degree.
The main Characteristics are:
- The implementation is for undirected graphs.
- The bandwidth minimization problems are considered NP-complete problems.
- The running time complexity is: O(m log(m)|V|)
- where |V| is the number of vertices,
- m is the maximum degree of the vertices in the graph.
|Boost| Boost Graph Inside
.. index::
single: cuthillMckeeOrdering - Experimental on v3.4
pgr_cuthillMckeeOrdering(Edges SQL)
Returns set of |result_node_order|
OR EMPTY SET
| Example: | Graph ordering of pgRouting :doc:`sampledata` |
|---|
.. literalinclude:: cuthillMckeeOrdering.queries :start-after: -- q1 :end-before: -- q2
Returns set of (seq, node)
| Column | Type | Description |
|---|---|---|
seq |
BIGINT |
Sequence of the order starting from 1. |
node |
BIGINT |
New ordering in reverse order. |
Indices and tables