algorithm.asciidoc 1.95 KB
Newer Older
Albert Hofkamp's avatar
Albert Hofkamp committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//////////////////////////////////////////////////////////////////////////////
// Copyright (c) 2020, 2022 Contributors to the Eclipse Foundation
//
// See the NOTICE file(s) distributed with this work for additional
// information regarding copyright ownership.
//
// This program and the accompanying materials are made available
// under the terms of the MIT License which is available at
// https://opensource.org/licenses/MIT
//
// SPDX-License-Identifier: MIT
//////////////////////////////////////////////////////////////////////////////

include::_part_attributes.asciidoc[]

[[dsm-algorithm]]
17
== Algorithm and code
Albert Hofkamp's avatar
Albert Hofkamp committed
18

19
20
The algorithm is defined in <<Wilschut2017>>.
The link between names of parameters in the algorithm and the code is listed in the <<clustering-function-parameter-table>> table.
Albert Hofkamp's avatar
Albert Hofkamp committed
21

22
23
The algorithm finds a bus, and performs bottom-up clustering of both the bus nodes and the non-bus nodes.
The bus detection algorithm is coded in the `BusComputing` class, while a clustering step is handled in the `ClusterComputing` class.
Albert Hofkamp's avatar
Albert Hofkamp committed
24

25
26
27
All these operations work on or produce subsets of nodes.
A subset is represented by a `BitSet` instance in code, over nodes in its associated matrix.
The clustering hierarchy is stored in `Group` instances.
Albert Hofkamp's avatar
Albert Hofkamp committed
28

Albert Hofkamp's avatar
Albert Hofkamp committed
29
30
The Markov clustering algorithm however assumes a complete matrix rather than a subset of it, where previously found clusters are compressed into a single node.
This conversion is handled by the `submatrix.SubMatrixFunctions` functions that construct and use a `SubNode` translation table to convert the overall matrix to a sub-matrix, and convert clustering results in the sub-matrix back to groups in the overall matrix.
Albert Hofkamp's avatar
Albert Hofkamp committed
31

32
33
After all computing steps are finished, a `Group` hierarchy describes which nodes and groups belong to which cluster.
From this information a shuffle array is constructed, relating result nodes back to originating nodes.
Albert Hofkamp's avatar
Albert Hofkamp committed
34
That array is then used to construct the resulting labels and the resulting adjacency matrix.