The closest algorithm with similar capabilities would be Tarjan's strongly connected components (SCC) algorithm, which decomposes directed graphs into maximal sets of mutually reachable vertices.

Thanks, I am familiar with Tarjan's work. As far as I can remember, he doesn't give a solution for encoding paths. I will take a second look in his paper.

Sureshkumar Somayajula

I checked the paper by Tarjan. It is not incremental because DFS is not incremental. In addition, the partitioning is too coarse.

In my article, I use a different approach based on the notion of "Domination in Directed Graphs". A brief discussion can be found here (the last two answers): https://www.researchgate.net/post/Do_directed_graphs_have_a_unique_structure_and_topology/5

I don't know why Tarjan stopped following a similar approach. He also has a paper called “A Fast Algorithm for Finding Dominators in a Flowgraph”. To be honest, I learned from this paper about the importance of dominators, which is neglected (maybe overseen) by the research community.

Two ideas which I have introduced

helped to complete an incremental implementation.

I appreciate your clarification regarding the domination-based approach versus Tarjan's algorithm. Building on our discussion, I'd like to propose some additional considerations:

While Tarjan's SCC decomposition effectively identifies strongly connected components, your approach appears to offer two significant advantages:

• Instead of the coarse partitioning of SCCs, your domination hierarchy seems to capture more subtle relationships between nodes
• This could be particularly valuable for maintaining path information during incremental updates

• Your approach's ability to handle incremental updates addresses a fundamental limitation of DFS-based methods
• The linear-time complexity per edge insertion is especially interesting - could you elaborate on how the domination structure helps maintain this bound?

Have you encountered any specific challenges with maintaining the domination relationships during edge deletions? This aspect could be particularly relevant for practical applications requiring bidirectional graph modifications.

Deletion of edges is not a problem. But before I explain why, you should understand how I am attacking the domination issue.

DFS gives only a vague hint about the connectivity of two vertices

I am using two ordered lists of vertices instead, and apply the rule;

if vertex-u can reach (connected) to vertex-v then vertex-v must be the right of vertex-u in both lists, and this is the clue.

This is a constant time operation, and the positions of vertices have not to be recalculated after a new vertex is inserted, only the position of the inserted vertex, i.e., vertex-v.

Please read:

Presentation Topology and Structure of Directed Acyclic Graphs - Relational Sorting

I found your presentation on the Topological-triple method really interesting - it's quite a clever way to solve some long-standing issues with graph encoding.

What caught my attention most was how your method improves on traditional approaches in two key ways:

I noticed you mentioned extending this to handle cycles using the Seven Bridges problem as inspiration. How's that work coming along? I'd be curious to hear if you've found a way to keep the quick lookup benefits when dealing with cyclic graphs.

Cycles aren’t a problem, since I had the idea to introduce proxies for cycle-head. A brief description.

We call a path cyclic if on an edge(u, v) vertex-v can reach vertex-u, then vertex-v is called a cycle-head. It is always the second occurrence of vertex-v on a path (of course, there is no second without a first, and we make use of this triviality). In such a case, we add “@” in front of the symbolic name of the vertex, and call it the proxy of vertex-v.

The process continues as if the edge was indeed an edge(u, @v), either a tree-, for-, or cross edge. So we achieve an acyclic skeleton of the digraph. It should also be mentioned that only the algorithm is allowed to use the proxy as a vertex.

Of course, care should be taken during traversal. Whenever the proxy is hit on a path, the process continues with the indices of original vertex-v.

Post-domination is not an issue either. Paths containing the proxy end always at the proxy, so they never reach the Target (please see attached figure). Consequently, we ignore them.

After all, we don’t have to deal with cycles anymore. There exist only acyclic digraphs (or their skeleton).

I really like your smart way of handling cycles - using the '@' symbol to mark loops in the graph makes a lot of sense! It's like creating a 'stand-in' version of a node when it shows up again in a path, which neatly solves the cycle problem without making things overly complicated.

Looking at your diagram, I can see how this makes things much clearer. Instead of getting stuck in loops, you're essentially creating a clean map that helps track paths better. It's straightforward but effective.

I'm wondering about something practical though - when you've tried this out with real examples, have you noticed any interesting patterns? Like, do some types of graphs create clusters of these '@' nodes in certain areas? I'd be interested to hear how it works out in actual use.

It is not a coincidence that the building-block resembles a "select" clause with two targets. I tried it only on a few occasions, but your question sounds like loops with multiple entries used in computer programming.

Initially, I was also confused how it was solved. The answer is; there is always an order, therefor clusters order themselves, too. If you hit a vertex first time, it is a matter of pre-domination. The second time, it is a matter of pre-domination, too. But this time, your tree is routed at cycle head.

It is also important to remember that edges are incrementally added one at a time, and their order of insertion is irrelevant.

You may also get surprised that the DLL handling digraphs with all the features I mentioned is about 600 LOC. Handling digraphs is really straightforward, if you do the right things in the right order. All the information you need is codified in the edges, and in the rule of transitivity.

The structure is unique, also the maximum set of sub-digraphs, and connectivity. The only possible variations are homogenous.

The analogy to SQL SELECT clauses isbrilliant, and not something I hadconsidered. Amazing it's all squeezedinto about 600 lines of code, too. Theobservation about doing things in the right order really drives home the point that good design can simplify what appears to be a complex problem. I'm particularly intrigued by the fact that you've stated that only homogeneous variations are possible. Can you tell me a bit more about the kind of variation you see in practice? This might be helpful for other people who want to implement your approach ( If you can allow me to work under your guidance and not expecting any grants too).

Regards.

Sorry about the confusing assertion. I meant given an unordered set of edge-relations, all; the structure, the maximum set of sub-digraphs, and connectivity are unique. They are elementary invariants.

I think this is equivalent to the topology of directed graphs as defined by P. Alexandroff, extended to cover also cyclic graphs:

"The topology of a directed acyclic graph is generated by the minimal neighborhoods of its vertices. The minimal neighborhood of vertex v being the set of all nodes reachable from v in the direction of the edges of the graph G. The transitive closure of the edge-relation on the vertices generates the same topology"

The only possible variations are the order of successors of a node in the pre- or post-domination trees, which produce homogenous results.

For further discussions, please contact me at [email protected].