MATSIM
Classes | Public Member Functions | Static Public Member Functions | Public Attributes | Private Member Functions | Private Attributes | List of all members
org.matsim.core.network.turnRestrictions.TurnRestrictionsContext Class Reference

Classes

class  ColoredLink
 

Public Member Functions

record ColoredNode (int index, Node node, List< ColoredLink > outLinks, List< ColoredLink > inLinks)
 
int getNodeCount ()
 
int getLinkCount ()
 

Static Public Member Functions

static TurnRestrictionsContext build (Network network)
 

Public Attributes

final Network network
 
Map< Id< Link >, ColoredLink > replacedLinks = new HashMap<>()
 
List< ColoredNode > coloredNodes = new ArrayList<>()
 
List< ColoredLink > coloredLinks = new ArrayList<>()
 
Map< Id< Link >, List< ColoredLink > > coloredLinksPerLinkMap = new HashMap<>()
 

Private Member Functions

 TurnRestrictionsContext (Network network)
 
ColoredLink applyTurnRestriction (TurnRestrictionsContext context, Collection< List< Id< Link >>> restrictions, Link startingLink)
 
void applyTurnRestriction (TurnRestrictionsContext context, Collection< List< Id< Link >>> restrictions, ColoredLink startingLink)
 
ColoredLink applyTurnRestriction (TurnRestrictionsContext context, Collection< List< Id< Link >>> restrictions, Link startingLink, ColoredLink coloredStartingLink)
 

Private Attributes

int nodeCount
 
int linkCount
 

Detailed Description

Turn restriction context that expands networks with turn restrictions with colored subgraphs.

Definition at line 16 of file TurnRestrictionsContext.java.

Constructor & Destructor Documentation

◆ TurnRestrictionsContext()

org.matsim.core.network.turnRestrictions.TurnRestrictionsContext.TurnRestrictionsContext ( Network  network)
private

Definition at line 28 of file TurnRestrictionsContext.java.

References org.matsim.api.core.v01.Id< T >.getNumberOfIds(), and org.matsim.core.network.turnRestrictions.TurnRestrictionsContext.network.

Referenced by org.matsim.core.network.turnRestrictions.TurnRestrictionsContext.build().

28  {
29  this.network = network;
30  this.nodeCount = Id.getNumberOfIds(Node.class);
31  this.linkCount = Id.getNumberOfIds(Link.class);
32  }
Here is the call graph for this function:

Member Function Documentation

◆ ColoredNode()

record org.matsim.core.network.turnRestrictions.TurnRestrictionsContext.ColoredNode ( int  index,
Node  node,
List< ColoredLink >  outLinks,
List< ColoredLink >  inLinks 
)

Definition at line 59 of file TurnRestrictionsContext.java.

References org.matsim.core.network.turnRestrictions.TurnRestrictionsContext.ColoredLink.index.

Referenced by org.matsim.core.network.turnRestrictions.TurnRestrictionsContext.applyTurnRestriction(), org.matsim.core.router.speedy.SpeedyGraphBuilder.buildWithTurnRestrictions(), org.matsim.core.network.turnRestrictions.TurnRestrictionsNetworkCleaner.collapseNetwork(), and org.matsim.core.network.turnRestrictions.TurnRestrictionsNetworkCleaner.colorNetwork().

64  {
65 
66  @Override
67  public int index() {
68  return index;
69  }
70 
71  @Override
72  public Node node() {
73  return node;
74  }
75 
76  @Override
77  public int hashCode() {
78  return index;
79  }
80  }

◆ build()

static TurnRestrictionsContext org.matsim.core.network.turnRestrictions.TurnRestrictionsContext.build ( Network  network)
static

Definition at line 82 of file TurnRestrictionsContext.java.

References org.matsim.core.network.turnRestrictions.TurnRestrictionsContext.applyTurnRestriction(), org.matsim.core.network.turnRestrictions.TurnRestrictionsContext.coloredLinksPerLinkMap, org.matsim.core.network.NetworkUtils.getDisallowedNextLinks(), org.matsim.api.core.v01.network.Network.getLinks(), org.matsim.core.network.turnRestrictions.DisallowedNextLinks.getMergedDisallowedLinkSequences(), org.matsim.core.network.turnRestrictions.TurnRestrictionsContext.ColoredLink.toColoredNode, and org.matsim.core.network.turnRestrictions.TurnRestrictionsContext.TurnRestrictionsContext().

Referenced by org.matsim.core.router.speedy.SpeedyGraphBuilder.buildWithTurnRestrictions(), and org.matsim.core.network.turnRestrictions.TurnRestrictionsNetworkCleaner.run().

82  {
83  /*
84  * The implementation follows the algorithm developed by
85  * Marcel Rieser (Simunto) and Hannes Rewald (Volkswagen Group)
86  * in October 2023 during the MATSim Code Sprint week in Berlin,
87  * and documented at https://github.com/matsim-org/matsim-code-examples/wiki/turn-restrictions.
88  *
89  * TL;DR:
90  * Main idea of algorithm: for each link with turn-restrictions, create a sub-graph of the network
91  * containing all links required to model all allowed paths, but exclude the last link of turn restrictions'
92  * link sequence to enforce the "disallow" along that route.
93  *
94  *
95  * Implementation details:
96  * - The easiest solution would be to make a copy of the original network, then start modifying it
97  * according to the algorithm above (e.g. add and delete links and nodes), and then to convert the
98  * resulting network into a graph. This would require substantial amount of memory for duplicating
99  * the complete network, and might pose problems as we will have multiple links with the same id.
100  * - Given the assumption that turn restrictions apply only to a small amount of the full network,
101  * we keep the original network intact. Instead, we keep all modifications in separate data-structures
102  * so they can be used to create the routing-graph.
103  * - If the network is already filtered for a specific mode, it might be that links referenced
104  * in a turn restriction are missing. The implementation must be able to deal with such cases,
105  * prevent NullPointerExceptions.
106  * - As turn restrictions are mode-specific, the algorithm needs to know for which mode the
107  * turn restriction need to be considered.
108  */
109 
110  TurnRestrictionsContext context = new TurnRestrictionsContext(network);
111 
112  for (Link startingLink : network.getLinks().values()) {
113  DisallowedNextLinks disallowedNextLinks = NetworkUtils.getDisallowedNextLinks(startingLink);
114  if (disallowedNextLinks == null) {
115  continue;
116  }
117  Collection<List<Id<Link>>> turnRestrictions = disallowedNextLinks.getMergedDisallowedLinkSequences();
118  if (turnRestrictions == null || turnRestrictions.isEmpty()) {
119  continue;
120  }
121 
122  // steps 1 to 5:
123  ColoredLink coloredStartingLink = context.applyTurnRestriction(context, turnRestrictions, startingLink);
124 
125  // step 6: turn restrictions have to be applied separately to existing colored links as well.
126  // see if there are already colored link copies available for this starting link
127  List<ColoredLink> coloredLinks = context.coloredLinksPerLinkMap.get(startingLink.getId());
128  if (coloredLinks != null) {
129  for (ColoredLink coloredLink : coloredLinks) {
130  // optimization: re-point toNode instead of re-applying full turn restrictions
131  if (coloredLink.toColoredNode == null) {
132  coloredLink.toColoredNode = coloredStartingLink.toColoredNode;
133  coloredLink.toNode = null;
134  } else {
135  context.applyTurnRestriction(context, turnRestrictions, coloredLink);
136  }
137  }
138  }
139  }
140 
141  return context;
142  }
org.matsim.api.core.v01.network.Network.getLinks
Map< Id< Link >, ? extends Link > getLinks()
Here is the call graph for this function:

◆ applyTurnRestriction() [1/3]

ColoredLink org.matsim.core.network.turnRestrictions.TurnRestrictionsContext.applyTurnRestriction ( TurnRestrictionsContext  context,
Collection< List< Id< Link >>>  restrictions,
Link  startingLink 
)
private

Definition at line 144 of file TurnRestrictionsContext.java.

Referenced by org.matsim.core.network.turnRestrictions.TurnRestrictionsContext.applyTurnRestriction(), and org.matsim.core.network.turnRestrictions.TurnRestrictionsContext.build().

144  {
145  return this.applyTurnRestriction(context, restrictions, startingLink, null);
146  }
org.matsim.core.network.turnRestrictions.TurnRestrictionsContext.applyTurnRestriction
ColoredLink applyTurnRestriction(TurnRestrictionsContext context, Collection< List< Id< Link >>> restrictions, Link startingLink)
Definition: TurnRestrictionsContext.java:144

◆ applyTurnRestriction() [2/3]

void org.matsim.core.network.turnRestrictions.TurnRestrictionsContext.applyTurnRestriction ( TurnRestrictionsContext  context,
Collection< List< Id< Link >>>  restrictions,
ColoredLink  startingLink 
)
private

Definition at line 148 of file TurnRestrictionsContext.java.

References org.matsim.core.network.turnRestrictions.TurnRestrictionsContext.applyTurnRestriction().

148  {
149  this.applyTurnRestriction(context, restrictions, null, startingLink);
150  }
org.matsim.core.network.turnRestrictions.TurnRestrictionsContext.applyTurnRestriction
ColoredLink applyTurnRestriction(TurnRestrictionsContext context, Collection< List< Id< Link >>> restrictions, Link startingLink)
Definition: TurnRestrictionsContext.java:144
Here is the call graph for this function:

◆ applyTurnRestriction() [3/3]

ColoredLink org.matsim.core.network.turnRestrictions.TurnRestrictionsContext.applyTurnRestriction ( TurnRestrictionsContext  context,
Collection< List< Id< Link >>>  restrictions,
Link  startingLink,
ColoredLink  coloredStartingLink 
)
private

Definition at line 152 of file TurnRestrictionsContext.java.

References org.matsim.core.network.turnRestrictions.TurnRestrictionsContext.ColoredLink.ColoredLink(), org.matsim.core.network.turnRestrictions.TurnRestrictionsContext.coloredLinks, org.matsim.core.network.turnRestrictions.TurnRestrictionsContext.coloredLinksPerLinkMap, org.matsim.core.network.turnRestrictions.TurnRestrictionsContext.ColoredNode(), org.matsim.core.network.turnRestrictions.TurnRestrictionsContext.coloredNodes, org.matsim.core.network.turnRestrictions.TurnRestrictionsContext.ColoredLink.fromNode, org.matsim.api.core.v01.Id< T >.get(), org.matsim.api.core.v01.network.Link.getFromNode(), org.matsim.api.core.v01.Identifiable< T >.getId(), org.matsim.api.core.v01.network.Node.getOutLinks(), org.matsim.api.core.v01.network.Link.getToNode(), org.matsim.core.network.turnRestrictions.TurnRestrictionsContext.ColoredLink.link, org.matsim.core.network.turnRestrictions.TurnRestrictionsContext.linkCount, org.matsim.core.network.turnRestrictions.TurnRestrictionsContext.nodeCount, org.matsim.core.network.turnRestrictions.TurnRestrictionsContext.replacedLinks, org.matsim.core.network.turnRestrictions.TurnRestrictionsContext.ColoredLink.toColoredNode, and org.matsim.core.network.turnRestrictions.TurnRestrictionsContext.ColoredLink.toNode.

152  {
153  Set<Node> affectedNodes = new HashSet<>();
154  Set<ColoredNode> affectedColoredNodes = new HashSet<>();
155  Set<Link> affectedLinks = new HashSet<>();
156  Set<ColoredLink> affectedColoredLinks = new HashSet<>();
157  Set<Id<Link>> endLinkIds = new HashSet<>();
158 
159  // step 1 and 2: collect end-links, affected-links and affected-nodes
160  for (List<Id<Link>> restriction : restrictions) {
161 
162  Link currentLink;
163  ColoredLink currentColoredLink;
164  Node currentNode = startingLink == null ? null : startingLink.getToNode();
165  // due to the optimization in step 6, every colored starting link leads to a colored to-node
166  ColoredNode currentColoredNode = coloredStartingLink == null ? null : coloredStartingLink.toColoredNode;
167 
168  // walk along the restricted path, collect affectedLinks, affectedNodes and endLink
169  for (Id<Link> linkId : restriction) {
170  if (currentNode != null) {
171  // handle regular node
172  affectedNodes.add(currentNode);
173  currentLink = null;
174  currentColoredLink = null;
175  for (Link outLink : currentNode.getOutLinks().values()) {
176  if (outLink.getId() == linkId) {
177  currentColoredLink = context.replacedLinks.get(linkId);
178  if (currentColoredLink == null) {
179  currentLink = outLink;
180  }
181  break;
182  }
183  }
184 
185  if (currentLink != null) {
186  affectedLinks.add(currentLink);
187  currentNode = currentLink.getToNode();
188  currentColoredNode = null;
189  }
190  if (currentColoredLink != null) {
191  affectedColoredLinks.add(currentColoredLink);
192  currentNode = currentColoredLink.toNode;
193  currentColoredNode = currentColoredLink.toColoredNode;
194  }
195  if (currentLink == null && currentColoredLink == null) {
196  // link of restriction is no longer part of the network, maybe we are in a sub-graph
197  break;
198  }
199  } else if (currentColoredNode != null) {
200  // handle colored node
201  affectedColoredNodes.add(currentColoredNode);
202  currentLink = null;
203  currentColoredLink = null;
204  for (ColoredLink outLink : currentColoredNode.outLinks) {
205  if (outLink.link.getId() == linkId) {
206  currentColoredLink = outLink;
207  break;
208  }
209  }
210  if (currentColoredLink != null) {
211  affectedColoredLinks.add(currentColoredLink);
212  currentNode = currentColoredLink.toNode;
213  currentColoredNode = currentColoredLink.toColoredNode;
214  }
215  if (currentColoredLink == null) {
216  // link of restriction is no longer part of the network, maybe we are in a sub-graph
217  break;
218  }
219  }
220  }
221  endLinkIds.add(restriction.get(restriction.size() - 1));
222  }
223 
224  // step 3: create colored copies of nodes
225  Map<Id<Node>, ColoredNode> newlyColoredNodes = new HashMap<>();
226  for (Node affectedNode : affectedNodes) {
227  int nodeIndex = context.nodeCount;
228  context.nodeCount++;
229  ColoredNode newlyColoredNode = new ColoredNode(nodeIndex, affectedNode, new ArrayList<>(), new ArrayList<>());
230  newlyColoredNodes.put(affectedNode.getId(), newlyColoredNode);
231  context.coloredNodes.add(newlyColoredNode);
232  }
233  for (ColoredNode affectedColoredNode : affectedColoredNodes) {
234  int nodeIndex = context.nodeCount;
235  context.nodeCount++;
236  ColoredNode newlyColoredNode = new ColoredNode(nodeIndex, affectedColoredNode.node, new ArrayList<>(), new ArrayList<>());
237  newlyColoredNodes.put(affectedColoredNode.node.getId(), newlyColoredNode);
238  context.coloredNodes.add(newlyColoredNode);
239  }
240 
241  // step 4: create colored copies of links
242  for (Node affectedNode : affectedNodes) {
243  for (Link outLink : affectedNode.getOutLinks().values()) {
244  if (endLinkIds.contains(outLink.getId())) {
245  continue;
246  }
247  ColoredLink replacedOutLink = context.replacedLinks.get(outLink.getId());
248  int linkIndex = context.linkCount;
249  context.linkCount++;
250  ColoredLink newlyColoredLink;
251  ColoredNode fromNode = newlyColoredNodes.get(outLink.getFromNode().getId());
252  if (affectedLinks.contains(outLink) || (replacedOutLink != null && affectedColoredLinks.contains(replacedOutLink))) {
253  ColoredNode toNode = newlyColoredNodes.get(outLink.getToNode().getId());
254  newlyColoredLink = new ColoredLink(linkIndex, outLink, fromNode, null, toNode, null);
255  } else {
256  Node toNode = outLink.getToNode();
257  newlyColoredLink = new ColoredLink(linkIndex, outLink, fromNode, null, null, toNode);
258  }
259  fromNode.outLinks.add(newlyColoredLink);
260  context.coloredLinks.add(newlyColoredLink);
261  context.coloredLinksPerLinkMap.computeIfAbsent(outLink.getId(), id -> new ArrayList<>(3)).add(newlyColoredLink);
262  }
263  }
264  for (ColoredNode affectedNode : affectedColoredNodes) {
265  for (ColoredLink outLink : affectedNode.outLinks) {
266  if (endLinkIds.contains(outLink.link.getId())) {
267  continue;
268  }
269  int linkIndex = context.linkCount;
270  context.linkCount++;
271  ColoredLink newlyColoredLink;
272  ColoredNode fromNode = newlyColoredNodes.get(outLink.link.getFromNode().getId());
273  if (affectedColoredLinks.contains(outLink)) {
274  ColoredNode toNode = newlyColoredNodes.get(outLink.link.getToNode().getId());
275  newlyColoredLink = new ColoredLink(linkIndex, outLink.link, fromNode, null, toNode, null);
276  } else {
277  newlyColoredLink = new ColoredLink(linkIndex, outLink.link, fromNode, null, outLink.toColoredNode, outLink.toNode);
278  }
279  fromNode.outLinks.add(newlyColoredLink);
280  context.coloredLinks.add(newlyColoredLink);
281  context.coloredLinksPerLinkMap.computeIfAbsent(outLink.link.getId(), id -> new ArrayList<>(3)).add(newlyColoredLink);
282  }
283  }
284 
285  // step 5: replace starting link
286  if (startingLink != null) {
287  ColoredNode toNode = newlyColoredNodes.get(startingLink.getToNode().getId());
288  int linkIndex = startingLink.getId().index(); // re-use the index
289  ColoredLink newlyColoredStartingLink = new ColoredLink(linkIndex, startingLink, null, startingLink.getFromNode(), toNode, null);
290  context.coloredLinks.add(newlyColoredStartingLink);
291  context.replacedLinks.put(startingLink.getId(), newlyColoredStartingLink);
292 
293  return newlyColoredStartingLink;
294  }
295  if (coloredStartingLink != null) {
296  // don't really replace the colored started link, but re-point it to the newly colored node
297  coloredStartingLink.toColoredNode = newlyColoredNodes.get(coloredStartingLink.link.getToNode().getId());
298  return null;
299 
300  }
301  throw new IllegalArgumentException("either startingLink or coloredStartingLink must be set");
302  }
org.matsim.core.network.turnRestrictions.TurnRestrictionsContext.ColoredNode
record ColoredNode(int index, Node node, List< ColoredLink > outLinks, List< ColoredLink > inLinks)
Definition: TurnRestrictionsContext.java:59
Here is the call graph for this function:

◆ getNodeCount()

int org.matsim.core.network.turnRestrictions.TurnRestrictionsContext.getNodeCount ( )

Definition at line 305 of file TurnRestrictionsContext.java.

References org.matsim.core.network.turnRestrictions.TurnRestrictionsContext.nodeCount.

Referenced by org.matsim.core.router.speedy.SpeedyGraphBuilder.buildWithTurnRestrictions().

305  {
306  return nodeCount;
307  }

◆ getLinkCount()

int org.matsim.core.network.turnRestrictions.TurnRestrictionsContext.getLinkCount ( )

Definition at line 309 of file TurnRestrictionsContext.java.

References org.matsim.core.network.turnRestrictions.TurnRestrictionsContext.linkCount.

Referenced by org.matsim.core.router.speedy.SpeedyGraphBuilder.buildWithTurnRestrictions().

309  {
310  return linkCount;
311  }

Member Data Documentation

◆ nodeCount

int org.matsim.core.network.turnRestrictions.TurnRestrictionsContext.nodeCount
private

Definition at line 18 of file TurnRestrictionsContext.java.

Referenced by org.matsim.core.network.turnRestrictions.TurnRestrictionsContext.applyTurnRestriction(), and org.matsim.core.network.turnRestrictions.TurnRestrictionsContext.getNodeCount().

◆ linkCount

int org.matsim.core.network.turnRestrictions.TurnRestrictionsContext.linkCount
private

Definition at line 19 of file TurnRestrictionsContext.java.

Referenced by org.matsim.core.network.turnRestrictions.TurnRestrictionsContext.applyTurnRestriction(), and org.matsim.core.network.turnRestrictions.TurnRestrictionsContext.getLinkCount().

◆ network

final Network org.matsim.core.network.turnRestrictions.TurnRestrictionsContext.network

Definition at line 21 of file TurnRestrictionsContext.java.

Referenced by org.matsim.core.network.turnRestrictions.TurnRestrictionsNetworkCleaner.collapseNetwork(), and org.matsim.core.network.turnRestrictions.TurnRestrictionsContext.TurnRestrictionsContext().

◆ replacedLinks

Map<Id<Link>, ColoredLink> org.matsim.core.network.turnRestrictions.TurnRestrictionsContext.replacedLinks = new HashMap<>()

Definition at line 23 of file TurnRestrictionsContext.java.

Referenced by org.matsim.core.network.turnRestrictions.TurnRestrictionsNetworkCleaner.advance(), org.matsim.core.network.turnRestrictions.TurnRestrictionsContext.applyTurnRestriction(), org.matsim.core.router.speedy.SpeedyGraphBuilder.buildWithTurnRestrictions(), org.matsim.core.network.turnRestrictions.TurnRestrictionsNetworkCleaner.collapseNetwork(), org.matsim.core.network.turnRestrictions.TurnRestrictionsNetworkCleaner.colorNetwork(), and org.matsim.core.network.turnRestrictions.TurnRestrictionsNetworkCleaner.reapplyRestrictions().

◆ coloredNodes

List<ColoredNode> org.matsim.core.network.turnRestrictions.TurnRestrictionsContext.coloredNodes = new ArrayList<>()

Definition at line 24 of file TurnRestrictionsContext.java.

Referenced by org.matsim.core.network.turnRestrictions.TurnRestrictionsContext.applyTurnRestriction(), org.matsim.core.router.speedy.SpeedyGraphBuilder.buildWithTurnRestrictions(), org.matsim.core.network.turnRestrictions.TurnRestrictionsNetworkCleaner.collapseNetwork(), and org.matsim.core.network.turnRestrictions.TurnRestrictionsNetworkCleaner.colorNetwork().

◆ coloredLinks

List<ColoredLink> org.matsim.core.network.turnRestrictions.TurnRestrictionsContext.coloredLinks = new ArrayList<>()

Definition at line 25 of file TurnRestrictionsContext.java.

Referenced by org.matsim.core.network.turnRestrictions.TurnRestrictionsContext.applyTurnRestriction(), org.matsim.core.router.speedy.SpeedyGraphBuilder.buildWithTurnRestrictions(), org.matsim.core.network.turnRestrictions.TurnRestrictionsNetworkCleaner.collapseNetwork(), and org.matsim.core.network.turnRestrictions.TurnRestrictionsNetworkCleaner.colorNetwork().

◆ coloredLinksPerLinkMap

Map<Id<Link>, List<ColoredLink> > org.matsim.core.network.turnRestrictions.TurnRestrictionsContext.coloredLinksPerLinkMap = new HashMap<>()

Definition at line 26 of file TurnRestrictionsContext.java.

Referenced by org.matsim.core.network.turnRestrictions.TurnRestrictionsContext.applyTurnRestriction(), org.matsim.core.network.turnRestrictions.TurnRestrictionsContext.build(), and org.matsim.core.network.turnRestrictions.TurnRestrictionsNetworkCleaner.collapseNetwork().

The documentation for this class was generated from the following file:
Generated by   doxygen 1.8.13