package graph;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;

import org.ubiety.ubigraph.UbigraphClient;

import ui.Ubi;

import core.BasicNode;
import core.Counter;
import core.Graph;
import core.GraphUtils;
import core.Node;
import core.RenderNode;

public class AlgoTriangleGraph implements Graph {


	private List<Node> nodes;
	private int nodeCount;

	public AlgoTriangleGraph(int nodeCount) {
		this.nodeCount = nodeCount;
		nodes = new ArrayList<Node>();

	public Set<Node> exclude(Set<Node> anchorSet) {
		Set<Node> result = new HashSet<Node>();
		for (Node node: nodes) {

			// If a node in the graph has all the anchors as neighbors
			// and the number of neighbors is 3
			// then add him to the exclude set.
			if (node.getNeighbors().containsAll(anchorSet) && node.getNeighbors().size() == 3) {
		return result;

	public Node getBestFit(Set<Node> currentSet) {

		// Create a set of nodes that's a copy of the graph
		Set<Node> sampleSet = new HashSet<Node>(nodes);

		// Remove from it all those nodes that are being tested
		// for best fit.

		// If there is more than one candidate, exclude nodes
		// that are already touching all elements of the current set.
		if (currentSet.size() > 1) {

		// If there are no candidates, then put all the nodes back in.
		// Everything is fair game.
		if (sampleSet.size() == 0) {

		// Using the nodes in the candidate set, create a ranked list
		// for which nodes adjacent to the highest number of samples
		// have the highest score.
		// Where scores are identical, prefer nodes with lower degree.
		Map<Node, Counter> nodeMap = new HashMap<Node, Counter>();
		for (Node node: currentSet) {
			for (Node neighbor: node.getNeighbors()) {

				//Consider a node if it's not in the current set
				//but is in the set of viable candidates
				if (!currentSet.contains(neighbor) && sampleSet.contains(neighbor)) {
					GraphUtils.markMap(nodeMap, neighbor, 1);
        SortedSet<Counter> counters = new TreeSet<Counter>(new DegreeComparator());

		// Return the node that scored highest.
        Node result = counters.first().getNode();
		return result;

	 * Returns an opposer list. The first two elements of the list are the nodes
	 * that will lose a link. The second two are the nodes that will gain a link.
	 * @param newNeighbors
	 * @return
	public List<Node> findOpposer(Set<Node> newNeighbors) {
		List<Node> result = null;

		//Find the new neighbor with the lowest degree
		SortedSet<Counter> counters = new TreeSet<Counter>();
		for (Node node: newNeighbors) {
			counters.add(new Counter(node, node.getNeighbors().size()));

		//Build a set that has all nodes except the lowest degree node
		Node minNode = counters.last().getNode();
		Set<Node> middle = new HashSet<Node>(newNeighbors);

		//Find the neighbors of all elements of that set
		Set<Node> neighborsToAll = new HashSet<Node>();
		Iterator<Node> midIt = middle.iterator();
		Node first =;
		while( midIt.hasNext()) {
			Node next =;
			Set<Node> nextNeighbors = next.getNeighbors();

		//Exclude the low node

		//If the neighbors to all are greater than one
		//get rid of the degenerate cases
		if (neighborsToAll.size() > 1) {

		//The nodes that remain are the candidate opposer nodes.
		//(There should be exactly one.)
		Node opposer = null;
		if (neighborsToAll.size() > 1) {
		} else if (neighborsToAll.size() < 1) {
		} else {
			opposer = neighborsToAll.iterator().next();

		if (opposer != null) {

			//Check that we're actually balancing the graph by moving a link
			Iterator<Counter> countIt = counters.iterator();
			Counter c1 =;
			Counter c2 =;
			int highest = c1.getValue() + c2.getValue();
			int lowest = minNode.getNeighbors().size() + opposer.getNeighbors().size();

			if (highest > lowest + 2) {
				result = new ArrayList<Node>();

				//The first two items of the returned list are the nodes
				//with the highest degree
		return result;

	//Graph Methods-----
	public void init() {

		for (int i = 0; i < 4; i++) {
    		Node node = new RenderNode(i);
    		for (int j = 0; j < i; j++) {
		int count = 4;

		while (nodes.size() < nodeCount) {

        	//Define a set of nodes
    		Set<Node> newNeighbors = new HashSet<Node>();

    		//Attach to the most recently added node
    		int indexA = nodes.size() - 1;
    		Node nodeA = nodes.get(indexA);

    		//Pick other nodes near it
    		for (int j = 1; j < 3; j++) {
    			Node nextNode = getBestFit(newNeighbors);

    		//Determine if we're looking at an unbalanced set.
    		List<Node> opposerList = findOpposer(newNeighbors);
    		if (opposerList != null) {

    			//Rebalance the set

    		} else {
    			//Add a new node
        		Node newNode = new RenderNode(count);

        		//Add new nodes to all new neighbors
        		for (Node neighbor: newNeighbors) {

		UbigraphClient client = Ubi.getClient();
		for (Node node: nodes) {
			((RenderNode) node).renderNode();
		for (Node node: nodes) {
			((RenderNode) node).renderEdges();


	public Set<Node> getNodes() {
	    return new HashSet<Node>(nodes);

	public class DegreeComparator implements Comparator<Counter> {

		public int compare(Counter o1, Counter o2) {
			int difference = (o1.getValue() - o2.getValue());
			if (difference == 0) {
				double diff = o1.getNode().getNeighbors().size() - o2.getNode().getNeighbors().size();
				difference = (int) (diff / Math.abs(diff));

			return -difference;

  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: