Skip to content

OMF import - islands checking algorithm #73

@robfitzgerald

Description

@robfitzgerald

when applying filters during segment import, we can likely end up isolating many links into unreachable "islands".

a heuristic for island checking and removal can be executed when we have the vertices and edges of the graph and an adjacency list, along with some max_depth (something small like 10 for tractability, which should be configurable):

d := max_depth
remove_edges = []
for edge in edges:
  result := connected_components_search(edge, d)
  if result.queue.empty:
    # island discovered
    remove_edges.extend(result.edges)

for edge in remove_edges:
  edges.remove(edge)

this allows us to find cases where, when traveling up to some max depth of edges from some location, we max out of edges to explore, indicating that all of the connected edges in the search were in fact in an island.

Metadata

Metadata

Assignees

Labels

No labels
No labels

Type

No type

Projects

No projects

Relationships

None yet

Development

No branches or pull requests

Issue actions