Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  /*
   * This program is free software; you can redistribute it and/or modify it under the
   * terms of the GNU Lesser General Public License, version 2.1 as published by the Free Software
   * Foundation.
   *
   * You should have received a copy of the GNU Lesser General Public License along with this
   * program; if not, you can obtain a copy at http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html
   * or from the Free Software Foundation, Inc.,
   * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  *
  * This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
  * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  * See the GNU Lesser General Public License for more details.
  *
  * Copyright (c) 2006 - 20011 Pentaho Corporation..  All rights reserved.
  * 
  * Contributed by Nick Coleman
  */
 package org.pentaho.metadata.query.impl.sql.graph;
 
 import java.util.List;
 import java.util.Map;
 
Class that build a Node-Arc graph based on BusinesTable and RelationshipMeta objects specified in a BusinessModel. It attempts to use Arc Consistency Optimization to find a Path that utilizes the smallest number of relationships to include a list of required tables.
 
 public class MqlGraph implements GraphElementChangeListener {
 	private static final Log logger = LogFactory.getLog(MqlGraph.class);
 
 	private List<Nodenodes;
 	private List<Arcarcs;
 	private boolean needsReset = false;

Creates a new graph for a business model

Parameters:
model Business model to base graph upon
 
 	@SuppressWarnings("unchecked")
 	public MqlGraph(LogicalModel model) {
 		this. = new ArrayList<Node>();
 		this. = new ArrayList<Arc>();
 		this. = new HashMap<LogicalTableNode>();
 		
 		// build the graph for this model
 	}

Calculates and returns a path that satisfies the required tables list or null if one cannot be found

Parameters:
requiredTables Tables that are required to be in path
Returns:
Path with smallest number of relationships to ensure all required tables are included
 
 	public Path getPath(PathType searchTechniqueList<LogicalTablerequiredTables) {
 		// if reset works and validity check passes, build path
 		if (reset(requiredTables) && isValid(searchTechnique)) {
 			.debug("Path determined sucessfully");
 			
 			Path path = new Path();
 			for (Arc arc) {
 				if (arc.isRequired()) {
 				  if ( .isDebugEnabled() ) .debug("Arc selected for path: " + arc);
 				}
 				else
 				  if ( .isDebugEnabled() ) .debug("Arc not used for path: Requirement Known[" + arc.isRequirementKnown() + "], Required[" + arc.isRequired() + "]");
 			}
 			
 			if (.isDebugEnabled()) {
 				for (Node n)
 				  if ( .isDebugEnabled() ) .debug("Node selection state: Requirement Known[" + n.isRequirementKnown() + "], Required[" + n.isRequired() + "]");
 			}
 			if (path.size()>0)
				return path;
		}
		return null;
	}

Resets this graph before locating a path
	private boolean reset(List<LogicalTablerequiredTables) {
		try {
			// reset required tables and nodes
			this. = requiredTables;
			if () {
				if (this.!=null)
				for (Node n)
				for (Arc a)
			}
			else {
				this. = true;
			}
			// initialize nodes
			for (Node n) {
				if (requiredTables.contains(n.getTable())) {
				}
			}
			return true;
		}
		  .debug("failed to reset"cx);
			return false;
		}
	}

Calculates graph validity
	private boolean isValid(PathType searchTechnique) {
		// remove all arcs from queue
		// initialize node queue with all nodes in graph
		try {
			// check for all search technique
			if (searchTechnique == .) {
				for (Node n)
				for (Arc a)
			}
			// start by making initial graph consistent
			// search to test assigning a requirement setting
			// to tables not yet determined
			search(searchTechnique);
			return true;
		}
		  .debug("failed to validate"cx);
			return false;
		}
	}

Performs work necessary to bind all nodes that have not been assigned a requirement value yet

Parameters:
searchTechnique Indicates type of search that should be performed
Throws:
ConsistencyException When determine that graph is impossible to satisfy
	private void search(PathType searchTechniquethrows ConsistencyException {
		// locate first solution
		Solution bestKnown = searchForNextSolution(searchTechniquenull);
		if ( .isDebugEnabled() ) .debug("initial solution found - Rating[" + bestKnown.getRating() + "]");
		// for paths looking for the best rating, continue until we can't find a better solution
		if (searchTechnique == . || searchTechnique == .) {
			try {
				Solution lastSolution = bestKnown;
				while(lastSolution != null) {
				  .debug("continuing search for more solutions from last one located");
					lastSolution = searchForNextSolution(searchTechniquelastSolution);
					if ( .isDebugEnabled() ) .debug("new solution located - Rating[" + bestKnown.getRating() + "]");
					if (lastSolution != null) {
					  if (.isTraceEnabled()) .trace("New solution is better than previously best known, continuing from it");
						bestKnown = lastSolution;
					}
				}
			}
			  .debug("failed while looking for more solutions"cx);
				// no need to do anything if no more solutions exist since we already have a best solution
			}
			// reset the search function before we can return to best solution
			.debug("returning to best known solution");
			// recreate path for best known solution
			Iterator<ArcarcIter = bestKnown.getSearchArcs().iterator();
			for (SearchDirection directionbestKnown.getSearchPath()) {
				// all of these operations should work without issue
				Arc arc = arcIter.next();
				if (!attemptArcAssignment(arcdirection))
					throw new ConsistencyException(arc);
			}
		}
	}

Attempts to find next valid solution to the graph depending on what type of PathType is desired.

Parameters:
searchTechnique Indicates type of search that should be performed
prevSolution Previous solution to allow this search to continue from that point
Returns:
rating for the resulting solution
Throws:
ConsistencyException When determine that graph is impossible to satisfy
	private Solution searchForNextSolution(PathType searchTechniqueSolution prevSolutionthrows ConsistencyException {
		// A left move equates to setting a requirement to false and a right move is equivalent to true.
		// Try setting to "false" first to reduce the number of tables for most searches.
		// For the "any relevant" search use "true" first which is quicker
		SearchDirection firstDirection;
		SearchDirection secondDirection;
		if (searchTechnique == .) {
			firstDirection = .;
			secondDirection = .;
		}
		else {
			firstDirection = .;
			secondDirection = .;
		}
		// if this is a subsequent search after a solution was already found, we need
		// to return to the location where the last move in the first direction was made
		List<SearchDirectionsearchPath  = new LinkedList<SearchDirection>();
		List<ArcsearchArcs  = new LinkedList<Arc>();
		if (prevSolution!=null) {
			ListIterator<SearchDirectionpathIter = searchPath.listIterator(searchPath.size());
			// continue to move back in search path until we find an arc that can
			// be assigned the second direction
			while (pathIter.hasPrevious()) {
				// reset the search function for next search operation
				searchPath.clear();
				searchArcs.clear();
				// locate the last move that has an alternative
				while (pathIter.hasPrevious()) {
					SearchDirection direction = pathIter.previous();
					if (direction == firstDirection)
						break;
				}
				// recreate path up to point where we can try a different direction
				Iterator<ArcarcIter = prevSolution.getSearchArcs().iterator();
				if (pathIter.hasPrevious()) {
					Iterator<SearchDirection>  redoIter = prevSolution.getSearchPath().iterator();
					int lastIdx = pathIter.previousIndex();
					for (int idx=0; idx<=lastIdxidx++) {
						// all of these operations should work without issue
						SearchDirection direction = redoIter.next();
						Arc arc = arcIter.next();
						if (!attemptArcAssignment(arcdirection))
							throw new ConsistencyException(arc);
						// add movement to newly constructed search path
						searchPath.add(direction);
						searchArcs.add(arc);
					}
				}
				// retrieve arc which we are going to move second direction
				Arc arc = arcIter.next();
				// if we can't move the second direction here, continue
				// to move back in search path until we find an arc that can
				// be assigned the second direction
				if (attemptArcAssignment(arcsecondDirection)) {
					// update new search path
					searchPath.add(secondDirection);
					searchArcs.add(arc);
					// before any searching will begin, make sure the path we are going down shouldn't
					// just be skipped
					try {
						checkCurrentStateForImprovement(searchTechniqueprevSolution.getRating());
						break;
					}
					catch(ConsistencyException cx) {}
				}
			}
			// if we weren't able to make another movement, there are not more solutions
			if (searchPath.size()==0) return null;
		}
		// dump current state of graph
		  .debug("-- Graph State Before Search --");
		}
		// look for arcs that are not bound
		int rating = -1;
		for (Arc a) {
			if (!a.isRequirementKnown()) {
				// try the first direction
				if (attemptArcAssignment(afirstDirection))
					searchPath.add(firstDirection);
				// if first direction fails, try the second
				else if (attemptArcAssignment(asecondDirection))
					searchPath.add(secondDirection);
				// If arc cannot be assigned a requirement value, throw an exception
				else
					throw new ConsistencyException(a);
				// record arc that was altered in search path
				searchArcs.add(a);
				// make sure solution is getting better
				if (prevSolution != null)
					rating = checkCurrentStateForImprovement(searchTechniqueprevSolution.getRating());
			}
		}
		// compute rating if never computed
		if (rating < 0)
			rating = checkCurrentStateForImprovement(searchTechnique.);
		// return solution to graph problem
		Solution s = new Solution(ratingsearchPathsearchArcs);
		return s;
	}
	private void dumpStateToLog() {
	  if (.isDebugEnabled()) {
  		.debug("-------------------------------------------------");
  		
  		for (Arc arc)
  			if (arc.isRequired())
  				.debug(arc + "-> Yes");
  			else if (arc.isNotRequired())
  				.debug(arc + "-> No");
  			else
  				.debug(arc + "-> ?");
  		
  		for (Node n)
  			if (n.isRequired())
  				.debug(n + "-> Yes");
  			else if (n.isNotRequired())
  				.debug(n + "-> No");
  			else
  				.debug(n + "-> ?");
  		
  		.debug("=================================================");
	  }
	}

Checks that the current state of the graph is better than (or has the potential to be better) than a minimum required value.

Parameters:
searchTechnique Technique being used in searching to determine rating method
minRating Minimum value that solution must be better than
Throws:
ConsistencyException If current state of graph is not better than minimum rating
	private int checkCurrentStateForImprovement(PathType searchTechniqueint minRatingthrows ConsistencyException {
		int rating = 0;
		switch(searchTechnique) {
			case :
				for (Node n)
					if (n.isRequired())
						rating++;
				break;
				for (Node n)
					if (n.isRequired()) {
					  // If relative size is not null, use it, otherwise, increment by just 1
						rating += (relSize != null) ? (relSize  + 1) : 1;
					}
				break;
			default:
				return 0;
		}
		if (rating >= minRating)
			throw new ConsistencyException();
		return rating;
	}

Attempts to assign an arc to a given requirement status and returns true if consistency may still be possible
	private boolean attemptArcAssignment(Arc arcSearchDirection direction) {
		// initialize search stack for roll back
		// try to assign value to element and propagate changes
		// to other elements. If propagation fails, rollback changes
		try {
		  if ( .isDebugEnabled() )  .debug("Attempting move - Direction[" + direction + "], Arc[" + arc + "]");
			arc.setRequirement((direction == .) ? false : true);
				.debug("Move succeeded - State after move");
			}
			return true;
		}
			.debug("Move failed");
			return false;
		}
	}

Called to start a new transaction in the search routing
	private void pushSearchStack() {
		if ( == null)
	}

Called to undo changes to elements during searching
	private void popSearchStack() {
		List<GraphElementalteredElements = .removeLast();
		for (GraphElement elementalteredElements)
	}

Called to reset the search stack to original state before searching began
	private void resetSearchStack() {
		while (.size()>0)
	}

Performs work of propagating changes from source nodes to target nodes until consistency is reached

Throws:
ConsistencyException When current graph cannot be made consistent
	private void propagate() throws ConsistencyException {
	  .debug("Beginning propagation");
		// first prune all non-required nodes
		for (Node n)
			n.prune();
		// process until queues are empty
		while (.size()>0 || .size()>0) {
			// process basic node consistency enforcement because it's
			// faster than the extended arc propagation checks
			if (.size()>0) {
				Node source = (Node.remove();
				// check if source node is bound to a requirement setting
				// before processing arcs
				if (source.isRequirementKnown()) {
					// get list of arcs originating at node
					List<ArcsourceArcs = source.getArcs();
					for (Arc arcsourceArcs) {
						Node target = (arc.getLeft()==source) ? arc.getRight() : arc.getLeft();
						// if source is not required, arc is not required and
						// we can try and prune the target
						if (source.isNotRequired()) {
							arc.setRequirement(false);
							target.prune();
						}
					}
				}
			}
			// process extended enforcement of arc constraints on altered nodes
			// since we need to make sure that any node that is connected already
			else {
				// enforce arc constraints on nodes
				List<ArcsourceArcs = source.getArcs();
				for (Arc arcsourceArcs)
					arc.propagate(source);
			}
		}
		// build required nodes list
		List<NoderequiredNodes = new LinkedList<Node>();
		for (Node n)
			if (n.isRequired())
				requiredNodes.add(n);
		// make sure all required nodes can reach one another before returning
		// to ensure consistency
		if (requiredNodes.size()>1) {
			List<NodetargetList = new LinkedList<Node>(requiredNodes);
			Node start = requiredNodes.remove(0);
			if (!start.canReachAllNodes(targetList)) {
				.debug("Arc propagation completed, but not all targets could be reached from first node");
				throw new ConsistencyException(start);
			}
		}
		.debug("Propagation completed successfully");
	}

Called whenever a target node is altered

Parameters:
n Node that was altered
	public void graphElementChanged(GraphElement element) {
		List<GraphElementsearchDelta = ( != null && .size()>0) ? .getLast() : null;
		if (searchDelta != null)
			searchDelta.add(element);
		if (element instanceof Node) {
			Node n = (Nodeelement;
			// for more complex arcs we need to do extended propagation checks
			if (n.getArcs().size()>1)
		}
	}

Builds this graph based on data stored in list of relationships

Parameters:
relationships List of relationships that describe the graph
	private void build(List<LogicalRelationshiprelationships) {
		// loop through relationships and add necessary arcs
		// to the graph
		for (LogicalRelationship relationshiprelationships) {
			// obtains nodes corresponding to tables
			Node left = getNodeForTable(relationship.getFromTable());
			Node right = getNodeForTable(relationship.getToTable());
			// record arcs that correspond to change
			Arc arc = createArc(leftrightrelationship);
			//TODO: if any table requires a relationship when the table is
			//		used to ensure proper filtering, add dependency here
			//
			// if (relationship.getTableFrom() requires relationship)
			//   left.addRequiredArc(arc);
			//
			// if (relationship.getTableTo() requires relationship)
			//   right.addRequiredArc(arc);
		}
	}

Returns a node corresponding to a business table

Parameters:
table Table to locate node
Returns:
Node corresponding to table
	private Node getNodeForTable(LogicalTable table) {
		Node n = .get(table);
		if (n == null) {
			n = new Node(.size(), tablethis);
			.put(tablen);
		}
		return n;
	}

Creates a new arc and records appropriate dependencies in internal collections and maps

Parameters:
left Left node for arc
right RIght node for arc
	private Arc createArc(Node leftNode rightLogicalRelationship relationship) {
		Arc arc = new Arc(leftrightrelationshipthis);
		.add(arc);
		.trace("Created " + arc);
		// add new arc to list of arcs originating from nodes
		left.addArc(arc);
		right.addArc(arc);
		return arc;
	}

Contains values indicating whether a search path took a left or right route
	private static enum SearchDirection {
		LEFT,
		RIGHT
	}

Class that holds a possible solution to the graph problem for use during searching
	private static class Solution {
		private int rating;
		private List<ArcsearchArcs;
		Solution(List<Arcarcsint ratingList<SearchDirectionsearchPathList<ArcsearchArcs) {
			this. = rating;
			this. = searchPath;
			this. = searchArcs;
			for (Arc aarcs.add(a.isRequired());
		}
		public int getRating() {
			return ;
		}
		}
			return ;
		}
		public List<ArcgetSearchArcs() {
			return ;
		}
	}
New to GrepCode? Check out our FAQ X