In my example, both (C, D) and (D, C) exist. I assume you would suggest putting a "1" in both cells. Considering the row headings, how do you decide which of "C" and "D" comes first? In other words, which one of the orders

(A, B, C, D) or (A, B, D, C) has to be used?

Is it a random selection (this would have consequences)?

Does the order of row (or column) headings have any meaning?

Thanks, I got it. Row- and column-headings may be unordered if I would like to replace an adjacency-list with an adjacency-matrix. More than that, row-headings don't need to be identical with column-headings, i.e. they don't have to be in the same order.

If I would like to use the matrix for path building, I assume it is going to lead to matrix exponentiation, can the row-, column-headings still be unordered?

0 1 1 0

0 0 0 1

0 0 0 1

0 0 1 0

My question is (and was) "is this representation enough to correctly replicate the topology of a directed graph?"

I think the answer is "Yes", but I am not sure whether rows/columns have to be ordered or not.

More important, can I with "adjacency matrix" representation reflect the paths through a graph?

My guess is "no way".

I am wondering why academia prefers "adjacency matrices" and "undirected graphs" to model AI or networks in general. Especially if I consider that with this choice, it is not obvious how "coherence in discourse" can be implemented.

Dear Enis Olgac, I'm not sure what you mean when you say that academia "prefers" adjacency matrics and undirected graphs. Any decent book or chapter on algorithmic graph theory will mention that there are several ways of representing graphs, such as adjacency matrices and adjacency lists, and that each representation has certain pros and cons in an algorithmic context. Similarly, such books or chapters normally mention undirected, directed and mixed graphs. Some of them mention more general structures, such as hypergraphs or bidirected graphs.

This is correct, and please do not feel offended. Directed Graphs, and adjacency lists are only mentioned. But as far as I can remember, in the realm of AI and/or (neural) networks I have never seen a concrete example of their usage, and that since 1986. There must be an overwhelming, and simple to explain advantage of undirected graphs and adjacency matrices, and I am just wandering, what this is. I would be grateful, if you can clear it for me because no one else is doing so. I would also be grateful for a link where I can read about the pros and cons, a direct comparison.

Ah, so you are thinking of applications in AI and Machine Learning specifically. In that case, you may be right. I work in Operational Research, and we tend to use whatever we need for the specific application at hand. If that means a mixed graph, then so be it. :-)

Hi Enis Olgac It's true that for many algorithms using an adjacency list can be quicker. However, one of the main reasons that using an adjacency matrix is a good idea is that it allows us to apply methods from linear algebra, especially graph spectra. One nice fact is that if you take a power of the adjacency matrix A^r, then the (u,v) entry will equal the number of walks of length r from u to v. (This will work in a digraph as well). Also various results use the determinant of such matrices to count subtrees, for example. (Note for the result that I mention above the order of the vertices is not important, but we do need the same ordering for the rows and columns)

Thanks, James. It is clear that you can compute the number of walks, but not the vertices visited in a particular walk (paths). Exactly this is a prerequisite to implement coherence in discourse. Two paths which reach two different vertices (maybe indicating contradictory results) will have walks of equal length. In general, you cannot answer queries involving paths (and these are the relevant ones in graph analysis) by looking at the walks.

It is the same as you would know the product is 12, but you cannot even guess what the multiplicands are (or is it a summation of some numbers like; 12.8-0.8).

I am curious about your definition of a subtree, would be great if you can specify it.

Here are mine:

• https://digraphs.blog/form-of-a-graph.html
• https://digraphs.blog/domination-in-graphs.html

Yes, you can't deduce the walks from the numbers themselves, you would need to go back to the matrix or the adjacency matrix to list them. But I was trying to answer your question on why adjacency matrices are used. Take, for example, the proof that there are only finitely many Moore graphs, and all of them have diameter two - that would be very difficult using only adjacency lists!

I must admit that I read subtrees as sub-graphs in your first answer, sorry.

Actually, the reason for my question in the first place was to find out whether there are some overwhelming advantages to using adjacency matrices in graphs analysis.

From the answers here and elsewhere, I understand that adjacency matrices exclude any analysis involving paths, by definition. Am I correct?

Maybe I have to rephrase my question: "Are undirected graphs invented to enable using adjacency matrices"

Hi Enis, they certainly don't exclude analysis with paths - after all, the adjacency matrix contains the adjacency list, so they are interchangable. If you want to find concrete paths, then you will need to apply an algorithm whichever representation you use, no?

In summary, which representation you use depends on what you want to do :) If you are doing algorithms, typically the adjacency list will be efficient, but for a mathematical proof the added structure of the adjacency matrix can be more powerful.

You are certainly correct. But what are the advantages of using adjacency matrices as if they were adjacency lists, or are there any known algorithms which use matrix operations as their core for graphs analysis involving paths?

Does path analysis preclude linear algebra?

As far as I know, E.J. Tarjan was trying to invent algorithms to express directed graphs as path expressions, which would have given way to use linear algebra for path analysis. I am not sure whether he ever succeeded.

Good question. The answer to this stack overflow question here https://stackoverflow.com/questions/62610614/which-graph-algorithms-prefer-adjacency-matrix-and-why might help.

Thank you very much, the link was a great help, and was inline with my expectations.

I invented an incremental algorithm, which can encode all paths of a directed graph (also cyclic ones) in linear time per edge insertion. The time depends on the number of vertices involved (known to the algorithm) at the instant of insertion. The four spanning lists, which encode the structure and topology of the graph, allow constant time queries about the connectedness of any given pair of vertices. Therefore, I am not sure whether the time requirements given in the link are not exaggerated. For example, (of course once the spanning lists are generated) traversing through all edges will be an iteration through the list of vertices, i.e. O(n).

I have another argument against undirected graphs.

If I can drive from one city to another, usually there are at least two lanes, one in each direction. If there is only one lane, a traffic light regulates the flow. I don't know of any lane with unregulated flow in both directions simultaneously.

My conclusion is that undirected graphs can be used to encode distances, but never the flow. The flow in both directions are mutually exclusive.

How is it possible to analyze flow in networks encoded as adjacency matrices.

Never saw a network from this perspective. I am wondering how a bidirectional link can be represented as two unidirectional links within the same network if it is modeled by an adjacency matrix, though.

By the way, does this mean that there is an underlying assumption that I can change the flow from +10 to -10 instantly within the same link?

Enis Olgac The best solution would likely be to look at the flow on the network modelled as a directed graph or a mixed graph. Then you can assign different capacities to the different directions in a natural manner. All of the relevant algorithms, e.g. Ford-Fulkerson, work on directed graphs.

If we agree that networks are special graphs, and therefore a graph is the thing, we are on the same page. This elementary aspect has gone lost for a while, and the graph is out of sight by now (not only in our discussion).

It is true that every graph has a unique structure if we let the isomorphisms by side (even if we consider cyclic graphs). And there is a unique topology determined by the graphs' structure. This uniqueness is uncomplicated to prove.

Thereby, the form of the graph is irrelevant.

I must admit that I was wrong, claiming that three lists of vertices (topological-triple) are required to correctly encode the structure and topology of any (directed) graph. We need only two lists, each including the complete set of vertices of the graph.

Peter Breuer, thanks for the clarification.

My claims are valid for directed graphs in general, no matter whether they are cyclic or not. I am using a given edge-set because orphaned vertices effect neither the structure nor the topology of the graph. The order of the edges is irrelevant.

Before I come back to the claims, I would like to understand how orphaned nodes can affect the topology.

Just to clear my understanding, here is the definition of topology as I understand it, by P. Alexandroff:

"The topology of a directed 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"

As far as I can see, orphaned vertices are orphaned, i.e. they do not appear in any of the edge relations. They can neither reach, nor can they be reached by any other vertex, their minimal neighborhood is empty. Therefore, they cannot be part of the topology. How can they affect something they are not part of it? Do I oversee something?

Of course, every vertex can reach itself by definition (in other words, they are aware of themselves), so why do I need additional edges to express something that I already know?

Keeping in mind that it is still an open question whether orphaned vertices can affect the topology or not, I would like to proceed with my claims about directed graphs.

The definition of structure is my starting point. According to Merriam-Webster, structure is:

• something arranged in a definite pattern of organization
• the arrangement of particles or parts in a substance or body
• organization of parts as dominated by the general character of the whole
• coherent form or organization
• the aggregate of elements of an entity in their relationships to each other

Given a directed graph by its edge relations, its structure is determined by its domination tree (for a discussion of domination-trees of directed graphs, please visit https://digraphs.blog/domination-in-graphs.html).

Next, I will explain why domination-trees materialize the structure of a directed graph. Please note that with directed graphs, acyclic as wells as cyclic directed graphs are meant.

I learned that any entry below the diagonal on an adjacency matrix if row and column headings are kept in the same order, will encode a cycle. But I also learned that an adjacency matrix is not a suitable vehicle to encode the structure, knowledge about how the vertices of the graph are organized.

So I am switching to "https://www.researchgate.net/post/Do_directed_graphs_have_a_unique_structure_and_topology",

because without the knowledge about the structure of the underlying graph, any analysis (attempt to resolve queries depending on transitive chains of edge relations aka paths) is and will remain searching for a needle in the haystack.