User:Zeracles/Starmap/Minimal Spanning Tree - Revision history

Zeracles: /* Code */ adjust links

2013-09-01T06:22:26Z

Code: adjust links

← Older revision		Revision as of 06:22, 1 September 2013
Line 24:		Line 24:

	==Code==		==Code==
	When prototyping, I wrote a [http://www.physics.usyd.edu.au/~asmith/files/MSTclosure.m matlab/octave version available here], and have recently done a [http://www.physics.usyd.edu.au/~asmith/files/MSTclosure.c C conversion available here].		When prototyping, I wrote a [http://www.physics.usyd.edu.au/~asmith/files/sc1/MSTclosure.m matlab/octave version available here], and have recently done a [http://www.physics.usyd.edu.au/~asmith/files/sc1/MSTclosure.c C conversion available here].

Zeracles: updated method and code

2013-08-27T04:38:05Z

updated method and code

Show changes

Zeracles: /* Boruvka's Algorithm */ remove redundant bits

2010-03-02T11:37:19Z

Boruvka's Algorithm: remove redundant bits

← Older revision		Revision as of 11:37, 2 March 2010
Line 32:		Line 32:

	localcount=8;		localcount=8;

	~~quantify=0;~~

	separation=0;		separation=0;
Line 51:		Line 49:
	dimensions=sizeinputpositions(2);		dimensions=sizeinputpositions(2);

	index=~~transpose(~~linspace(1,lengthinputpositions,lengthinputpositions));		index=linspace(1,lengthinputpositions,lengthinputpositions);

	inputpositionxs=inputpositions(:,1);		inputpositionxs=inputpositions(:,1);
Line 95:		Line 93:

	treenumber=index;		treenumber=index;
	numbertrees=length~~(unique~~(treenumber));		numbertrees=length(treenumber);
	branches=[];		branches=[];
	searchfactor=1; % setting this to zero can lead to infinite loop if this is scaled multiplicatively		searchfactor=1; % setting this to zero can lead to infinite loop if this is scaled multiplicatively

Zeracles: MCOFG description

2010-02-23T05:20:32Z

MCOFG description

@@ Line 1: / Line 1: @@
 I originally coded up [[wikipedia:Prim's_algorithm|Jarnik/Prim's algorithm]]. In the process of optimising it, I unwittingly reinvented [[wikipedia:Bor%C5%AFvka%27s_algorithm|Boruvka's algorithm]], which handles large numbers of input points better, at least the way I've done it. Demonstration [http://www.star-control.com/forum/index.php/topic,1660.msg35209.html#msg35209 here].
 ==Boruvka's Algorithm==
 Also downloadable [http://www.physics.usyd.edu.au/~asmith/files/sc1/MST_Boruvka.m here]

Zeracles: /* Boruvka's Algorithm */ minor bugfix and added Minimally Connected Opaque Friend Graph option

2010-02-23T04:33:25Z

Boruvka's Algorithm: minor bugfix and added Minimally Connected Opaque Friend Graph option

Show changes

Zeracles: link

2010-02-19T16:52:56Z

link

← Older revision		Revision as of 16:52, 19 February 2010
Line 1:		Line 1:
	I originally coded up [[wikipedia:Prim's_algorithm\|Jarnik/Prim's algorithm]]. In the process of optimising it, I unwittingly reinvented [[wikipedia:Bor%C5%AFvka%27s_algorithm\|Boruvka's algorithm]], which handles large numbers of input points better, at least the way I've done it.		I originally coded up [[wikipedia:Prim's_algorithm\|Jarnik/Prim's algorithm]]. In the process of optimising it, I unwittingly reinvented [[wikipedia:Bor%C5%AFvka%27s_algorithm\|Boruvka's algorithm]], which handles large numbers of input points better, at least the way I've done it. Demonstration [http://www.star-control.com/forum/index.php/topic,1660.msg35209.html#msg35209 here].
	==Boruvka's Algorithm==		==Boruvka's Algorithm==
	Also downloadable [http://www.physics.usyd.edu.au/~asmith/files/sc1/MST_Boruvka.m here]		Also downloadable [http://www.physics.usyd.edu.au/~asmith/files/sc1/MST_Boruvka.m here]

Zeracles: Boruvka's algorithm is faster, at least the way I've done it

2010-02-14T14:49:06Z

Boruvka's algorithm is faster, at least the way I've done it

Show changes

Zeracles: renamed target and added line

2010-02-14T14:16:21Z

renamed target and added line

← Older revision		Revision as of 14:16, 14 February 2010
Line 1:		Line 1:
	Also downloadable [http://www.physics.usyd.edu.au/~asmith/files/sc1/~~MST~~.m here]		=Jarnik/Prim's Algorithm=
			Also downloadable [http://www.physics.usyd.edu.au/~asmith/files/sc1/MST_JarnikPrim.m here]
	~~It definitely needs some improvement, but for now -~~
	% minimal spannng tree in matlab		% minimal spannng tree in matlab
			% Jarnik/Prim's algorithm - runs pretty slowly for any more than 50 input points
	% see http://www.star-control.com/forum/index.php/topic,1660.msg33938.html#msg33938		% see http://www.star-control.com/forum/index.php/topic,1660.msg33938.html#msg33938
	% by Anthony Smith (Zeracles)		% by Anthony Smith (Zeracles)

Zeracles: added comments

2009-12-18T09:04:06Z

added comments

← Older revision		Revision as of 09:04, 18 December 2009
Line 3:		Line 3:
	It definitely needs some improvement, but for now -		It definitely needs some improvement, but for now -
	% minimal spannng tree in matlab		% minimal spannng tree in matlab
			% see http://www.star-control.com/forum/index.php/topic,1660.msg33938.html#msg33938
	% by Anthony Smith (Zeracles)		% by Anthony Smith (Zeracles)
	% astroant@hotmail.com		% astroant@hotmail.com
Line 67:		Line 68:
	branches=[];		branches=[];

	while lengthremainingpositions>0		while lengthremainingpositions>0 % keep going until nothing remains unlinked to the tree (the ``remainingpositions")
	mindistances=[];		mindistances=[];
	for i=linspace(1,lengthtreepositions,lengthtreepositions)		for i=linspace(1,lengthtreepositions,lengthtreepositions) % search around each of the tree positions for remainingpositions
			% retrieve coordinates of a tree position
	treepositionx=inputpositions(treeindices(i),1);		treepositionx=inputpositions(treeindices(i),1);
	treepositiony=inputpositions(treeindices(i),2);		treepositiony=inputpositions(treeindices(i),2);
Line 79:		Line 81:
	occupiedbox=0;		occupiedbox=0;
	searchfactor=1;		searchfactor=1;
	while occupiedbox==0		while occupiedbox==0 % search for remainingpositions inside a box that grows until some are found
	boxradius=searchfactor*searchincrement;		boxradius=searchfactor*searchincrement;

Line 100:		Line 102:
	mindistancecandidates=[];		mindistancecandidates=[];
	mindistancecandidateindices=[];		mindistancecandidateindices=[];
	if sum(closerremainingmask)>0		if sum(closerremainingmask)>0 % if there are remainingpositions inside the box, calculate the actual distances to them
	for k=find(closerremainingmask==1)		for k=find(closerremainingmask==1)
	branchcandidatex=remainingpositionxs(k);		branchcandidatex=remainingpositionxs(k);
Line 107:		Line 109:
	branchcandidatez=remainingpositionzs(k);		branchcandidatez=remainingpositionzs(k);
	end		end
	branchcandidateindex=remainingpositionindices(k);		branchcandidateindex=remainingpositionindices(k); % set up to remember the index of each prospective link destination

	if dimensions==2		if dimensions==2
Line 122:		Line 124:
	end		end
	if numel(mindistancecandidates)>0		if numel(mindistancecandidates)>0
	mindistance=[min(mindistancecandidates),treeindex,mindistancecandidateindices(find(mindistancecandidates==min(mindistancecandidates)))];		mindistance=[min(mindistancecandidates),treeindex,mindistancecandidateindices(find(mindistancecandidates==min(mindistancecandidates)))]; % minimum distances carry the indices of the prospective link destination
	mindistances=[mindistances;mindistance];		mindistances=[mindistances;mindistance];

	occupiedbox=1;		occupiedbox=1;
	end		end
	searchfactor=searchfactor+1;		searchfactor=searchfactor+1; % make the search box bigger
	end		end
	end		end
Line 133:		Line 135:
	branchindex=find(branchdistance==mindistances(:,1));		branchindex=find(branchdistance==mindistances(:,1));
	numberbranchcandidates=numel(branchindex);		numberbranchcandidates=numel(branchindex);
	if numberbranchcandidates>1		if numberbranchcandidates>1 % if there's a tie for minimum length
	branchindex=branchindex(ceil(numberbranchcandidates*rand(1)));		branchindex=branchindex(ceil(numberbranchcandidates*rand(1)));
	end		end

			% add this branch to the tree
	branch=mindistances(branchindex,:);		branch=mindistances(branchindex,:);
	branches=[branches;branch];		branches=[branches;branch];

			% add that location to the tree
	treeindices=[treeindices;branch(3)];		treeindices=[treeindices;branch(3)];
	lengthtreepositions=lengthtreepositions+1;		lengthtreepositions=lengthtreepositions+1;

			% remove that location from the remainingpositions
	remainingmask=ones(lengthremainingpositions,1);		remainingmask=ones(lengthremainingpositions,1);
	removed=find(remainingpositionindices==branch(3));		removed=find(remainingpositionindices==branch(3));
Line 158:		Line 164:
	save('branches','branches')		save('branches','branches')

			% for plotting
	sizebranches=size(branches);		sizebranches=size(branches);
	numberofbranches=sizebranches(1);		numberofbranches=sizebranches(1);

Zeracles: link

2009-12-18T08:24:02Z

link

← Older revision		Revision as of 08:24, 18 December 2009
Line 1:		Line 1:
			Also downloadable [http://www.physics.usyd.edu.au/~asmith/files/sc1/MST.m here]

	It definitely needs some improvement, but for now -		It definitely needs some improvement, but for now -
	% minimal spannng tree in matlab		% minimal spannng tree in matlab