matlab开发-Edmondsalgorithm

matlab开发-Edmondsalgorithm。爱德蒙算法从图中获得最大生成权树的一种实现

function[ED]=edmonds（VE）%
%input is a directed graph 
%V- Set of vertices [v1 v2v3....]
%E- Set of edges is [ v1 v2 weight（v1v2）; ...] format

% Author: Ashish Choudhary Ph.D
%         Pharmaceutical genomics division TGEN.
%         13208E Shea Blvd Scottsdale AZ 85259.
% Note/Disclaimer: This code is for academic purposes only.
% The implementation is derived from the book by Alan Gibbons.

%initialization
ED（1）.BV=[];% Bucket of vertices
ED（1）.BE=[];% Bucket of Edges

ED（1）.V=V;
ED（1）.E=E;

CURRENT_i=1;

while（1）    % breaking condition later
    
    CURRENT_i
    V=ED（CURRENT_i）.V
    E=ED（CURRENT_i）.E
     
    VERTICES_NOT_IN_BV=setdiff（VED（CURRENT_i）.BV）;
    
    if （numel（VERTICES_NOT_IN_BV）==0）
        break; %first phase
    end
    
    %let us add the first such
    VERTEX_ADDED=VERTICES_NOT_IN_BV（1）;
    ED（CURRENT_i）.BV=[ED（CURRENT_i）.BVVERTEX_ADDED];%
    
    %now check if largest incoming edge has a positive value
        
    [EDGE_VALUEEDGE_ADDED]=index_of_max_value_incoming_edge（EVERTEX_ADDED）;
    
    if EDGE_VALUE>0 %dont do anything otherwise
        
    %upon adding check if there is a cicuit. 
    %If so we will need to relabel everything  
    [distpath]=iscycle（[E（ED（CURRENT_i）.BE:）]E（EDGE_ADDED1）E（EDGE_ADDED2））
    
  
    ED（CURRENT_i）.VERTICESINCKT=path;
    %now if the path was of finite length this 
    
     % now  adding to edge buckets
    ED（CURRENT_i）.BE=[ED（CURRENT_i）.BEEDGE_ADDED];
    if dist        [GSTRMAPVERTMAPEDGE]=relabelgraph（ED（CURRENT_i））;
        ED（CURRENT_i）.MAPPINGVERT=MAPVERT;
        ED（CURRENT_i）.MAPPINGEDGE=MAPEDGE;
        
        CURRENT_i=CURRENT_i+1
        ED（CURRENT_i）.BV=GSTR.BV;
        ED（CURRENT_i）.BE=GSTR.BE;
        ED（CURRENT_i）.V=GSTR.V;
        ED（CURRENT_i）.E=GSTR.E;
        
    end 
   
    
    end% end of EDGE_VALUE>0
end
    
%And now the reconstruction phase
   
%TREEMAX=reconstruct（ED）;



%%
function[FLAGS]=exists_incoming_edge（GNODEARRAY）
%finds if the nodes listed in the array have an incoming edge

for i=1:numel（NODEARRAY）
    FLAGS（i）=ismember（NODEARRAY（i）G（:2））;
end



%%
function[EDGE_VALUEEDGE_INDEX]=index_of_max_value_incoming_edge（GVERTEX）
%first find incoming edges
if numel（G）==0
    EDGE_VALUE=-1;
    EDGE_INDEX=NaN;
    return;
end
%
INDICES=find（G（:2）==VERTEX）
VALUES=（G（INDICES3））;
[EDGE_VALUELOC]=max（VALUES）;
EDGE_INDEX=INDICES（LOC）;


%%
function[distpath]=iscycle（GSD）
   if size（G1）>0
       MAXN=max（[SDmax（ unique（G（:1:2）） ）]）;
       G=[G;MAXNMAXN0];
    DG = sparse（G（:1）G（:2）G（:3））;
    
        
  
    [distpath]=graphshortestpath（DGSD）;
    %if there is no path from S to D try D to S
    if dist==Inf
        [distpath]=graphshortestpath（DGDS）;
    end 
   else
     dist=Inf;
     path=[];
   end
   


   
  

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     文件        2955  2009-08-01 23:25  edmonds.m
     文件         411  2009-08-01 23:58  example.m
     文件         220  2009-08-02 00:02  example2.m
     文件         256  2009-08-01 23:47  incidence_to_3n.m
     文件        2342  2008-09-02 15:08  reconstruct_2.m
     文件        3599  2008-09-01 20:44  relabelgraph.m
     文件         292  2009-08-01 23:52  showgraph.m
     文件        1514  2014-02-12 12:55  license.txt