﻿
402
Chapter9 GraphAlgorithms
start
A(3)
B(2)
C(3)
D(2)
E(1)
F(3)
G(2)
H(1)
K(4)
finish
Figure9.33 Activity-nodegraph
timepast10units.Ontheotherhand,activityBislesscriticalandcanbedelayedupto
twotimeunitswithoutaffectingtheﬁnalcompletiontime.
Toperformthesecalculations,weconverttheactivity-nodegraphtoanevent-node
graph.Eacheventcorrespondstothecompletionofanactivityandallitsdependentactiv-
ities.Eventsreachablefromanodevintheevent-nodegraphmaynotcommenceuntil
aftertheeventviscompleted.Thisgraphcanbeconstructedautomaticallyorbyhand.
Dummyedgesandnodesmayneedtobeinsertedinthecasewhereanactivitydependson
severalothers.Thisisnecessaryinordertoavoidintroducingfalsedependencies(orfalse
lackofdependencies).Theevent-nodegraphcorrespondingtothegraphinFigure9.33is
showninFigure9.34.
Toﬁndtheearliestcompletiontimeoftheproject,wemerelyneedtoﬁndthelengthof
thelongestpathfromtheﬁrsteventtothelastevent.Forgeneralgraphs,thelongest-path
problemgenerallydoesnotmakesense,becauseofthepossibilityofpositive-costcycles.
Thesearetheequivalentofnegative-costcyclesinshortest-pathproblems.Ifpositive-cost
1
2
3
6'
6
4
5
7'
7
8'
8
9
10'
10
A/3
B/2
C/3
0
0
D/2
0
0
0
0
E/1
F/3
G/2
K/4
0
0
0
H/1
Figure9.34 Event-nodegraph
Export pdf to powerpoint - C# Create PDF from PowerPoint Library to convert pptx, ppt to PDF in C#.net, ASP.NET MVC, WinForms, WPF
Online C# Tutorial for Creating PDF from Microsoft PowerPoint Presentation
convert pdf to powerpoint slides; how to convert pdf to ppt online
Export pdf to powerpoint - VB.NET Create PDF from PowerPoint Library to convert pptx, ppt to PDF in vb.net, ASP.NET MVC, WinForms, WPF
VB.NET Tutorial for Export PDF file from Microsoft Office PowerPoint
create powerpoint from pdf; picture from pdf to powerpoint
9.3 Shortest-PathAlgorithms
403
completiontimeforallnodesinthegraph.IfEC
i
istheearliestcompletiontimefornode
i,thentheapplicablerulesare
EC
1
=0
EC
w
= max
(v,w)∈E
(EC
v
+c
v,w
)
Figure9.35showstheearliestcompletiontimeforeacheventinourexampleevent-node
graph.
Wecanalsocomputethelatesttime,LC
i
,thateacheventcanﬁnishwithoutaffecting
theﬁnalcompletiontime.Theformulastodothisare
LC
n
=EC
n
LC
v
= min
(v,w)∈E
(LC
w
c
v,w
)
Thesevaluescanbecomputedinlineartimebymaintaining,foreachvertex,alistofall
theirtopologicalorder,andthelatestcompletiontimesarecomputedbyreversetopological
order.ThelatestcompletiontimesareshowninFigure9.36.
Theslacktimeforeachedgeintheevent-nodegraphrepresentstheamountoftime
thatthecompletionofthecorresponding activitycanbedelayed without delaying the
overallcompletion.Itiseasytoseethat
Slack
(v,w)
=LC
w
EC
v
c
v,w
1
2
3
6'
6
4
5
7'
7
8'
8
9
10'
10
A/3
B/2
C/3
0
0
D/2
0
0
0
0
E/1
F/3
G/2
K/4
0
0
0
H/1
0
3
2
3
5
6
3
6
9
5
7
7
9
10
Figure9.35 Earliestcompletiontimes
1
2
3
6'
6
4
5
7'
7
8'
8
9
10'
10
A/3
B/2
C/3
0
0
D/2
0
0
0
0
E/1
F/3
G/2
K/4
0
0
0
H/1
0
3
4
4
6
6
5
6
9
7
9
9
9
10
Figure9.36 Latestcompletiontimes
Online Convert PowerPoint to PDF file. Best free online export
Online Powerpoint to PDF Converter. Download Free Trial. Then just wait until the conversion from Powerpoint to PDF is complete and download the file.
converting pdf to ppt; how to convert pdf to powerpoint
C# WPF PDF Viewer SDK to convert and export PDF document to other
Viewer & Editor. WPF: View PDF. WPF: Annotate PDF. WPF: Export PDF. WPF: Print PDF. PDF Create. Create PDF from Word. Create PDF from Excel. Create PDF from PowerPoint
conversion of pdf to ppt online; how to convert pdf to ppt using
404
Chapter9 GraphAlgorithms
1
2
3
6'
6
4
5
7'
7
8'
8
9
10'
10
A/3/0
B/2/2
C/3/0
D/2/1
E/1/2
F/3/0
G/2/2
K/4/2
H/1/0
0
3
2
3
5
6
3
6
9
5
7
7
9
10
0
3
4
4
6
6
5
6
9
7
9
9
9
10
Figure9.37 Earliestcompletiontime,latestcompletiontime,andslack
Figure9.37showstheslack(asthethirdentry)foreachactivityintheevent-nodegraph.
Foreachnode,thetopnumberistheearliestcompletiontimeandthebottomentryisthe
latestcompletiontime.
Someactivitieshavezeroslack.Thesearecriticalactivities,whichmustﬁnishonsched-
ule.Thereisatleastonepathconsistingentirelyofzero-slackedges;suchapathisacritical
path.
Sometimesitisimportanttoﬁndtheshortestpathsbetweenallpairsofverticesinthe
graph.Althoughwecouldjustruntheappropriatesingle-sourcealgorithm|V|times,we
theinformationatonce.
InChapter10,wewillseeanO(|V|
3
)algorithmtosolvethisproblemforweighted
graphs.Although,fordensegraphs,thisisthesameboundasrunningasimple(non-
priorityqueue)Dijkstra’salgorithm|V|times,theloopsaresotightthatthespecialized
all-pairsalgorithmislikelytobefasterinpractice.Onsparsegraphs,ofcourse,itisfaster
torun|V|Dijkstra’salgorithmscodedwithpriorityqueues.
9.3.6 ShortestPathExample
InthissectionwewritesomeC
++
canconvert
zero
to
five
byasequenceofone-charactersubstitutionsasfollows:
zero hero
here hire fire five
.
Thisisanunweightedshortestprobleminwhicheachwordisavertex,andtwover-
ticeshaveedges(inbothdirections)betweenthemiftheycanbeconvertedtoeachother
withaone-charactersubstitution.
In Section4.8,wedescribed and wroteaC
++
routinethat would create a
map
in
whichthekeysarewords,andthevaluesare
vector
scontainingthewordsthatcanresult
fromaone-charactertransformation.Assuch,this
map
listformat,andweonlyneedtowriteoneroutinetorunthesingle-sourceunweighted
shortest-pathalgorithmandasecondroutinetooutputthesequenceofwords,afterthe
VB.NET PDF - Convert PDF with VB.NET WPF PDF Viewer
PDF in WPF. Annotate PDF in WPF. Export PDF in WPF. Print PDF in WPF. PDF Create. Create PDF from Word. Create PDF from Excel. Create PDF from PowerPoint. Create
converter pdf to powerpoint; add pdf to powerpoint
VB.NET PDF Converter Library SDK to convert PDF to other file
PDF Export. |. Home ›› XDoc.PDF ›› VB.NET PDF: PDF Export. for converting MicroSoft Office Word, Excel and PowerPoint document to PDF file in VB
convert pdf to editable powerpoint online; convert pdf to editable ppt online
1
// Runs the e shortest t path calculation from the e adjacency map, returning a a vector
2
// that contains s the e sequence of word changes to get from first to o second.
3
unordered_map<string,string>
4
findChain( const t unordered_map<string,vector<string>> > & adjacentWords,
5
const string g & first, const string & second )
6
{
7
unordered_map<string,string> previousWord;
8
queue<string> q;
9
10
q.push( first t );
11
12
while( !q.empty( ) )
13
{
14
string current = q.front( ); ; q.pop( ( );
15
auto itr r = = adjacentWords.find( current t );
16
17
const vector<string> & adj = = itr->second;
18
for( string & & str r : adj j )
19
if( previousWord[ str ] == "" " )
20
{
21
previousWord[ str ] = current;
22
q.push( str );
23
}
24
}
25
previousWord[ first ] = "";
26
27
return previousWord;
28
}
29
30
// After the shortest t path calculation n has run, computes s the e vector that
31
// contains s the e sequence of words changes s to o get from first to second.
32
vector<string> getChainFromPreviousMap(
33
const unordered_map<string,string> & previous, const t string g & second )
34
{
35
vector<string> result;
36
auto & prev = const_cast<unordered_map<string,string> &>( ( previous s );
37
38
for( string current = second; current t != = ""; current t = = prev[ current ] )
39
result.push_back( current );
40
41
reverse( begin( result t ), , end( result t ) ) );
42
return result;
43
}
Figure9.38 C
++
C# PDF Converter Library SDK to convert PDF to other file formats
PDF Export. |. Home ›› XDoc.PDF ›› C# PDF: PDF Export. Able to export PDF document to HTML file. Able to create convert PDF to SVG file.
adding pdf to powerpoint; conversion of pdf into ppt
C# HTML5 PDF Viewer SDK to convert and export PDF document to
Export PDF in WPF. Print PDF in WPF. PDF Create. Create PDF from Word. Create PDF from Excel. Create PDF from PowerPoint. Create PDF from Tiff. Create PDF from
online pdf converter to powerpoint; pdf to powerpoint conversion
406
Chapter9 GraphAlgorithms
single-sourceshortest-pathalgorithmhascompleted.Thesetworoutinesarebothshown
inFigure9.38.
Theﬁrstroutineis
findChain
,whichtakesthe
map
thetwowordstobeconnectedandreturnsa
map
inwhichthekeysarewords,andthe
first
.
Inotherwords,intheexampleabove,ifthestartingwordis
zero
,thevalueforkey
five
is
fire
,thevalueforkey
fire
is
hire
,thevalueforkey
hire
is
here
,andsoon.Clearlythis
providesenoughinformationforthesecondroutine,
getChainFromPreviousMap
,whichcan
workitswaybackward.
findChain
plicity,itassumesthat
first
isakeyin
(thisiseasilytestedpriortothecall,
ﬁed).Thebasicloopincorrectlyassignsapreviousentryfor
first
(whentheinitialword
first
isprocessed)soatline25thatentryisrepaired.
getChainFromPrevMap
usesthe
prev
mapand
second
,whichpresumablyisakeyinthe
map
through
prev
.Thisgeneratesthewordsbackward,sotheSTL
reverse
algorithmisusedto
ﬁxtheproblem.Thecastatline36isneededbecause
operator[]
cannotbeappliedonan
immutable
map
.
Itispossibletogeneralizethisproblemtoallow single-charactersubstitutionsthat
listrequiresonlyalittlemoreeffort:InthelastalgorithminSection4.8,every timea
representativeforwordwingroupgiscomputed,wecheckiftherepresentativeisaword
possibletoassignacosttoacharacterdeletionorinsertion(thatishigherthanasimple
substitution),andthisyieldsaweightedshortest-pathproblemthatcanbesolvedwith
Dijkstra’salgorithm.
9.4 NetworkFlowProblems
Suppose we are given a directed graph = (V,E) with edge capacities c
v,w
. These
capacitiescould representtheamount ofwaterthat could ﬂow througha pipeorthe
amountoftrafﬁcthatcould ﬂow on astreetbetween twointersections.Wehavetwo
vertices:s,whichwecallthesource,andt,whichisthesink.Throughanyedge,(v,w),
atmostc
v,w
unitsof“ﬂow”maypass.Atanyvertex,v,thatisnoteithersort,thetotal
ﬂowcominginmustequalthetotalﬂowgoingout.Themaximum-ﬂow problemisto
determinethemaximumamountofﬂowthatcanpassfromstot.Asanexample,forthe
graphinFigure9.39ontheleftthemaximumﬂowis5,asindicatedbythegraphonthe
right.Althoughthisexamplegraphisacyclic,thisisnotarequirement;our(eventual)
algorithmwillworkevenifthegraphhasacycle.
Asrequiredbytheproblemstatement,noedgecarriesmoreﬂowthanitscapacity.
Vertexahasthreeunitsofﬂowcomingin,whichitdistributestocandd.Vertexdtakes
threeunitsofﬂowfromaandbandcombinesthis,sendingtheresulttot.Avertexcan
C# WPF PDF Viewer SDK to view, annotate, convert and print PDF in
Export PDF in WPF. Print PDF in WPF. PDF Create. Create PDF from Word. Create PDF from Excel. Create PDF from PowerPoint. Create PDF from Tiff. Create PDF from
pdf to powerpoint converter; convert pdf to powerpoint
VB.NET PDF- HTML5 PDF Viewer for VB.NET Project
PDF in WPF. Annotate PDF in WPF. Export PDF in WPF. Print PDF in WPF. PDF Create. Create PDF from Word. Create PDF from Excel. Create PDF from PowerPoint. Create
pdf to ppt; how to convert pdf to ppt
9.4 NetworkFlowProblems
407
s
a
b
c
d
t
s
a
b
c
d
t
4
2
1
2
2
4
3
3
3
2
2
2
1
2
3
0
Figure9.39 Agraph(left)anditsmaximumﬂow
combineanddistributeﬂowinanymannerthatitlikes,aslongasedgecapacitiesarenot
violatedandaslongasﬂowconservationismaintained(whatgoesinmustcomeout).
Lookingatthegraph,weseethatshasedgesofcapacities4and2leavingit,andthas
of5.However,Figure9.40showshowwecanprovethatthemaximumﬂow is5.We
cutthegraphintotwoparts;onepartcontainssandsomeothervertices;theotherpart
containst.Sinceﬂowmustcrossthroughthecut,thetotalcapacityofalledges(u,v)where
uisins’spartitionandvisint’spartitionisaboundonthemaximumﬂow.Theseedgesare
(a,c)and(d,t),withtotalcapacity5,sothemaximumﬂowcannotexceed5.Anygraph
hasalargenumberofcuts;thecutwithminimumtotalcapacityprovidesaboundonthe
maximumﬂow,andasitturnsout(butitisnotimmediatelyobvious),theminimumcut
capacityisexactlyequaltothemaximumﬂow.
s
a
b
c
d
t
4
2
1
2
2
4
3
3
Figure9.40 AcutingraphGpartitionstheverticeswithsandtindifferentgroups.The
totaledgecostacrossthecutis5,provingthataﬂowof5ismaximum.
408
Chapter9 GraphAlgorithms
9.4.1 ASimpleMaximum-FlowAlgorithm
Aﬁrstattempttosolvetheproblemproceedsinstages.Westartwithourgraph,G,and
construct aﬂow graph G
f
.G
f
tells theﬂow thathasbeenattainedatanystageinthe
algorithm.InitiallyalledgesinG
f
havenoﬂow,andwehopethatwhenthealgorithm
terminates,G
f
containsamaximumﬂow.Wealsoconstructagraph,G
r
,calledtheresidual
graph.G
r
bysubtractingthecurrentﬂowfromthecapacityforeachedge.AnedgeinG
r
isknownas
aresidualedge.
Ateachstage,weﬁndapathinG
r
fromstot.Thispathisknownasanaugmenting
f
andrecomputingG
r
.Whenweﬁndnopath
fromstotinG
r
,weterminate.Thisalgorithmisnondeterministic,inthatwearefreeto
chooseanypathfromstot;obviouslysomechoicesarebetterthanothers,andwewill
G,G
f
,G
r
,respectively.Keepinmindthatthereisaslightﬂawinthisalgorithm.Theinitial
conﬁgurationisinFigure9.41.
Therearemanypathsfromstotintheresidualgraph.Supposeweselects,b,d,t.
conventionthatoncewehaveﬁlled(saturated)anedge,itisremovedfromtheresidual
graph.WethenobtainFigure9.42.
Next,wemightselectthepaths,a,c,t,whichalsoallowstwounitsofﬂow.Makingthe
Theonlypathlefttoselectiss,a,d,t,whichallowsoneunitofﬂow.Theresulting
graphsareshowninFigure9.44.
Thealgorithmterminatesatthispoint,becausetisunreachablefroms.Theresulting
ﬂowof5happenstobethemaximum.Toseewhattheproblemis,supposethatwith
ourinitialgraph,wechosethepaths,a,d,t.Thispathallowsthreeunitsofﬂowandthus
seemstobeagoodchoice.Theresultofthischoice,however,leavesonlyonepathfrom
stotintheresidualgraph;itallowsonemoreunitofﬂow,andthus,ouralgorithmhas
s
a
b
c
d
t
s
a
b
c
d
t
s
a
b
c
d
t
4
2
1
2
2
4
3
3
4
1
2
2
3
4
2
3
0
0
0
0
0
0
0
0
Figure9.41 Initialstagesofthegraph,ﬂowgraph,andresidualgraph
s
a
b
c
d
t
s
a
b
c
d
t
s
a
b
c
d
t
4
2
1
2
2
4
3
3
4
1
2
3
4
1
0
2
0
0
2
0
0
2
Figure9.42 G,G
f
,G
r
s
a
b
c
d
t
s
a
b
c
d
t
s
a
b
c
d
t
4
2
1
2
2
4
3
3
2
1
4
1
1
2
2
0
2
2
0
2
2
Figure9.43 G,G
f
,G
r
s
a
b
c
d
t
s
a
b
c
d
t
s
a
b
c
d
t
4
2
1
2
2
4
3
3
1
1
3
1
3
2
0
2
2
1
2
3
Figure9.44 G,G
f
,G
r
410
Chapter9 GraphAlgorithms
s
a
b
c
d
t
s
a
b
c
d
t
s
a
b
c
d
t
4
2
1
2
2
4
3
3
1
1
2
2
1
3
2
3
0
0
0
0
3
0
3
Figure9.45 GG
f
G
r
if initial action is s to o add d three e units of ﬂow w along s,a,d,
t—algorithmterminatesafteronemorestepwithsuboptimalsolution
failedtoﬁndanoptimalsolution.Thisisanexampleofagreedyalgorithmthatdoesnot
work.Figure9.45showswhythealgorithmfails.
Inordertomakethisalgorithmwork,weneedtoallowthealgorithmtochangeits
mind.Todothis,foreveryedge(v,w)withﬂowf
v,w
intheresidualgraph(w,v)ofcapacityf
v,w
.Ineffect,weareallowingthealgorithmtoundo
itsdecisionsbysendingﬂowbackintheoppositedirection.Thisisbestseenbyexample.
Startingfromouroriginalgraphandselectingtheaugmentingpaths,a,d,t,weobtainthe
graphsinFigure9.46.
Noticethatintheresidualgraph,thereareedgesinbothdirectionsbetweenaandd.
Eitheronemoreunitofﬂowcanbepushedfromatod,oruptothreeunitscanbepushed
back—wecanundoﬂow.Nowthealgorithmﬁndstheaugmentingpaths,b,d,a,c,t,of
ﬂow2.Bypushingtwounitsofﬂowfromdtoa,thealgorithmtakestwounitsofﬂow
awayfromtheedge(a,d)andisessentiallychangingitsmind.Figure9.47showsthenew
graphs.
s
a
b
c
d
t
s
a
b
c
d
t
s
a
b
c
d
t
4
2
1
2
2
4
3
3
3
1
1
2
2
3
1
3
3
2
3
0
0
0
0
3
0
3