import java.util.Stack;
import java.io.FileInputStream;
import java.io.FileOutputStream;

// the data structure for the graph searching
// method of edge linking.

Graph = "{" List(GraphNode) *l "}" *l.
GraphNode : EndNode | IntermediateNode common EdgeLoc NodeData .
EndNode : SourceNode | TargetNode common .
NodeData = <cost> int [ PathData ] .
PathData = "path" <pathCost> int <path> GraphNode.
IntermediateNode = "inode" [NodeList] *l.
SourceNode = "src" [NodeList] *l.
TargetNode = *l "target" *l.

NodeList = "list" <graphNodeList> ListP(GraphNode).

PixelCoord = "(" <x> int "," <y> int ")".
EdgeLoc = <left> PixelCoord <right> PixelCoord.

List(S) ~ { S }.
ListP(S) ~ "(" S {"," S } ")" .

Main = <s> String.


//////////////////////////////////////////////////////////
// datastructures for generating the graph edges and nodes
// from the source and target points.

GraphGenerator = <src> PixelCoord <target> PixelCoord [ LineEquation ] [<generatedGraph> Graph ].
LineEquation = <Slope> float <Constant> float <direction> int.


//////////////////////////////////////////////////////////
// File IO classes

Image = <height> int <width> int <maxPixelVal> int.



{
src (2,1) (2,0) 0
src (2,0) (2,1) 0
// vertical edges
inode (2,1) (1,1) 8
inode (3,1) (2,1) 2
inode (2,2) (1,2) 8
inode (3,2) (2,2) 0
inode (2,3) (1,3) 1
inode (3,3) (2,3) 9

// horizontal edges
inode (2,1) (2,2) 6
inode (2,2) (2,1) 8
inode (2,3) (2,2) 1
inode (2,2) (2,3) 13

// testing nodes for horizontal edges
// going straight
//inode (1,2) (1,1) 5
//inode (1,1) (1,2) 8
//inode (3,2) (3,1) 9
//inode (3,1) (3,2) 9


target (2,3) (2,4) 0
target (2,4) (2,3) 0

}// the behavior for calculating the cost of each edge.
GraphGenerator {
 
    {{ public static int InfiniteCost = Integer.MAX_VALUE; }}

    void calculateCost(Image im) 
	bypassing {PathData, NodeList} to GraphNode  {
	
	before IntermediateNode {{
	    int cost = GraphGenerator.InfiniteCost;
	    
	    if(!im.outsideImage(host.get_edgeloc().get_left()) 
	       && !im.outsideImage(host.get_edgeloc().get_right()) 
	       //&&host.hasOutgoinEdges()
	       ) {

		// get left pixel value
		int leftVal = im.getPixelVal(host.get_edgeloc().get_left());
		
		// get right pixel value
		int rightVal = im.getPixelVal(host.get_edgeloc().get_right());	    
		
		// calculate the cost
		cost = im.get_maxPixelVal() - (rightVal - leftVal);

		host.printNode();
		System.out.println("cost = "
				   + im.get_maxPixelVal()
				   + " - (" + rightVal + " - " + leftVal +")"); 
	    }

	    // set the cost
	    host.get_nodedata().set_cost(cost);

	}}
	
    }
}


GraphNode {
    

    {{
	public boolean hasOutgoinEdges() {
	    return false;
	}
	
	public boolean costIsInfinite() {
	    if (nodedata.cost == GraphGenerator.InfiniteCost)
		return true;
	    return false;
	}

	public boolean pathCostIsInfinite() {
	    int cost = getPathCost();
	    if (cost == GraphGenerator.InfiniteCost)
		return true;
	    return false;
	}

	public void setCostToInfinite() {
	    nodedata.cost = GraphGenerator.InfiniteCost;
	}

    }}
}

IntermediateNode {

    {{
	public boolean hasOutgoinEdges() {
	    if (nodelist != null)
		return true;
	    return false;
	}
    }}
}

SourceNode {

    {{
	public boolean hasOutgoinEdges() {
	    if (nodelist != null)
		return true;
	    return false;
	}
    }}
}


// The Main for the edge linking program
Main {
    public static void main(String args[]) throws Exception {{

	if (args.length < 9) {
	    System.out.println("Usage: edgelink [image file name] [height] [width] [startx] [starty] [endx] [endy] [width] [output file name]");

	    System.exit(-1);
	}
	
	String fileName = args[0];
	String imHeight = args[1];
	String imWidth = args[2];
	String startX = args[3];
	String startY = args[4];
	String targetX = args[5];
	String targetY = args[6];
	String width = args[7];
	String outputFileName = args[8];
	System.out.println("Processing file " + fileName);
	System.out.println("image size = " + imHeight + "x" + imWidth);
	System.out.println("src = ("+startX+","+startY+")" 
			   + "target = (" + targetX + ","+targetY+")");
	System.out.println("width = " + width);


	//Graph g = Graph.parse(System.in);
	//PrintVisitor pv = new PrintVisitor(System.out);
	//g.universal_trv0(pv);
	//pv.finish();
	//g.universal_trv0(new DisplayVisitor(System.out));
	//System.out.flush();
	//Graph.debug = true;
	Graph.printPath = true;
	// LineEquation.debgu = true;

	// set the source and target nodes
	PixelCoord src = PixelCoord.parse("("+startX+","+startY+")");
	PixelCoord target = PixelCoord.parse("("+targetX+"," + targetY+")");
	
	// create a new generator
	GraphGenerator newGen = new GraphGenerator(src, target);

	// read in the image file
	Image image = new Image(fileName, 
				Integer.parseInt(imHeight), 
				Integer.parseInt(imWidth));
	System.out.println("image max = " + image.get_maxPixelVal() );

	//image.print();

	// set the costs for all of the nodes
	newGen.calculateCost(image);
	
	PrintVisitor pv = new PrintVisitor(System.out);
	newGen.get_generatedGraph().universal_trv0(pv);
	pv.finish();

	// process the graph
	newGen.get_generatedGraph().ProcessGraph();

	// obtain the output edge image
	Image outputImage = image.sameSizeBlank();
	newGen.get_generatedGraph().getOutputImage(outputImage);
	
	//outputImage.print();
	
	outputImage.save(outputFileName);
    }}
}



Graph {

    // the debug variable to turn on and off the messages
    {{ public static boolean debug = false; }}

    // the variable for printing the shortest path
    {{ public static boolean printPath = false; }}

    // Method to process the Graph
    public void ProcessGraph() {{
	if (debug) System.out.println("PrcessGraph");

	// First Connect the Graph
	ConnectGraph();

	// Run the searching algorithm
	SearchGraph();
	
	// Output the shortest path for debug
	if (printPath) PrintShortestPath();

    }}

    //////////////////////////////////////////////////////////////
    // print the shortest path that was found
    public void PrintShortestPath() {{

	SourceNode path = findShortestSource();
	
	path.printPath();
	
    }}


    public SourceNode findShortestSource() 
	bypassing {NodeList, PathData} to SourceNode {
	{{ SourceNode returnVal = null; }}
	
	before SourceNode {{
	    if (returnVal == null)
		returnVal = host;
	    else if (returnVal.getPathCost() > host.getPathCost())
		returnVal = host;
	}}
	
	return SourceNode {{ returnVal; }}
    }


    //////////////////////////////////////////////////////////////
    // Search the graph for the shortest path
    public void SearchGraph() 
	bypassing {NodeList, PathData} to SourceNode {
	
	before SourceNode {{
	    if (Graph.debug) System.out.println("SearchStarted");
	    host.SearchGraph();
	    if (Graph.debug) System.out.println("SearchEnded");
	}}
    }

    //////////////////////////////////////////////////////////////
    // Connect the actual graph for the graph searching
    // algorithm.
    public void ConnectGraph() {{

	// get the graph node list
	GraphNode_List nodeList = get_graphnode_list();

	// for each node find it's possible exits
	findPossibleExits(nodeList);

    }}


    public void findPossibleExits(GraphNode_List nodelist)
	bypassing {PathData, ->*,tail,*, NodeList} to GraphNode {
	
	
	before SourceNode {{
	    if (Graph.debug) System.out.println("findPossibleExits");
	    //gather all exit nodes for 
	    NodeList exitNodes = nodelist.gatherExits(host.get_edgeloc());

	    if (exitNodes == null)
		host.setCostToInfinite();
	    
	    // set the exit nodes
	    host.set_nodelist(exitNodes);
	}}

	before IntermediateNode {{

	    NodeList exitNodes = null;

	    // gather all exit nodes for 
	    if (host.get_edgeloc() !=null) {
		exitNodes = nodelist.gatherExits(host.get_edgeloc());
	    }

	    if (exitNodes == null)
		host.setCostToInfinite();

	    // set the exit nodes
	    host.set_nodelist(exitNodes);
	}}

    }

    //////////////////////////////////////////////////////////////
    // generate the edge image
    public void getOutputImage(Image im) {{

	SourceNode path = findShortestSource();
	
	path.getOutputImage(im);
	
    }}


}


// method for source node
SourceNode {

        public void SearchGraph() 
	    bypassing {PathData, ->*,tail,* } to TargetNode {
	    
	    {{ Stack pathStack = new Stack(); }}
	    {{ SourceNode srcNode = null; }}
	    
	    before SourceNode {{
		srcNode = host;
		if (Graph.debug){
		    System.out.println("setting new src node");
		    host.printNode();
		    System.out.println();
		}
	    }}
	    
	    before IntermediateNode {{
		if (Graph.debug) {
		    System.out.println("Pushing node");
		    host.printNode();
		    System.out.println();
		}
		pathStack.push(host);
	    }}
	    
	    after IntermediateNode {{
		GraphNode foo = (GraphNode) pathStack.pop();

		if (Graph.debug) {
		    System.out.println("Poping node");
		    foo.printNode();
		    System.out.println();
		}
		
		GraphNode predecessor = null;

		if (pathStack.empty()) {
		    predecessor = srcNode;
		} else {
		    predecessor = (GraphNode) pathStack.peek();
		}
		
		int predPathCost = predecessor.getPathCost();


		// if My cost is infinite, then just forget
		// it, I'm not going to attempt to use me as the
		// optimal path, but need to set my predecessor
		// to infinite as well so that this path
		// won't be used
		if (host.costIsInfinite() || host.pathCostIsInfinite()) { 
		    if (predPathCost == -1)
			predecessor.setPathCostToInfinite();
		    return;
		}

		int myCost = host.getCost();
		int myPathCost = host.getPathCost();
		int myNewPathCost = myCost + myPathCost;
		
		if (Graph.debug) System.out.println("prePathCost = " + predPathCost 
						    + " myNewPathCost = " + myNewPathCost);
		
		if (predPathCost == -1 || myNewPathCost < predPathCost) {
		    if (Graph.debug) {
			System.out.println("Setting new path with cost " + myNewPathCost);
			host.printNode();
			System.out.println();
		    }
		    predecessor.setNewPath(myNewPathCost, host);
		}
	    }}
	    
	    
	    after TargetNode {{
		
		GraphNode predecessor = null;
		if (pathStack.empty()) {
		    predecessor = srcNode;
		} else {
		    predecessor = (GraphNode) pathStack.peek();
		}
		
		int predPathCost = predecessor.getPathCost();
		int myNewPathCost = host.getCost();
		
		if (predPathCost == -1 || myNewPathCost < predPathCost) {
		    if (Graph.debug) {
			System.out.println("Setting new path with cost " + myNewPathCost);
			host.printNode();
			System.out.println();
		    }
		    predecessor.setNewPath(myNewPathCost, host);
		}		
	    }}
	    
	}



    public void printPath() 
	bypassing NodeList to TargetNode {
	{{ PrintVisitor pv = new PrintVisitor(System.out); }}
	
	before SourceNode {{
	    System.out.println("Shortest Path with cost " + host.getPathCost());
	    host.printNode(pv);
	    System.out.println();
	}}
	
	before IntermediateNode {{
	    host.printNode(pv);	    
	    System.out.println();
	}}
	
	before TargetNode {{
	    host.printNode(pv);
	    System.out.println();
	}}
	
    }

    public void getOutputImage(Image im) 
	bypassing NodeList to TargetNode {
	{{ PrintVisitor pv = new PrintVisitor(System.out); }}
	
	before SourceNode {{
	    //System.out.println("Shortest Path with cost " + host.getPathCost());
	    //host.printNode(pv);
	    //System.out.println();
	}}
	
	before IntermediateNode {{
	    im.setPixel(host.get_edgeloc().get_right(), 1);
	    //host.printNode(pv);	    
	    //System.out.println();
	}}
	
	before TargetNode {{
	    //host.printNode(pv);
	    //System.out.println();
	}}
	
    }
    
}

// methods for GraphNode

GraphNode {

    public void printNode() {{
	printNode(new PrintVisitor(System.out));
    }}

    // printNode
    public void printNode(PrintVisitor pv) {{
        get_edgeloc().universal_trv0(pv);
	pv.finish();
	System.out.print(getCost());
    }}

    // getPathCost
    public int getPathCost() 
        bypassing {PathData, NodeList} to NodeData {

	{{ int returnVal = -1; }}

	before NodeData {{
	    if (host.get_pathdata() != null)
		returnVal = host.get_pathdata().get_pathCost();
	}}

	return int {{ returnVal }}

    }
    
    // getCost
    public int getCost() 
	bypassing {PathData, NodeList} to NodeData {

	{{ int returnVal = 0; }}

	before NodeData {{
	    returnVal = host.get_cost();
	}}

	return int {{ returnVal }}

    }

    // setNewPath
    public void setNewPath(int newCost, GraphNode newPath) 
	bypassing {PathData, NodeList} to NodeData {

	before NodeData {{
	    PathData thisPath = null;
	    if (host.get_pathdata() == null) {
		host.set_pathdata(new PathData(newCost, newPath));
	    } else {
		host.get_pathdata().set_pathCost(newCost);
		host.get_pathdata().set_path(newPath);
	    }
	}}
	
    }

    // setNewPathCost
    public void setPathCostToInfinite() 
	bypassing {PathData, NodeList} to NodeData {
	    
	    before NodeData {{
		PathData thisPath = null;
		if (host.get_pathdata() == null) {
		    host.set_pathdata(new PathData(GraphGenerator.InfiniteCost, null));
		} else {
		    host.get_pathdata().set_pathCost(GraphGenerator.InfiniteCost);		
		}
	    }}
	}
}

// method for intermediate node list
GraphNode_List {


    {{ 
	public NodeList gatherExits(EdgeLoc edgeloc) {
	    NodeList returnVal = gatherExitsWrapper(edgeloc);

	    if (returnVal.get_graphNodeList() == null)
		return null;

	    return returnVal;
	}
    }}

    public NodeList gatherExitsWrapper(EdgeLoc edgeloc)
	bypassing {NodeList, PathData} to GraphNode {

	{{ NodeList returnNodeList = new NodeList(); }}

	before GraphNode {{

	    EdgeLoc thisEdgeLoc = host.get_edgeloc();
	    if (thisEdgeLoc.isExitOf(edgeloc)) {
		if (Graph.debug) {
		    PrintVisitor pv = new PrintVisitor(System.out);
		    System.out.println("Exit for:");
		    edgeloc.universal_trv0(pv);
		    pv.finish();
		    System.out.println();
		    System.out.println("is:");
		    thisEdgeLoc.universal_trv0(pv);
		    pv.finish();
		    System.out.println();
		}

		returnNodeList.addGraphNode(host);
	    }
	}}

	return NodeList {{ returnNodeList }}
    }
}


// code for NodeList
NodeList {

    public void addGraphNode(GraphNode node) {{
	if (graphNodeList == null)
	    graphNodeList = new GraphNode_ListP();
	graphNodeList.addElement(node);
    }}

}

// code for edgeloc
EdgeLoc {

    public boolean isExitOf(EdgeLoc src) {{

	// is the exit of src edge if, 
	// turning left, 
	// turning right, 
	// or is continuing in the same direction.
	if (isTurningLeft(src)
	    || isTurningRight(src)
	    || isSameDirection(src))
	    return true;
	else return false;
    }}

    public boolean isTurningLeft(EdgeLoc src) {{
	PixelCoord srcLeft = src.get_left();
	PixelCoord srcRight = src.get_right();
	PixelCoord myLeft = get_left();
	PixelCoord myRight = get_right();

	// if my left is equal to the src's left then
	// we're turning left. We have 4 cases,
	// -1,1 1,1 1,-1 -1,-1
	if (myLeft.isEqual(srcLeft)) {
	    int srcx = srcRight.get_x();
	    int srcy = srcRight.get_y();
	    int myx = myRight.get_x();
	    int myy = myRight.get_y();
	    if(((srcLeft.get_x() == srcx) 
		&& (((srcx-1) == myx && (srcy+1) == myy)
		    ||((srcx+1) == myx && (srcy-1) == myy)))
	       || ((srcLeft.get_y() == srcy)
		&& (((srcx+1) == myx && (srcy+1) == myy)
		    ||((srcx-1) == myx && (srcy-1) == myy)))) {
		if (Graph.debug) System.out.println("turning left");
		return true;
	    }
	}
	return false;
    }}

    public boolean isTurningRight(EdgeLoc src) {{
	PixelCoord srcLeft = src.get_left();
	PixelCoord srcRight = src.get_right();
	PixelCoord myLeft = get_left();
	PixelCoord myRight = get_right();

	// if my right is equal to the src's right then
	// we're turning right. We have 4 cases,
	// -1,1 1,1 1,-1 -1,-1
	if (myRight.isEqual(srcRight)) {
	    int srcx = srcLeft.get_x();
	    int srcy = srcLeft.get_y();
	    int myx = myLeft.get_x();
	    int myy = myLeft.get_y();
	    if(((srcRight.get_y() == srcy) 
		&& (((srcx-1) == myx && (srcy+1) == myy)
		    ||((srcx+1) == myx && (srcy-1) == myy)))
	       || ((srcRight.get_x() == srcx)
		&& (((srcx+1) == myx && (srcy+1) == myy)
		    ||((srcx-1) == myx && (srcy-1) == myy)))) {
		if (Graph.debug) System.out.println("Turing Right");
		return true;
	    }
	}
	return false;
    }}

    public boolean isSameDirection(EdgeLoc src) {{
	
	PixelCoord srcLeft = src.get_left();
	PixelCoord srcRight = src.get_right();
	PixelCoord myLeft = get_left();
	PixelCoord myRight = get_right();
	// we're contiuing down the same direction if
	// going vertical, 
	// going horizonal, 

	if (srcLeft.get_y() == srcRight.get_y()
	    && myLeft.get_y() == myRight.get_y()
	    && srcLeft.get_x() == myLeft.get_x()
	    && srcRight.get_x() == myRight.get_x()
	    ) {
	    
	    int direction = srcRight.get_x()- srcLeft.get_x();
	    int leftDiff = srcLeft.get_y() - myLeft.get_y();
	    int rightDiff = srcRight.get_y() - myRight.get_y();

	    if ( leftDiff == rightDiff
		&& (leftDiff*direction == 1)
		 ) {
		if (Graph.debug) System.out.println("Same direction");
		return true;
	    }

	} else if (srcLeft.get_x() == srcRight.get_x()
	    && myLeft.get_x() == myRight.get_x()
	    && srcLeft.get_y() == myLeft.get_y()
	    && srcRight.get_y() == myRight.get_y()
	    ) {
	    
	    int direction = srcLeft.get_y() - srcRight.get_y();
	    int leftDiff = srcLeft.get_x() - myLeft.get_x();
	    int rightDiff = srcRight.get_x() - myRight.get_x();

	    if ( leftDiff == rightDiff
		&& (leftDiff*direction == 1)
		) {
		if (Graph.debug) System.out.println("Same direction");
		return true;
	    }

	} 
	
	return false;
    }}
}


PixelCoord {

    public boolean isEqual(PixelCoord right) {{
	if (get_x() == right.get_x() 
	    && get_y() == right.get_y())
	    return true;
	return false;
    }}

}
// behavior file for generating the graph for the
// graph edge linking algorithm

GraphGenerator {
    {{  
	GraphGenerator(PixelCoord _src, PixelCoord _target) {
	    src = _src;
	    target = _target;
	    lineequation = new LineEquation(_src, _target);
	    generatedGraph = new Graph(new GraphNode_List());
	    generateGraph();
	}
	
	public void generateGraph() {
	    // first add edges for the source and destination
	    int direction = lineequation.get_direction();
	    lineequation.processSource(generatedGraph, src, direction);
	    lineequation.processDest(generatedGraph, target, direction);
	    
	    // add edges along the line
	    if (!lineequation.isVerticalLine())
		lineequation.processNonVerticalEdges(generatedGraph, src.get_x(), target.get_x());
	    else
		lineequation.processVerticalEdges(generatedGraph, src.get_y(), target.get_y());
	    
	}

    }}
}


LineEquation {

    {{
	// print debug info
	boolean debug = false;

	// true if it's a vertical line
	boolean _isVerticalLine=false;
	

	// the defintion for direction
	static int N = 0;
	static int S = 1;	
	static int E = 2;	
	static int W = 3;
	static int NE = 4;
	static int NW = 5;
	static int SE = 6;
	static int SW = 7;
	
	LineEquation(PixelCoord _src, PixelCoord _target) {
	    float deltaY = _target.get_y() - _src.get_y();
	    float deltaX = _target.get_x() - _src.get_x();
	    
	    if (deltaX == 0) {
		_isVerticalLine = true;
		Constant = _target.get_x();
		if (debug) System.out.println("New Vertical Line");
	    } else {
		Slope = deltaY/deltaX;
		Constant = _src.get_y() - Slope * _src.get_x();
		if (debug) System.out.println("New Line Equation with slope="
					      +Slope+" const="+Constant);
	    }
	    
	    // determine the direction of the path

	    // if delta y is greater than 0 then  we're going south
	    if (deltaY >= 0) {

		// deltaY dominate so we decide between vertical directions
		if (deltaX >= 0 && deltaY > deltaX)
		    direction = S;
		if (deltaX < 0 && deltaY >= deltaX*-1)
		    direction = S;

		// the deltaX dominate so we choose between horizontal directions
		if (deltaX > 0 && deltaY <= deltaX)
		    direction = E;
		if (deltaX < 0 && deltaY <= deltaX*-1)
		    direction = W;

		// else deltaY < 0  
	    } else {
		float posDeltaY = deltaY*-1;

		// deltaY dominate so we decide between vertical directions
		if (deltaX >= 0 && posDeltaY > deltaX)
		    direction = N;
		if (deltaX < 0 && posDeltaY >= deltaX*-1)
		    direction = N;

		// the deltaX dominate so we choose between horizontal directions
		if (deltaX > 0 && posDeltaY <= deltaX)
		    direction = E;
		if (deltaX < 0 && posDeltaY <= deltaX*-1)
		    direction = W;
	    }
	    
	    if (debug) System.out.println("direction = " + direction);

	}

	boolean isVerticalLine() {
	    return _isVerticalLine;
	}
	
	float getY(float x) {
	    float floatX = (float) x;
	    float floatY = Slope * floatX + Constant;
	    if (debug) System.out.println("x="+x+"y="+floatY);
	    return floatY;
	}
	

	protected void processSource(Graph graph, PixelCoord src, int direction) {
	    PixelCoord otherSide=null;

	    if (direction == N) {
		otherSide = PixelCoord.parse("(" + src.get_x() + ","+(src.get_y() +1) +")" );
	    } else if (direction == S) {
		otherSide = PixelCoord.parse("(" + src.get_x() + ","+(src.get_y() -1) +")" );		
	    } else if (direction == W) {
		otherSide = PixelCoord.parse("(" + (src.get_x()+1) + ","+src.get_y() +")" );				
	    } else if (direction == E) {
		otherSide = PixelCoord.parse("(" + (src.get_x()-1) + ","+src.get_y() +")" );
	    }
	    // add the edges
	    graph.get_graphnode_list().addElement(new SourceNode(src, otherSide));
	    graph.get_graphnode_list().addElement(new SourceNode(otherSide, src));	    
	}

	protected void processDest(Graph graph, PixelCoord src, int direction) {
	    PixelCoord otherSide=null;

	    if (direction == N) {
		otherSide = PixelCoord.parse("(" + src.get_x() + ","+(src.get_y() -1) +")" );
	    } else if (direction == S) {
		otherSide = PixelCoord.parse("(" + src.get_x() + ","+(src.get_y() +1) +")" );		
	    } else if (direction == W) {
		otherSide = PixelCoord.parse("(" + (src.get_x()-1) + ","+src.get_y() +")" );				
	    } else if (direction == E) {
		otherSide = PixelCoord.parse("(" + (src.get_x()+1) + ","+src.get_y() +")" );
	    }
	    // add the edges
	    graph.get_graphnode_list().addElement(new TargetNode(src, otherSide));
	    graph.get_graphnode_list().addElement(new TargetNode(otherSide, src));	    
	}


	public void processVerticalEdges(Graph graph, int starty, int endy){
	    if (direction != N && direction != S) 
		System.out.println("Error for processing vertical edges, no vertical direction!");

	    int xval = (int)Constant;
	    int begin; 
	    int finish;
	    
	    if (starty > endy) {
		begin = endy;
		finish = starty;
	    } else {
		begin = starty;
		finish = endy;
	    }	    
	    
	    for (int y = begin; y < finish; y++) {
		processPoint(graph, xval, y);		
	    }
	    int width = 2;
	    processLastPoint(graph, xval, finish, width);
	}

	public void processNonVerticalEdges(Graph graph, int startx, int endx){

	    int beginx; 
	    int finishx;
	    
	    if (startx > endx) {
		beginx = endx;
		finishx = startx;
	    } else {
		beginx = startx;
		finishx = endx;
	    }
	    
	    if (debug) System.out.println("beginx = " + beginx + " finishx = " + finishx);
	    
	    // loop through each of the pixels in the line connecting the source and
	    // destination
	    for (int x = beginx; x < finishx; x++) {
		
		
		// number of steps for each delta x = 1
		float stepVal = 1/abs(Slope);
		float runningVal = (float)x;
		int steps = (int) abs(Slope);
		
		if (debug) System.out.println("stepval = " + stepVal 
					      + " runningVal = " + runningVal + " steps = " + steps);
		
		for (int s = 0; s <= steps ; s++) {
		    int yval = (int)getY(runningVal);
		    runningVal = runningVal + stepVal;
		    
		    if (debug) System.out.println("yval=" + yval + " runningval="+runningVal);
		    // for each point add edges
		    processPoint(graph, x, yval);
		}
		
	    }

	    int width = 2;
	    processLastPoint(graph, finishx, (int)getY(finishx), width);
	    
	}
    
	public void processLastPoint(Graph graph, int x, int yval, int width) {
	    addLeftEdge(graph,x, yval);
	    for (int v = 1; v < width; v++) {
		if (direction == N || direction == S) {
		    addLeftEdge(graph,x+v, yval);
		    addLeftEdge(graph,x-v, yval);
		} else if (direction == W || direction == E) {
		    addLeftEdge(graph,x, yval+v);
		    addLeftEdge(graph,x, yval-v);
		}
	    }
	    addRightEdge(graph, x, yval, width);
	    
	}
	
	public void processPoint(Graph graph, int x, int yval) {
	    int width = 2;

	    addIntermediatePoint(graph,x, yval);
	    for (int v = 1; v < width; v++) {
		if (direction == N || direction == S) {
		    addIntermediatePoint(graph,x+v, yval);
		    addIntermediatePoint(graph,x-v, yval);
		} else if (direction == W || direction == E) {
		    addIntermediatePoint(graph,x, yval+v);
		    addIntermediatePoint(graph,x, yval-v);
		}
	    }
	    addRightEdge(graph, x, yval, width);
	}

	public void addLeftEdge(Graph graph, int x, int yval) {

	    PixelCoord src = PixelCoord.parse("("+(x)+","+yval+")");
	    PixelCoord parallel = null;
	    
	    if (direction == N) {
		parallel = PixelCoord.parse("(" + (x-1) + ","+ yval +")" );
	    } else if (direction == S) {
		parallel = PixelCoord.parse("(" + (x+1) + ","+ yval +")" );
	    } else if (direction == W) {
		parallel = PixelCoord.parse("(" + x + ","+ (yval+1) +")" );
	    } else if (direction == E) {
		parallel = PixelCoord.parse("(" + x + ","+ (yval-1) +")" );
	    }

	    // add the edges
	    graph.get_graphnode_list().addElement(new IntermediateNode(parallel, src));	    
	
	    if (debug) {
		System.out.print("Adding right edge:");
		PrintVisitor pv = new PrintVisitor(System.out);
		src.universal_trv0(pv);
		parallel.universal_trv0(pv);
		pv.finish();
		System.out.println();
	    }

	}
	public void addRightEdge(Graph graph, int x, int yval, int width) {

	    PixelCoord src = null;
	    PixelCoord parallel = null;
	    
	    if (direction == N) {
		src = PixelCoord.parse("("+(x+width-1)+","+yval+")");
		parallel = PixelCoord.parse("(" + (x+width) + ","+ yval +")" );
	    } else if (direction == S) {
		src = PixelCoord.parse("("+(x-width+1)+","+yval+")");
		parallel = PixelCoord.parse("(" + (x-width) + ","+ yval +")" );
	    } else if (direction == W) {
		src = PixelCoord.parse("("+x+","+(yval-width+1)+")");
		parallel = PixelCoord.parse("(" + x + ","+ (yval-width) +")" );
	    } else if (direction == E) {
		src = PixelCoord.parse("("+x+","+(yval+width-1)+")");
		parallel = PixelCoord.parse("(" + x + ","+ (yval+width) +")" );
	    }

	    // add the edges
	    graph.get_graphnode_list().addElement(new IntermediateNode(src, parallel));	    
	
	    if (debug) {
		System.out.print("Adding right edge:");
		PrintVisitor pv = new PrintVisitor(System.out);
		src.universal_trv0(pv);
		parallel.universal_trv0(pv);
		pv.finish();
		System.out.println();
	    }

	}

	public void addIntermediatePoint(Graph graph, int x, int yval) {

	    PixelCoord src = PixelCoord.parse("("+x+","+yval+")");
	    PixelCoord otherSide=null;
	    PixelCoord parallel = null;
	    
	    if (direction == N) {
		otherSide = PixelCoord.parse("(" + x + ","+ (yval -1) +")" );
		parallel = PixelCoord.parse("(" + (x-1) + ","+ yval +")" );
	    } else if (direction == S) {
		otherSide = PixelCoord.parse("(" + x + ","+(yval +1) +")" );		
		parallel = PixelCoord.parse("(" + (x+1) + ","+ yval +")" );
	    } else if (direction == W) {
		otherSide = PixelCoord.parse("(" + (x-1) + ","+yval +")" );				
		parallel = PixelCoord.parse("(" + x + ","+ (yval+1) +")" );
	    } else if (direction == E) {
		otherSide = PixelCoord.parse("(" + (x+1) + ","+yval +")" );
		parallel = PixelCoord.parse("(" + x + ","+ (yval-1) +")" );
	    }
	    // add the edges
	    graph.get_graphnode_list().addElement(new IntermediateNode(src, otherSide));
	    graph.get_graphnode_list().addElement(new IntermediateNode(otherSide, src));	    
	    graph.get_graphnode_list().addElement(new IntermediateNode(parallel, src));	    
	
	    if (debug) {
		System.out.print("Adding edges for nodes:");
		PrintVisitor pv = new PrintVisitor(System.out);
		src.universal_trv0(pv);
		otherSide.universal_trv0(pv);
		parallel.universal_trv0(pv);
		pv.finish();
		System.out.println();
	    }
	}
	
	public static float abs(float x) { 
	    if (x < 0) return x*-1;
	    return x;
	}
    }}
    
}


SourceNode {

    {{
	public SourceNode(PixelCoord left, PixelCoord right) {
	    super();
	    set_edgeloc(new EdgeLoc(left, right));
	    set_nodedata(new NodeData(0, null));
	}
    }}
}

TargetNode {

    {{
	public TargetNode(PixelCoord left, PixelCoord right) {
	    super();
	    set_edgeloc(new EdgeLoc(left, right));
	    set_nodedata(new NodeData(0, null));
	}
    }}
}

IntermediateNode {

    {{
	public IntermediateNode(PixelCoord left, PixelCoord right) {
	    super();
	    set_edgeloc(new EdgeLoc(left, right));
	    set_nodedata(new NodeData(0, null));
	}
    }}
}
// the behavior for the image handling

Image {
    {{ byte [][] im;}}
    
    {{
	Image(String fname, int h, int w) {
	    height = h;
	    width = w;
	    im = readImageFromFile(fname, h, w);
	    maxPixelVal = caculateMax();
	}
	

	int caculateMax() {
	    int max = 0;
	    for (int y=0; y<height; y++) {
		for (int x=0; x<width; x++) {
		    if (max < im[y][x])
			max = im[y][x];
		}
	    }
	    return max;
	}

	byte [][] readImageFromFile(String fname, int h, int w) {
	    byte [][] returnByte = new byte[h][w];
	    try { 
		FileInputStream in = new FileInputStream(fname);
		for(int x=0; x<h; x++) {
		    in.read(returnByte[x]);
		}

	    } catch (Exception e) {
		System.out.println(e);
	    }
	    return returnByte;
	}

	boolean outsideImage(PixelCoord pixel) {
	    int x = pixel.get_x();
	    int y = pixel.get_y();
	    if (x < 1 || y < 1)
		return true;
	    if (x > width || y > height)
		return true;
	    return false;
	}
	
	void setPixel(int x, int y, int val) {
	    im[y-1][x-1] = (byte) val;
	}

	void setPixel(PixelCoord pixel, int val) {
	    setPixel(pixel.get_x(), pixel.get_y(), val);
	}


	int getPixelVal(int x, int y) {
	    return im[y-1][x-1];
	    
	}

	int getPixelVal(PixelCoord pixel) {
	    return getPixelVal(pixel.get_x(), pixel.get_y());
	}

	

	void save(String fname) {
	    try {
		FileOutputStream out = new FileOutputStream(fname);
		for (int x=0; x<height; x++) {
		    out.write(im[x]);
		}
		out.close();
	    } catch (Exception e) {
		System.out.println(e);
	    }
	}

	void print() {
	    for (int y=0; y<height; y++) {
		for (int x=0; x<width; x++) {
		    System.out.print((int)im[y][x] + " ");
		}
		System.out.println();
	    }
	    
	}

	Image sameSizeBlank() {
	    Image imCopy = new Image();
	    
	    imCopy.height = height;
	    imCopy.width = width;
	    imCopy.im = new byte[height][width];

	    for (int y = 0; y < height; y++) {
		for (int x = 0; x < width; x++) {
		    imCopy.im[y][x] = 0;
		}
	    }

	    return imCopy;
	}

	Image copy() {
	    Image imCopy = new Image();

	    imCopy.height = height;
	    imCopy.width = width;

	    for (int y = 0; y < height; y++) {
		for (int x = 0; x < width; x++) {
		    imCopy.im[y][x] = im[y][x];
		}
	    }

	    return imCopy;
	}

    }}
}