# there must be an relation edges # and a file Speeds2 if not(isDBObject("Speeds2")) then restore Speeds2 from Speeds2 endif query meminit(20000) query memclear() # in a first step, we sssign speeds to the edges of the relation if isDBObject("useAll") then delete useAll endif let useAll = TRUE if not(isDBObject("EdgesB")) then let EdgesB = Speeds2 feed {s} Edges feed filter[isdefined(.Curve)] filter[ useAll or (.RoadType = "motorway") or (.RoadType = "motorway_link") or (.RoadType = "trunk") or (.RoadType = "trunk_link") or (.RoadType = "primary") or (.RoadType = "primary_link") or (.RoadType = "secondary") or (.RoadType = "secondary_link") or (.RoadType = "tertiary") or (.RoadType = "tertiary_link") or (.RoadType = "road") or (.RoadType = "unclassified") or (.RoadType = "residential") or (.RoadType = "living_street") ] itHashJoin[RoadType_s, RoadType] extend[Cost: size(.Curve,[const geoid value WGS1984]) / (.Speed_s / 3.6), Middle: 0, NEdges: 1.0] project[Source, Target, SourcePos, TargetPos, Cost, Middle, NEdges] filter[isdefined(.Cost)] consume endif # store the EdgesB relation into an ordered relation to be able to create a graph from it if not(isDBObject("EdgesB2")) then let EdgesB2 = EdgesB feed sortbyh[Source, Target] oconsume[Source, Target] endif # store the largest connected component into relation EdgesC if not(isDBObject("EdgesC")) then { query memglet("EdgesB", EdgesB2) | let maxcompno = "EdgesB" mgconnectedcomponents sortbyh[CompNo] groupby[CompNo; Cnt: group count] kbiggest[1; Cnt] extract[CompNo] | let EdgesC = "EdgesB" mgconnectedcomponents filter[.CompNo = maxcompno] remove[CompNo] consume | query memdelete("EdgesB") | delete maxcompno } endif # release memory used by the graph "EdgesB" query memclear() # We renumber the nodes from 0 .. nodecount -1 # using an mgraph2 if not(isDBObject("EdgesD")) then { query EdgesC feed createmgraph2[Source,Target,.Cost,"EdgesD", TRUE] count | let EdgesD = "EdgesD" mg2feed projectextend[; Source : .MG_Source, SourcePos : .SourcePos, Cost : .MG_Cost, Middle : .Middle, NEdges : .NEdges, Target : .MG_Target, TargetPos : .TargetPos ] consume | if isDBObject("NodeCount") then delete NodeCount endif | let NodeCount = mg2numvertices("EdgesD") } endif # release old memory objects query memclear() # create an mgraph3 from the EdgesD relation query EdgesD feed createmgraph3[Source, Target, Cost, NodeCount, "EdgesX"] count # store the nodes into a relation NodesA if not(isDBObject("NodesA")) then let NodesA = "EdgesX" mg3feed project[Source, SourcePos] renameattr[NodeIdNew: Source, Pos: SourcePos] "EdgesX" mg3feed project[Target, TargetPos] renameattr[NodeIdNew: Target, Pos: TargetPos] concat sorth rdup consume endif # create an empty relation for the contraction edges query "EdgesX" mg3feed head[0] letmconsume["ContractionX"] # create an empty relation for the deleted nodes query NodesA feed projectextend[; Node: .NodeIdNew, Pos: .Pos, Prio: 0.0, Reinsertions: 0, NewPrio: 0.0, CEdges: 0, Deleted: 0] head[0] letmconsume["DeletedNodes"]; # create a main memory vector holding the number of contracted neighbors # for each node, initial of course 0 query NodesA feed extend[CN : 0] projecttransformstream[CN] collect_mvector["ContractedNeighbours",TRUE] #define a function increasing the ContractedNeighboursVector at a specified index if isDBObject("increaseCN") then delete increaseCN endif let increaseCN = fun( node : int) pwrap("ContractedNeighbours") putmv[node, pwrap("ContractedNeighbours") getmv[node] + 1] # store a priority function if isDBObject("edgeDiff") then delete edgeDiff endif # simple version let edgeDiff = fun(node : int) (pwrap("EdgesX") mg3numsuccessors[node] * pwrap("EdgesX") mg3numpredecessors[node]) - (pwrap("EdgesX") mg3numsuccessors[node] + pwrap("EdgesX") mg3numpredecessors[node]) # more exact version #if isDBObject("allIn") then delete allIn endif # #let allIn = fun(node : int) # pwrap("EdgesX") mg3successors[node] project[Target] sorth rdup # pwrap("EdgesX") mg3predecessors[node] project[Source] sorth rdup # pMerge[Target,Source] # filter[ isdefined(.Source)] count # # #if isDBObject("allOut") then delete allOut endif # #let allOut = fun(node : int) # pwrap("EdgesX") mg3successors[node] project[Target] sorth rdup # pwrap("EdgesX") mg3predecessors[node] project[Source] sorth rdup # pMerge[Target,Source] # filter[ isdefined(.Target)] count # # #if isDBObject("noDelEdges") then delete noDelEdges endif # # #let noDelEdges = fun(node : int) # (pwrap("EdgesX") mg3numsuccessors[node]) + # (pwrap("EdgesX") mg3numpredecessors[node]) # # #let edgeDiff = fun(node : int) (allIn(node) * allOut(node)) - noDelEdges(node) if isDBObject("getPriority") then delete getPriority endif let getPriority = fun(node : int) (8.0 * edgeDiff(node)) + (1 * pwrap("ContractedNeighbours") getmv[node]) #let getPriority = fun(node : int) 8.0 * edgeDiff(node) # create a priority queue from the nodes query NodesA feed projectextend[; Node: .NodeIdNew, Pos: .Pos, Prio: getPriority(.NodeIdNew), Reinsertions : -1 ] mcreatepqueue[Prio, "NodesX"] count # define a function for contraction # define a function creating contraction edges if isDBObject("mtcreationEdges") then delete mtcreationEdges endif let mtcreationEdges = fun(node10 : int, maxHops : int) pwrap("EdgesX") mg3predecessors[node10] sortbyh[Source,Cost] krdup[Source] {i} loopjoin[ fun(t10 : TUPLE) (fun(node11: int) pwrap("EdgesX") mg3successors[node11]) pwrap("EdgesX") mg3successors[node10] sortbyh[Target,Cost] krdup[Target] {o} mtMinPathCosts1[Target,attr(t10,Source_i), Target_o, Cost, maxHops, attr(t10, Cost_i) + (pwrap("EdgesX") mg3successors[node10] max[Cost]) ] filter[attr(t10,Source_i) # .Target_o] extend[Cost : attr(t10,Cost_i) + .Cost_o] filter[.MinPC >= .Cost] remove[MinPC] ] if isDBObject("mtcontract") then delete mtcontract endif let mtcontract = fun(maxprio: int, minBlockSize : int, maxHops : int, progress : int) "NodesX" mfeedpq extend[ NewPrio : getPriority(.Node) ] replaceAttr[Reinsertions : .Reinsertions + 1] extend[CEdges: fun(t: TUPLE) ifthenelse( (attr(t,NewPrio)) <= attr(t, Prio) + 4, mtcreationEdges(attr(t,Node), maxHops) groupby[; Added: fun(g: GROUP) g feed projectextend[; Source: .Source_i, SourcePos: .SourcePos_i, Cost: .Cost_i + .Cost_o, Middle: attr(t, Node), NEdges: .NEdges_i + .NEdges_o, Target: .Target_o, TargetPos: .TargetPos_o ] mg3insert[pwrap("EdgesX")] minsert[pwrap("ContractionX")] groupby[ ; D1 : fun(g2 : GROUP) g2 feed project[Source] g2 feed project[Target] renameattr[Source : Target] concat sorth rdup extend[D1_1 : increaseCN(.Source)] count ] count ] count , bool2int(pwrap("NodesX") minserttuplepqprojectU[t, (attr(t,NewPrio)), Prio; Node, Pos, Prio, Reinsertions]) - 10 ) ] filter[.CEdges >= 0] addModCounter[Num,1, (.Prio > maxprio) and (.. > minBlockSize), 0] extend[ Dummy : ifthenelse(.Num = 0,pwrap("NodesX") mpqreorderupdate[ getPriority(.Node), Prio ] ,0)] remove[Num,Dummy] addcounter[Progress,1] filter[ ifthenelse((.Progress mod progress)=0, TRUE echo[num2string(.Progress)], TRUE)] remove[Progress] extend[Deleted: bool2int(pwrap("EdgesX") mg3disconnect[.Node]) ] minsert[pwrap("DeletedNodes")] count # export graph to a ddsg file query "EdgesX" mg3exportddsg["EdgesX.ddsg", 10000] ########## the actual Contraction, play with arguments ## mtcontract(maxPrio, minBlockSize, maxHops, ProgressAfterEachNodes) query mtcontract(80,100,5, NodeCount div 100) if isDBObject("bdcreationEdges") then delete bdcreationEdges endif let bdcreationEdges = fun(node11 : int, maxHopsF : int, maxHopsB : int) pwrap("EdgesX") mg3predecessors[node11] sortbyh[Source,Cost] krdup[Source] {i} pwrap("EdgesX") mg3successors[node11] sortbyh[Target,Cost] krdup[Target] {o} product filter[.Source_i # .Target_o] extend[C : .Cost_i + .Cost_o] extend[SP : mg3minPathCost(pwrap("EdgesX"), .Source_i, .Target_o, maxHopsF, maxHopsB, node11, .C)] filter[.C < .SP] remove[C,SP] if isDBObject("bdcontract") then delete bdcontract endif let bdcontract = fun(maxprio: int, minBlockSize : int, maxHopsF : int, maxHopsB : int, progress : int) "NodesX" mfeedpq replaceAttr[Reinsertions : .Reinsertions + 1] extend[ NewPrio : getPriority(.Node) ] extend[CEdges: fun(t: TUPLE) ifthenelse( attr(t, NewPrio) <= attr(t, Prio), bdcreationEdges(attr(t,Node), maxHopsF, maxHopsB) memgroupby[; Added: fun(g: MGROUP) g mfeed extend[ D1 : increaseCN(.Source_i), D2 : increaseCN(.Target_o) ] projectextend[; Source: .Source_i, SourcePos: .SourcePos_i, Cost: .Cost_i + .Cost_o, Middle: attr(t, Node), NEdges: .NEdges_i + .NEdges_o, Target: .Target_o, TargetPos: .TargetPos_o ] mg3insert[pwrap("EdgesX")] minsert[pwrap("ContractionX")] count ] count , bool2int(pwrap("NodesX") minserttuplepqprojectU[t, attr(t, NewPrio) , Prio; Node, Pos, Prio,Reinsertions]) - 10 ) ] filter[.CEdges >= 0] addModCounter[Num,1, (.Prio > maxprio) and (.. > minBlockSize), 0] extend[ Dummy : ifthenelse(.Num = 0,pwrap("NodesX") mpqreorderupdate[ -1.0, Prio ],0)] remove[Num,Dummy] addcounter[Progress,1] filter[ ifthenelse((.Progress mod progress)=0, TRUE echo[num2string(.Progress)], TRUE)] remove[Progress] extend[Deleted: bool2int(pwrap("EdgesX") mg3disconnect[.Node]) ] minsert[pwrap("DeletedNodes")] count # query bdcontract(10,600,2,1, NodeCount div 100) ####### make result persistent if isDBObject("EdgesX") then delete EdgesX endif let EdgesX = "EdgesX" mg3feed consume if isDBObject("NodesX") then delete NodesX endif let NodesX = "NodesX" mfeedpq consume {query memdelete("NodesX") | query NodesX feed mcreatepqueue[Prio, "NodesX"] count} if isDBObject("ContractionX") then delete ContractionX endif let ContractionX = "ContractionX" mfeed consume if isDBObject("NodeOrder") then delete NodeOrder endif let NodeOrder = "DeletedNodes" mfeed addcounter[NewId, 1] consume