protected boolean isOccluded(E edge, Shape graphSpaceShape) {

		Layout<V, E> layout = viewer.getGraphLayout();
		Graph<V, E> graph = layout.getGraph();
		Collection<V> vertices = graph.getVertices();

		for (V vertex : vertices) {
			Rectangle vertexBounds = getVertexBoundsInGraphSpace(viewer, vertex);

			Pair<V> endpoints = graph.getEndpoints(edge);
			if (vertex == endpoints.getFirst() || vertex == endpoints.getSecond()) {
				// do we ever care if an edge is occluded by its own vertices?
				continue;
			}

			if (graphSpaceShape.intersects(vertexBounds)) {
				return true;
			}
		}

		return false;
	}
 

private void addSourceSubtreeRootedAt(Node n, Tree.Node tn, int firstIndex, int lastIndex,
    String[] sourceWords) {
  int nextUncoveredIndex = firstIndex;
  Tree.NodeSourceStartComparator cmp = new Tree.NodeSourceStartComparator();
  List<Tree.Node> children = tn.children();
  Collections.sort(children, cmp);
  for (Tree.Node child : children) {
    if (child.isLeaf()) {
      continue;
    }
    int sourceStartIndex = child.sourceStartIndex();
    int sourceEndIndex = child.sourceEndIndex();
    if (sourceStartIndex > nextUncoveredIndex) {
      insertSourceLeaf(n, sourceWords, nextUncoveredIndex, sourceStartIndex);
    }
    Node childNode = new Node(child.label(), true);
    addEdge(new DerivationTreeEdge(true), new Pair<>(n, childNode), EdgeType.DIRECTED);
    nextUncoveredIndex = sourceEndIndex;
    addSourceSubtreeRootedAt(childNode, child, sourceStartIndex, sourceEndIndex, sourceWords);
  }
  if (nextUncoveredIndex < lastIndex) {
    insertSourceLeaf(n, sourceWords, nextUncoveredIndex, lastIndex);
  }
}
 

public Double getEdgeScore(E e) {
	Double score = scoreMap.get(e);
	if (score != null) return score;
	Pair<V> ends = g.getEndpoints(e);
	Set<V> vmap = new HashSet<V>(g.getNeighbors(ends.getFirst()));
	vmap.add(ends.getFirst());
	Collection<V> v1Neighbors = g.getNeighbors(ends.getSecond());
	int countCommon = 0;
	if (vmap.contains(ends.getSecond())){
		countCommon++;
	}
	for (V neighbor : v1Neighbors){
		if (vmap.contains(neighbor)){
			countCommon++;
		}
	}
	Double structureSimilarity = 
		(double)countCommon/Math.sqrt(vmap.size()*(v1Neighbors.size()+1));
	scoreMap.put(e, structureSimilarity);
	return structureSimilarity;
}
 

@Override
public boolean addEdge(E edge, Pair<? extends V> endpoints, EdgeType edgeType) {
	boolean added = super.addEdge(edge, endpoints, edgeType);
	if (added) {
		fireEdgesAdded(Arrays.asList(edge));
	}
	return added;
}
 

/**
 * Returns a mapping edges to vertices that touch them.
 * 
 * @param viewer the viewer containing the graph
 * @param edgeCollection the edges to check for occlusion
 * @return a mapping of occluded edges (a subset of the provided edges) to those vertices that
 *         occlude them.
 */
private Map<E, Set<V>> getOccludedEdges(Collection<E> edgeCollection) {

	Layout<V, E> layout = viewer.getGraphLayout();
	Graph<V, E> graph = layout.getGraph();

	Set<V> prototype = new HashSet<>();
	Factory<Set<V>> factory = FactoryUtils.prototypeFactory(prototype);
	Map<E, Set<V>> map = MapUtils.lazyMap(new HashMap<E, Set<V>>(), factory);

	Map<V, Rectangle> vertexBoundsMap = getVertexBounds();
	Set<Entry<V, Rectangle>> entrySet = vertexBoundsMap.entrySet();
	for (Entry<V, Rectangle> entry : entrySet) {
		V v = entry.getKey();
		Rectangle vertexBounds = getVertexBoundsInGraphSpace(viewer, v);

		for (E edge : edgeCollection) {
			Shape edgeShape = getEdgeShapeInGraphSpace(viewer, edge);
			Pair<V> endpoints = graph.getEndpoints(edge);
			if (v == endpoints.getFirst() || v == endpoints.getSecond()) {
				// do we ever care if an edge is occluded by its own vertices?
				continue;
			}

			if (edgeShape.intersects(vertexBounds)) {
				Set<V> set = map.get(edge);
				set.add(v);
			}
		}
	}

	return map;
}
 

private void addSubtreeRootedAt(Node n, Tree.Node tn) {
  for (Tree.Node child : tn.children()) {
    Node childNode = new Node(child.label(), false);
    addVertex(childNode);
    addEdge(new DerivationTreeEdge(false), new Pair<>(n, childNode), EdgeType.DIRECTED);
    addSubtreeRootedAt(childNode, child);
  }
}
 

private void insertSourceLeaf(Node n, String[] words, int start, int end) {
  final String[] leafWords = Arrays.copyOfRange(words, start, end);
  String label = leafWords[0];
  for (int i = 1; i < leafWords.length; i++) {
    label += " " + leafWords[i];
  }
  Node childNode = new Node(label, true);
  addEdge(new DerivationTreeEdge(true), new Pair<>(n, childNode), EdgeType.DIRECTED);
}
 

public void labelEdge(final RenderContext<Node, Edge> rc, final Layout<Node, Edge> layout, final Edge e, final String label) {
    if (label == null || label.length() == 0) {
        return;
    }

    final Graph<Node, Edge> graph = layout.getGraph();
    // don't draw edge if either incident vertex is not drawn
    final Pair<Node> endpoints = graph.getEndpoints(e);
    final Node v1 = endpoints.getFirst();
    final Node v2 = endpoints.getSecond();
    if (!rc.getEdgeIncludePredicate().evaluate(Context.<Graph<Node, Edge>, Edge>getInstance(graph, e))) {
        return;
    }

    if (!rc.getVertexIncludePredicate().evaluate(Context.<Graph<Node, Edge>, Node>getInstance(graph, v1)) ||
        !rc.getVertexIncludePredicate().evaluate(Context.<Graph<Node, Edge>, Node>getInstance(graph, v2))) {
        return;
    }

    final Point2D p1 = rc.getMultiLayerTransformer().transform(Layer.LAYOUT, layout.transform(v1));
    final Point2D p2 = rc.getMultiLayerTransformer().transform(Layer.LAYOUT, layout.transform(v2));

    final GraphicsDecorator g = rc.getGraphicsContext();
    final Component component = prepareRenderer(rc, rc.getEdgeLabelRenderer(), label, rc.getPickedEdgeState().isPicked(e), e);
    final Dimension d = component.getPreferredSize();

    final AffineTransform old = g.getTransform();
    final AffineTransform xform = new AffineTransform(old);
    final FontMetrics fm = g.getFontMetrics();
    int w = fm.stringWidth(e.text);
    double p = Math.max(0, p1.getX() + p2.getX() - w);
    xform.translate(Math.min(layout.getSize().width - w, p / 2), (p1.getY() + p2.getY() - fm.getHeight()) / 2);
    g.setTransform(xform);
    g.draw(component, rc.getRendererPane(), 0, 0, d.width, d.height, true);

    g.setTransform(old);
}
 

public Pair<V> getEndpoints(E edge) {
	return delegate.getEndpoints(edge);
}
 

@Override
public boolean addEdge(E e, Pair<? extends V> endpoints, EdgeType type) {
	maybePerformAdd(() -> super.addEdge(e, endpoints, type));
	return completeGraph.addEdge(e, endpoints, type);
}
 

@Override
public boolean addEdge(E e, Pair<? extends V> endpoints) {
	maybePerformAdd(() -> super.addEdge(e, endpoints));
	return completeGraph.addEdge(e, endpoints);
}
 

private void moveArticulationsAroundVertices(Set<V> vertices, E edge, boolean goLeft) {

		Layout<V, E> layout = viewer.getGraphLayout();
		Graph<V, E> graph = layout.getGraph();
		Pair<V> endpoints = graph.getEndpoints(edge);

		V start = endpoints.getFirst();
		V end = endpoints.getSecond();
		Point2D startPoint = layout.apply(start);
		Point2D endPoint = layout.apply(end);

//		Rectangle bounds = getBoundsForVerticesInLayoutSpace(viewer, vertices);

// paint the shape
//		Color color = getIntersectingBoxColor(edge);
//		String name = goLeft ? "Left" : "Right";
//		DebugShape<V, E> debugShape =
//			new DebugShape<V, E>(viewer, debugCounter, name,
//				translateShapeFromLayoutSpaceToGraphSpace(bounds, viewer), color);
//		viewer.addPostRenderPaintable(debugShape);

		Rectangle bounds = spaceBetweenEndPointsShape.getBounds();

		int padding = 20;
		int x = goLeft ? bounds.x : bounds.x + bounds.width;
		x += goLeft ? -padding : padding;

		Point2D top = new Point2D.Double(x, bounds.y - padding);
		Point2D bottom = new Point2D.Double(x, bounds.y + bounds.height + padding);

		if (startPoint.getY() > endPoint.getY()) {
			// swap the top and bottom points, as our source vertex is below the destination
			Point2D newTop = bottom;
			bottom = top;
			top = newTop;
		}

		List<Point2D> articulationPoints = new ArrayList<>();
		articulationPoints.add(top);
		articulationPoints.add(bottom);

		edge.setArticulationPoints(articulationPoints);
	}
 

protected List<Point2D> removeBadlyAngledArticulations(E edge, List<Point2D> articulations) {

		Layout<V, E> layout = viewer.getGraphLayout();
		Graph<V, E> graph = layout.getGraph();
		Pair<V> endpoints = graph.getEndpoints(edge);
		V start = endpoints.getFirst();
		V end = endpoints.getSecond();

		Point2D startPoint = layout.apply(start);
		Point2D endPoint = layout.apply(end);

		if (startPoint.getY() > endPoint.getY()) {
			// swap the top and bottom points, as our source vertex is below the destination
			Point2D newStart = endPoint;
			endPoint = startPoint;
			startPoint = newStart;
		}

		List<Point2D> newList = new ArrayList<>();
		for (Point2D articulation : articulations) {
			double deltaY = articulation.getY() - startPoint.getY();
			double deltaX = articulation.getX() - startPoint.getX();
			double theta = Math.atan2(deltaY, deltaX);
			double degrees = theta * 180 / Math.PI;

			if (degrees < 0 || degrees > 180) {
				continue;
			}

			deltaY = endPoint.getY() - articulation.getY();
			deltaX = endPoint.getX() - articulation.getX();
			theta = Math.atan2(deltaY, deltaX);
			degrees = theta * 180 / Math.PI;

			if (degrees < 0 || degrees > 180) {
				continue;
			}

			newList.add(articulation);
		}

		return newList;
	}
 

public static <V, E> Shape getEdgeShapeInGraphSpace(VisualizationServer<V, E> viewer, E e) {

		Layout<V, E> layout = viewer.getGraphLayout();
		Pair<V> pair = layout.getGraph().getEndpoints(e);
		V startVertex = pair.getFirst();
		V endVertex = pair.getSecond();

		Point2D startVertexCenter = getVertexCenterPointInGraphSpace(viewer, startVertex);
		if (startVertexCenter == null) {
			return null;
		}

		Point2D endVertexCenter = getVertexCenterPointInGraphSpace(viewer, endVertex);
		if (endVertexCenter == null) {
			return null;
		}

		boolean isLoop = startVertex.equals(endVertex);
		double startX = (float) startVertexCenter.getX();
		double startY = (float) startVertexCenter.getY();
		double endX = (float) endVertexCenter.getX();
		double endY = (float) endVertexCenter.getY();

		RenderContext<V, E> renderContext = viewer.getRenderContext();
		if (isLoop) {
			//
			// Our edge loops are sized and positioned according to the shared
			// code in the utils class.  We do this so that our hit detection matches our rendering.
			//
			Function<? super V, Shape> vertexShapeTransformer =
				renderContext.getVertexShapeTransformer();
			Shape vertexShape = getVertexShapeForEdge(endVertex, vertexShapeTransformer);
			return createHollowEgdeLoopInGraphSpace(vertexShape, startX, startY);
		}

		// translate the edge from 0,0 to the starting vertex point
		AffineTransform xform = AffineTransform.getTranslateInstance(startX, startY);
		Shape edgeShape = renderContext.getEdgeShapeTransformer().apply(e);

		double deltaX = endX - startX;
		double deltaY = endY - startY;

		// rotate the edge to the angle between the vertices
		double theta = Math.atan2(deltaY, deltaX);
		xform.rotate(theta);

		// stretch the edge to span the distance between the vertices
		double dist = Math.sqrt(deltaX * deltaX + deltaY * deltaY);
		xform.scale(dist, 1.0f);

		// apply the transformations; converting the given shape from model space into graph space
		return xform.createTransformedShape(edgeShape);
	}
 

@Test
public void testAddEdge_Overloaded_Edge_Pair_WhenUnfiltered() {

	doTestAddEdge_WhenUnfiltered((e, v1, v2) -> graph.addEdge(e, new Pair<>(v1, v2)));
}
 

@Test
public void testAddEdge_Overloaded_Edge_Pair_WhenFiltered() {

	doTestAddEdge_WhenFiltered((e, v1, v2) -> graph.addEdge(e, new Pair<>(v1, v2)));
}
 

@Override
public void labelEdge(RenderContext<V, E> rc, Layout<V, E> layout, E e, String label) {
	if (label == null || label.length() == 0) {
		return;
	}

	Graph<V, E> graph = layout.getGraph();
	// don't draw edge if either incident vertex is not drawn
	Pair<V> endpoints = graph.getEndpoints(e);
	V v1 = endpoints.getFirst();
	V v2 = endpoints.getSecond();
	if (!rc.getVertexIncludePredicate().evaluate(Context.<Graph<V, E>, V> getInstance(graph, v1))
			|| !rc.getVertexIncludePredicate().evaluate(Context.<Graph<V, E>, V> getInstance(graph, v2))) {
		return;
	}

	Point2D p1 = layout.transform(v1);
	Point2D p2 = layout.transform(v2);
	p1 = rc.getMultiLayerTransformer().transform(Layer.LAYOUT, p1);
	p2 = rc.getMultiLayerTransformer().transform(Layer.LAYOUT, p2);
	float x1 = (float) p1.getX();
	float y1 = (float) p1.getY();
	float x2 = (float) p2.getX();
	float y2 = (float) p2.getY();

	GraphicsDecorator g = rc.getGraphicsContext();
	float distX = x2 - x1;
	float distY = y2 - y1;
	double totalLength = Math.sqrt(distX * distX + distY * distY);

	double closeness = rc.getEdgeLabelClosenessTransformer().transform(Context.<Graph<V, E>, E> getInstance(graph, e))
			.doubleValue();

	int posX = (int) (x1 + closeness * distX);
	int posY = (int) (y1 + closeness * distY);

	int xDisplacement = 0;
	int yDisplacement = 0;

	xDisplacement = (int) (rc.getLabelOffset() * (distX / totalLength));
	yDisplacement = (int) (rc.getLabelOffset() * (-distY / totalLength));

	AffineTransform old = g.getTransform();
	AffineTransform xform = new AffineTransform(old);
	xform.translate(posX + xDisplacement, posY + yDisplacement);

	double parallelOffset = 0.0d;
	Component component = prepareRenderer(rc, rc.getEdgeLabelRenderer(), label, rc.getPickedEdgeState().isPicked(e), e);
	Dimension d = component.getPreferredSize();
	xform.translate(-d.width / 2.0d, -(d.height / 2.0d - parallelOffset));
	g.setTransform(xform);
	g.setColor(Colors.WHITE);
	g.draw(component, rc.getRendererPane(), 0, 0, d.width, d.height, true);
	g.setTransform(old);
}