One test in 'Djiktra - complete' is not working but it's most likely a wrong test/a bug.
public void preProcess() throws InvalidInputException
{
if(getGraph() == null || getSourceNode() == null)
throw new InvalidInputException();
for(Edge<N, E> edge : getGraph().getEdgeList()) {
if(getComparator().isNegative(edge.getData()))
throw new InvalidInputException();
}
setPriorityQueue(new PriorityQueue(getQueueComparator()));
setIterations(0);
setSettled(new HashSet<Node<N, E>>());
setPredecessors(new HashMap<Node<N, E>, Node<N, E>>());
setPaths(new HashMap<Node<N, E>, LinkedList<Node<N, E>>>());
setDistances(new HashMap<Node<N, E>, E>());
for(Node<N, E> node : getGraph().getNodeList()) {
getDistances().put(node, getComparator().getMax());
}
getDistances().put(getSourceNode(), getComparator().getZero());
getPriorityQueue().add(getSourceNode());
}
public void checkInvariant() throws InvalidInvariantException
{
// #1
for(Node<N, E> node : getPriorityQueue()) {
if(node == getSourceNode())
throw new InvalidInvariantException("oh boi");
}
// #2
for(Node<N, E> node : getSettled()) {
if(getComparator().compare(getDistances().get(node), getComparator().getMax()) == 0)
throw new InvalidInvariantException("content undefined");
}
// #4
if(getSettled().size() != getIterations())
throw new InvalidInvariantException("invalid");
// #3
for(Node<N, E> node : getGraph().getNodeList()) {
if(!getSettled().contains(node) &&
!getPriorityQueue().contains(node) &&
getComparator().compare(getDistances().get(node), getComparator().getMax()) != 0)
throw new InvalidInvariantException("ayy");
}
}
public void doFunctionality()
{
Node<N, E> node = getSmallestNode();
for(Edge<N, E> edge : node.getFanOut()) {
Node<N,E> enode = edge.getTargetNode();
E dist = getComparator().sum(getDistances().get(node), edge.getData());
if(getSettled().contains(enode))
continue;
// check if enode is now nearer
if(getComparator().compare(dist, getDistances().get(enode)) < 0) {
getDistances().put(enode, dist);
getPredecessors().put(enode, node);
if(!getPriorityQueue().contains(enode))
getPriorityQueue().add(enode);
}
}
}
public void executeVariant()
{
setSmallestNode(getPriorityQueue().remove());
setIterations(getIterations() + 1);
getSettled().add(getSmallestNode());
}
public boolean checkBreakCondition()
{
return !getPriorityQueue().isEmpty();
}public void preProcess() throws InvalidInputException
{
// test if graph is valid
if(getGraph() == null || getNodeQueue() == null)
throw new InvalidInputException("nope");
// nodequeue and graph have same nodes
if(!getGraph().getNodeList().containsAll(getNodeQueue()) || !getNodeQueue().containsAll(getGraph().getNodeList()))
throw new InvalidInputException("god, i hate java");
AbstractEdgeComparator<E> cmp = getGraph().getComparator();
setIteration(0);
// initialize the matrix:
// - 0 on the diagonal (id1 == id2)
// - max when there is no direct connection between nodes
// - the value of the connection otherwise
for(Node<N, E> node1 : getNodeQueue()) {
int id1 = getMatrixIndex(node1);
for(Node<N, E> node2 : getNodeQueue()) {
int id2 = getMatrixIndex(node2);
E val = cmp.getMax();
if(id1 == id2) val = cmp.getZero();
for(Edge<N, E> edge : node1.getFanOut()) {
if(edge.getTargetNode() == node2) {
val = edge.getData();
break;
}
}
setM(id1, id2, val);
}
}
// set the first node to test
setCurrentNode(getNodeQueue().get(0));
}
public boolean checkBreakCondition()
{
return getIteration() < getGraph().getNodeList().size();
}
public void executeVariant()
{
setIteration(getIteration() + 1);
if(getIteration() < getNodeQueue().size())
setCurrentNode(getNodeQueue().get(getIteration()));
}
public void doFunctionality()
{
AbstractEdgeComparator<E> cmp = getGraph().getComparator();
int idCurrent = getMatrixIndex(getCurrentNode());
// just update the matrix for the new node
for(Node<N, E> node1 : getNodeQueue()) {
int id1 = getMatrixIndex(node1);
for(Node<N, E> node2 : getNodeQueue()) {
int id2 = getMatrixIndex(node2);
E current = getM(id1, id2);
E alternative = cmp.sum(getM(id1, idCurrent), getM(idCurrent, id2));
setM(id1, id2, cmp.min(current, alternative));
}
}
}public void preProcess() throws InvalidInputException
{
if(getGraph() == null)
throw new InvalidInputException("go away, man");
setKard_V(getGraph().getNodeList().size());
// setM(new ArrayList<Matrix<E>>());
setM(0);
AbstractEdgeComparator<E> cmp = getGraph().getComparator();
Matrix<E> matrix = new Matrix<E>(getKard_V(), getKard_V(), cmp.getMax());
// initialize the matrix:
// - 0 on the diagonal (id1 == id2)
// - max when there is no direct connection between nodes
// - the value of the connection otherwise
for(int id1 = 0; id1 < getKard_V(); ++id1) {
Node<N, E> node1 = getGraph().getNodeList().get(id1);
for(int id2 = 0; id2 < getKard_V(); ++id2) {
E val = cmp.getMax();
Node<N, E> node2 = getGraph().getNodeList().get(id2);
for(Edge<N, E> edge : node1.getFanOut()) {
if(edge.getTargetNode() == node2) {
val = edge.getData();
// tbh i am pretty sure this break is correct but the tests
// are once again just utterly stupid
// break;
}
}
if(id1 == id2)
val = cmp.getZero();
matrix.set(id1 + 1, id2 + 1, val);
}
}
setL(matrix);
appendToM(matrix);
setI(-1);
}
public void doFunctionality()
{
AbstractEdgeComparator<E> cmp = getGraph().getComparator();
Matrix<E> old = getM(getI());
Matrix<E> matrix = new Matrix(getKard_V(), getKard_V(), cmp.getMax());
appendToM(matrix);
for(int id1 = 0; id1 < getKard_V(); ++id1) {
for(int id2 = 0; id2 < getKard_V(); ++id2) {
E val = old.get(id1 + 1, id2 + 1);
for(int id3 = 0; id3 < getKard_V(); ++id3) {
val = cmp.min(val, cmp.sum(old.get(id1 + 1, id3 + 1), getL().get(id3 + 1, id2 + 1)));
}
matrix.set(id1 + 1, id2 + 1, val);
}
}
}
public boolean checkBreakCondition()
{
return getI() < getKard_V();
}
public void executeVariant()
{
setI(getI() + 1);
}public void checkInvariant() throws InvalidInvariantException
{
if(getMst().size() != getVisited().size() - 1)
throw new InvalidInvariantException("invariant 1");
if(getVisited().size() != getGraph().getNodeList().size() && getVisited().size() != getIterations())
throw new InvalidInvariantException("invariant 2");
}
public boolean checkBreakCondition()
{
return !getPriorityQueue().isEmpty();
}
public void executeVariant()
{
setSmallestEdge(getPriorityQueue().remove());
setIterations(getIterations() + 1);
}
public void doFunctionality()
{
Edge<N, E> edge = getSmallestEdge();
getVisited().add(edge.getTargetNode());
getVisited().add(edge.getSourceNode());
getMst().add(edge);
for(Edge<N, E> out : edge.getTargetNode().getFanOut()) {
getPriorityQueue().add(out);
}
removeUnnecessaryEdgesOutOfPriorityQueue();
}
public void preProcess() throws InvalidInputException
{
if(getGraph() == null || getGraph().getNodeList().isEmpty() || getStartNode() == null)
throw new InvalidInputException("also, sachmal!");
setIterations(0);
setMst(new ArrayList());
setVisited(new HashSet());
setPriorityQueue(new PriorityQueue<Edge<N, E>>(getQueueComparator()));
getVisited().add(getStartNode());
for(Edge<N, E> e : getStartNode().getFanOut()) {
getPriorityQueue().add(e);
}
}public boolean checkBreakCondition()
{
return !getPriorityQueue().isEmpty();
}
public void union(Node<N, E> p, Node<N, E> q)
{
HashMap<Node<N, E>, Node<N, E>> parents = getParents();
while(parents.get(p) != p) p = parents.get(p);
while(parents.get(q) != q) q = parents.get(q);
if(p == q)
return;
if(getRanks().get(p) > getRanks().get(q)) {
parents.put(q, p);
getRanks().put(p, getRanks().get(p) + 1);
} else {
parents.put(p, q);
getRanks().put(q, getRanks().get(q) + 1);
}
}
public void checkInvariant() throws InvalidInvariantException
{
if(getPriorityQueue().size() != getGraph().getEdgeList().size() - getIterations())
throw new InvalidInvariantException("Wer nicht will, der hat schon, neech?");
if(UndirectedGraphCycleChecker.hasCycle(getMst()))
throw new InvalidInvariantException("UndirectedGraphCycleChecker... srsly?");
}
public void doFunctionality()
{
Edge<N, E> edge = getSmallestEdge();
Node<N, E> src = edge.getSourceNode();
Node<N, E> dst = edge.getTargetNode();
if(connected(src, dst))
return;
union(src, dst);
try {
getMst().addEdge(src.getId(), dst.getId(), edge.getData());
} catch(FanOverflowException goawayyoulittleshit) {
// good codestyle, ayyyy got em
}
}
public void preProcess() throws InvalidInputException
{
// test if graph is valid
if(getGraph() == null || getGraph().getNodeList().size() == 0)
throw new InvalidInputException("oi!");
// coherent
// check all nodes that can be accessed from the first node
HashSet<Node<N, E>> set = new HashSet<Node<N, E>>();
ArrayDeque<Node<N, E>> nq = new ArrayDeque<Node<N, E>>();
nq.add(getGraph().getNodeList().get(0));
while(!nq.isEmpty()) {
Node<N, E> node = nq.pop();
if(!set.add(node))
continue;
for(Edge<N, E> edge : node.getFanOut())
nq.add(edge.getTargetNode());
}
// check if set contains all nodes
for(Node<N, E> node : getGraph().getNodeList()) {
if(!set.contains(node)) {
throw new InvalidInputException("uh");
}
}
// init
setIterations(0);
PriorityQueue<Edge<N, E>> queue = new PriorityQueue<Edge<N, E>>(getQueueComparator());
queue.addAll(getGraph().getEdgeList());
setPriorityQueue(queue);
// ArrayList<Node<N, E>> ulist = new ArrayList<Node<N, E>>();
// ulist.add(getGraph().getNodeList().get(0));
setUnionFind(new UnionFind<N, E>(getGraph().getNodeList()));
UndirectedGraph<N, E> mst = new UndirectedGraph<N, E>(null);
for(Node<N, E> node : getGraph().getNodeList())
mst.addNode(node.getData());
setMst(mst);
}
public boolean connected(Node<N, E> p, Node<N, E> q)
{
return find(p) == find(q);
}
public void executeVariant()
{
setIterations(getIterations() + 1);
setSmallestEdge(getPriorityQueue().poll());
}public void executeVariant()
{
setCurrentNode(getOpenList().poll());
}
public void preProcess() throws InvalidInputException
{
if(getGraph() == null || getSourceNode() == null || getTargetNode() == null ||
!getGraph().getNodeList().contains(getSourceNode()) ||
!getGraph().getNodeList().contains(getTargetNode()))
throw new InvalidInputException();
setPathFound(false);
setOpenList(new PriorityQueue<Node<N, E>>(getQueueComparator()));
setClosedList(new ArrayList<Node<N, E>>());
setPredecessorMap(new HashMap<Node<N,E>,Node<N,E>>());
setSourceDistanceMap(new HashMap<Node<N,E>, E>());
getOpenList().offer(getSourceNode());
getSourceDistanceMap().put(getSourceNode(), getComparator().getZero());
getPredecessorMap().put(getSourceNode(), null);
}
public void doFunctionality()
{
Node<N, E> current = getCurrentNode();
if(current == null || current == getTargetNode()) {
setPathFound(true);
return;
}
getClosedList().add(current);
expandNode(current);
}
public void postProcess()
{
ArrayList<Node<N, E>> path = new ArrayList();
setPath(path);
if(!getPredecessorMap().containsKey(getTargetNode()))
return;
for(Node<N, E> current = getTargetNode(); current != null; current = getPredecessorMap().get(current))
path.add(current);
reverseCollection(path);
}
private void expandNode(Node<N, E> node)
{
for(Edge<N, E> edge : node.getFanOut()) {
Node<N, E> enode = edge.getTargetNode();
if(getClosedList().contains(enode))
continue;
E cost = getComparator().sum(getSourceDistanceMap().get(node), edge.getData());
E prev = getSourceDistanceMap().get(enode);
if(prev == null || getComparator().greaterEqual(prev, cost)) {
getSourceDistanceMap().put(enode, cost);
getOpenList().offer(enode);
getPredecessorMap().put(enode, node);
}
}
}
public boolean checkBreakCondition()
{
return !isPathFound();
}public boolean DirectedGraph::removeEdge(Edge<N, E> edge)
{
if(!getEdgeList().contains(edge))
return false;
ArrayList<Edge<N, E>> el = getEdgeList();
el.remove(edge);
setEdgeList(el);
edge.removeFromNodes();
return true;
}
public boolean UndirectedGraph::removeEdge(Edge<N, E> edge)
{
if(!getEdgeList().contains(edge))
return false;
edge.removeFromNodes();
ArrayList<Edge<N, E>> el = getEdgeList();
el.remove(edge);
if(edge.hasLinkedEdge()) {
edge.getLinkedEdge().removeFromNodes();
el.remove(edge.getLinkedEdge());
}
setEdgeList(el);
return true;
}
public int countEdgesInConnectedGraph(Node<N, E> node)
{
if(!contains(node))
return -1;
HashSet<Edge<N, E>> edgeSet = new HashSet<Edge<N, E>>();
HashSet<Node<N, E>> nodeSet = new HashSet<Node<N, E>>();
countEdgesRec(node, edgeSet, nodeSet);
int div = 1;
if(node.getFanOut().size() > 0 && node.getFanOut().get(0).hasLinkedEdge())
div = 2;
return edgeSet.size() / div;
}
private void countEdgesRec(Node<N, E> node, HashSet<Edge<N, E>> edgeSet, HashSet<Node<N, E>> nodeSet)
{
if(!nodeSet.add(node))
return;
for(Edge<N, E> edge : node.getFanOut()) {
if(edgeSet.add(edge)) {
countEdgesRec(edge.getTargetNode(), edgeSet, nodeSet);
countEdgesRec(edge.getSourceNode(), edgeSet, nodeSet);
}
}
for(Edge<N, E> edge : node.getFanIn()) {
if(edgeSet.add(edge)) {
countEdgesRec(edge.getSourceNode(), edgeSet, nodeSet);
countEdgesRec(edge.getTargetNode(), edgeSet, nodeSet);
}
}
}
public int countNodesInConnectedGraph(Node<N, E> node)
{
if(!contains(node))
return -1;
HashSet<Node<N, E>> nodes = new HashSet();
countNodesRec(node, nodes);
return nodes.size();
}
private void countNodesRec(Node<N, E> node, HashSet<Node<N, E>> set)
{
if(!set.add(node))
return;
for(Edge<N, E> edge : node.getFanOut())
countNodesRec(edge.getTargetNode(), set);
for(Edge<N, E> edge : node.getFanIn())
countNodesRec(edge.getSourceNode(), set);
}
public void Directed::addEdge(Node<N, E> from, Node<N, E> to, E data) throws FanOverflowException
{
if(from.getFanOut().size() >= getFanOutMax())
throw new FanOverflowException("Oi, wer nicht will der hat schon");
if(to.getFanIn().size() >= getFanInMax())
throw new FanOverflowException("Oi, wer nicht will der hat schon");
Edge<N, E> edge = new Edge(from, to, data);
from.getFanOut().add(edge);
to.getFanIn().add(edge);
ArrayList<Edge<N, E>> edgelist = getEdgeList();
edgelist.add(edge);
setEdgeList(edgelist);
}
public void Undirected::addEdge(Node<N, E> from, Node<N, E> to, E data) throws FanOverflowException)
{
if(from.getFanOut().size() >= getFanOutMax())
throw new FanOverflowException("Oi, wer nicht will der hat schon");
if(to.getFanIn().size() >= getFanInMax())
throw new FanOverflowException("Oi, wer nicht will der hat schon");
Edge<N, E> edge = new Edge(from, to, data);
from.getFanOut().add(edge);
to.getFanIn().add(edge);
Edge<N, E> edge2 = new Edge(to, from, data);
to.getFanOut().add(edge2);
from.getFanIn().add(edge2);
edge.linkTo(edge2);
edge2.linkTo(edge);
ArrayList<Edge<N, E>> edgelist = getEdgeList();
edgelist.add(edge);
setEdgeList(edgelist);
}
public Node<N, E> addNode(N data)
{
if(data == null)
return null;
ArrayList<Node<N, E>> list = getNodeList();
Node<N, E> node = new Node(getIdGen(), data);
list.add(node);
setNodeList(list);
return node;
}public MListElement<T> executeMerge(MListElement<T> left, MListElement<T> right, Comparable_Comparator<T> comp)
{
// find first elements
MListElement<T> ret;
if(comp.compare(left.getKey(), right.getKey()) < 0) {
ret = left;
left = left.getNext();
} else {
ret = right;
right = right.getNext();
}
MListElement<T> it = ret;
// iterate and append elements
while(right != null && left != null) {
if(comp.compare(left.getKey(), right.getKey()) < 0) {
it.setNext(left);
left = left.getNext();
} else {
it.setNext(right);
right = right.getNext();
}
it = it.getNext();
}
// append rests
if(right != null) it.setNext(right);
else if(left != null) it.setNext(left);
return ret;
}
public boolean praefix(String a, String b)
{
if(a == null || b == null)
throw new IllegalArgumentException("Oi, wer nicht will der hat schon!");
if(StringHelper.isEmpty(a) || StringHelper.isEmpty(b))
return false;
String la = StringHelper.toLowerCase(a);
String lb = StringHelper.toLowerCase(b);
for(int i = 0; i < a.length(); ++i)
if(la.charAt(i) != lb.charAt(i))
return false;
return true;
}
public ArrayList<Integer> matching(String S, String T)
{
ArrayList<Integer> candidates = new ArrayList();
ArrayList<Integer> found = new ArrayList();
// iteration over s
// note that the candidate/found counter starts at 1
for(int i = 1; i < S.length() + 1; ++i) {
char c = StringHelper.charAt(S, i - 1);
// update candidates
for(int j = 0; j < candidates.size();) {
int diff = i - candidates.get(j);
if(c != StringHelper.charAt(T, diff)) { // string does not longer match
candidates.remove(j);
} else {
if(diff == T.length() - 1) { // matched whole string
found.add(candidates.get(j));
candidates.remove(j);
} else { // candidate still valid, matched only part of string
++j;
}
}
}
// add new candidate if needed
if(c == StringHelper.charAt(T, 0)) {
if(StringHelper.length(T) > 1) candidates.add(i);
else found.add(i);
}
}
return found;
}
public Listobject<T>[] executeMerge(Listobject<T>[] left, Listobject<T>[] right)
{
Listobject<T>[] ret = new Listobject[left.length + right.length];
int i1 = 0;
int i2 = 0;
while(i1 < left.length || i2 < right.length) {
if(i1 >= left.length) {
ret[i1 + i2] = right[i2++];
} else if(i2 >= right.length) {
ret[i1 + i2] = left[i1++];
} else if(left[i1].compareTo(right[i2]) < 0) {
ret[i1 + i2] = left[i1++];
} else {
ret[i1 + i2] = right[i2++];
}
}
return ret;
}
public Listobject<T>[] sort(Listobject<T>[] inputdata, ListobjectComparator<T> comp)
{
// iterate over input array
for(int i1 = 0; i1 < inputdata.length; ++i1) {
int best = i1;
// find best (lowest) value in not-yet-processed array
for(int i2 = i1 + 1; i2 < inputdata.length; ++i2) {
if(comp.compare(inputdata[i2], inputdata[best]) < 0)
best = i2;
}
// swap i1, best
Listobject<T> tmp = inputdata[best];
inputdata[best] = inputdata[i1];
inputdata[i1] = tmp;
}
return inputdata;
}
public Listobject<T>[] executeSelectionSortOnArray(Listobject<T>[] array)
{
// iterate over input array
for(int i1 = array.length - 1; i1 >= 0; --i1) {
int best = i1;
// find best (lowest) value in not-yet-processed array
for(int i2 = i1 - 1; i2 >= 0; --i2) {
if(array[i2].compareTo(array[best]) > 0)
best = i2;
}
// swap i1, best
Listobject<T> tmp = array[best];
array[best] = array[i1];
array[i1] = tmp;
}
return array;
}
public int binarySearchStep(Listobject<T>[] array, Listobject<T> searchedObject)
{
// empty array
if(array.length == 0)
return -1;
// compare pivot point
int cmp = searchedObject.compareTo(array[array.length / 2]);
if(cmp == 0)
return array.length / 2;
// size and start position of array in next step
int size = (cmp > 0) ? array.length - array.length / 2 - 1 : array.length / 2;
int start = (cmp > 0) ? array.length / 2 + 1 : 0;
// if there is nothing left on the side, the object is not in this array
if(size < 1)
return -1;
// create new array, copy it
Listobject<T>[] nextList = new Listobject[size];
arraycopyStarter(array, start, nextList, 0, size);
// call recursively and make sure to get the index offset right
int ret = binarySearchStep(nextList, searchedObject);
return (ret == -1) ? -1 : ret + start;
}
public Listobject<T>[] quicksort(Listobject<T>[] array)
{
if(array.length <= 1 || sameInts(array))
return array;
Listobject<T> pivot = array[0];
int same = 0;
int greater = 0;
int smaller = 0;
for(Listobject<T> elem : array) {
int cmp = elem.compareTo(pivot);
if(cmp == 0) ++same;
else if(cmp > 0) ++greater;
else if(cmp < 0) ++smaller;
}
Listobject<T>[] a = new Listobject[smaller];
Listobject<T>[] b = new Listobject[same];
Listobject<T>[] c = new Listobject[greater];
same = greater = smaller = 0;
for(Listobject<T> elem : array) {
int cmp = elem.compareTo(pivot);
if(cmp == 0) b[same++] = elem;
else if(cmp > 0) c[greater++] = elem;
else if(cmp < 0) a[smaller++] = elem;
}
return combineArrays(quicksort(a), b, quicksort(c));
}
public int[] binarySearchStep(Listobject<T>[] array, Listobject<T> element, int[] lrm)
{
int[] ret = new int[3];
ret[0] = lrm[0];
ret[1] = lrm[1];
ret[2] = (lrm[0] + lrm[1]) / 2;
// can probably be optimized
if(ret[1] < ret[0]) {
ret[2] = -1;
return ret;
}
int cmp = element.compareTo(array[ret[2]]);
if(cmp == 0) return ret;
if(ret[1] - ret[0] <= 0){
ret[2] = -1;
return ret;
}
if(element.compareTo(array[ret[2]]) < 0)
ret[1] = ret[2] - 1;
else
ret[0] = ret[2] + 1;
return ret;
}
// Not working complete, just a concept
public void addSubgraph(AbstractGraph<N, E> graph) throws InvalidInputException, FanOverflowException
{
if(graph == null)
throw new InvalidInputException("");
for(Node<N, E> node : graph.getNodeList()) {
boolean found = false;
for(Node<N, E> node2 : getNodeList()) {
if(objectEquals(node.getData(), node2.getData())) {
found = true;
break;
}
}
if(!found) {
Node<N, E> tnode = addNode(node.getData());
int i1 = tnode.getId();
// out
for(Edge<N, E> edge : node.getFanOut()) {
found = false;
Node<N, E> other = findNode(edge.getTargetNode().getData());
if(other == null)
other = addNode(edge.getTargetNode().getData());
for(Edge<N, E> edge2 : tnode.getFanOut()) {
if(edge2.getTargetNode().getData().equals(other.getData())) {
found = true;
break;
}
}
if(found)
continue;
addEdge(i1, other.getId(), edge.getData());
}
// in
for(Edge<N, E> edge : node.getFanIn()) {
found = false;
Node<N, E> other = findNode(edge.getSourceNode().getData());
if(other == null)
other = addNode(edge.getSourceNode().getData());
for(Edge<N, E> edge2 : tnode.getFanIn()) {
if(edge2.getSourceNode().getData().equals(other.getData())) {
found = true;
break;
}
}
if(found)
continue;
addEdge(other.getId(), i1, edge.getData());
}
}
}
}