Graph analysis

This application is part of the Netron graph library v2

What is it?

This application shows how to use the various traditional graph algorithms from the
new Netron data structures library and how the results can be shown interactively
using the graph library.

How to use it?

The menu allows you to access various samples. The orange connections show graphically
what you can read in the right panel in matrix form. The graphs are generated randomy
using a simple Erdos-Renyi algorithm. You can explore the code and experiment with
various settings and algorithms. In the near future some more algorithms will be
added. These algorithms have had recently much attention in the context of the so-called
small-world phenomena about which you will find more information on this site.

About the algorithms

Depth first traversal (DFT):

This algorithms visits all nodes recursively taking node children before continuing
on the same level to neighbors (brother/sister nodes). In the picture below you can
see the orange path visiting all nodes (except number 9 since it is unconnected to
any other). Note that this algorithm takes node four after node one. In the breadth
first algorithm (see below) node three would be taken after node one since it is
on the same hierachical level. The DFT algorithms goes as deep as possible before
visiting other nodes.

Breadth first traversal:

This algorithm visits all nodes recursively by visiting first neighboring nodes (brother/sister
nodes) before going down to a lower (child) level. Notice in the picture below how
all nodes of the same hierachy level are visited before going down to the next level.

Prim:

This algorithm, sometimes called DJP algorithm or Jarnik algorithm, computes a spanning
tree of a graph. In the screenshot below you can see in orange a tree which touches
every node and is a tree consisting of edges from the graph. The yellow lables are
the weights of the edges. The Kruskal algorithm uses these weights to find a minimum
spanning in contrast to this algorithm where the weights don’t really matter.

Kruskal:

This algorithm finds a minimum spanning tree for a connected weighted graph (see
above).

Floyd:

The Floyd-Warshall algorithm is an algorithm to solve the shortest path problem in
a weighted, directed graph. In this case the orange lines merely show whether or
not there exists a shortest path between two vertices. What really matters is the
adjacency matrix outputted by the algorithm which says what or how much the weight
is between any two vertices.

Dijkstra:

This algorithm solves the problem of finding the shortest path from a point in a
graph (the source) to a destination. It turns out that one can find the shortest
paths from a given source to all points in a graph in the same time, hence this problem
is sometimes called the single-source shortest paths problem. It is heavily used
in all kinds of traffic problems, TCP/IP, routers, and so on. See also the remarks
above on Floyd’s algorithm.

On random graphs

Recently a lot of research is going on in graph theory and random networks in particular.
The so-called small-world phenomenon, also called six degrees of freedom, pervades
both technology and natures: the way our brain is connected, the way the internet
hangs together, the social relationships of people…it seems to underly a lot of
systems. In this graph analysis demo you can experiment with various random graph
algorithm, among which the Watts-Strogatz small-world algorithm.