I am the inventor of Topological-triple Iterable Topology of a Directed Acyclic Graph
Recently, I extended the algorithm to support general directed graphs.
Topological-triple does not only reflect the topology of a given directed graph, but also its structure. It contains not only information about all paths thru the graph in a compressed form, but also organization of its vertices. Therefore it makes sub-graph decomposition readily available. If needed, one could trace all paths simply by iterating through a compact data-structure in the direction of binary relations represented by the edges, or in the reverse direction. Recurring traversals are not necessary even if new edges are inserted. The time complexity of insertion of an edge is linear in terms of the vertices.
The proof of the algorithm will be published in the proceedings of “FICC 2021”. A reference implementation is about 21 KB and less than 1 KLOC in size.
Can a data-structure with these features be useful in HPC space?