Flowchart

This flowchart details all execution paths through BubbleFinder, from input parsing to output, for each available command.

flowchart TD
  A["Start: ./BubbleFinder COMMAND -g GRAPH -o OUT"] --> B["Read input file (option -g).<br>Auto-detect compression: .gz / .bz2 / .xz"]
  B --> C{"Input format?"}
  C -->|"--gfa or *.gfa / *.gbz"| D["Parse GFA/GBZ as bidirected graph"]
  C -->|"--gfa-directed"| E["Parse GFA as directed graph"]
  C -->|"--graph or *.graph"| F["Parse .graph as directed graph"]

  D --> G{"Command"}
  E --> G
  F --> G

  %% SNARLS
  G -->|snarls| S0["Build undirected counterpart<br>of bidirected GFA graph"]
  S0 -->|"For each connected component"| S1["Compute BC-tree + SPQR trees<br>for each biconnected component"]
  S1 --> S2["Traverse SPQR trees.<br>Enumerate ALL snarls (linear-time)"]
  S2 --> S_triv{"-T flag?"}
  S_triv -->|"yes (include trivial)"| S3a["Output all snarls as clique-lines"]
  S_triv -->|"no (default: exclude trivial)"| S3b["Expand cliques to pairs,<br>filter out trivial snarls"]
  S3b --> S3c["Output non-trivial snarl pairs"]

  %% SUPERBUBBLES
  G -->|superbubbles| SB_mode{"--directed flag?"}

  SB_mode -->|"no (default: bidirected)"| SB0["Build doubled directed graph<br>with oriented copies v+ / v- for each segment v"]
  SB0 -->|"For each connected component"| SB1["Compute BC-tree + SPQR trees<br>for each biconnected component"]
  SB1 --> SB2["Traverse SPQR trees with DP on skeletons.<br>Enumerate ALL superbubbles<br>on the doubled graph"]
  SB2 --> SB3["Orientation projection.<br>Merge mirror bubbles, drop +/- , sort endpoints"]
  SB3 --> SB_triv{"-T flag?"}
  SB_triv -->|"yes (include trivial)"| SB4a["Output all segment ID pairs"]
  SB_triv -->|"no (default: exclude trivial)"| SB4b["Filter out trivial superbubbles"]
  SB4b --> SB4c["Output non-trivial segment ID pairs"]

  SB_mode -->|"yes (--directed)"| DSB0["Use directed input as-is"]
  DSB0 -->|"For each connected component"| DSB1["Compute BC-tree + SPQR trees<br>for each biconnected component"]
  DSB1 --> DSB2["Traverse SPQR trees with DP on skeletons.<br>Enumerate ALL directed superbubbles"]
  DSB2 --> DSB_triv{"-T flag?"}
  DSB_triv -->|"yes (include trivial)"| DSB3a["Output all oriented ID pairs"]
  DSB_triv -->|"no (default: exclude trivial)"| DSB3b["Filter out trivial superbubbles"]
  DSB3b --> DSB3c["Output non-trivial oriented ID pairs"]

  %% ULTRABUBBLES
  G -->|ultrabubbles| U_mode{"--doubled flag?"}

  U_mode -->|"no (default: oriented)"| U0{"At least 1 tip or 1 cut vertex<br>per connected component?"}
  U0 -->|no| Ufail["Fail: need at least 1 tip or cut vertex per CC"]
  U0 -->|yes| U1["Orient each CC via DFS<br>starting from a tip or cut vertex"]
  U1 --> U2["Resolve same-sign conflicts<br>by adding auxiliary tips (linear size)"]
  U2 --> U3["Run CLSD directed weak superbubble decomposition"]
  U3 --> U4["Map weak superbubbles back to ultrabubbles.<br>Discard bubbles with auxiliary endpoints"]
  U4 --> U_triv{"-T flag?"}
  U_triv -->|"yes (include trivial)"| U5a["Output all oriented incidence pairs"]
  U_triv -->|"no (default: exclude trivial)"| U5b["Filter out trivial ultrabubbles"]
  U5b --> U5c["Output non-trivial oriented incidence pairs"]
  U4 --> U7{"Option --clsd-trees FILE?"}
  U7 -->|yes| U8["Also output ultrabubble hierarchy"]
  U7 -->|no| End1["Done"]

  U_mode -->|"yes (--doubled)"| UD0["Build doubled directed graph<br>(no CC restriction)"]
  UD0 -->|"For each connected component"| UD1["Run CLSD directed weak superbubble decomposition<br>on doubled graph"]
  UD1 --> UD2["Map back to ultrabubbles.<br>Discard auxiliary endpoints"]
  UD2 --> UD_triv{"-T flag?"}
  UD_triv -->|"yes (include trivial)"| UD3a["Output all oriented incidence pairs"]
  UD_triv -->|"no (default: exclude trivial)"| UD3b["Filter out trivial ultrabubbles"]
  UD3b --> UD3c["Output non-trivial oriented incidence pairs"]

  %% SPQR-TREE OUTPUT
  G -->|spqr-tree| P0{"GFA / GBZ input?"}
  P0 -->|no| Pfail["Fail: spqr-tree requires GFA/GBZ input"]
  P0 -->|yes| P1["Compute components + BC-tree + SPQR decomposition"]
  P1 --> P2["Output: .spqr v0.4 file"]

Loading