Skip to content

Resolve cyclic data flow graphs #157

@BenjaminArp

Description

@BenjaminArp

Pain Points:

  • manual labor, due to need of (cyclic) microsecend models for acyclic analyis
  • keeping pipe active to microsecend repo

Solution Idea:
To handle cyclic graphs effectively, I propose a new import/mapping strategy that resolves cycles during the flow creation process. This approach ensures that we only deal with directed acyclic graphs (DAGs) when defining flows. The steps are as follows:

  1. Initial Vertex Assignment: Assign each vertex in the cyclic graph a unique order based on its position in the DAG.
  2. Flow Creation with Cycle Detection: As we create flows, we monitor for any cycles by checking if a vertex is revisited. This is identified by comparing the order of the current vertex with the vertices visited in the current flow.
  3. Cycle Resolution: If a cycle is detected (i.e., a flow revisits a vertex), we resolve it by:
    - Ending the Flow: Terminating the flow at the current vertex if revisiting it creates a cycle.
    - Redirecting to Higher-Order Vertex: Redirecting the flow to a vertex with a higher order, ensuring that the graph remains acyclic.

By implementing this strategy, we can effectively manage cyclic graphs by transforming them into DAGs, thusmaking it ppossible to analyze microsecends cyclic graphs without modifing the analysis.

Metadata

Metadata

Assignees

Labels

enhancementNew feature or requestresearchInvestigation or reserach related issue

Type

No type

Projects

No projects

Milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions