DBTimes

Home

Products

Contact us

Permissible Sequences of Events Generator

Problem definition
Relationship matrix
Problem definition
Module and demo description
Run Demo

Problem definition

Assume there is a set of n elements, we will call events, E = {e1 , e2 , … , en }.

Definition 1. A sequence S is a subset of two or more events, where it can determined the order of occurrence for each pair of events -- event ei occurs before ej, if ei is earlier in the sequence than ej. 

Assume also, that between each pair of events ( ei , ej ) could be defined one of the following order relationships: 

  1. ( ei , ej ) = Before – event ei occurs before ej (i.e., ei must be located earlier than ej in the sequence)
  2. ( ei , ej ) = Immediately Before  – event ei occurs immediately before ej (i.e., ei must be located right before ej in the sequence)
  3. ( ei , ej ) = After – event ei occurs after ej (i.e., ei must be located later than ej in the sequence)
  4. ( ei , ej ) = Immediately After – event ei occurs immediately after ej (i.e., ei located must be right after ej in the sequence) 
  5. ( ei , ej ) = Not Dependent – occurrence of event ei is not dependent on occurrence of ej (i.e., ei can be located earlier or later than ej in the sequence) 
  6. ( ei , ej ) = Excludes – event ei excludes ej (i.e., ei and ej can’t exist in the same sequence).

All relationships are symmetric, i.e., the following is true:

·  if ( ei , ej ) = Before , than ( ej , ei ) = After

·  if ( ei , ej ) = Immediately Before, than ( ej , ei ) = Immediately After

·  if ( ei , ej ) = After, than ( ej , ei ) = Before 

·  if ( ei , ej ) = Immediately After, than ( ej , ei ) = Immediately Before

·  if ( ei , ej ) = Not Dependent, than ( ej , ei ) = Not Dependent

·  if ( ei , ej ) = Excludes, than ( ej , ei ) = Excludes

Definition 2. A sequence is permissible, if it does not violate any of the defined order relationships.

Definition 3. Relationships between events are contradictory, if it is not possible to build a permissible sequence that includes these events. For example, the following relationships are contradictory: ( ei , ej ) = Before, ( ej , ek ) = Before, ( ei , ek ) = After .

 

The task is to find all permissible sequences given arbitrary, but not contradictory, order relationships between each pair of events.

Relationship matrix

We will represent event relationships as a triangular matrix, with cell (i, j) containing the relationship value for events ( ei , ej ). Because all relationships are symmetric and because the relationship with itself has no meaning, we will only consider relationships ( ei , ej ), i != j, i < j.

For example, the matrix for 7 events may look like this:
where X stands for Excludes, N - Not Dependent, B - Before, A - After, IB - Immediately Before, IA - Immediately After.

 

e1

e2

e3

e4

e5

e6

e7

e1

-

X

X

N

IB

N

B

e2

-

-

X

A

N

N

N

e3

-

-

-

X

N

A

N

e4

-

-

-

-

N

IA

N

e5

-

-

-

-

-

B

N

e6

-

-

-

-

-

-

N

e7

-

-

-

-

-

-

-

Module and demo description

The module to generate permissible sequences is written in C# as a .NET library.  It generates sequences using Relationship Matrix as an input.

Run Demo to see the module work using your own relationship matrix. 

Note, that Not Dependent relationship does not have any text in the corresponding cell, e.g., the matrix for the one above will look like this. 

*

 

 

To enter order relationship for a pair of events click on a square that corresponds to the pair.  The  relationship values in the square will change with each click.  For example, to enter Immediately Before relationship, click on a square three times . 
The *diagram in the upper left corner reminds that the vertical event is the first in the pair of events. For example, Immediately Before relationship in the first row means, "event 1 must occur immediately before event 5", and After in the second row - "event 2 must occur after event 4".