Skip to content

Graph based cycle search

Full example code: examples/algorithm/cycle_search.py

Overview

  1. Load data
  2. Create graph
  3. Detect all cycles
  4. Cluster cycles
  5. Cycle selection

Loading data

For more info on how to load data from your mapping system, please check our parser module.

Create graph

After cleaning the input data, we create our graph based with some restrictions on maximum edge length and conduction velocity between nodes.

from dgmr.graph import Graph

sample_coords = ... #
sample_scalars = ... #

properties = {
    'max_edge_length': 7,
    'cv_min': 0.1,
    'cv_max': 5.0,
    'period': period
}
filters = ['cv']

graph = (
    Graph(sample_coords, sample_scalars)
    .set_properties(properties)
    .apply_filter(filters)
)

Detect all cycles

We can now perform a cycle search on this graph. In our example we will use the Dijkstra shortest path algorithm to find cycles.

from dgmr.algorithm.cycles import CompleteSearch

cycles = (
    CompleteSearch(graph)
    .set_algorithm('dijkstra')
    .set_search_type('shortest')
    .run()
)

Cluster cycles

Next we use spectral clustering to cluster our cycles. This will add a label to each cycle.

clustered_cycles = (
    cycles
    .set_cluster_method('spectral')
    .cluster()
)

Cycle selection

As a final step, we select a single cycle from each cluster. In our example filter on cycle length and keep the shortest cycle in each cluster.

# Convert cycles to a dictionary based on their assigned cluster labels
clustered_dict = clustered_cycles.group_by('cluster_labels')

# Take the shortest cycle in each cluster
shortest_dict = {
    key: value.select_by('cycle_length', 'smallest')
    for key, value in clustered_dict.items()
}