# Computing Persistent Homology of Directed Flag Complexes
## 4 Materials and Methods
### Representing the Directed Flag Complex in Memory  
An important feature of Flagser is its memory efficiency which allows it to carry out rather large computations on a laptop with a mere 16 GB of RAM (see controlled examples in Section 2). In order to achieve this, the directed flag complex of a graph is generated on the fly and not stored in memory. An \(n\)-simplex of the directed flag complex \(\mathrm{dFI}(G)\) corresponds to a directed \((n+1)\)-clique in the graph \(G=(V,E)\). Hence each \(n\)-simplex is identified with its list of vertices ordered by their in-degrees in the corresponding directed clique from 0 to \(n\). The construction of the directed flag complex is performed by a double iteration:  
1. For an arbitrary fixed vertex \(v_{0}\in V\), we iterate over all simplices which have \(v_{0}\) as the initial vertex. 2. Iterate Step 1 over all vertices (but see 3 below). This procedure enumerates all simplices exactly once. In more detail, consider a fixed vertex \(v_{0}\). The first iteration of Step 1 starts by finding all vertices \(w\) such that there exists a directed edge from \(v_{0}\) to \(w\). This produces the set \(S_{1}^{v_{0}}\) of all 1-simplices of the form \((v_{0},w)\), i.e., all 1-simplices that have \(v_{0}\) as their initial vertex. In the second iteration of Step 1, construct for each 1-simplex \((v_{0},v_{1})\in S_{1}^{v_{0}}\) obtained in the first iteration, the set \(S_{2}^{v_{0},v_{1}}\) by finding the intersection of the two sets of vertices that can be reached from \(v_{0}\) and \(v_{1}\), respectively. In other words,  
\[S_{2}^{v_{0},v_{1}}=\{w\in V\mid(v_{0},w)\in\ S_{1}^{v_{0}},\text{ and }(v_{1},w)\in S_{1}^{v_{1}}\}.\]  
This is the set of all 2-simplices in \(\mathrm{dFI}(G)\) of the form \((v_{0},v_{1},w)\). Proceed by iterating Step 1, thus creating the prefix tree of the set of simplices with initial vertex \(v_{0}\). The process must terminate, since the graph \(G\) is assumed to be finite. In Step 2 the same procedure is iterated over all vertices in the graph (under the constraint described in 3 below.) This algorithm has three main advantages:  
1. The construction of the directed flag complex is very highly parallelisable. In theory one could use one CPU for each of the vertices of the graph, so that each CPU computes only the simplices with this vertex as initial vertex. 2. Only the graph is loaded into memory. The directed flag complex, which is usually much bigger, does not have any impact on the memory footprint. 3. The procedure skips branches of the iteration based on the prefix. The idea is that if a simplex is not contained in the complex in question, then no simplex containing it as a face can be in the complex. Therefore, if we computed that a simplex \((v_{0},\ldots,v_{k})\) is not contained in our complex, then we don't have to iterate Step 1 on its vertices to compute the vertices \(w\) that are reachable from each of the \(v_{i}\). This allows us to skip the full iteration branch of all simplices with prefix \((v_{0},\ldots,v_{k})\). This is particularly useful for iterating over the simplices in a subcomplex. In the code, the adjacency matrix (and for improved performance its transpose) are both stored as bitsets (Bitsets store a single bit of information (0 or 1) as one physical bit in memory, whereas usually every bit is stored as one byte (8 bit). This representation improves the memory usage by a factor of 8, and additionally allows the compiler to use much more efficient bitwise logical operations, like \"AND\" or \"OR\". Example of the bitwise logical \"AND\" operation: 0111 and 1101 = 0101). This makes the computation of the directed flag complex more efficient. Given a \(k\)-simplex \((v_{0},\ldots,v_{k})\) in \(\mathrm{dFl}(G)\), the set of vertices  
\[\{w\in V\mid(v_{0},\ldots,v_{k},w)\in\mathrm{dFl}(G)\}\]  
is computed as the intersection of the sets of vertices that the vertices \(v_{0},\ldots,v_{k}\) have a connection to.