## 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) {
}
}
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) {
}

// 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) {
}

//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.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
}
}
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
opposerList.get(0).removeNeighbor(opposerList.get(1));

} else {
Node newNode = new RenderNode(count);
count++;

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

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;
}

}
}
```