To gain historical insight in the geological events that have shaped a particular region into what it is today, geologists must be able to determine the order in which the rocks from that region were formed. Unfortunately, it is usually only possible to determine the age relationship between types of rocks at places where they come into contact with each other. The age relationship at such contact places can be schematically represented for a specific region on a so-called lithological map. The illustration below shows an example of such a map, where areas with the same lithological type - say where the same type of rock is found - are given the same label. In this example, the lithological types are designated by the letters A to L (with the exception of the letter I). Arrows indicate contact points where the relative age of adjacent types of rocks was determined. The arrows point from older rocks to younger specimens. For the area in gray on the lithological map, it can, for example, be deduced that the lithological type L is older than the lithological types A, D and J. All age relationships between the types of rocks from a specific region can thus be listed in a lithological table. For example, the following lithological table includes all age relations from the corresponding lithological map.

lithologische kaart
older younger
A E
A J
B G
C B
D A
D E
D F
D J
E J
F A
F E
F H
F J
H A
H E
H J
H K
J C
K J
L A
L D
L J

The challenge is to determine the order in which the lithological types were formed based on the information from a lithological table. Such a sequence that is consistent with the data from a lithological table is called a topological order. The determination of all possible topological orders is a complex problem that we're not going to address here. As such your assignment is to determine for a given sequence whether it is a topological order or not, taking into account a given lithological table.

Assignment

  1. Write a function isChronological to which three arguments should be passed. The first two arguments are lithological types that are represented by a single letter. The third argument is a string that represents a given sequence of lithological types. In this string letters that correspond with older types are before letters that correspond with younger types. The function should return the value True if the first lithological type is older than the second type, or if the two types are the same, otherwise the False value should be returned. Make sure that the function also returns the value False if the character that corresponds to one of the given lithological types is not in the third argument.

  2. Use the isChronological function to write a function isTopologicalOrder, to which two arguments should be passed. The first argument is a string that represents a given sequence, and which should be interpreted in the same way as the argument described in the isChronological function. The second argument is the location of a text file that contains a topological table. The first row of the file is reserved for column headings; the following rows each contain two letters separated by a tab. As shown in the above example, the first column represents the older lithological type and the second column the younger type. The function should return the value True if the given sequence is a topological order, which means it is consistent with all pairwise age relationships of rocks as defined by the rows of the specified file. Otherwise, the value False must be returned.

Example

In the following example the file topologicalorder1.txt1 will be used.

>>> isChronological('A', 'B', 'ACEGHLDBFJK')
True
>>> isChronological('B', 'A', 'ACEGHLDBFJK')
False
>>> isTopologicalOrder('KLGHABECFJD', 'topologicalorder1.txt')
False
>>> isTopologicalOrder('LDFHAEKJCBG', 'topologicalorder1.txt')
True