View Javadoc
1   package org.opentrafficsim.road.gtu.generator.od;
2   
3   import java.util.ArrayList;
4   import java.util.Arrays;
5   import java.util.Comparator;
6   import java.util.LinkedHashMap;
7   import java.util.LinkedHashSet;
8   import java.util.List;
9   import java.util.Map;
10  import java.util.Map.Entry;
11  import java.util.Set;
12  import java.util.stream.Collectors;
13  
14  import org.djunits.unit.FrequencyUnit;
15  import org.djunits.value.vdouble.scalar.Duration;
16  import org.djunits.value.vdouble.scalar.Frequency;
17  import org.djunits.value.vdouble.scalar.Length;
18  import org.djunits.value.vdouble.scalar.Time;
19  import org.djutils.exceptions.Throw;
20  import org.opentrafficsim.base.parameters.ParameterException;
21  import org.opentrafficsim.core.distributions.Generator;
22  import org.opentrafficsim.core.distributions.ProbabilityException;
23  import org.opentrafficsim.core.dsol.OTSSimulatorInterface;
24  import org.opentrafficsim.core.gtu.GTUDirectionality;
25  import org.opentrafficsim.core.gtu.GTUException;
26  import org.opentrafficsim.core.gtu.GTUType;
27  import org.opentrafficsim.core.idgenerator.IdGenerator;
28  import org.opentrafficsim.core.math.Draw;
29  import org.opentrafficsim.core.network.Link;
30  import org.opentrafficsim.core.network.LinkType;
31  import org.opentrafficsim.core.network.NetworkException;
32  import org.opentrafficsim.core.network.Node;
33  import org.opentrafficsim.road.gtu.generator.GeneratorPositions;
34  import org.opentrafficsim.road.gtu.generator.GeneratorPositions.LaneBiases;
35  import org.opentrafficsim.road.gtu.generator.LaneBasedGTUGenerator;
36  import org.opentrafficsim.road.gtu.generator.LaneBasedGTUGenerator.RoomChecker;
37  import org.opentrafficsim.road.gtu.generator.MarkovCorrelation;
38  import org.opentrafficsim.road.gtu.generator.characteristics.LaneBasedGTUCharacteristics;
39  import org.opentrafficsim.road.gtu.generator.characteristics.LaneBasedGTUCharacteristicsGenerator;
40  import org.opentrafficsim.road.gtu.generator.headway.Arrivals;
41  import org.opentrafficsim.road.gtu.generator.headway.ArrivalsHeadwayGenerator;
42  import org.opentrafficsim.road.gtu.generator.headway.ArrivalsHeadwayGenerator.HeadwayDistribution;
43  import org.opentrafficsim.road.gtu.generator.headway.DemandPattern;
44  import org.opentrafficsim.road.gtu.strategical.od.Categorization;
45  import org.opentrafficsim.road.gtu.strategical.od.Category;
46  import org.opentrafficsim.road.gtu.strategical.od.ODMatrix;
47  import org.opentrafficsim.road.network.OTSRoadNetwork;
48  import org.opentrafficsim.road.network.lane.CrossSectionLink;
49  import org.opentrafficsim.road.network.lane.DirectedLanePosition;
50  import org.opentrafficsim.road.network.lane.Lane;
51  import org.opentrafficsim.road.network.lane.object.sensor.DestinationSensor;
52  import org.opentrafficsim.road.network.lane.object.sensor.Sensor;
53  
54  import nl.tudelft.simulation.dsol.SimRuntimeException;
55  import nl.tudelft.simulation.dsol.simulators.DEVSSimulatorInterface;
56  import nl.tudelft.simulation.jstats.streams.MersenneTwister;
57  import nl.tudelft.simulation.jstats.streams.StreamInterface;
58  
59  /**
60   * Utility to create vehicle generators on a network from an OD.
61   * <p>
62   * Copyright (c) 2013-2020 Delft University of Technology, PO Box 5, 2600 AA, Delft, the Netherlands. All rights reserved. <br>
63   * BSD-style license. See <a href="http://opentrafficsim.org/node/13">OpenTrafficSim License</a>.
64   * <p>
65   * @version $Revision$, $LastChangedDate$, by $Author$, initial version 30 nov. 2017 <br>
66   * @author <a href="http://www.tbm.tudelft.nl/averbraeck">Alexander Verbraeck</a>
67   * @author <a href="http://www.tudelft.nl/pknoppers">Peter Knoppers</a>
68   * @author <a href="http://www.transport.citg.tudelft.nl">Wouter Schakel</a>
69   */
70  public final class ODApplier
71  {
72  
73      /**
74       * Utility class.
75       */
76      private ODApplier()
77      {
78          //
79      }
80  
81      /**
82       * Applies the OD to the network by creating vehicle generators. The map returned contains objects created for vehicle
83       * generation. These are bundled in a {@code GeneratorObjects} and mapped to the vehicle generator id. Vehicle generator id
84       * is equal to the origin node id. For lane-based generators the id's are appended with an ordered number (e.g. A1), where
85       * the ordering is first by link id, and then right to left concerning the lateral lane position at the start of the lane.
86       * For node "A" this would for example be:<br>
87       * <table >
88       * <caption>&nbsp;</caption>
89       * <tr>
90       * <th>Generator id</th>
91       * <th>Link</th>
92       * <th>Lateral start offset</th>
93       * </tr>
94       * <tr>
95       * <th>A1</th>
96       * <th>AB</th>
97       * <th>-1.75m</th>
98       * </tr>
99       * <tr>
100      * <th>A2</th>
101      * <th>AB</th>
102      * <th>1.75m</th>
103      * </tr>
104      * <tr>
105      * <th>A3</th>
106      * <th>AC</th>
107      * <th>-3.5m</th>
108      * </tr>
109      * <tr>
110      * <th>A4</th>
111      * <th>AC</th>
112      * <th>0.0m</th>
113      * </tr>
114      * </table>
115      * @param network OTSRoadNetwork; network
116      * @param od ODMatrix; OD matrix
117      * @param odOptions ODOptions; options for vehicle generation
118      * @return Map&lt;String, GeneratorObjects&gt; map of generator id's and created generator objects mainly for testing
119      * @throws ParameterException if a parameter is missing
120      * @throws SimRuntimeException if this method is called after simulation time 0
121      */
122     @SuppressWarnings("checkstyle:methodlength")
123     public static Map<String, GeneratorObjects> applyOD(final OTSRoadNetwork network, final ODMatrix od,
124             final ODOptions odOptions) throws ParameterException, SimRuntimeException
125     {
126         Throw.whenNull(network, "Network may not be null.");
127         Throw.whenNull(od, "OD matrix may not be null.");
128         Throw.whenNull(odOptions, "OD options may not be null.");
129         OTSSimulatorInterface simulator = network.getSimulator();
130         Throw.when(!simulator.getSimulatorTime().eq0(), SimRuntimeException.class,
131             "Method ODApplier.applyOD() should be invoked at simulation time 0.");
132 
133         // TODO sinks? white extension links?
134         for (Node destination : od.getDestinations())
135         {
136             createSensorsAtDestination(destination, simulator);
137         }
138 
139         final Categorization categorization = od.getCategorization();
140         final boolean laneBased = categorization.entails(Lane.class);
141         boolean markovian = od.getCategorization().entails(GTUType.class);
142 
143         // TODO clean up stream acquiring code after task OTS-315 has been completed
144         StreamInterface stream = simulator.getReplication().getStream("generation");
145         if (stream == null)
146         {
147             stream = simulator.getReplication().getStream("default");
148             if (stream == null)
149             {
150                 System.out.println(
151                     "Using locally created stream (not from the simulator) for vehicle generation, with seed 1.");
152                 stream = new MersenneTwister(1L);
153             }
154             else
155             {
156                 System.out.println("Using stream 'default' for vehicle generation.");
157             }
158         }
159 
160         Map<String, GeneratorObjects> output = new LinkedHashMap<>();
161         for (Node origin : od.getOrigins())
162         {
163             // Step 1: create DemandNode trees, starting with a root for each vehicle generator
164             DemandNode<Node, DemandNode<Node, DemandNode<Category, ?>>> rootNode = null; // root node for each generator
165             /**
166              * Depending on whether the categorization is lane based or not, we either have 1 root per origin, or we have 1 root
167              * per lane (i.e. 1 generator at an origin putting traffic on multiple lanes, or N generators per origin, each
168              * generating traffic on 1 lane). In order to know to which root node the sub nodes belong in a loop, we store root
169              * nodes by lane. Effectively, the map functions as an artificial branching of demand before the origin node, only
170              * used if the categorization contains lanes. For non-lane based demand, the root node and destination node created
171              * in the outer loop can simply be used.
172              */
173             Map<Lane, DemandNode<Node, DemandNode<Node, DemandNode<Category, ?>>>> originNodePerLane = new LinkedHashMap<>();
174             MarkovChain markovChain = null;
175             if (!laneBased)
176             {
177                 rootNode = new DemandNode<>(origin, stream, null);
178                 LinkType linkType = getLinkTypeFromNode(origin);
179                 if (markovian)
180                 {
181                     MarkovCorrelation<GTUType, Frequency> correlation = odOptions.get(ODOptions.MARKOV, null, origin,
182                         linkType);
183                     if (correlation != null)
184                     {
185                         Throw.when(!od.getCategorization().entails(GTUType.class), IllegalArgumentException.class,
186                             "Markov correlation can only be used on OD categorization entailing GTU type.");
187                         markovChain = new MarkovChain(correlation);
188                     }
189                 }
190             }
191             for (Node destination : od.getDestinations())
192             {
193                 Set<Category> categories = od.getCategories(origin, destination);
194                 if (!categories.isEmpty())
195                 {
196                     DemandNode<Node, DemandNode<Category, ?>> destinationNode = null;
197                     if (!laneBased)
198                     {
199                         destinationNode = new DemandNode<>(destination, stream, markovChain);
200                         rootNode.addChild(destinationNode);
201                     }
202                     for (Category category : categories)
203                     {
204                         if (laneBased)
205                         {
206                             // obtain or create root and destination nodes
207                             Lane lane = category.get(Lane.class);
208                             rootNode = originNodePerLane.get(lane);
209                             if (rootNode == null)
210                             {
211                                 rootNode = new DemandNode<>(origin, stream, null);
212                                 originNodePerLane.put(lane, rootNode);
213                             }
214                             destinationNode = rootNode.getChild(destination);
215                             if (destinationNode == null)
216                             {
217                                 markovChain = null;
218                                 if (markovian)
219                                 {
220                                     MarkovCorrelation<GTUType, Frequency> correlation = odOptions.get(ODOptions.MARKOV, lane,
221                                         origin, lane.getParentLink().getLinkType());
222                                     if (correlation != null)
223                                     {
224                                         Throw.when(!od.getCategorization().entails(GTUType.class),
225                                             IllegalArgumentException.class,
226                                             "Markov correlation can only be used on OD categorization entailing GTU type.");
227                                         markovChain = new MarkovChain(correlation); // 1 for each generator
228                                     }
229                                 }
230                                 destinationNode = new DemandNode<>(destination, stream, markovChain);
231                                 rootNode.addChild(destinationNode);
232                             }
233                         }
234                         DemandNode<Category, ?> categoryNode = new DemandNode<>(category, od.getDemandPattern(origin,
235                             destination, category));
236                         if (markovian)
237                         {
238                             destinationNode.addLeaf(categoryNode, category.get(GTUType.class));
239                         }
240                         else
241                         {
242                             destinationNode.addChild(categoryNode);
243                         }
244                     }
245                 }
246             }
247 
248             // Step 2: gather DirectedLanePositions for each generator pertaining to each DemandNode<...>
249             Map<DemandNode<Node, DemandNode<Node, DemandNode<Category, ?>>>, Set<DirectedLanePosition>> initialPositions =
250                 new LinkedHashMap<>();
251             Map<CrossSectionLink, Double> linkWeights = null;
252             Map<CrossSectionLink, Node> viaNodes = null;
253             if (laneBased)
254             {
255                 for (Lane lane : originNodePerLane.keySet())
256                 {
257                     DemandNode<Node, DemandNode<Node, DemandNode<Category, ?>>> demandNode = originNodePerLane.get(lane);
258                     Set<DirectedLanePosition> initialPosition = new LinkedHashSet<>();
259                     try
260                     {
261                         initialPosition.add(lane.getParentLink().getStartNode().equals(demandNode.getObject())
262                             ? new DirectedLanePosition(lane, Length.ZERO, GTUDirectionality.DIR_PLUS)
263                             : new DirectedLanePosition(lane, lane.getLength(), GTUDirectionality.DIR_MINUS));
264                     }
265                     catch (GTUException ge)
266                     {
267                         throw new RuntimeException(ge);
268                     }
269                     initialPositions.put(demandNode, initialPosition);
270                 }
271             }
272             else
273             {
274                 Set<DirectedLanePosition> positionSet = new LinkedHashSet<>();
275                 for (Link link : origin.getLinks())
276                 {
277                     if (link.getLinkType().isConnector())
278                     {
279                         if (link.getStartNode().equals(origin))
280                         {
281                             Node connectedNode = link.getEndNode();
282                             // count number of served links
283                             int served = 0;
284                             for (Link connectedLink : connectedNode.getLinks())
285                             {
286                                 if (connectedLink instanceof CrossSectionLink && !connectedLink.getLinkType().isConnector())
287                                 {
288                                     served++;
289                                 }
290                             }
291                             for (Link connectedLink : connectedNode.getLinks())
292                             {
293                                 if (connectedLink instanceof CrossSectionLink)
294                                 {
295                                     if (link instanceof CrossSectionLink./../org/opentrafficsim/road/network/lane/CrossSectionLink.html#CrossSectionLink">CrossSectionLink && ((CrossSectionLink) link)
296                                         .getDemandWeight() != null)
297                                     {
298                                         if (linkWeights == null)
299                                         {
300                                             linkWeights = new LinkedHashMap<>();
301                                             viaNodes = new LinkedHashMap<>();
302                                         }
303                                         // store weight under connected link, as this
304                                         linkWeights.put(((CrossSectionLinkrg/opentrafficsim/road/network/lane/CrossSectionLink.html#CrossSectionLink">CrossSectionLink) connectedLink), ((CrossSectionLink) link)
305                                             .getDemandWeight() / served);
306                                         viaNodes.put((CrossSectionLink) connectedLink, connectedNode);
307                                     }
308                                     setDirectedLanePosition((CrossSectionLink) connectedLink, connectedNode, positionSet);
309                                 }
310                             }
311                         }
312                     }
313                     else if (link instanceof CrossSectionLink)
314                     {
315                         setDirectedLanePosition((CrossSectionLink) link, origin, positionSet);
316                     }
317                 }
318                 initialPositions.put(rootNode, positionSet);
319             }
320 
321             // Step 3: create generator(s)
322             initialPositions = sortByValue(initialPositions); // sorts by lateral position at link start
323             Map<Node, Integer> originGeneratorCounts = new LinkedHashMap<>();
324             for (DemandNode<Node, DemandNode<Node, DemandNode<Category, ?>>> root : initialPositions.keySet())
325             {
326                 Set<DirectedLanePosition> initialPosition = initialPositions.get(root);
327                 // id
328                 Node o = root.getObject();
329                 String id = o.getId();
330                 if (laneBased)
331                 {
332                     Integer count = originGeneratorCounts.get(o);
333                     if (count == null)
334                     {
335                         count = 0;
336                     }
337                     count++;
338                     id += count;
339                     originGeneratorCounts.put(o, count);
340                 }
341                 // functional generation elements
342                 Lane lane;
343                 LinkType linkType;
344                 if (laneBased)
345                 {
346                     lane = initialPosition.iterator().next().getLane();
347                     linkType = lane.getParentLink().getLinkType();
348                 }
349                 else
350                 {
351                     lane = null;
352                     linkType = getLinkTypeFromNode(o);
353                 }
354                 HeadwayDistribution randomization = odOptions.get(ODOptions.HEADWAY_DIST, lane, o, linkType);
355                 ArrivalsHeadwayGeneratorvalsHeadwayGenerator.html#ArrivalsHeadwayGenerator">ArrivalsHeadwayGenerator headwayGenerator = new ArrivalsHeadwayGenerator(root, simulator, stream,
356                     randomization);
357                 GTUCharacteristicsGeneratorODWrapper characteristicsGenerator = new GTUCharacteristicsGeneratorODWrapper(
358                     root, simulator, odOptions.get(ODOptions.GTU_TYPE, lane, o, linkType), stream);
359                 RoomChecker roomChecker = odOptions.get(ODOptions.ROOM_CHECKER, lane, o, linkType);
360                 IdGenerator idGenerator = odOptions.get(ODOptions.GTU_ID, lane, o, linkType);
361                 LaneBiases biases = odOptions.get(ODOptions.getLaneBiasOption(network), lane, o, linkType);
362                 // and finally, the generator
363                 try
364                 {
365                     LaneBasedGTUGeneratorneBasedGTUGenerator.html#LaneBasedGTUGenerator">LaneBasedGTUGenerator generator = new LaneBasedGTUGenerator(id, headwayGenerator,
366                         characteristicsGenerator, GeneratorPositions.create(initialPosition, stream, biases, linkWeights,
367                             viaNodes), network, simulator, roomChecker, idGenerator);
368                     generator.setNoLaneChangeDistance(odOptions.get(ODOptions.NO_LC_DIST, lane, o, linkType));
369                     generator.setInstantaneousLaneChange(odOptions.get(ODOptions.INSTANT_LC, lane, o, linkType));
370                     generator.setErrorHandler(odOptions.get(ODOptions.ERROR_HANDLER, lane, o, linkType));
371                     output.put(id, new GeneratorObjects(generator, headwayGenerator, characteristicsGenerator));
372                 }
373                 catch (SimRuntimeException exception)
374                 {
375                     // should not happen, we check that time is 0
376                     simulator.getLogger().always().error(exception);
377                     throw new RuntimeException(exception);
378                 }
379                 catch (ProbabilityException exception)
380                 {
381                     // should not happen, as we define probabilities in the headwayGenerator
382                     simulator.getLogger().always().error(exception);
383                     throw new RuntimeException(exception);
384                 }
385             }
386         }
387         return output;
388     }
389 
390     /**
391      * Create destination sensors at all lanes connected to a destination node. This method considers connectors too.
392      * @param destination Node; destination node
393      * @param simulator OTSSimulatorInterface; simulator
394      */
395     private static void createSensorsAtDestination(final Node destination, final OTSSimulatorInterface simulator)
396     {
397         for (Link link : destination.getLinks())
398         {
399             if (link.getLinkType().isConnector() && !link.getStartNode().equals(destination))
400             {
401                 createSensorsAtDestinationNode(link.getStartNode(), simulator);
402             }
403             else
404             {
405                 createSensorsAtDestinationNode(destination, simulator);
406             }
407         }
408     }
409 
410     /**
411      * Create sensors at all lanes connected to this node. This method does not handle connectors.
412      * @param destination Node; the destination node
413      * @param simulator OTSSimulatorInterface; simulator
414      */
415     private static void createSensorsAtDestinationNode(final Node destination, final OTSSimulatorInterface simulator)
416     {
417         for (Link link : destination.getLinks())
418         {
419             if (link instanceof CrossSectionLink)
420             {
421                 for (Lane lane : ((CrossSectionLink) link).getLanes())
422                 {
423                     try
424                     {
425                         // if the lane already contains a SinkSensor, skip creating a new one
426                         boolean destinationSensorExists = false;
427                         for (Sensor sensor : lane.getSensors())
428                         {
429                             if (sensor instanceof DestinationSensor)
430                             {
431                                 destinationSensorExists = true;
432                             }
433                         }
434                         if (!destinationSensorExists)
435                         {
436                             if (link.getEndNode().equals(destination))
437                             {
438                                 new DestinationSensor(lane, lane.getLength(), GTUDirectionality.DIR_PLUS, simulator);
439                             }
440                             else if (link.getStartNode().equals(destination))
441                             {
442                                 new DestinationSensor(lane, Length.ZERO, GTUDirectionality.DIR_MINUS, simulator);
443                             }
444                         }
445                     }
446                     catch (NetworkException exception)
447                     {
448                         // can not happen, we use Length.ZERO and lane.getLength()
449                         simulator.getLogger().always().error(exception);
450                         throw new RuntimeException(exception);
451                     }
452                 }
453             }
454         }
455     }
456 
457     /**
458      * Returns the common ancestor {@code LinkType} of all links connected to the node, moving through connectors.
459      * @param node Node; origin node
460      * @return common ancestor {@code LinkType} of all links connected to the node, moving through connectors
461      */
462     private static LinkType getLinkTypeFromNode(final Node node)
463     {
464         return getLinkTypeFromNode0(node, false);
465     }
466 
467     /**
468      * Returns the common ancestor {@code LinkType} of all links connected to the node, moving through connectors.
469      * @param node Node; origin node
470      * @param ignoreConnectors boolean; ignore connectors
471      * @return common ancestor {@code LinkType} of all links connected to the node, moving through connectors
472      */
473     private static LinkType getLinkTypeFromNode0(final Node node, final boolean ignoreConnectors)
474     {
475         LinkType linkType = null;
476         for (Link link : node.getLinks())
477         {
478             LinkType next = link.getLinkType();
479             if (!ignoreConnectors && next.isConnector())
480             {
481                 Node otherNode = link.getStartNode().equals(node) ? link.getEndNode() : link.getStartNode();
482                 next = getLinkTypeFromNode0(otherNode, true);
483             }
484             if (next != null && !next.isConnector())
485             {
486                 if (linkType == null)
487                 {
488                     linkType = next;
489                 }
490                 else
491                 {
492                     linkType = linkType.commonAncestor(next);
493                     if (linkType == null)
494                     {
495                         // incompatible link types
496                         return null;
497                     }
498                 }
499             }
500         }
501         return linkType;
502     }
503 
504     /**
505      * Returns a sorted map.
506      * @param map Map&lt;K, V&gt;; input map
507      * @param <K> key type (implemented for cleaner code only)
508      * @param <V> value type (implemented for cleaner code only)
509      * @return Map; sorted map
510      */
511     private static <K, V extends Set<DirectedLanePosition>> Map<K, V> sortByValue(final Map<K, V> map)
512     {
513         return map.entrySet().stream().sorted(new Comparator<Map.Entry<K, V>>()
514         {
515             @Override
516             public int compare(final Entry<K, V> o1, final Entry<K, V> o2)
517             {
518                 DirectedLanePosition lanePos1 = o1.getValue().iterator().next();
519                 String linkId1 = lanePos1.getLane().getParentLink().getId();
520                 DirectedLanePosition lanePos2 = o2.getValue().iterator().next();
521                 String linkId2 = lanePos2.getLane().getParentLink().getId();
522                 int c = linkId1.compareToIgnoreCase(linkId2);
523                 if (c == 0)
524                 {
525                     Length pos1 = lanePos1.getGtuDirection().isPlus() ? Length.ZERO : lanePos1.getLane().getLength();
526                     Length lat1 = lanePos1.getLane().getLateralCenterPosition(pos1);
527                     Length pos2 = lanePos2.getGtuDirection().isPlus() ? Length.ZERO : lanePos2.getLane().getLength();
528                     Length lat2 = lanePos2.getLane().getLateralCenterPosition(pos2);
529                     return lat1.compareTo(lat2);
530                 }
531                 return c;
532             }
533         }).collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue, (e1, e2) -> e1, LinkedHashMap::new));
534     }
535 
536     /**
537      * Adds {@code DirectedLanePosition}s to the input set, for {@code Lane}s on the given link, starting at the given
538      * {@code Node}.
539      * @param link CrossSectionLink; link with lanes to add positions for
540      * @param node Node; node on the side where positions should be placed
541      * @param positionSet Set&lt;DirectedLanePosition&gt;; set to add position to
542      */
543     private static void setDirectedLanePosition(final CrossSectionLink link, final Node node,
544             final Set<DirectedLanePosition> positionSet)
545     {
546         for (Lane lane : link.getLanes())
547         {
548             // TODO should be GTU type dependent.
549             if (!lane.getParentLink().getStartNode().equals(node))
550             {
551                 return;
552                 // TODO handle lanes that ARE drivable contrary to the design direction of the link
553             }
554             try
555             {
556                 positionSet.add(lane.getParentLink().getStartNode().equals(node) ? new DirectedLanePosition(lane,
557                     Length.ZERO, GTUDirectionality.DIR_PLUS) : new DirectedLanePosition(lane, lane.getLength(),
558                         GTUDirectionality.DIR_MINUS));
559             }
560             catch (GTUException ge)
561             {
562                 link.getSimulator().getLogger().always().error(ge);
563                 throw new RuntimeException(ge);
564             }
565         }
566     }
567 
568     /**
569      * Node for demand tree. Based on two constructors there are 2 types of nodes:<br>
570      * <ul>
571      * <li>Branch nodes; with an object and a stream for randomly drawing a child node.</li>
572      * <li>Leaf nodes; with an object and demand data (time, frequency, interpolation).</li>
573      * </ul>
574      * To accomplish a branching of Node (origin) &gt; Node (destination) &gt; Category, the following generics types can be
575      * used:<br>
576      * <br>
577      * {@code DemandNode<Node, DemandNode<Node, DemandNode<Category, ?>>>}
578      * <p>
579      * Copyright (c) 2013-2020 Delft University of Technology, PO Box 5, 2600 AA, Delft, the Netherlands. All rights reserved.
580      * <br>
581      * BSD-style license. See <a href="http://opentrafficsim.org/node/13">OpenTrafficSim License</a>.
582      * <p>
583      * @version $Revision$, $LastChangedDate$, by $Author$, initial version 1 dec. 2017 <br>
584      * @author <a href="http://www.tbm.tudelft.nl/averbraeck">Alexander Verbraeck</a>
585      * @author <a href="http://www.tudelft.nl/pknoppers">Peter Knoppers</a>
586      * @author <a href="http://www.transport.citg.tudelft.nl">Wouter Schakel</a>
587      * @param <T> type of contained object
588      * @param <K> type of child nodes
589      */
590     private static class DemandNode<T, K extends DemandNode<?, ?>> implements Arrivals
591     {
592 
593         /** Node object. */
594         private final T object;
595 
596         /** Random stream to draw child node. */
597         private final StreamInterface stream;
598 
599         /** Children. */
600         private final List<K> children = new ArrayList<>();
601 
602         /** Demand data. */
603         private final DemandPattern demandPattern;
604 
605         /** Unique GTU types of leaf nodes. */
606         private final List<GTUType> gtuTypes = new ArrayList<>();
607 
608         /** Number of leaf nodes for the unique GTU types. */
609         private final List<Integer> gtuTypeCounts = new ArrayList<>();
610 
611         /** GTU type of leaf nodes. */
612         private final Map<K, GTUType> gtuTypesPerChild = new LinkedHashMap<>();
613 
614         /** Markov chain for GTU type selection. */
615         private final MarkovChain markov;
616 
617         /**
618          * Constructor for branching node, with Markov selection.
619          * @param object T; node object
620          * @param stream StreamInterface; random stream to draw child node
621          * @param markov MarkovChain; Markov chain
622          */
623         DemandNode(final T object, final StreamInterface stream, final MarkovChain markov)
624         {
625             this.object = object;
626             this.stream = stream;
627             this.demandPattern = null;
628             this.markov = markov;
629         }
630 
631         /**
632          * Constructor for leaf node, without Markov selection.
633          * @param object T; node object
634          * @param demandPattern DemandPattern; demand data
635          */
636         DemandNode(final T object, final DemandPattern demandPattern)
637         {
638             this.object = object;
639             this.stream = null;
640             this.demandPattern = demandPattern;
641             this.markov = null;
642         }
643 
644         /**
645          * Adds child to a branching node.
646          * @param child K; child node
647          */
648         public void addChild(final K child)
649         {
650             this.children.add(child);
651         }
652 
653         /**
654          * Adds child to a branching node.
655          * @param child K; child node
656          * @param gtuType GTUType; gtu type for Markov chain
657          */
658         public void addLeaf(final K child, final GTUType gtuType)
659         {
660             Throw.when(this.gtuTypes == null, IllegalStateException.class,
661                 "Adding leaf with GTUType in not possible on a non-Markov node.");
662             addChild(child);
663             this.gtuTypesPerChild.put(child, gtuType);
664             if (!this.gtuTypes.contains(gtuType))
665             {
666                 this.gtuTypes.add(gtuType);
667                 this.gtuTypeCounts.add(1);
668             }
669             else
670             {
671                 int index = this.gtuTypes.indexOf(gtuType);
672                 this.gtuTypeCounts.set(index, this.gtuTypeCounts.get(index) + 1);
673             }
674         }
675 
676         /**
677          * Randomly draws a child node.
678          * @param time Time; simulation time
679          * @return K; randomly drawn child node
680          */
681         public K draw(final Time time)
682         {
683             Throw.when(this.children.isEmpty(), RuntimeException.class, "Calling draw on a leaf node in the demand tree.");
684             Map<K, Double> weightMap = new LinkedHashMap<>();
685             if (this.markov == null)
686             {
687                 // regular draw, loop children and collect their frequencies
688                 for (K child : this.children)
689                 {
690                     double f = child.getFrequency(time, true).si; // sliceStart = true is arbitrary
691                     weightMap.put(child, f);
692                 }
693             }
694             else
695             {
696                 // markov chain draw, the markov chain only selects a GTU type, not a child node
697                 GTUType[] gtuTypeArray = new GTUType[this.gtuTypes.size()];
698                 gtuTypeArray = this.gtuTypes.toArray(gtuTypeArray);
699                 Frequency[] steadyState = new Frequency[this.gtuTypes.size()];
700                 Arrays.fill(steadyState, Frequency.ZERO);
701                 Map<K, Frequency> frequencies = new LinkedHashMap<>(); // stored, saves us from calculating them twice
702                 for (K child : this.children)
703                 {
704                     GTUType gtuType = this.gtuTypesPerChild.get(child);
705                     int index = this.gtuTypes.indexOf(gtuType);
706                     Frequency f = child.getFrequency(time, true); // sliceStart = true is arbitrary
707                     frequencies.put(child, f);
708                     steadyState[index] = steadyState[index].plus(f);
709                 }
710                 GTUType nextGtuType = this.markov.draw(gtuTypeArray, steadyState, this.stream);
711                 // select only child nodes registered to the next GTU type
712                 for (K child : this.children)
713                 {
714                     if (this.gtuTypesPerChild.get(child).equals(nextGtuType))
715                     {
716                         double f = frequencies.get(child).si;
717                         weightMap.put(child, f);
718                     }
719                 }
720             }
721             return Draw.drawWeighted(weightMap, this.stream);
722         }
723 
724         /**
725          * Returns the node object.
726          * @return T; node object
727          */
728         public T getObject()
729         {
730             return this.object;
731         }
732 
733         /**
734          * Returns the child that pertains to specified object or {@code null} if no such child is present.
735          * @param obj Object; child object
736          * @return child that pertains to specified object or {@code null} if no such child is present
737          */
738         public K getChild(final Object obj)
739         {
740             for (K child : this.children)
741             {
742                 if (child.getObject().equals(obj))
743                 {
744                     return child;
745                 }
746             }
747             return null;
748         }
749 
750         /** {@inheritDoc} */
751         @Override
752         public Frequency getFrequency(final Time time, final boolean sliceStart)
753         {
754             if (this.demandPattern != null)
755             {
756                 return this.demandPattern.getFrequency(time, sliceStart);
757             }
758             Frequency f = new Frequency(0.0, FrequencyUnit.PER_HOUR);
759             for (K child : this.children)
760             {
761                 f = f.plus(child.getFrequency(time, sliceStart));
762             }
763             return f;
764         }
765 
766         /** {@inheritDoc} */
767         @Override
768         public Time nextTimeSlice(final Time time)
769         {
770             if (this.demandPattern != null)
771             {
772                 return this.demandPattern.nextTimeSlice(time);
773             }
774             Time out = null;
775             for (K child : this.children)
776             {
777                 Time childSlice = child.nextTimeSlice(time);
778                 out = out == null || (childSlice != null && childSlice.lt(out)) ? childSlice : out;
779             }
780             return out;
781         }
782 
783         /** {@inheritDoc} */
784         @Override
785         public String toString()
786         {
787             return "DemandNode [object=" + this.object + ", stream=" + this.stream + ", children=" + this.children
788                 + ", demandPattern=" + this.demandPattern + ", gtuTypes=" + this.gtuTypes + ", gtuTypeCounts="
789                 + this.gtuTypeCounts + ", gtuTypesPerChild=" + this.gtuTypesPerChild + ", markov=" + this.markov + "]";
790         }
791 
792     }
793 
794     /**
795      * Wrapper class around a {@code MarkovCorrelation}, including the last type. One of these should be used for each vehicle
796      * generator.
797      */
798     private static class MarkovChain
799     {
800         /** Markov correlation for GTU type selection. */
801         private final MarkovCorrelation<GTUType, Frequency> markov;
802 
803         /** Previously returned GTU type. */
804         private GTUType previousGtuType = null;
805 
806         /**
807          * Constructor.
808          * @param markov MarkovCorrelation&lt;GTUType, Frequency&gt;; Markov correlation for GTU type selection
809          */
810         MarkovChain(final MarkovCorrelation<GTUType, Frequency> markov)
811         {
812             this.markov = markov;
813         }
814 
815         /**
816          * Returns a next GTU type drawn using a Markov chain.
817          * @param gtuTypes GTUType[]; GTUTypes to consider
818          * @param intensities Frequency[]; frequency for each GTU type, i.e. the steady-state
819          * @param stream StreamInterface; stream for random numbers
820          * @return next GTU type drawn using a Markov chain
821          */
822         public GTUType draw(final GTUType[] gtuTypes, final Frequency[] intensities, final StreamInterface stream)
823         {
824             this.previousGtuType = this.markov.drawState(this.previousGtuType, gtuTypes, intensities, stream);
825             return this.previousGtuType;
826         }
827     }
828 
829     /**
830      * Characteristics generation based on OD demand.
831      * <p>
832      * Copyright (c) 2013-2020 Delft University of Technology, PO Box 5, 2600 AA, Delft, the Netherlands. All rights reserved.
833      * <br>
834      * BSD-style license. See <a href="http://opentrafficsim.org/node/13">OpenTrafficSim License</a>.
835      * <p>
836      * @version $Revision$, $LastChangedDate$, by $Author$, initial version 7 dec. 2017 <br>
837      * @author <a href="http://www.tbm.tudelft.nl/averbraeck">Alexander Verbraeck</a>
838      * @author <a href="http://www.tudelft.nl/pknoppers">Peter Knoppers</a>
839      * @author <a href="http://www.transport.citg.tudelft.nl">Wouter Schakel</a>
840      */
841     private static class GTUCharacteristicsGeneratorODWrapper implements LaneBasedGTUCharacteristicsGenerator
842     {
843 
844         /** Root node with origin. */
845         private final DemandNode<Node, DemandNode<Node, DemandNode<Category, ?>>> root;
846 
847         /** Simulator. */
848         private final DEVSSimulatorInterface.TimeDoubleUnit simulator;
849 
850         /** Characteristics generator based on OD information. */
851         private final GTUCharacteristicsGeneratorOD characteristicsGenerator;
852 
853         /** Stream for random numbers. */
854         private final StreamInterface randomStream;
855 
856         /**
857          * @param root DemandNode&lt;Node, DemandNode&lt;Node, DemandNode&lt;Category, ?&gt;&gt;&gt;; root node with origin
858          * @param simulator DEVSSimulatorInterface.TimeDoubleUnit; simulator
859          * @param characteristicsGenerator GTUCharacteristicsGeneratorOD; characteristics generator based on OD information
860          * @param randomStream StreamInterface; stream for random numbers
861          */
862         GTUCharacteristicsGeneratorODWrapper(final DemandNode<Node, DemandNode<Node, DemandNode<Category, ?>>> root,
863                 final DEVSSimulatorInterface.TimeDoubleUnit simulator,
864                 final GTUCharacteristicsGeneratorOD characteristicsGenerator, final StreamInterface randomStream)
865         {
866             this.root = root;
867             this.simulator = simulator;
868             this.characteristicsGenerator = characteristicsGenerator;
869             this.randomStream = randomStream;
870         }
871 
872         /** {@inheritDoc} */
873         @Override
874         public LaneBasedGTUCharacteristics draw() throws ProbabilityException, ParameterException, GTUException
875         {
876             // obtain node objects
877             Time time = this.simulator.getSimulatorTime();
878             Node origin = this.root.getObject();
879             DemandNode<Node, DemandNode<Category, ?>> destinationNode = this.root.draw(time);
880             Node destination = destinationNode.getObject();
881             Category category = destinationNode.draw(time).getObject();
882             // forward to lower-level generator
883             // XXX typically calls DefaultGTUCharacteristicsGeneratorOD.draw(...)
884             return this.characteristicsGenerator.draw(origin, destination, category, this.randomStream);
885         }
886 
887         /** {@inheritDoc} */
888         @Override
889         public String toString()
890         {
891             return "GTUCharacteristicsGeneratorODWrapper [root=" + this.root + ", simulator=" + this.simulator
892                 + ", characteristicsGenerator=" + this.characteristicsGenerator + ", randomStream=" + this.randomStream
893                 + "]";
894         }
895 
896     }
897 
898     /**
899      * Class to contain created generator objects.
900      * <p>
901      * Copyright (c) 2013-2020 Delft University of Technology, PO Box 5, 2600 AA, Delft, the Netherlands. All rights reserved.
902      * <br>
903      * BSD-style license. See <a href="http://opentrafficsim.org/node/13">OpenTrafficSim License</a>.
904      * <p>
905      * @version $Revision$, $LastChangedDate$, by $Author$, initial version 12 dec. 2017 <br>
906      * @author <a href="http://www.tbm.tudelft.nl/averbraeck">Alexander Verbraeck</a>
907      * @author <a href="http://www.tudelft.nl/pknoppers">Peter Knoppers</a>
908      * @author <a href="http://www.transport.citg.tudelft.nl">Wouter Schakel</a>
909      */
910     public static class GeneratorObjects
911     {
912 
913         /** Main generator for GTU's. */
914         private final LaneBasedGTUGenerator generator;
915 
916         /** Generator of headways. */
917         private final Generator<Duration> headwayGenerator;
918 
919         /** Generator of GTU characteristics. */
920         private final LaneBasedGTUCharacteristicsGenerator characteristicsGenerator;
921 
922         /**
923          * @param generator LaneBasedGTUGenerator; main generator for GTU's
924          * @param headwayGenerator Generator&lt;Duration&gt;; generator of headways
925          * @param characteristicsGenerator LaneBasedGTUCharacteristicsGenerator; generator of GTU characteristics
926          */
927         public GeneratorObjects(final LaneBasedGTUGenerator generator, final Generator<Duration> headwayGenerator,
928                 final LaneBasedGTUCharacteristicsGenerator characteristicsGenerator)
929         {
930             this.generator = generator;
931             this.headwayGenerator = headwayGenerator;
932             this.characteristicsGenerator = characteristicsGenerator;
933         }
934 
935         /**
936          * Returns the main generator for GTU's.
937          * @return LaneBasedGTUGenerator; main generator for GTU's
938          */
939         public LaneBasedGTUGenerator getGenerator()
940         {
941             return this.generator;
942         }
943 
944         /**
945          * Returns the generator of headways.
946          * @return Generator&lt;Duration&gt; generator of headways
947          */
948         public Generator<Duration> getHeadwayGenerator()
949         {
950             return this.headwayGenerator;
951         }
952 
953         /**
954          * Returns the generator of GTU characteristics.
955          * @return LaneBasedGTUCharacteristicsGenerator; generator of GTU characteristics
956          */
957         public LaneBasedGTUCharacteristicsGenerator getCharachteristicsGenerator()
958         {
959             return this.characteristicsGenerator;
960         }
961 
962     }
963 
964 }