Generating a random directed graph (network) with some properties, efficiently

Hi,

Im currently building a code to simulate the push/relabel max-flow algorithm.

Therefor, in order to make the simulation more entertaining and also to check myself, I need a graph generator.

The graph need to have certain properties:

-directed

-no self loops (ie no (v,v) edges)

-relatively sparse

-connected

the sparse + connected part is the problematic part for me. If anybody has any idea how to do this efficiently please share with me.

Thanks, Dan

Answer 1

[Walter Roberson]

temp = randi(NumberOfNodes, NumberOfVertices, 2);
temp(diff(temp,[],2)==0, :) = []; %remove self-loops
s = temp(:,1); t = temp(:,2);

which you can then digraph()

Note: this might not use all of the nodes. randperm() can help use all of the nodes.

[Walter Roberson]

The connected part requires that every node except the initial node be the destination of at least one directed edge, and that every node except the final node be the source of at least directed edge. You can guarantee that by using randperm() to generate at least some of the edges.

... though that in itself would not guarantee that there were no disconnected loops.

You can guarantee no disconnected loops by ensuring that each node other than the first is the target of at least one edge from a lower-valued vertex.

s = floor(rand(1, N-1) .* (1:N-1)) + 1
t = 2:N;

[N/A]

What is the difference between the input NumberOfNodes and NumberOfVertices?

What is the type of graph representation captured by s and t?

[Walter Roberson]

temp = randi(NumberOfNodes, NumberOfVertices, 2);

Number of Nodes is the number of nodes that exists in the graph.

Number of Vertices is the number of trial edges that will created.

You could probably use NumberOfEdges instead of NumberOfVertices to be more clear.

s and t notation is "source and target" https://www.mathworks.com/help/matlab/ref/digraph.html#d123e341494 -- for digraphs, s is the node that is being exited by an edge, and t is the node that is being entered by the edge.

Answer 2

[Dan Yaron]

Thanks a lot