Draw network of nodes from a matrix

Hi,

I would like to draw connected nodes that resemble a network with source and destination.

What I really want is translating a given data (from a matrix) to a graph.

For example; I have the following: S=[1,1,1,1,2,3,3,4,5,6] and D=[2,4,6,3,4,6,7,5,6,7]

As it can be seen matrix S forms the source nodes and matrix D forms the destination nodes(for example first element of matrix S as node 1 is connected to first element of matrix D as node 2... and so on).

The graph for the matrix must look like below:

http://i39.tinypic.com/vn096t.jpg

The source and destination matrices are just an example, I need to generate those two matrices randomly (this is ok).

But how can I make sure that the generated two matrices can create an existed path/paths from source (node 1) to destination (node 7)? In another word, the randomly generated matrix can create dead end or a loop without reaching the destination.

Maybe it is not difficult to solve such a problem with only 7 nodes but how about any number of nodes??

Best Regards

NAF

Answer 1

[Walter Roberson]

You have two different issues there:

1. drawing the graph
2. determining whether there is a path from source to destination

If the matrices are generated randomly, you cannot be certain that the graph will be planar. Often it will not be. This means that the graph would often have to cross edges if you try to draw it flat. Drawing in 3D gives more freedom, but there are random graphs that cannot be drawn in 3D. A quick mental model suggests to me that there might be some random graphs that would require up to (N-2) dimensions to draw for N points.

Automatic graph layout routines are somewhat messy to do right even in 2D.

I would suggest that if you do not need to draw the graph, that you do not do so. It is a bunch of bother, at least if you are trying to avoid edge crossings or make the graph "pretty".

The second question, of determining whether there is a path between the source and destination, can be solved by Dijkstra's Shortest Path algorithm. There is at least one implementation in the MATLAB File Exchange. There are some alternative algorithms for determining whether two points are connected or not that theoretically take less time, but with a good Dijkstra's implementation for sparse graphs, the difference is not so much.

[Nayef]

Thank you for the reply, actually I still want to draw the connected point because I think MATLAB can do that. Second I still want to find a way to check if there is a path exist without using Dijkstra's method, because it search for the shortest path not if there is a path or not. Also Dijkstra'a is a complicated method.

Best Regards

[Walter Roberson]

How do you want the connected nodes to be laid out?

By far the easiest way would be to position them equally around a circle, and draw straight-line connections between them.

Dijkstra's method does not need to be complicated. The run-time is more predictable if you implement it using matrix multiplication, but there are other implementations that do not do that, and which are more suitable for sparser graphs. But of course it is you implementing it, not me, so pick the algorithm you feel most comfortable with.

The alternate algorithm:

Put the start node in to one set. Put the destination node in to a second set.

Iterate:

If the intersection of the first set and the second set is non-empty, then there is _some_ path between the first and second set, so end.

Otherwise:

Find the set of nodes that are directly reachable from any member of the first set. Add this set of nodes to the first set.

Find the set of nodes that are directly reachable from any member of the second set. Add this set of nodes to the second set.

Go back to the beginning of the loop.

This algorithm has an obvious optimization: you do not need to re-check the connections of anything that was already in one of the sets, so you only need to check the connections from the nodes that were last added to the set.

[Walter Roberson]

Oh yes: if at any point, no connected nodes are found that were not already in the set, then the two sets are disconnected and there is no path, so end.