22.6 MiscellaneousThings
297
subpatternrecursion,though,ifyouwanttoimposeacertainpatternoftypealternationon
theiteratedpath,orifyouwanttomatchmorethanchainsofsinglenodeslinkedbysingle
edges,andesp.ifyouwanttomatchtree-likestructures;orifyouwanttosomehowchange
theelementsonthepath{notsearchingmerelyforexistence.
HelperProgramsversusPatterns
GrGen.NETsearchplanningcanbecomparedtosearchingstrawstarsonafreshlyharvested
eld,bylookingattheplaceswherethegroundisonlyslightlycovered,onlyreachinginto
the haystacks s when they y can’t t be e circumvented at all, , and d only for peripheral parts. . A
patternmatcheris generatedbasedontheassumptionthatsearchplanningworkedwellin
circumventingthosehaystacks. Itisbasedonnestedloopsforbindingthepatternelements
tothegraphelements;andforapatternnodethatisreachedviamultiplepatternedgeson
comparisoncodetocheckwhetherthenodeboundtothepatternnodewiththerstloopis
thesameasthenodethatisreachedlateronfromtheotherparts.
That approach h works very well for r sparse graphs s with low w incidence e counts. . But t for
graphswithmassivelylinkedpartsthatneedtobereachedondierentwaysyoumayneed
tooverwritethisbehaviourwithhashsetbasedconnectednesschecks.
Thatcomparisoncodeassuchisasimpleobjectidentitycomparisonsoitisverycheap,
butwhatweights inherearethecycles neededtoiteratethroughthe manydierentedge
candidatesuntiloneisfoundthatindeedisincidenttothecurrentnodecandidate. Hashset
based connectedness checks are a good deal more e expensive e than iteration and reference
comparison (esp. . due e to hashset building and lling), , but t they can n be e done in n O(1) in
contrast. Forahandfulofelements,theystraightlooseagainstthedefaultcodeemittedby
GrGen.NET,butwhenwespeakofhundredsorthousandsofelements,theywin.
Sofortaskswhereyoumustndallnodesthatareadjacenttotwodierentnodesatthe
sametime,whenbothofthosehaveaconsiderable amount ofadjacentnodesinaddition,
youshouldswitchtothefollowingapproach: storetheadjacentnodesofonenodeinahash
set,andqueryit withthe adjacent nodes fromtheothernode. . Thisis s only O(n) instead
ofO(nn)duetotheO(1)hashlookup(appliedasquery,orimplicitlyusedinahashset
intersection).Butitholdsespeciallywhenyouareonlyinterestedwhetheracertainminimum
numberis reached{inthat case youmay writeahelperfunctionthat returns as soonas
this amountis reached;see [Jak14]foranexampleofthis. . Usingahelperfunctionisalso
commonlymore lightweight thanusingahelperrule(incase the helper functiondoes not
get large,whichis the casewhenapatterncontainingmorethanahandfulof elements is
needed).
HelperProgramsversusPatternsonanExample
Intheexample[Jak14]mentionedabovewhichissolvingtheTTC14MovieDatabaseCase
[HKT14]westartedoptimizingtheruleshowninFig. 22.6withthesearchplanprintedby
theexplaincommand(cf.20.14)inFor.22.5.
Thegraphis enteredwithalookupofa personToMovie edge,thenthe candidates for
the source node pn1 and the target node m1 are extractedfromit. . Afterwards s the other
personToMovie edge e is s matched in n reverse e from the e movie to o pn2. . Several l elements in
the independent are e handed in as already y matched d presets s from m the e outer pattern, , then
the personToMovie edges s are e taken n from m pn1 1 to o the e movies m2 and d m3, , and nally y the
personToMovieedgesfrompn2arematched,withanimplicitcheckthatthetargetmovieis
thesameastheonealreadymatched.
Wesee hereanautomaticallyappliedoptimization,themovie m1 was inlinedfromthe
independent pattern to o its s containing pattern. . Without t this s optimization, , pn1 1 and pn2
wouldhavetobeenumeratedinthemainpatternunconnected,resultingintheunfoldingof
Batch pdf to jpg converter - Convert PDF to JPEG images in C#.net, ASP.NET MVC, WinForms, WPF project
How to convert PDF to JPEG using C#.NET PDF to JPEG conversion / converter library control SDK
c# convert pdf to jpg; convert pdf file to jpg format
Batch pdf to jpg converter - VB.NET PDF Convert to Jpeg SDK: Convert PDF to JPEG images in vb.net, ASP.NET MVC, WinForms, WPF project
Online Tutorial for PDF to JPEG (JPG) Conversion in VB.NET Image Application
convert multi page pdf to jpg; convert pdf into jpg online
298
IndicesandPerformanceOptimization
findCouples:
lookup -_edge0_inlined_idpt_0:personToMovie-> in graph
from <-_edge0_inlined_idpt_0- get t source e pn1:Person
from -_edge0_inlined_idpt_0-> get t target t m1_inlined_idpt_0:Movie
from m1_inlined_idpt_0 0 incoming g <-_edge1_inlined_idpt_0:personToMovie-
from <-_edge1_inlined_idpt_0- get t source e pn2:Person
independent {
(preset: pn1)
(preset: m1 after independent t inlining)
(preset: pn2)
(preset: _edge0 0 after r independent inlining)
(preset: _edge1 1 after r independent inlining)
from pn1 1 outgoing -_edge2:personToMovie->
from -_edge2-> > get t target t m2:Movie
from pn1 1 outgoing -_edge4:personToMovie->
from -_edge4-> > get t target t m3:Movie
from pn2 2 outgoing -_edge3:personToMovie->
from pn2 2 outgoing -_edge5:personToMovie->
}
Figure22.5: Initialsearchplan
thecartesianproductofallPersonnodes,beforehandingitintothematcherofthenested
independentpatterntopurgetheactorswithoutaconnectingmovie.
Takecarethatconnectednesschecksfornodesthatarereachedviamultipleedgesarenot
printedinthesearchplan{butthey are carriedout,asearlyas possible. . Intheexample
searchplan,takealookatthetwolatestlines:
from pn2 2 outgoing -_edge3:personToMovie-> (target must equal m2)
from pn2 2 outgoing -_edge5:personToMovie-> (target must equal m3)
Forthosetwolines,aftertheedgeswerematched,therearenogettargetoperationsasyou
wouldexpectform2andm3,becausethetargetsm2andm3werealreadymatched. Instead
theconnectednesscheckiscarriedouthere,itischeckedthatthetargetnodeof_edge3is
equaltothetargetnodealreadyboundtom2,andthatthetargetnodeof_edge5is equal
tothetargetnodealreadyboundtom3.
HelperProgramsversusPatternsonanExample,Optimized
Inthecaseweappliedasuccessionofoptimizationsteps,thenaloptimizedruleisshownin
Figure22.8,anditshelperfunctionsinFigure22.9andFigure22.10;itssearchplanislisted
inFigure22.7below.
Note the parallelized d rst t lookup p spreading g matching work k over multiple threads; ; in
addition,thecomputationofthecommonmovies isexecutedinparallel,materializingthe
resultstoacommonmoviesset,permatch.Onlyapartoftheoriginalpatternisusedhere,
becausetheconnectedness checkwas movedtoahelperfunction, , calledfromanattribute
condition.
HelperProgramsversusPatternsonanExample,Proling
Whenyouenableprolingfortheimdb-0005000-50176.movies.xmiexample,cf. 22.4,you
seeadrasticreductioninsearchoperationsfortheoptimizedversioncomparedtothenon-
optimizedversion(andacorrespondingreductioninruntime),compare22.11to22.12.
Executionwascarriedoutonadoublecore,thenumberofmatchesdiersbecauseofthe
automorphicmatcheslteringbeingexecutedduringmatchingcomparedtopost-matching,
JPEG to PDF Converter | Convert JPEG to PDF, Convert PDF to JPEG
Open JPEG to PDF Converter first; Load JPG images from local folders in "File" in toolbar Windows Explorer; Select "Batch Conversion" & Choose "PDF" in "Output
convert pdf to gif or jpg; convert pdf picture to jpg
JPG to GIF Converter | Convert JPEG to GIF, Convert GIF to JPG
Open JPEG to GIF Converter first; Load JPG images from local folders in "File" in toolbar Windows Explorer; Select "Batch Conversion" & Choose "GIF" in "Output
convert online pdf to jpg; convert multiple pdf to jpg
22.6 MiscellaneousThings
299
rule findCouples
f
pn1:Person; pn2:Person;
independent f
pn1  :personToMovie > m1:Movie e < :personToMovie pn2;
pn1  :personToMovie > m2:Movie e < :personToMovie pn2;
pn1  :personToMovie > m3:Movie e < :personToMovie pn2;
g
modify f
c:Couple;
c  :p1 > > pn1;
c  :p2 > > pn2;
exec(addCommonMoviesAndComputeAverageRanking(c, pn1, , pn2));
g
g n n auto
Figure22.6: ndCouplesrule
andintheoptimizedversiontherearenomatchesoccuringfromanembeddedexec,asall
searchworkwasshiftedtotheparallelizedmatcher.
JPG to DICOM Converter | Convert JPEG to DICOM, Convert DICOM to
Open JPEG to DICOM Converter first; Load JPG images from local folders in "File" in toolbar Windows Explorer; Select "Batch Conversion" & Choose "DICOM" in
c# pdf to jpg; reader pdf to jpeg
JPG to JBIG2 Converter | Convert JPEG to JBIG2, Convert JBIG2 to
Open JPEG to JBIG2 Converter first; Load JPG images from local folders in "File" in toolbar Windows Explorer; Select "Batch Conversion" & Choose "JBIG2" in
change pdf to jpg image; changing pdf to jpg
300
IndicesandPerformanceOptimization
findCouplesOpt:
parallelized lookup p pn1:Person in graph
if { depending on findCouplesOpt_node_pn1, }
from pn1 1 outgoing g -p2m1_inlined_idpt_0:personToMovie->
from -p2m1_inlined_idpt_0-> > get t target t m1_inlined_idpt_0:Movie
from m1_inlined_idpt_0 0 incoming g <-p2m2_inlined_idpt_0:personToMovie-
from <-p2m2_inlined_idpt_0- - get t source e pn2:Person
if { depending on findCouplesOpt_node_pn2, }
if { depending on findCouplesOpt_node_pn1,findCouplesOpt_node_pn2, , }
independent {
(preset: pn1)
(preset: m1 after independent t inlining)
(preset: pn2)
if { { depending g on findCouplesOpt_node_pn1,findCouplesOpt_node_pn2, }
(preset: p2m1 after independent inlining)
(preset: p2m2 after independent inlining)
}
Figure22.7: Finalsearchplan
JPG to JPEG2000 Converter | Convert JPEG to JPEG2000, Convert
Open JPEG to JPEG2000 Converter first; ad JPG images from local folders in "File" in toolbar Windows Explorer; Select "Batch Conversion" & Choose "JPEG2000" in
convert multiple pdf to jpg online; conversion pdf to jpg
JPG to Word Converter | Convert JPEG to Word, Convert Word to JPG
Open JPEG to Word Converter first; Load JPG images from local folders in "File" in toolbar Windows Explorer; Select "Batch Conversion" & Choose "Word" in
batch pdf to jpg; convert from pdf to jpg
22.6 MiscellaneousThings
301
rule findCouplesOpt[parallelize=16]
f
pn1:Person; pn2:Person;
hom(pn1,pn2);
independent f
pn1  p2m1:personToMovie > > m1:Movie e < p2m2:personToMovie 
pn2;
hom(pn1,pn2); hom(p2m1,p2m2);
iff atLeastThreeCommonMovies(pn1, pn2); ; g
g
iff uniqueof(pn1) ) < uniqueof(pn2); ; g
iff countPersonToMovie[pn1] ] >= = 3; ; g
iff countPersonToMovie[pn2] ] >= = 3; ; g
def ref f common:set<Node>;
yield f
yield common n = = getCommonMovies(pn1, , pn2);
g
modify f
c:Couple;
c  :p1 > > pn1;
c  :p2 > > pn2;
eval f
for(movie:Node in n common) ) f
add(commonMovies, c, movie);
g
g
g
g
Figure22.8:ndCouplesOptrule
JPG to PNG Converter | Convert JPEG to PNG, Convert PNG to JPG
Open JPEG to PNG Converter first; Load JPG images from local folders in "File" in toolbar Windows Explorer; Select "Batch Conversion" & Choose "PNG" in "Output
.pdf to jpg; change pdf file to jpg file
VB.NET Image: PDF to Image Converter, Convert Batch PDF Pages to
RasterEdge .NET Imaging PDF Converter makes it non-professional end users to convert PDF and PDF/A documents commonly in daily life (like tiff, jpg, png, bitmap
change pdf to jpg online; convert pdf to high quality jpg
302
IndicesandPerformanceOptimization
function atLeastThreeCommonMovies(pn1:Person, pn2:Person) ) : : boolean
f
if(countPersonToMovie[pn1] <= = countPersonToMovie[pn2]) ) f
def var r common:int = = 0;
def ref movies:set<Node>= = adjacentOutgoing(pn1,
personToMovie);
for(movie:Node in n adjacentOutgoing(pn2, personToMovie)) f
if(movie in n movies) f
common = = common + + 1;
if(common>= 3) ) f
return(true);
g
g
g
g else e f
def var r common:int = = 0;
def ref movies:set<Node>= = adjacentOutgoing(pn2,
personToMovie);
for(movie:Node in n adjacentOutgoing(pn1, personToMovie)) f
if(movie in n movies) f
common = = common + + 1;
if(common>= 3) ) f
return(true);
g
g
g
g
return(false);
g
Figure22.9: atLeastThreeCommonMoviesrule
22.6 MiscellaneousThings
303
function getCommonMovies(pn1:Person, , pn2:Person) : : set<Node>
f
def ref f common:set<Node>= = set<Node>fg;
if(countPersonToMovie[pn1] >= = countPersonToMovie[pn2]) ) f
def ref movies:set<Node>= = adjacentOutgoing(pn2,
personToMovie);
for(movie:Node in n adjacentOutgoing(pn1, personToMovie)) f
if(movie in n movies) f
common.add(movie);
g
g
g else e f
def ref movies:set<Node>= = adjacentOutgoing(pn1,
personToMovie);
for(movie:Node in n adjacentOutgoing(pn2, personToMovie)) f
if(movie in n movies) f
common.add(movie);
g
g
g
return(common);
g
Figure22.10: getCommonMoviesrule
Executing Graph Rewrite Sequence e done e after r 23174.7 ms with h result t True:
- 138718180 0 search h steps executed
- 34958 matches found
- 34958 rewrites performed
> show w profile findCouples
profile for action findCouples:
calls total: 1
steps of first loop of pattern matcher total: 5000
search steps total l (in n pattern matching, , if checking, , yielding): 136430986
search steps total l during g eval computation): 0
search steps total l during g exec-ution (incl. . actions called): : 2287194
search steps until l one e match: : 0.00
loop steps s until l one match: 0.00
search steps per loop p step p (until one match): 0.00
search steps until l more e than one e match: : 136430986.00
loop steps s until l more e than n one match: 5000.00
search steps per loop p step p (until more than n one e match): 4441.29
parallelization potential: 474.49
Figure22.11:ProleofndCouples
304
IndicesandPerformanceOptimization
Executing Graph Rewrite Sequence e done e after r 1764.0 ms s with h result True:
- 2962438 search steps s executed
- 17479 matches found
- 17479 rewrites performed
> show w profile findCouplesOpt
profile for action findCouplesOpt:
calls total: 1
steps of first loop of pattern matcher total: 5000
search steps total l (in n pattern matching, , if checking, , yielding): 2962438
search steps total l during g eval computation): 0
search steps total l during g exec-ution (incl. . actions called): : 0
for thread 0:
search steps total: 373345
loop steps s total: : 2193
search steps until l one e match: : 0.00
loop steps s until l one match: 0.00
search steps per loop p step p (until one match): 0.00
search steps until l more e than one e match: : 373345.00
loop steps s until l more e than n one match: 2193.00
search steps per loop p step p (until more than n one e match): 33.64
for thread 1:
search steps total: 374142
loop steps s total: : 2807
search steps until l one e match: : 0.00
loop steps s until l one match: 0.00
search steps per loop p step p (until one match): 0.00
search steps until l more e than one e match: : 374142.00
loop steps s until l more e than n one match: 2807.00
search steps per loop p step p (until more than n one e match): 15.91
Figure22.12: ProleofndCouplesOpt
CHAPTER 23
EXAMPLES
23.1 Fractals
TheGrGen.NETpackageshipswithsamplesforfractalgeneration. Wewillconstructthe
SierpinskitriangleandtheKochsnow ake.Theyarecreatedbyconsecutiveruleapplications
startingwiththeinitialhostgraphs
fortheSierpinskitriangleresp.theKochsnow ake.Firstofallwehavetocompilethemodel
andrulesetles.SoexecuteinGrGen.NET’sbindirectory
GrGen.exe ..\specs\sierpinski.grg
GrGen.exe ..\specs\snowflake.grg
or
mono GrGen.exe e ../specs/sierpinski.grg
mono GrGen.exe e ../specs/snowflake.grg
respectively. If f you u are e on n a Unix-like system you have e to o adjust the path separators
of the GrShell scripts. . Just t edit the e rst three lines of f /test/Sierpinski.grs and
/test/Snowflake.grs. Andas s we have the le Sierpinski.grs alreadyopened, , wecan
increasethenumberofiterations togetevenmorebeautifulgraphs
1
. Justfollowthecom-
ments. BecarefulwhenincreasingthenumberofiterationsofKoch’ssnow ake|yComp’s
layout algorithmmight needsome timeandattempts to layout it nicely. . Weexecutethe
Sierpinskiscriptby
GrShell.exe ..\test\Sierpinski.grs
or
mono GrShell.exe e ../test/Sierpinski.grs
respectively. Becausebothofthescriptsareusingthedebugmode,wecompleteexecution
bytypingr(un).SeeSection20.12forfurtherinformation.Theresultinggraphsshouldlook
likeFigures23.1and23.2.
1
Becareful:Therunningtimeincreasesexponentiallyinthenumberofiterations.
305
306
Examples
Figure23.1: Sierpinskitriangle
Figure23.2:Kochsnow ake
Documents you may be interested
Documents you may be interested