Paper idea:

selectors
meta graphs
instance graphs

Traverse instance graph:

select set of nodes:
based on events of entire traversal history
based on events on path from root

execute code at internal events: look to future?
look to meta information. Is it intuitively clear?

at meta graph level:

Given a meta graph and a selector, is there a path that satisfies the selector?
It is not a path but a part of a graph traversal.
Fix depth-first traversal. Do we find a node that satisfies the selector.

Given a meta graph G and a selector, does a depth-first traversal of G find a node that satisfies the selector?
Depth-first traversal has choices: optional edges. If abstract class: exactly one alternative.

OR DEFINE new path concept.
A traversal path is a sequence of nodes and edges start at root Start(G). Need to take all 
required has-a edges.
s forward e1 n1 forward e2 n2 ... backward e2 n1 backward e1

Better:
Is there a subgraph so that a depth-first traversal of the subgraph finds a node satisfying the selector.
subgraph must satisfy the rule: all required edges are included.

Define constraints on paths:
If all edges are optional and flow (Start), flow(X1), flow(Nx1) 
X3 in flow(X2) || flow(nX2)
Those constraints choose only ordinary paths.

get old satisfiability problem.

For Ravi:
Generalization:

Meta graphs:
Two kinds of edges: required and optional.

Generalized paths from A to B: 
Depth-first traversal (with forward and backward edges) for a subgraph that includes all required edges and some optional edges.
Depth-first traversal starts at A and ends at B.

Selector expressions: SD with intersection.

If no backward edges are allowed in paths, the problem is NP-complete.

What if backward edges are allowed.

transportation pattern
visitor
collect visitors
Walter

Problem when meta information is not precise.

Use limited form of Socrates?

Study the same problems: Sat, IMPL.