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
采纳的回答
Walter Roberson
2018-4-18
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.
3 个评论
Walter Roberson
2018-4-18
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
2021-10-9
What is the difference between the input NumberOfNodes and NumberOfVertices?
What is the type of graph representation captured by s and t?
Walter Roberson
2021-10-10
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.
更多回答（1 个）
类别
在 帮助中心 和 File Exchange 中查找有关 Networks 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!
Translated by 
