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
???


???
??

?屬性????????????大小?????日期????時(shí)間???名稱
-----------?---------??----------?-----??----
?????文件????????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