Hi Mira:

I found two gems in your graph algorithms:

1.
Attaching code to strategy edges and

2.
Extending strategies with "reverse edges" to define derived edges.

I consider those to be very elegant and important improvements.

Re. 1:
Attaching code to strategy edges seems not be expressible 
elegantly with other means. In you example, you attach code to the
strategy edge: source.Graph->target.Adjacency
and it means that each time we go back to Graph and we find again
an Adjacency object, we need to update the component count.
The implementation of this will need some code in both
Graph and Adjacency. How is code attachment to strategy edges
implemented in general?

Re. 2:
I think the machinery in the strategies paper will be enough
to define a precise semantics of reverse edges.

Your example also nicely demonstrates how cycles in strategy graphs
are needed. You have a cycle from Adjacency through Vertex back to Adjacency.

-- Karl

From mira@ccs.neu.edu Tue Dec  2 17:49:58 1997
Subject: cycle-check and more
To: lieber@ccs.neu.edu (Karl Lieberherr)
Date: Tue, 2 Dec 1997 17:49:56 -0500 (EST)
Cc: dougo@ccs.neu.edu (Doug Orleans), johan@ccs.neu.edu (Johan Ovlinger)

Hi:

I have attached some first ideas about using the idea of generic visitors 
that are parameterized by strategies for implementing graph algorithms 
(my way of doing so). There might be some unintended deviations from existing
Dem/Java syntax because of my incomplete knowledge of Dem/Java and some
others which I needed for expressing things, which may or may not exist
in Dem/Java. However, I hope you will get a feeling about the technique.
We could discuss technical details during the seminar.

Again, any feedback is very welcome.

Thanks.

-- Mira

---------- cut here ---------

	First Ideas for Implementing Visitors for Graph Algorithms
	----------------------------------------------------------


StrategyType1 = from Graph to Adjucency to Vertex via: x
		               to Adjucency via: y.

	// Note that Graph, Adjucency, Vertex, as well as x and y 
        // are class-valued, respectively link-valued variables. 
        // Using these variable names instead of say A, B. C.
	// makes more intuitive that we are traversing a graph
        // going from the graph to each adjucency A in
        // its adjucency list and than to each vertex V included in 
        // the adjucency list and than 
        // recursively to the adjucency A1 of V. 
	// The visitors below are so-called domain specific visitors
	// ==> it's quite intuitive to use domain specific names
	// for class and link-valued names.

Q: How could we characterize this strategy type? Could we say that
   it has a source (== Graph) an intermediate (== Vertex) and a target 
   (== Adjucency)?
   Anyway, this assumtion is made in the definition of
   a generic DTFVisitor below.

GenericDFTVisitor(StrategyType1 s) {

	// We could also say:
	// GenericDFTVisitor(s: from Graph to Adjucency to Vertex via: x 
                               to Adjucency via: y)

	s.intermediate {
		change (@ this.doSomething;
			  next() @)

		// i.e. when at a vertex, we do what is implemented in
		// doSomething, and continue
                // the traversal to the adjucency list of this vertex.
		// This method is left abstract, so that
		// specific uses of the DFT provide a specific operation
		// to be done at each node during a dft-traversal. For 
		// example when we want top have the vertex set of the 
		// graph in their DFT order printed, doSomething would
		// simply print the vertex, while when the DFT visitor
		// get incrementally modified to perfom cycle checking
		// nothing will happen at the vertex objects.
		
		void doSomething {};

		} 

	s.target {
		boolean mark;
		init (@ amrk = false @)
		change (@ if !mark 
			    {mark = true;
			     next()} @)
	 }

   }

GenericCycleCheck{
	
	 Stack stack;
	 
	 s.target {

		change (@ if (stack.include(this)){
				System.out.println("cycle found");
				stack.print;
				}
				else {
					stack.push(this);
					next();
					// note that due to the fact that
					// next() is within the else 
					// statement the traversal will 
					// be automatically interrupted
					// when a cycle is found.
					stack.pop;
				}
		@)

	} modifies GenericDTF;

// Note that the GenericCycleCheck has no startegy as a parameter. In this
// case, i.e. in the case of a generic modifier visitor that has no
// strategy parameter, the strategy of the visitor being modified is
// implicitly the also the strategy of the modifier. 

The generic DFTVisitor can be used as the core of several other
graph algorithms. These has to specify a concrete doSomething.
A simple example is to simply print the name of each vertex:

GenericPrintingDFT{

	s.intermediate {
		doSomething() {this.print}
			}
}

Another example, I was thinking about is to adjust the generic DFT in
order to get a visitor for computing all connected components of 
a graph. One possiblity would be to use attaching functionality to 
strategy edges:

GenericConnectivityVisitor {
	
	Integer componentNumber;
	init (@ componentNumber = 0 @)
	
	s.source {

	   change (@ next();
		     System.out.println("there were altogether" + 
			componentNumber + "components");
		}

	s.source->target {
		target.startConnectedComponent(); 
	   }

	s.target {

		startConnectedComponent(){
			System.out.print("this is a new 
			connected component of the graph");
			componentNumber += 1;
			};

			// what we do with the connected component is 
			// implemented here. In the generic ConnectivityVisitor
			// the method is left abstract.

	   }

  } modifies GenericPrintDFT


Note that the strategy being passed as a parameter to GenericDTFVisitor
makes no commitment about the links that are used to go from Adjucency to
Vertex and vica versa. Thsi has to be specified when a concrete 
class graph that describes the straucture of graph objects is provided.
In the following, we consider the class graph that is presented in 
Fig. 8.8, pp. 213 in the AP book. In this class graph, once we
have arrived to an Adjucency object we want to go through its neighbors,
i.e. we want to go throgh the neighbors link to Vertex. Once at a 
Vertex, we want to go back to that Adjucency object that has the
Vertex object at hand as its source link. However, there is no 
link in the class graph that connects a Vertex to "its Adjucency",
i.e. to the adjucency object that has the vertex as its source.
What we need is a kind of derved link going in the opposite
direction of source. In the following. I use the notation:

	<-source 

for expressing this derived link.
I think that this notation is valuable for expressing in a structure-shy
way that we somehow need to compute the derived link from Vertex to 
the Adjucency that has Vertex as its source. 

<-source could be implementd in a similar way to transportation
patterns. When <-source is encountered, the generator should notice
that we need to go from v:Vertex back along the path:

	Graph ->adjucency-> Adjucency ->source-> Vertex

to the adjucency a:Adjucency, such that a.source == v.
This results in:
 
	1- transporting g:Graph along the dft traverse,
	   as a parameter of the generated dft, or cycle-ckeck methods.
	2- implementing the traversal code in Vertex as follows:
	
		For all adj in g.get-adjucency do
		  if adj.source == this then adj.dft (cycle-check respectively)

	 // Be careful, LoD is violated here :-) But, this is OK,
	 // since this code is generated. Furthermore, this is only
	 // a first idea about how to implement "reverse links"
	 // a la <-source.
				
After having said all that about reverse links, the above generic
dft and cycle checking functionality could be instantiated as 
follows for the class graph in Fig. 8.8. of the AP book.

s1 = from Graph to Adjucency to Vertex via *neighbors*
				to Adjucency via *<-source*
Graph{

  dft() is GenericDFT(s1);
  cycle-check is GenericCycleCheck(s1);

  }