This file in:

http://www.ccs.neu.edu/research/demeter/design-decisions/traversal-strategies/graph-theory/general-pathset.txt

Preceeding discussion in:

http://www.ccs.neu.edu/research/demeter/design-decisions/traversal-strategies/strategies-as-types/
http://www.ccs.neu.edu/research/demeter/design-decisions/traversal-strategies/substrategy/

what is called "conform" here should be called "compatible":

Here is some skeleton text for the technical report on semantic
checking of adaptive programs we are working on.
This is my summary of what we discussed today.

I give first definitions and then some facts and conjectures.

It looks like that the definition of graph conformance is key.
Does everybody agree with both applications of conformance?

Next we need to think about how to check efficiently for conformance.

It looks like that subgraph homeomorphism was a useful stepping stone
which has already flown out the window? Do you agree?
Or can we still use it?

Who proves my conjectures wrong?

-- Karl
=====================

To make adaptive concepts more useful, we reformulate the
basic concepts in graph theory and then we apply them to
various kinds of graphs such as: class graphs, strategy graphs,
traversal graphs, object graphs etc.

First we define the concept of path sets for general graphs reusing
the definition of path sets for class graphs and strategy graphs.

Let G1 be a directed node-labeled graph (V1,E1)
    G2                                  (V2,E2) with source s and target t.
N is a name map: V2 -> V1.
P[g](x,y) is the set of paths in graph g from x to y.

PathSet[G1](G2) =
{ p' | p' in P[G1](N(s),N(t)) and exists p in P[G2](s,t)
	   such that p' is an expansion of N(p) }

-----------
Labeled subgraph homeomorphism problem

Instance: Node-labeled graphs G1 = (V1,E1), G2 = (V2,E2).
Question: Does G1 contain a subgraph homeomorphic to G2, i.e.,
a subgraph G1'=(V1',E1') that can be converted to a graph isomorphic to G2 by
repeatedly removing any vertex of degree 2
and adding the edge joining its two neighbors?

Application:  ? 
------------

------------
Conformance of graphs (proposed by Doug Orleans: is this correct?)

Instance: Node-labeled graphs G1 = (V1,E1), G2 = (V2,E2) 
with source s and target t.
Question: Does G1 conform to G2, i.e., for all paths 
p in P[G2](s,t) there exists a path p' in P[G1](N(s),N(t)) such that
p' is an expansion of p.

Applications: 
does a class graph conform to a strategy graph?
does a class graph conform to an interface class graph? 

Johan: does this match what you had in mind?
-------------

------------
Strong embedding of graphs (motivated by substrategies)

Instance: Node-labeled graphs G1 = (V1,E1), G2 = (V2,E2)
          with source s and target t.
Question: Is G2 strongly embedded in G1, i.e., there is a subgraph G4
of G2 such that for all graphs G3:
PathSet[G3](G1) = PathSet[G3](G4).

Application: 
G2 is a substrategy of G1.
-------------

Some Facts:

Fact 1:
PathSet[G1](G2) !=  {} does _not_ 
imply G1 contains a subgraph homeomorphic to G2.

Proof:
Counterexample by Doug Orleans:
Short-cut example.

Fact 2:
PathSet[G1](G2) !=  {} does _not_ imply that G1 conforms to G2.

Proof:
Counterexample by Doug Orleans:
For example: zig-zag example with one edge deleted in class graph.

Fact 3: 
If G1 conforms to G2 and G2 has at least one path from s to t,
then PathSet[G1](G2) != {}.

Conjecture 4:
G2 is strongly embedded in G1 iff G1 conforms to G2. 

Conjecture 5:
If G2 is a subgraph of G1 then PathSet[G1](G2) != {}

Conjecture 6:
If G2 is strongly embedded in G1 then PathSet[G1](G2) != {}