# Direct Superbubble Detection
## 3 Results  
We extended the \"Linear Superbubble Detection\" ([[https://github.com/Fabianexe/Superbubble](https://github.com/Fabianexe/Superbubble)]([https://github.com/Fabianexe/Superbubble](https://github.com/Fabianexe/Superbubble))) software LSD[7] with the new algorithm presented in the previous section. LSD is written in Python and uses the NetworkX package [10] to handle graph data structures. Since the same data structures are used, benchmarking the different algorithms provided in LSD allows a fair comparison of running times.  
In the implementation, we deviated from the presentation above in two minor details. First, instead of using the reverse postorder of the DFS-tree, we directly used postorder and the corresponding (trivial) redefinitions of the helper functions \(\operatorname{\texttt{OutChild}}()\) and \(\operatorname{\texttt{OutParent}}()\). Second, we did not completely separate the determination of the cycles, the identification of the roots, and the identification of the superbubbles. Instead, we performed cycle search, root detection, and superbubble identification immediately for each DFS-tree. Since cycles and superbubbles are necessarily completely contained within the DFS-trees, this does not affect the correctness of the algorithm. As a by-product, we obtained a speedup by a constant factor because cycles reachable within a given DFS-tree were marked as \"already processed\" in the superbubble detection step and hence were not (superfluously) considered as candidate additional roots.  
In order to benchmark the direct detection algorithm in comparison to other linear-time superbubble detection algorithms, we used the same datasets as in our previous work [7]. In order to guarantee comparability, performance data for all algorithms were computed with the same version of LSD on the same hardware. The results are summarized in Table 1.  
For most datasets, we observed an approximately three-fold speedup of Directbubble compared to LSD. The exception is the Slashdot dataset for which no performance gain was observed.  
To understand this outlier, it is necessary to understand the source of the speedup in the other test cases. In a typical case, both Directbubble and LSD performed three depth-first searches: in LSD, they are used to determine SCCs, create auxiliary graphs, and detect superbubbles. Directbubble uses them to identify the cycles, quasi-legitimate roots, and finally the superbubbles. Both need to handle exceptional cases. LSD requires the construction of the Sung graph if an SCC coincides with a connected component of the input graph (rather than being just part of it). Since the Sung graph is twice the size of the SCC, this roughly doubles the running time. Directbubble behaves exceptionally for vertices that are reachable from a source. In this case, the detection of cycles and quasi-legitimate roots in cycles was skipped, incurring a substantial speedup. When a graph had neither an SCC that was also a connected component, nor large subgraphs reachable from a source, then LSD and Directbubble essentially performed the computations and thus performed very similarly. The Slashdot dataset is such a case. Typically, however, directed graphs have some sources so that Directbubble outperforms its competitors on most real-life graphs.