AlgoTriangleGraph.java

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 {

	//CONSTANTS

	//VARIABLES
	private List<Node> nodes;
	private int nodeCount;

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

	//METHODS
	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) {
				result.addAll(node.getNeighbors());
			}
		}
		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.
		sampleSet.removeAll(currentSet);

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

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

		// 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());
        counters.addAll(nodeMap.values());

		// 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);
		middle.remove(minNode);

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

		//Exclude the low node
		neighborsToAll.remove(minNode);

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

		//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 = countIt.next();
			Counter c2 = countIt.next();
			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
				result.add(c1.getNode());
				result.add(c2.getNode());
				result.add(minNode);
				result.add(opposer);
			}
		}
		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++) {
				node.addNeighbor(nodes.get(j));
    		}
    		nodes.add(node);
		}
		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);
    		newNeighbors.add(nodeA);

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

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

    			//Rebalance the set
    			opposerList.get(0).removeNeighbor(opposerList.get(1));
    			opposerList.get(2).addNeighbor(opposerList.get(3));

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

        		//Add new nodes to all new neighbors
        		for (Node neighbor: newNeighbors) {
        			newNode.addNeighbor(neighbor);
        		}
                nodes.add(newNode);
    		}
        }

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

	}

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

	//INNER CLASSES
	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;
		}

	}
}

Advertisement