This is the simple case of a single path state machine matrix.
Sorry for the pseudo-code being in C# style, but it was easier to express the idea with objects.
First, construct a turnpike matrix.
Read my description of what a turnpike matrix is (don't bother with the FSM answer, just the explanation of a turnpike matrix) at http://stackoverflow.com/questions/2691073/testing-finite-state-machines/2698241#2698241.
However, the restrictions you describe make the case a simple single path state machine. It is the simplest state machine possible with complete coverage.
For a simple case of 5 airports,
vert nodes=src/entry points,
horiz nodes=dst/exit points.
A1 A2 A3 A4 A5
A1 x
A2 x
A3 x
A4 x
A5 x
Notice that for each row, as well as for each column, there should be no more than one transition.
To get the path of the machine, you would sort the matrix into
A1 A2 A3 A4 A5
A2 x
A1 x
A3 x
A4 x
A5 x
Or sort into a diagonal square matrix - an eigen vector of ordered pairs.
A1 A2 A3 A4 A5
A2 x
A5 x
A1 x
A3 x
A4 x
where the ordered pairs are the list of tickets:
a2:a1, a5:a2, a1:a3, a3:a4, a4:a5.
or in more formal notation,
<a2,a1>, <a5,a2>, <a1,a3>, <a3,a4>, <a4,a5>.
Hmmm .. ordered pairs huh? Smelling a hint of recursion in Lisp?
<a2,<a1,<a3,<a4,a5>>>>
There are two modes of the machine,
- trip planning - you don't know how
many airports there are, and you
need a generic trip plan for an
unspecified number of airports
- trip reconstruction - you have all
the turnpike tickets of a past trip
but they are all one big stack in
your glove compartment/luggage bag.
I am presuming your question is about trip reconstruction. So, you pick one ticket after another randomly from that pile of tickets.
We presume the ticket pile is of indefinite size.
tak mnx cda
bom 0
daj 0
phi 0
Where 0 value denotes unordered tickets. Let us define unordered ticket as a ticket where its dst is not matched with the src of another ticket.
The following next ticket finds that mnx(dst) = kul(src) match.
tak mnx cda kul
bom 0
daj 1
phi 0
mnx 0
At any moment you pick the next ticket, there is a possibility that it connects two sequential airports. If that happen, you create a cluster node out of that two nodes:
<bom,tak>, <daj,<mnx,kul>>
and the matrix is reduced,
tak cda kul
bom 0
daj L1
phi 0
where
L1 = <daj,<mnx,kul>>
which is a sublist of the main list.
Keep on picking the next random tickets.
tak cda kul svn xml phi
bom 0
daj L1
phi 0
olm 0
jdk 0
klm 0
Match either existent.dst to new.src
or existent.src to new.dst:
tak cda kul svn xml
bom 0
daj L1
olm 0
jdk 0
klm L2
<bom,tak>, <daj,<mnx,kul>>, <<klm,phi>, cda>
The above topological exercise is for visual comprehension only. The following is the algorithmic solution.
The concept is to cluster ordered pairs into sublists to reduce the burden on the hash structures we will use to house the tickets. Gradually, there will be more and more pseudo-tickets (formed from merged matched tickets), each containing a growing sublist of ordered destinations. Finally, there will remain one single pseudo-ticket containing the complete itinerary vector in its sublist.
As you see, perhaps, this is best done with Lisp.
However, as an exercise of linked lists and maps ...
Create the following structures:
class Ticket:MapEntry<src, Vector<dst> >{
src, dst
Vector<dst> dstVec; // sublist of mergers
//constructor
Ticket(src,dst){
this.src=src;
this.dst=dst;
this.dstVec.append(dst);
}
}
class TicketHash<x>{
x -> TicketMapEntry;
void add(Ticket t){
super.put(t.x, t);
}
}
So that effectively,
TicketHash<src>{
src -> TicketMapEntry;
void add(Ticket t){
super.put(t.src, t);
}
}
TicketHash<dst>{
dst -> TicketMapEntry;
void add(Ticket t){
super.put(t.dst, t);
}
}
TicketHash<dst> mapbyDst = hash of map entries(dst->Ticket), key=dst
TicketHash<src> mapbySrc = hash of map entries(src->Ticket), key=src
When a ticket is randomly picked from the pile,
void pickTicket(Ticket t){
// does t.dst exist in mapbyDst?
// i.e. attempt to match src of next ticket to dst of an existent ticket.
Ticket zt = dstExists(t);
// check if the merged ticket also matches the other end.
if(zt!=null)
t = zt;
// attempt to match dst of next ticket to src of an existent ticket.
if (srcExists(t)!=null) return;
// otherwise if unmatched either way, add the new ticket
else {
// Add t.dst to list of existing dst
mapbyDst.add(t);
mapbySrc.add(t);
}
}
Check for existent dst:
Ticket dstExists(Ticket t){
// find existing ticket whose dst matches t.src
Ticket zt = mapbyDst.getEntry(t.src);
if (zt==null) return false; //no match
// an ordered pair is matched...
//Merge new ticket into existent ticket
//retain existent ticket and discard new ticket.
Ticket xt = mapbySrc.getEntry(t.src);
//append sublist of new ticket to sublist of existent ticket
xt.srcVec.join(t.srcVec); // join the two linked lists.
// remove the matched dst ticket from mapbyDst
mapbyDst.remove(zt);
// replace it with the merged ticket from mapbySrc
mapbyDst.add(zt);
return zt;
}
Ticket srcExists(Ticket t){
// find existing ticket whose dst matches t.src
Ticket zt = mapbySrc.getEntry(t.dst);
if (zt==null) return false; //no match
// an ordered pair is matched...
//Merge new ticket into existent ticket
//retain existent ticket and discard new ticket.
Ticket xt = mapbyDst.getEntry(t.dst);
//append sublist of new ticket to sublist of existent ticket
xt.srcVec.join(t.srcVec); // join the two linked lists.
// remove the matched dst ticket from mapbyDst
mapbySrc.remove(zt);
// replace it with the merged ticket from mapbySrc
mapbySrc.add(zt);
return zt;
}
Check for existent src:
Ticket srcExists(Ticket t){
// find existing ticket whose src matches t.dst
Ticket zt = mapbySrc.getEntry(t.dst);
if (zt == null) return null;
// if an ordered pair is matched
// remove the dst from mapbyDst
mapbySrc.remove(zt);
//Merge new ticket into existent ticket
//reinsert existent ticket and discard new ticket.
mapbySrc.getEntry(zt);
//append sublist of new ticket to sublist of existent ticket
zt.srcVec.append(t.srcVec);
return zt;
}
I have a feeling the above has quite some typos, but the concept should be right. Any typo found, someone could help correct it for, plsss.