The topology of a graph can be computed incrementally, one edge at a time, without visiting all possible paths through it.

The process is also valid if the graph contains cycles because any graph can be created by properly nesting the building-block given in the figure. The dashed edge (@Entry, Entry) is imaginary, i.e. it is not contained in the edge set of the graph, and denoted as a proxy of the Entry. Consequently, cyclic graphs can be encoded as their acyclic equivalents (skeletons) while reflecting their topology.

Graphs in general have a unique structure and topology for each class, on the basis of which they are distinguished and classified into different classes. This certainly applies to directed graphs, which include different classes. The constant properties (invariants) of these classes of graphs are what can make a class of these classes distinct and unique.

I am not sure about the undirected graphs, but there are only four classes of directed graphs.

Using the building-block I mentioned, even you can compose and/or decompose any directed graph.

Try it. If you cannot find a counter example, shame your answer.

I am assuming that you will share your counter example with the layman like me.

And take your time, and enjoy new frontiers.

Sorry, I forgot to mention whom I am addressing: Daniel Ketels.

By the way, the definition of the topology I am using is by P. Alexandroff, and it is:

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

If you do not agree with him, how does yours (Daniel Ketels) sound?

Here is the reference:

1. Alexandrov, P. (1937) Diskrete Räume. Matematiceskiy Sbornik., 44, 501– 519

Ali Rashid Ibrahim, as I mentioned above, there are four classes of directed graphs. Every additional edge during the composition and/or decomposition process has the power to transform the structure of the graph from one class to the other. Because there are no computational disadvantages, I treat them all as of type (4).

Daniel Ketels, my apologies for wasting your wasted time in studying.

You better should use your time to think twice, e.g. about your counter example (if you are in doubt, add an axiomatic vertex which is the predecessor of all vertices without a predecessor, the genesis. And the dooms-day, which is the successor of all vertices without a successor, so you have the complete picture).

I am not going to complain that you cannot find a fifth class of directed graphs, it may take you ages, if at all.

Just for the fun of it, I am adding a graphic showing a graph decomposition demonstrating all the advantages of the process I am referring to.

Thanks for taking your time, and for the great but useless insight you shared. And don't leave your big university, it is a real-world outside.

Here is how you can encode the example graph.

This was an earlier workout, though still valid. To decode the reachability relations, you have to compare the indices of any given vertex pair (u, v).

If u's indices are smaller than v's u can reach v. They are not connected otherwise.

Recent work uses two pairs of two indices for encoding, using the same principle.

My claim once again:

Every directed graph (also the cyclic ones) can be encoded in linear time per edge insertion using this technology.

The decoding requires constant time per vertex pair.

The encoding represents all paths through the graph per iteration with a backtracking facility.

I am not sure whether century long studies have brought anything with similar capability and performance.

Before humbling other people's work, one should refer to own results.

My algorithm is developed based on the very basic principles of edge-relations and transitivity. The algorithm does not use any theoretical or practical achievements of others.

I am fulfilling the claims in an extremely simple implementation of less than 1000 LoC.

I am using a simple, non-mathematical language to describe it because in my opinion, a theory which cannot be translated into natural language is half completed. Furthermore, I am eager to publish the details before the end of the year so that everybody can study it. A basic knowledge of data-structures would be sufficient to make sense of it, without digging into the endless diversity of topological spaces.

For those who need proof of correctness, a proof based on mathematical induction will be included. Just as a buzz word, I would love to title it "Topologically Sorted Domination-Trees of Directed Graphs".

It covers all what I am doing.

Because I was attacked personally and very aggressively yesterday, I decided to defend myself at this place.

My aim was and is not to insult or offend anyone, not to mention science. But I am not going to allow some self-proclaimed moral guardians without any authority whatsoever to restrict what I may think, my visions are and share those. And from now on, I will ignore their rubbish.

Only the owner of this site can disallow me to publish my thoughts. Of course, people can report my posts and ask to remove them from this site.

The truth of the facts does not depend on an individual's feelings or beliefs. I will continue (starting from scratch) to discuss and document the previously mentioned claims based on edge-relations and transitivity alone, are the facts of life.

No one is urged to read what I am sharing; feel yourself free to turn the page.

I said I am going to start from scratch, and I am doing so.

I started reading the paper mentioned earlier (https://www.m-hikari.com/ijma/ijma-2018/ijma-1-4-2018/p/abduIJMA1-4-2018.pdf), with all my respect to the authors. They see directed graphs and their corresponding topologies as abstract objects of mathematical study. Here is how they define the correspondence: “The family 𝐵 = {𝒬(𝑣): 𝑣 ∈ 𝑉} forms a base for a topology on the set 𝑉 of nodes of a transitive directed graph 𝐷 = (𝑉, 𝐸), where 𝒬(𝑣) = {𝑣} ∪ {𝑢 ∈ 𝑉: (𝑢, 𝑣) ∈ 𝐸(𝐷)}.”

To me, directed graphs have never been abstract. They were concrete examples (instances) that model the control flow of computer programs. I was interested in answering one single question: "Under which circumstances does this statement come to execution", and I meant all the circumstances. The aspects of discrete set of statements were not a great help.

The authors say, "Topology is an interesting and important field of mathematics. It is a powerful tool leading to such beneficial concepts as connectivity, continuity, and homotopy." I was interested in a fourth attribute, though: Coherence in the model. At this point, coherence should be understood as "systematic or logical connection or consistency (between the statements of the program)". Soon, I found out that paths through the directed graph helped me understand the logic of the underlying program.

Later on, I realized that this approach was necessary to understand the logic (reasoning) of any model represented as I directed graph, if there is a concrete narrative behind it. For example, one can ask "why does this task did not start as planned, are there not enough resources" as a project controller, or "what is the longest string I can build given these pieces" as someone who is trying out DNA sequences. The outline of the process of laying out the coherence in the model is always the same.

Given that the nodes and edges of a graph (I will omit directed for the rest of the discussion) are finite, the paths (chains of transitive connections of nodes) through it are also finite. Consequently, a finite graph can only produce a unique set of paths. So I made myself go searching for the most feasible data structure to encode/decode the set of all possible paths.

Surprisingly enough, computing such a data structure was not complex at all, and I am going to document how it can be achieved.

Those who are interested in my endeavor are kindly invited to follow.

A Graph

I use almost the same definition of a graph as stated in the paper mentioned earlier, except for the additional distinct vertices Source, a vertex without any predecessor, and Sink, a vertex without any successor. Therefore, the minimal (initial) graph will contain two vertices, Source and Sink, and an edge (Source, Sink).

Only one operation, edge insertion, is permitted to extend a graph, and only one edge can be inserted at a time. An edge denoting a binary relationship between two vertices is specified as (u, v), where u is the tail and v is the head of the edge. If either vertex is not an element of the vertex set V, it will be added to the set.

After the insertion of the first edge (a, b), the graph will contain the sets V = {Source, Sink, a, b} and E = {(Source, a), (b, Sink), (a, b)} (we will omit the vertices Source and Sink and edges containing Source and Sink for the rest of the discussion), and therefore V will be denoted as {a, b} and E as {(a, b)}.

Vertex Types

Except Source and Sink, there are four types of vertices which a graph contains.

1. Those with exactly one inbound, and one outbound edges.

2. Those with exactly one inbound, and at least one outbound edges.

3. Those with at least one inbound, and exactly one outbound edges.

4. Those with at least one inbound, and one out bound edges.

Graph Types

Graphs are an unordered set of edges. The types of edges a graph contains determines its type, and there are only four of them.

1. Graphs consist of vertices of type 1. These types of graphs can be pictured as a list.

2. Graphs consist of vertices of type 2. These types of graphs can be pictured as a tree.

3. Graphs consist of vertices of type 3. These types of graphs can be pictured as an upended tree.

4. Graphs consist of vertices of type 4. These types of graphs can be pictured as a graph.

Please see the attached illustration. I omitted the vertices Source and Sink in all pictures.

Encoding/Decoding A Graph

Type 1 graphs are encoded with a single ordered set of vertices. In the sample, this set would be [A, B, D, E]. The rule for encoding is “Vertex u can reach vertex v if v is to the right of u in the ordered set, or vertex v can be reached by vertex u, if u is to the left of v in the ordered set”. Please note that the edges of a graph are always bidirectional. Therefore, u and v are said to be connected if u can reach v, or v can be reached by u.

The question “How do we encode two nodes which are not connected” arises immediately. Assume that a graph has two nodes, X and Y. The list (ordered set) [X, Y] alone would mean X and Y are connected. We simply invent another list where the order of nodes is upended, [Y, X], and adjust the rule how to recognize connections among vertices. The new rule would be “Vertex u can reach vertex v if v is to the right of u in both of the ordered sets, or vertex v can be reached by vertex u, if u is to the left of v in both of the ordered sets”.

Using the same procedure, we can encode any number of disconnected nodes (sub-graphs) in a graph. New disconnected nodes are to be appended to the list named Q1 (the claimer) and prepend to Q2 (the verifier). If, the new node has to be inserted in the middle of the claimer Q1 (for example a list of alphabetically sorted words), in the verifier Q2, it has to be inserted immediately before the node immediately after which it is inserted in the claimer. In this example, if node Z is to be inserted after node X, Q1 becomes [X, Z, Y] and Q2 becomes [Y, Z, X].

Using the same technique, we can also encode Type 2, Type 3 graphs. Type 4 graphs can also be encoded using this technique if they are well-nested, but require a different approach if they are ill-nested. The discussion of how Type 4 graphs are nested will be postponed until the structure of graphs is defined. Let us consider an example. If the graph contains an edge {(A, B)} and a node {X} it will be encoded as Q1 = [A, B, X], and Q2 = [X, A, B].

Lists Q1 and Q2 are tightly coupled. Their decision about the connectedness of two vertices is valid only as a pair. Consequently, any change in one of them has to be reflected in the other.

A Fair Comparison

The sample graph given on page 74 of the paper (https://www.m-hikari.com/ijma/ijma-2018/ijma-1-4-2018/p/abduIJMA1-4-2018.pdf) can be represented in an edge-oriented approach. Here fore, we take the edges as the nodes of the graphs, and relations between them as the edges of the graph. Please see the attached graphic.

The new graph can be encoded using two tightly coupled spanning lists:

Q1=[e1, e4, e2, e3] and Q2=[e4, e1, e2, e3]. Decoding follows the same rules as mentioned earlier.

This encoding covers all three concepts of topology as mentioned in the paper, namely connectivity, continuity, and homotopy. In addition, it encodes all paths through the graph, where P1=[e1, e2, e3], and P2=[e4, e2, e3]. The paths can be constructed by a simple iteration process with backtracking capability.

The structure of the graph (also not mentioned in the paper but is a unique aspect of its topology, especially continuity) is its decomposition into three unique sub-graphs S1={e1, e4}, S2={e2}, S3={e3}. I will discuss the structure of a graph (especially why it has to be unique), and how to compute it when time is due.

The Structure of a Graph

The “The” in the title is not a typo. Not only that every directed graph has intrinsically a structure, this structure is also unique. Let me explain “why”.

We have to start with the definition of “Domination in Graphs”.

A vertex u is said to pre-dominate another vertex v, if every inbound-path to v contains u. Similarly, if vertex w is on every outbound-path from v, w is called to post-dominate vertex v.

We can create two graphs

• A graph which contains all edge-relations of the form (PreDom(u), u)
• A graph which contains all edge-relations of the form (PostDom(u), u)

It is trivial to show that the reduced graphs of these edge-relations form a tree, as illustrated in Figure 1 (attached).

Let us define a sub-graph to be of the form (Entry, Body, Target), where:

• Entry is a node.
• Body is the successors of the node in PreDom tree except its post-dominator.
• Target is the predecessor of the node in PostDom tree.

This definition leads to a unique decomposition of a graph into its sub-graphs. For the given example, the decomposition will be:

S1 = (S1, {}, C1)

C1 = (C1, {S5, C2}, S7)

S5 = (S5, {}, S7)

C2 = (C2, {}, C3)

C3 = (C3, {S3, S4}, S7)

S3 = (S3, {}, S7)

S4 = (S4, {}, S7)

S7 = (S7, {}, S9)

S9 = (S9, {}, Sink)

The sub-graphs as well as the successors of the entries do not to be in an order of any kind.

A decomposition which obeys this definition (illustrated in Figure 2) is called the structure of the graph because

Besides connectivity, continuation is a crucial concept which defines topology. A non-mathematical definition of topology says, “no matter which transformations in which order, and how often are applied, connected objects have to remain connected”. In the next post, I will discuss how continuity can be implemented by using expand/collapse procedures recursively.

By the way, please do not hesitate to extend this concept of graph structuring to any arbitrary edge‑relations defining acyclic graphs. Its application to cyclic graphs will be explained in a separate post.

Continuation and Connectivity in Graphs

Even if the structure of a graph is known, the concept of domination is not a great help to determine the connectivity of nodes. Although there exists an intrinsic order between sub-graphs, nodes which are not entries of sub-graphs remain unordered. This situation causes increased combinatorial complexity, and heavy computations, if we seek an orderly processing of nodes. On the other hand, the structure of a graph allows us to effectively compute connectivity among nodes.

In the concept of domination, dominators (entries) isolate a sub-graph from the rest of the graph, such that the sub-graph is an independent entity. Consequently, connectivity of nodes is decided and encoded within a sub-graph.

We have already discussed that two tightly coupled lists are needed to encode the connectivity of graphs, except for ill-nested graphs, which we will discuss at a later time. Accordingly, the encodings, in order of increasing level of detail, of the sample graph illustrated in the last post will be:

• Q1 = [S1, C1, S7, S9], Q2 = [S1, C1, S7, S9]
• Q1 = [S1, [C1, S5, C2, C3], S7, S9], Q2 = [S1, [C1, C2, C3, S5], S7, S9]
• Q1 = [S1, [C1, S5, C2, [C3, S3, S4]], S7, S9], Q2 = [S1, [C1, C2, [C3, S4, S3], S5], S7, S9]

Please note that for the sake of clarity, the sample graph is kept as simple as possible.

Possibly, the closest analogy to this process is “variable substitution”, which is a well-known technique. As we go deeper into the details of a sub-graph, we expand its entry followed by its body first in list Q1, and then in list Q2, where the nodes are listed in appropriate order to encode the connectivity.

The rule for decoding the connectivity is the same as before, node-u can reach node-v if node-v resides to the right of node-u in both lists.

If lesser detail is required, the sub-graph is substituted with is head in both lists, collapsing the sub-graph.

After all, with this technique, we can combine encoding /decoding the connectivity of a graph with the guaranty of continuity during expand/collapse processes.

Cycles

There exist only four types of edges (u, v) denoting an edge-relation:

Back-edges are pseudo edges which have u as their targets, and have the same effect as forward, tree, or cross edges.

If we encounter a back-edge for the first time, we introduce a pseudo-node @u and insert a tree-edge (v, @u) instead of (v, u). If further edges have u as their targets, it is replaced literally by @u and processing continues as usual, considering them either as forward or cross-edges. Of course, @u is recorded as a proxy of u.

This (well, one can call it a trick) converts a cyclic graph into its acyclic skeleton. Later on, whenever the graph is traversed as soon as @u is reached, it is thought (without literally replacing it) to be u and the traversal is continued without an interruption.

I am attaching the illustration of the building block of a directed graph once again. It can be seen that the explanation is the exact implementation of what is sketched on the paper.

Please note that the definition of a sub-graph has also to be adjusted accordingly, now being (Entry, Body, Target, Proxy).