  Temporal graphs represent graph evolution over time, and have been receiving
considerable research attention. Work on expressing temporal graph patterns or
discovering temporal motifs typically assumes relatively simple temporal
constraints, such as journeys or, more generally, existential constraints,
possibly with finite delays. In this paper we propose to use timed automata to
express temporal constraints, leading to a general and powerful notion of
temporal basic graph pattern (BGP). The new difficulty is the evaluation of the
temporal constraint on a large set of matchings. An important benefit of timed
automata is that they support an iterative state assignment, which can be
useful for early detection of matches and pruning of non-matches. We introduce
algorithms to retrieve all instances of a temporal BGP match in a graph, and
present results of an extensive experimental evaluation, demonstrating
interesting performance trade-offs. We show that an on-demand algorithm that
processes total matchings incrementally over time is preferable when dealing
with cyclic patterns on sparse graphs. On acyclic patterns or dense graphs, and
when connectivity of partial matchings can be guaranteed, the best performance
is achieved by maintaining partial matchings over time and allowing automaton
evaluation to be fully incremental.
