12. Correctness Checking

Let's Make it Simulate

It is time to make our road network example do something. Our goal, after all, is a simulation, not just a passive description of a road network. What do we need to add to make it work?

Vehicles

These are the objects that move over roads.

Vehicle Sources

We need to inject vehicles into the network. For practical purposes a source is a kind of intersection with outgoing roads and no incoming roads.

Vehicle Sinks

If we only inject vehicles, the traffic will get rather congested, so we need a place for vehicles to go to leave the network. A vehicle sink is a kind of intersection with incoming roads and no outgoing roads.

Events

The key event in a road network is the arrival of a vehicle at a road or intersection. If we ignore stop signs and collision avoidance, arrival at an intersection causes the vehicle to select an outgoing road and schedule its arrival at that road. (Road selection can be as simple as random). Arrival at a road causes the scheduling of an arrival event at the intersection at the far end of the road.

Given both sources and sinks, we can talk about total travel time, how long it takes a vehicle to get from source to sink. We can also have vehicles output "trip diaries" of where they visited. The idea of a trip diary sounds particularly useful during debugging, but only if there are very few vehicles.

Correctness Checking While Adding Roads

Sources and sinks are new types of intersections. It is easy to add them, each is a new subclass of intersection, but they have correctness rules that are more interesting: How do we enforce the rule that sources have no incoming roads, and sinks have no outgoing roads?

First note: It is easy to make mistakes in a large road network. You could easily forget to connect some intersections. Thinking through the correctness constraints suggests the following:

Unprotected intersections

Regular intersections ought to have at least one incoming and one outgoing road. Intersections with just one road in and one road out seem a bit silly, but they provide a way for a road to change names and they provide a way to name a waypoint along a long road.

4-way stops

Intersections protected by stopsigns on all incoming roads ought to have at least 2 incoming roads and one outgoing road. The point here is that if you have only one incoming road, there is never a need to stop, or alternately, you could simply incorporate the time taken in stopping and restarting into the time delay for the road.

Sources

A source of traffic can have outgoing roads, but it should not have any incoming roads.

Sink

A traffic sink can have incoming roads, but it should not have any outgoing roads.

Some of these constraints can only be checked after the entire road network has been defined. After all, the next line of input could define a road that connects two intersections, correcting a deficiency in each of them. Therefore, we need to scan all the intersections to check for correctness after the entire network is defined.

In the class Intersection we have defined at this point, we have two lists that are currently unused, except by bug comments:

        LinkedList  outgoing = new LinkedList  ();
        LinkedList  incoming = new LinkedList  ();
	// Bug: the above two lists are unused, but we think we'll need them.
	// Bug: multiple types of intersections (uncontrolled, stoplight, ...)

We need to manage these lists and then, when the time comes, check them to see if the rules have been satisfied.

We could make the insertions in these lists directly when we initialize a new road. The old code we have in the road initializer had approximately this structure:

		if (source == null) {
			Errors.fatal( ... );
		}
		// Bug: should we add this to source.outgoing list?

We could just write this:

		if (source == null) {
			Errors.fatal( ... );
		}
		source.outgoing.add( this );

This approach it has an annoying consequence: Errors such as trying to make a road to a source or a road from a sink are only reported at the end, after the entire road network has been processed. It would be more pleasant if the error messages for these two errors were reported immediately, in the context of the improper road definition instead of later. We can do this by adding two new methods to each intersection. Let's call them addOutgoing() and an addIncoming().

We could make these virtual methods of the class Intersection, requiring each subclass to provide its own version of these, but most types of intersection allow both incoming and outgoing roads. Only our new classes restrict these, so what we want is a default method that can be overridden by selected subclasses.

This leads us to put the following default methods in class Intersection:

	public void addIncoming( Road r, String err ) {
                /** Add a road to the incoming list of this intersection.
                 *  This is a default method that subclasses may override.
                 */
                this.incoming.add( r );
        }

        public void addOutgoing( Road r, String err ) {
                /** Add a road to the outgoing list of this intersection.
                 *  This is a default method that subclasses may override.
                 */
                this.outgoing.add( r );
        }

With these in place, we can now override the defaults with new methods where required. For example, in class of Intersection. For example, we might override addOutgoing() like this in the Sink subclass:

        public void addOutgoing( Road r, String err ) {
                /** Override the default addOutgoing method
                 */
                Errors.fatal( err + "-- road from a sink forbidden" );
        }

Correctness Checking After Adding Roads

After the entire road network is built, we can now check all the correctness constraints by calling checkNetwork(). The call in the main program looks like this:

                        readNetwork( new Scanner( new File( args[0] )));
                        checkNetwork();
                        writeNetwork();

If we plan for it, the actual work of checking the network looks very easy:

        private static void checkNetwork() {
                /** Check the correctness of the network.
                 *  Each intersection does the bulk of the work.
                 */
                for (Intersection i: inters) {
                        i.checkCorrectness();
                }
        }

We want every subclass of itersection to include a checkCorrectness() method, so we put this abstract declaration in the main definition of class Intersection: subclasses of intersection:

        public abstract void checkCorrectness();
                /** Check if the intersection is legally configured
                 */

Finally, here is a typical correctness check in one of the subclasses:

        public void checkCorrectness() {
                /** Check that uncontrolled intersection has at
                 *  least one incoming road and one outgoing road.
                 */
                if (incoming.isEmpty()) {
                        Errors.fatal(
                                "intersection nostop "
                                + name
                                + " has no incoming roads"
                        );
                }
                if ( outgoing.isEmpty()) {
                        Errors.fatal(
                                "intersection nostop "
                                + name
                                + " has no outgoing roads"
                        );
                }
        }