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
twotimeunitswithoutaffectingthefinalcompletiontime.
Toperformthesecalculations,weconverttheactivity-nodegraphtoanevent-node
graph.Eacheventcorrespondstothecompletionofanactivityandallitsdependentactiv-
ities.Eventsreachablefromanodevintheevent-nodegraphmaynotcommenceuntil
aftertheeventviscompleted.Thisgraphcanbeconstructedautomaticallyorbyhand.
Dummyedgesandnodesmayneedtobeinsertedinthecasewhereanactivitydependson
severalothers.Thisisnecessaryinordertoavoidintroducingfalsedependencies(orfalse
lackofdependencies).Theevent-nodegraphcorrespondingtothegraphinFigure9.33is
showninFigure9.34.
Tofindtheearliestcompletiontimeoftheproject,wemerelyneedtofindthelengthof
thelongestpathfromthefirsteventtothelastevent.Forgeneralgraphs,thelongest-path
problemgenerallydoesnotmakesense,becauseofthepossibilityofpositive-costcycles.
Thesearetheequivalentofnegative-costcyclesinshortest-pathproblems.Ifpositive-cost
cyclesarepresent,wecouldaskforthelongestsimplepath,butnosatisfactorysolutionis
knownforthisproblem.Sincetheevent-nodegraphisacyclic,weneednotworryabout
cycles.Inthiscase,itiseasytoadapttheshortest-pathalgorithmtocomputetheearliest
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
,thateacheventcanfinishwithoutaffecting
thefinalcompletiontime.Theformulastodothisare
LC
n
=EC
n
LC
v
= min
(v,w)∈E
(LC
w
c
v,w
)
Thesevaluescanbecomputedinlineartimebymaintaining,foreachvertex,alistofall
adjacentandprecedingvertices.Theearliestcompletiontimesarecomputedforverticesby
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,whichmustfinishonsched-
ule.Thereisatleastonepathconsistingentirelyofzero-slackedges;suchapathisacritical
path.
9.3.5 All-PairsShortestPath
Sometimesitisimportanttofindtheshortestpathsbetweenallpairsofverticesinthe
graph.Althoughwecouldjustruntheappropriatesingle-sourcealgorithm|V|times,we
mightexpectasomewhatfastersolution,especiallyonadensegraph,ifwecomputeall
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
++
routinestocomputewordladders.Inawordladdereach
wordisformedbychangingonecharacterintheladder’spreviousword.Forinstance,we
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
representsthegraph,inadjacency
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
++
codetofindwordladders
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.
Thefirstroutineis
findChain
,whichtakesthe
map
representingtheadjacencylistsand
thetwowordstobeconnectedandreturnsa
map
inwhichthekeysarewords,andthe
correspondingvalueisthewordpriortothekeyontheshortestladderstartingat
first
.
Inotherwords,intheexampleabove,ifthestartingwordis
zero
,thevalueforkey
five
is
fire
,thevalueforkey
fire
is
hire
,thevalueforkey
hire
is
here
,andsoon.Clearlythis
providesenoughinformationforthesecondroutine,
getChainFromPreviousMap
,whichcan
workitswaybackward.
findChain
isadirectimplementationofthepseudocodeinFigure9.18,andforsim-
plicity,itassumesthat
first
isakeyin
adjacentWords
(thisiseasilytestedpriortothecall,
orwecanaddextracodeatline16thatthrowsanexceptionifthisconditionisnotsatis-
fied).Thebasicloopincorrectlyassignsapreviousentryfor
first
(whentheinitialword
adjacentto
first
isprocessed)soatline25thatentryisrepaired.
getChainFromPrevMap
usesthe
prev
mapand
second
,whichpresumablyisakeyinthe
map
andreturnsthewordsusedtoformthewordladderbyworkingitswaybackward
through
prev
.Thisgeneratesthewordsbackward,sotheSTL
reverse
algorithmisusedto
fixtheproblem.Thecastatline36isneededbecause
operator[]
cannotbeappliedonan
immutable
map
.
Itispossibletogeneralizethisproblemtoallow single-charactersubstitutionsthat
includethedeletionofacharacterortheadditionofacharacter.Tocomputetheadjacency
listrequiresonlyalittlemoreeffort:InthelastalgorithminSection4.8,every timea
representativeforwordwingroupgiscomputed,wecheckiftherepresentativeisaword
ingroupg−1.Ifitis,thentherepresentativeisadjacentto(itisasingle-character
deletion),andwisadjacenttotherepresentative(itisasingle-characteraddition).Itisalso
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 flow througha pipeorthe
amountoftrafficthatcould flow on astreetbetween twointersections.Wehavetwo
vertices:s,whichwecallthesource,andt,whichisthesink.Throughanyedge,(v,w),
atmostc
v,w
unitsof“flow”maypass.Atanyvertex,v,thatisnoteithersort,thetotal
flowcominginmustequalthetotalflowgoingout.Themaximum-flow problemisto
determinethemaximumamountofflowthatcanpassfromstot.Asanexample,forthe
graphinFigure9.39ontheleftthemaximumflowis5,asindicatedbythegraphonthe
right.Althoughthisexamplegraphisacyclic,thisisnotarequirement;our(eventual)
algorithmwillworkevenifthegraphhasacycle.
Asrequiredbytheproblemstatement,noedgecarriesmoreflowthanitscapacity.
Vertexahasthreeunitsofflowcomingin,whichitdistributestocandd.Vertexdtakes
threeunitsofflowfromaandbandcombinesthis,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)anditsmaximumflow
combineanddistributeflowinanymannerthatitlikes,aslongasedgecapacitiesarenot
violatedandaslongasflowconservationismaintained(whatgoesinmustcomeout).
Lookingatthegraph,weseethatshasedgesofcapacities4and2leavingit,andthas
edgesofcapacities3and3enteringit.Soperhapsthemaximumflowcouldbe6instead
of5.However,Figure9.40showshowwecanprovethatthemaximumflow is5.We
cutthegraphintotwoparts;onepartcontainssandsomeothervertices;theotherpart
containst.Sinceflowmustcrossthroughthecut,thetotalcapacityofalledges(u,v)where
uisins’spartitionandvisint’spartitionisaboundonthemaximumflow.Theseedgesare
(a,c)and(d,t),withtotalcapacity5,sothemaximumflowcannotexceed5.Anygraph
hasalargenumberofcuts;thecutwithminimumtotalcapacityprovidesaboundonthe
maximumflow,andasitturnsout(butitisnotimmediatelyobvious),theminimumcut
capacityisexactlyequaltothemaximumflow.
s
a
b
c
d
t
4
2
1
2
2
4
3
3
Figure9.40 AcutingraphGpartitionstheverticeswithsandtindifferentgroups.The
totaledgecostacrossthecutis5,provingthataflowof5ismaximum.
408
Chapter9 GraphAlgorithms
9.4.1 ASimpleMaximum-FlowAlgorithm
Afirstattempttosolvetheproblemproceedsinstages.Westartwithourgraph,G,and
construct aflow graph G
f
.G
f
tells theflow thathasbeenattainedatanystageinthe
algorithm.InitiallyalledgesinG
f
havenoflow,andwehopethatwhenthealgorithm
terminates,G
f
containsamaximumflow.Wealsoconstructagraph,G
r
,calledtheresidual
graph.G
r
tells,foreachedge,howmuchmoreflowcanbeadded.Wecancalculatethis
bysubtractingthecurrentflowfromthecapacityforeachedge.AnedgeinG
r
isknownas
aresidualedge.
Ateachstage,wefindapathinG
r
fromstot.Thispathisknownasanaugmenting
path.Theminimumedgeonthispathistheamountofflowthatcanbeaddedtoevery
edgeonthepath.WedothisbyadjustingG
f
andrecomputingG
r
.Whenwefindnopath
fromstotinG
r
,weterminate.Thisalgorithmisnondeterministic,inthatwearefreeto
chooseanypathfromstot;obviouslysomechoicesarebetterthanothers,andwewill
addressthisissuelater.Wewillrunthisalgorithmonourexample.Thegraphsbeloware
G,G
f
,G
r
,respectively.Keepinmindthatthereisaslightflawinthisalgorithm.Theinitial
configurationisinFigure9.41.
Therearemanypathsfromstotintheresidualgraph.Supposeweselects,b,d,t.
Thenwecansendtwounitsofflowthrougheveryedgeonthispath.Wewilladoptthe
conventionthatoncewehavefilled(saturated)anedge,itisremovedfromtheresidual
graph.WethenobtainFigure9.42.
Next,wemightselectthepaths,a,c,t,whichalsoallowstwounitsofflow.Makingthe
requiredadjustmentsgivesthegraphsinFigure9.43.
Theonlypathlefttoselectiss,a,d,t,whichallowsoneunitofflow.Theresulting
graphsareshowninFigure9.44.
Thealgorithmterminatesatthispoint,becausetisunreachablefroms.Theresulting
flowof5happenstobethemaximum.Toseewhattheproblemis,supposethatwith
ourinitialgraph,wechosethepaths,a,d,t.Thispathallowsthreeunitsofflowandthus
seemstobeagoodchoice.Theresultofthischoice,however,leavesonlyonepathfrom
stotintheresidualgraph;itallowsonemoreunitofflow,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,flowgraph,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
aftertwounitsofflowaddedalongs,b,d,t
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
aftertwounitsofflowaddedalongs,a,c,t
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
afteroneunitofflowaddedalongs,a,d,t—algorithmterminates
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 flow w along s,a,d,
t—algorithmterminatesafteronemorestepwithsuboptimalsolution
failedtofindanoptimalsolution.Thisisanexampleofagreedyalgorithmthatdoesnot
work.Figure9.45showswhythealgorithmfails.
Inordertomakethisalgorithmwork,weneedtoallowthealgorithmtochangeits
mind.Todothis,foreveryedge(v,w)withflowf
v,w
intheflowgraph,wewilladdanedge
intheresidualgraph(w,v)ofcapacityf
v,w
.Ineffect,weareallowingthealgorithmtoundo
itsdecisionsbysendingflowbackintheoppositedirection.Thisisbestseenbyexample.
Startingfromouroriginalgraphandselectingtheaugmentingpaths,a,d,t,weobtainthe
graphsinFigure9.46.
Noticethatintheresidualgraph,thereareedgesinbothdirectionsbetweenaandd.
Eitheronemoreunitofflowcanbepushedfromatod,oruptothreeunitscanbepushed
back—wecanundoflow.Nowthealgorithmfindstheaugmentingpaths,b,d,a,c,t,of
flow2.Bypushingtwounitsofflowfromdtoa,thealgorithmtakestwounitsofflow
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
Figure9.46 Graphsafterthreeunitsofflowaddedalongs,a,d,tusingcorrectalgorithm
9.4 NetworkFlowProblems
411
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
2
2
2
1
3
1
3
2
3
2
0
2
2
1
2
3
1
Figure9.47 Graphs after two units of flow added along s,b,d,a,c,using correct
algorithm
Thereisnoaugmentingpathinthisgraph,sothealgorithmterminates.Notethatthe
sameresultwouldoccurifatFigure9.46,theaugmentingpaths,a,c,twaschosenwhich
allowsoneunitofflow,becausethenasubsequentaugmentingpathcouldbefound.
Itiseasytoseethatifthealgorithmterminates,thenitmustterminatewithamaximum
flow.Terminationimpliesthatthereisnopathfromstotintheresidualgraph.Socutthe
residualgraph,puttingtheverticesreachablefromson onesideandtheunreachables
(whichincludet)ontheotherside.Figure9.48showsthecut.Clearlyanyedgesinthe
originalgraphGthatcrossthecutmustbesaturated;otherwise,therewouldberesidual
flowremainingononeoftheedges,whichwouldthenimplyanedgethatcrossesthecut
(inthewrongdisalloweddirection)inG
r
.ButthatmeansthattheflowinGisexactlyequal
tothecapacityofacutinG;hence,wehaveamaximumflow.
Iftheedgecostsinthegraphareintegers,thenthealgorithmmustterminate;each
augmentationaddsaunitofflow,soweeventuallyreachthemaximumflow,thoughthere
s
a
b
c
d
t
s
a
b
c
d
t
3
1
2
2
2
1
3
1
3
2
1
3
2
0
2
2
1
2
3
Figure9.48 Theverticesreachablefromsintheresidualgraphformonesideofacut;
theunreachablesformtheothersideofthecut
Documents you may be interested
Documents you may be interested