This is a directed graph. If you find a cycle in it, then it is an invalid entry.

a<-b // a preceeds b

b<-c // b preceeds c

c<-a // c preceeds a, but this forms a cycle: a<-b<-c<-a

You can use a depth first search or a breadth first search to find the cycle. Any standard algorithms book or website will tell you how to do it. You will need a stack or recursion for DFS or a queue for BFS.

See

http://en.wikipedia.org/wiki/Graph_theory

You can also try a time/space tradeoff and solve the problem in O(1) time without a stack or queue by using a technique called "path enumeration". The idea is to precompute all edges - even those with path length > 1. The problem is the #of edges can grow very large depending on the topology of your graph. But in some cases with relatively "flat" and "bushy" graphs, this might be a very acceptable tradeoff. This was explained in a Joe Celko book.

Regards,

Clifford Dibble