ProCon schedule generation algorithm

From AEWiki
Jump to: navigation, search

Contents

Introduction

This paper describes an algorithm called PCSG for generating a visually appealing printable schedule given a set of events with set start times and lengths. It was invented by Nat Budin for use in ProCon, an online event registration system.

Key Definitions

  • Event: an Event is an object consisting, at minimum, of a start timestamp and a length.
  • Track: a Track is a set of Events that have been logically grouped together. An Event can belong to multiple Tracks, but only if all Tracks it belongs to are consecutive.
  • Block: a Block is an object consisting of a start time, an end time, and an interval in seconds. A single Block corresponds to a section of the schedule that will be generated. PCSG generates blocks automatically based on a heuristic. The reason for using Blocks rather than simply laying out all events together is in case we have large gaps of time in the middle of our schedule that should be skipped for brevity.

Step 1: Generate Blocks

The first step is to generate the Blocks that will be used to lay out the schedule. To do that, we use the following temporary variables:

  • current_block - an Event array. This array is used to accumulate Events to be used together in a Block. This variable is initialized to an empty array.
  • high_water_mark - a timestamp. This is the latest end time of any Event in current_block. This variable is initialized to NULL.
  • schedule_block - a Block array. This array is used to accumulate Blocks as we create them. This variable is initialized to an empty array.

The following steps are followed:

  • For each Event in the schedule, in chronological order by start time:
    • If high_water_mark is NULL:
      • Set high_water_mark to the end time of the current Event.
    • Otherwise, if high_water_mark is at least 3 hours earlier than the start time of the current Event:
      • If there are any Events in current_block:
        • Create a new Block using the events in current_block.
        • Add the new Block to schedule_blocks.
        • Clear current_block.
    • Append the current Event to current_block.
    • If high_water_mark is earlier than the end time of the current Event:
      • Set high_water_mark to the end time of the current Event.
  • If there are any events left in current_block:
    • Create a new Block using the events in current_block.
    • Add the new Block to schedule_blocks.
  • Finally, return schedule_blocks.

Step 2: Calculate Block intervals

After we have generated a set of Blocks, we must calculate how granular the schedule must be for each one, in order to avoid displaying an Event with too little vertical space to be read easily, or making the schedule too long vertically. To do that, we'll use two temporary variables:

  • shortest_event_length - a variable to store the length, in seconds, of the shortest Event in this Block
  • block_interval - the time interval, in seconds, between the rows in this Block

We proceed as follows:

  • For each Block that doesn't already have a set interval:
    • First set block_interval provisionally to 30 minutes (60 * 30 = 1800 seconds).
    • Set shortest_event_length to the length of the first Event in this Block.
    • For each Event in this Block:
      • If this Event is shorter than shortest_event_length, set shortest_event_length to this Event's length.
    • We loop to determine if we need to make the interval more granular. While shortest_event_length < (block_interval * 4) and block_interval > 60:
      • Divide <tt>block_interval by 2.
      • (This ensures that each Event will get at least 4 rows on the table, as long as that wouldn't make each row represent less than one minute.)
    • We loop to determine if we need to make the interval less granular. While shortest_event_length > (block_interval * 8):
      • Multiply block_interval by 2.
      • (This ensures that the shortest Event in the Block will get 4 rows.)
    • Set the Block's interval to block_interval.

Step 3: Place Events

We're finally ready to generate the visual dimensions for each Event on the schedule. The basic idea is that the schedule will be laid out using each Track as an equally wide column, with possible sub-columns within the Track. Sub-columns grow and shrink dynamically based on how many Events in that track occur simultaneously.

Variables

Sometimes we need to split a Track into sub-columns. This could be because two events start at the same time in that Track. It could also be because one event in the Track starts in the middle of another one. To deal with both of these cases, we'll use two temporary structures:

  • grabbed_columns - a hash of hashes that's used for marking a column "used" for a span of time. The outer hash is keyed by Track, and the inner hash is keyed by sub-column number within that Track. The value of the inner hash is an ending time for this column grab. In other words, grabbed_columns[track][subcol] = end_time.
  • pregrabs - a hash used for marking which events have sub-column reservations that haven't yet begun. The key is an Event, and the value is a boolean value. In other words, if pregrabs[this_event] is true, than this_event has pre-grabbed a sub-column.

In addition, we'll use the following variables:

  • colsize - the horizontal size, in percent, of a track.
  • now - a counter, holding the time for the current row we're laying out.
  • nowevents - an array of Events going on now.
  • colnum - a counter for which track column we are currently working on.
  • trackevents - an array of Events going on now in the current Track.
  • eventsize - the relative width of an event right now in the current Track,
  • eventnum - a counter for where we are horizontally in the track.

Algorithm

Let's do it, Rockapella.

  • Set colsize to (100 / the number of Tracks) - 10. (We reserve 10% of the horizontal width for the time labels on the left side of the schedule.)
  • Clear pregrabs and grabbed_columns.
  • For each Block:
    • Set now to the start time of the Block.
    • While now < the end time of the Block:
      • Clear nowevents, then loop through each Event in the Block, and add it to nowevents if now falls between its start and end time.
      • Check for expired column grabs: loop through each grab in each Track in grabbed_columns, and if the end_time value is less than or equal to now, delete it.
      • Set colnum to 0.
      • For each Track:
        • Clear trackevents, then loop through each Event in nowevents, and if it is part of the current Track, add it to trackevents.
        • Check for upcoming events that we'll need to pre-grab. Do this by looping through trackevents, and for each:
          • Loop through all events on the schedule, and for each:
            • If the event is not already in pregrabs, and the event is on this Track, and the Event starts after this trackevent does, and the Event ends before this trackevent does:
              • Find a column number to pre-grab for this event: starting with 1, check whether each column number is currently present in grabbed_columns[Track], and if so, add 1 and check again until you find one that isn't.
              • Set grabbed_columns[Track][ColumnNumberToGrab] to the event's start time.
              • Set pregrabs[Event] to a true value.
        • Set eventsize to (colsize - 0.5) / (trackevents.size + grabbed_columns[track].size).
        • Set eventnum to 0.
          • Calculate the visual dimensions of each event in trackevents:
            • If we already calculated the dimensions for this event, skip it and move on to the next one.
            • If grabbed_columns[Track][eventnum] is currently set (i.e. column number eventnum has been grabbed), add 1 and check again until it is not.
            • Set the visual dimensions for this event as follows:
              • left is (colsize * colnum) + (eventsize * eventnum) + 10.0
              • width is eventsize
              • top is ((event.start - Block.start) / Block.length) * 100.0
              • height is (event.length / Block.length) * 100.0
          • Grab this column by setting grabbed_columns[Track][eventnum] to the event's end time.
          • Increment eventnum by 1.
        • Increment colnum by 1.
      • Increment now by this Block's interval.
Personal tools
Namespaces

Variants
Actions
Navigation
Toolbox