bei Dijkstra schlägt ein Test fehl, bei A* zwei, ich kann allerdings nicht sagen, wo der Fehler liegt.
Code: Alles auswählen
Merge Array iteratively:
public Listobject<T>[] executeMerge(Listobject<T>[] left, Listobject<T>[] right)
{
if ((left == null)|(right == null)){
throw new NullPointerException();
}
int l1 = left.length;
int l2 = right.length;
int i1 = 0;
int i2 = 0;
if (l1 == 0){
return right;
}
if (l2 == 0){
return left;
}
Listobject<T>[] r = new Listobject<>[l1 + l2];
while ((i1 < (l1))||(i2 < (l2))){
if (i1 == (l1)){
r[i1 + i2] = right[i2];
i2++;
continue;
}
if (i2 == (l2)){
r[i1 + i2] = left[i1];
i1++;
continue;
}
if (left[i1].compareTo(right[i2]) < 0){
r[i1 + i2] = left[i1];
i1++;
}
else{
r[i1 + i2] = right[i2];
i2++;
}
}
return r;
}
binary Search iterative:
public int[] binarySearchStep(Listobject<T>[] array, Listobject<T> element, int[] lrm)
{
if (array == null || element == null){
throw new NullPointerException();
}
int[] r = new int[3];
r[0] = lrm[0];
r[1] = lrm[1];
r[2] = -1;
int m = (r[0] + r[1]) / 2;
if (array.length == 0) {
return r;
}
if (array[m].compareTo(element) == 0) {
r[2] = m;
return r;
}
if (r[1] == m) {
return r;
}
if (array[m].compareTo(element) > 0) {
r[1] = m - 1;
} else {
r[0] = m + 1;
}
r[2] = m;
return r;
}
binary Search recursive:
public int binarySearchStep(Listobject<T>[] array, Listobject<T> searchedObject)
{
if (searchedObject == null || array == null) {
throw new NullPointerException();
}
if(array.length < 1)
return -1;
int m = array.length / 2;
int c = searchedObject.compareTo(array[m]);
if(array.length == 1 && c != 0){
return -1;
}
if(c == 0){
return m;
}
int l = 0;
Listobject<T>[] a;
if (c > 0){
l = array.length - m - 1;
a = new Listobject<>[l];
arraycopyStarter(array,m+1,a,0,l );
}
else{
if (array.length%2 == 0){
l = array.length - m;
}
else{
l = array.length - m - 1;
}
a = new Listobject<>[l];
arraycopyStarter(array,0,a,0,l) ;
}
int r = binarySearchStep(a,searchedObject);
if (r == -1){
return - 1;
}
if (c > 0){
return m + 1 + binarySearchStep(a,searchedObject);
}
return binarySearchStep(a,searchedObject);
}
Quicksort recursive:
public Listobject<T>[] quicksort(Listobject<T>[] array)
{
if (array.length <= 1){
return array;
}
Listobject pivot = array[0];
int el = 0;
int ep = 0;
for (int i = 0; i < array.length; i++){
int c = array[i].compareTo(pivot);
if (c == 0){
ep++;
}
if (c < 0){
el++;
}
}
Listobject<T>[] l = new Listobject<>[el];
Listobject<T>[] r = new Listobject<>[array.length - el - ep];
Listobject<T>[] p = new Listobject<>[ep];
int il = 0;
int ir = 0;
int ip = 0;
for (int j = 0; j < array.length; j++){
int c = array[j].compareTo(pivot);
if (c == 0){
p[ip] = array[j];
ip++;
}
if (c < 0){
l[il] = array[j];
il++;
}
if (c > 0){
r[ir] = array[j];
ir++;
}
}
return combineArrays(quicksort(l), p, quicksort(r));
}
Selectionsort:
public Listobject<T>[] executeSelectionSortOnArray(Listobject<T>[] array)
{
int l = array.length;
while (l > 1){
int m = 0;
for (int j = 1; j < l; j++){
if (array[j].compareTo(array[m]) > 0){
m = j;
}
}
if (m != (l - 1)){
Listobject<T> c = array[m];
array[m] = array[l - 1];
array[l - 1] = c;
}
l--;
}
return array;
}
Sort O(n^2)
(Selectionsort, da bereits vorher programmiert)
public Listobject<T>[] sort(Listobject<T>[] inputdata, ListobjectComparator<T> comp)
{
Listobject<T>[] array = inputdata;
int l = array.length;
while (l > 1){
int m = 0;
for (int j = 1; j < l; j++){
if (comp.compare(array[j],array[m]) > 0){
m = j;
}
}
if (m != (l - 1)){
Listobject<T> c = array[m];
array[m] = array[l - 1];
array[l - 1] = c;
}
l--;
}
return array;
}
Merge LinkedList:
public MListElement<T> executeMerge(MListElement<T> left, MListElement<T> right, Comparable_Comparator<T> comp)
{
if (left == null){
return right;
}
if (right == null){
return left;
}
MListElement<T> lc = left;
MListElement<T> rc = right;
MListElement<T> r;
MListElement c;
if (comp.compare(lc.getKey(),rc.getKey()) > 0){
r = rc;
c = r;
rc = rc.getNext();
}
else{
r = lc;
c = r;
lc = lc.getNext();
}
while ((lc != null)||(rc != null)){
if (lc == null){
c.setNext(rc);
break;
}
if (rc == null){
c.setNext(lc);
break;
}
if (comp.compare(lc.getKey(),rc.getKey()) > 0){
c.setNext(rc);
rc = rc.getNext();
c = c.getNext();
}
else{
c.setNext(lc);
lc = lc.getNext();
c = c.getNext();
}
}
return r;
}
prefix Checker:
public boolean praefix(String a, String b)
{
if ((a == null)||(b == null)){
throw new IllegalArgumentException();
}
if ((StringHelper.isEmpty(a))||(StringHelper.isEmpty(b))){
return false;
}
char[] aa = StringHelper.toCharArray(StringHelper.toLowerCase(a));
char[] ba = StringHelper.toCharArray(StringHelper.toLowerCase(b));
int al = aa.length;
for (int i = 0; i< al; i++){
if (aa[i] != ba[i]){
return false;
}
}
return true;
}
Simple String Matching:
public ArrayList<Integer> matching(String S, String T)
{
ArrayList<Integer> r = new ArrayList<Integer>();
ArrayList<Integer> s = new ArrayList<Integer>();
char[] as = StringHelper.toCharArray(StringHelper.toLowerCase(S));
char[] at = StringHelper.toCharArray(StringHelper.toLowerCase(T));
int l = as.length;
int lt = at.length;
for (int i = 0; i < l; i++) {
for(int j = 0; j < s.size(); j++){
if(as[i] != at[i + 1 - s.get(j)]){
s.remove(j);
j--;
}
else{
if(i + 1 - s.get(j) == lt - 1){
r.add(s.get(j));
s.remove(j);
j--;
}
}
}
if(as[i] == at[0]){
if(lt > 1){
s.add(i+1);
}
else {
r.add(i+1);
}
}
}
return r;
}
Graph addNode:
public Node<N, E> addNode(N data)
{
if (data == null){
return null;
}
IdGenerator I = getIdGen();
ArrayList<Node<N,E>> l = getNodeList();
Node<N,E> n = new Node<N,E>(I,data);
l.add(n);
setNodeList(l);
return n;
}
Graph removeNode:
public boolean removeNode(Node<N, E> node)
{
if (node == null){
return false;
}
ArrayList<Node<N,E>> n = getNodeList();
if (!n.contains(node)){
return false;
}
ArrayList<Edge<N,E>> fi = node.getFanIn();
ArrayList<Edge<N,E>> fo = node.getFanOut();
ArrayList<Edge<N,E>> e = getEdgeList();
for (Edge<N,E> c: fi){
c.removeFromNodes();
e.remove(c);
}
for (Edge<N,E> c: fo){
c.removeFromNodes();
e.remove(c);
}
setEdgeList(e);
n.remove(node);
setNodeList(n);
return true;
}
Graph findNode:
public Node<N, E> findNode(Node<N, E> startNode, N data)
{
if (startNode == null || data == null || !getNodeList().contains(startNode)){
return null;
}
ArrayDeque<Node<N, E>> s = new ArrayDeque();
HashSet<Node<N, E>> v = new HashSet();
s.push(startNode);
v.add(startNode);
while (!s.isEmpty()) {
Node<N, E> n = s.pop();
if (objectEquals(data, n.getData())){
return n;
}
for (Edge<N, E> e: n.getFanOut()) {
Node<N, E> t = e.getTargetNode();
if (!v.contains(t)) {
s.push(t);
v.add(t);
}
}
}
return null;
}
Graph addEdge:
(undirected)
public void addEdge(Node<N, E> from, Node<N, E> to, E data) throws FanOverflowException
{
if (from.getFanIn().size() >= getFanInMax() || to.getFanIn().size() >= getFanInMax() ||
from.getFanOut().size() >= getFanOutMax() || to.getFanOut().size() >= getFanOutMax()){
throw new FanOverflowException();
}
ArrayList<Edge<N,E>> tfi = to.getFanIn();
ArrayList<Edge<N,E>> ffo = from.getFanOut();
ArrayList<Edge<N,E>> el = getEdgeList();
Edge<N,E> i = new Edge<N,E>(from,to,data);
tfi.add(i);
ffo.add(i);
el.add(i);
ArrayList<Edge<N,E>> tfo = to.getFanOut();
ArrayList<Edge<N,E>> ffi = from.getFanIn();
Edge<N,E> i2 = new Edge<N,E>(to,from,data);
tfo.add(i2);
ffi.add(i2);
i.linkTo(i2);
i2.linkTo(i);
setEdgeList(el);
}
(directed)
public void addEdge(Node<N, E> from, Node<N, E> to, E data) throws FanOverflowException
{
if (to.getFanIn().size() >= getFanInMax()||from.getFanOut().size() >= getFanOutMax()){
throw new FanOverflowException();
}
ArrayList<Edge<N,E>> tfi = to.getFanIn();
ArrayList<Edge<N,E>> ffo = from.getFanOut();
ArrayList<Edge<N,E>> el = getEdgeList();
Edge<N,E> i = new Edge<N,E>(from,to,data);
tfi.add(i);
ffo.add(i);
el.add(i);
setEdgeList(el);
}
Graph removeEdge:
(undirected)
public boolean removeEdge(Edge<N, E> edge)
{
if (edge == null){
return false;
}
ArrayList<Edge<N,E>> el = getEdgeList();
if (!el.contains(edge)){
return false;
}
if (edge.hasLinkedEdge()){
Edge<N,E> l = edge.getLinkedEdge();
l.removeFromNodes();
}
edge.removeFromNodes();
el.remove(edge);
setEdgeList(el);
return true;
}
(directed)
public boolean removeEdge(Edge<N, E> edge)
{
if (edge == null){
return false;
}
ArrayList<Edge<N,E>> el = getEdgeList();
if (!el.contains(edge)){
return false;
}
edge.removeFromNodes();
el.remove(edge);
setEdgeList(el);
return true;
}
Graph findEdge:???
Graph compareGraphs:???
Graph countEdges:
public int countEdgesInConnectedGraph(Node<N, E> node)
{
if(!contains(node)){
return -1;
}
HashSet<Edge<N, E>> e = new HashSet<Edge<N, E>>();
HashSet<Node<N, E>> n = new HashSet<Node<N, E>>();
countEdgesRec(node, e, n);
int u = 1;
if(node.getFanOut().size() > 0 && node.getFanOut().get(0).hasLinkedEdge()){
u = 2;
}
return e.size() / u;
}
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> e : node.getFanOut()) {
if(edgeSet.add(e)) {
countEdgesRec(e.getTargetNode(), edgeSet, nodeSet);
}
}
for(Edge<N, E> e : node.getFanIn()) {
if(edgeSet.add(e)) {
countEdgesRec(e.getSourceNode(), edgeSet, nodeSet);
}
}
}
Graph countNodes:
public int countNodesInConnectedGraph(Node<N, E> node)
{
if (!contains(node)){
return -1;
}
HashSet<Node<N,E>> h = new HashSet<Node<N,E>>();
countNodesRec(node, h);
return h.size();
}
private void countNodesRec(Node<N, E> node, HashSet<Node<N, E>> set)
{
if (!set.add(node)){
return;
}
for (Edge<N,E> e: node.getFanOut()){
if (!set.contains(e.getTargetNode())){
countNodesRec(e.getTargetNode(),set);
}
}
for (Edge<N,E> e: node.getFanIn()){
if (!set.contains(e.getSourceNode())){
countNodesRec(e.getSourceNode(),set);
}
}
}
Graph filterNodes:???
Dijkstra (21/22, Fehlerhafter Test?):
public void preProcess() throws InvalidInputException
{
if (getGraph() == null || getSourceNode() == null){
throw new InvalidInputException("null");
}
ArrayList<Edge<N,E>> el = getGraph().getEdgeList();
for (Edge<N,E> e: el){
if (getComparator().isNegative(e.getData())){
throw new InvalidInputException("negative");
}
}
setIterations(0);
HashMap<Node<N,E>, Node<N,E>> pre = new HashMap<Node<N,E>, Node<N,E>>(100, (float) 0.5);
setPredecessors(pre);
HashSet<Node<N,E>> set = new HashSet<Node<N,E>>(100, (float) 0.5);
setSettled(set);
setSmallestNode(getSourceNode());
HashMap<Node<N,E>, LinkedList<Node<N,E>>> pat = new HashMap<Node<N,E>, LinkedList<Node<N,E>>>(100, (float) 0.5);
setPaths(pat);
PriorityQueue<Node<N,E>> prio = new PriorityQueue<Node<N,E>>(getQueueComparator());
prio.add(getSourceNode());
setPriorityQueue(prio);
HashMap<Node<N,E>, E> dis = new HashMap<Node<N,E>,E>(100, (float) 0.5);
for (Node<N,E> n: getGraph().getNodeList()){
dis.put(n,getComparator().getMax());
}
dis.put(getSourceNode(),getComparator().getZero());
setDistances(dis);
}
public boolean checkBreakCondition()
{
return !getPriorityQueue().isEmpty();
}
public void executeVariant()
{
setIterations(getIterations() + 1);
setSmallestNode(getPriorityQueue().remove());
getSettled().add(getSmallestNode());
}
public void checkInvariant() throws InvalidInvariantException
{
if (getPriorityQueue().contains(getSourceNode())) throw new InvalidInvariantException("SourceNode");
if (!(getSettled().size() == getIterations())) throw new InvalidInvariantException("settledSize");
for (Node<N,E> s: getSettled()){
if (getComparator().compare(getDistances().get(s), getComparator().getMax()) == 0) throw new InvalidInvariantException("settled");
}
for (Node<N,E> n: getGraph().getNodeList()){
if (!getSettled().contains(n) && !getPriorityQueue().contains(n) &&
(getComparator().compare(getDistances().get(n), getComparator().getMax()) != 0)) throw new InvalidInvariantException("unsettled");
}
}
public void doFunctionality()
{
Node<N,E> c = getSmallestNode();
ArrayList<Edge<N,E>> out = c.getFanOut();
for (Edge<N,E> o: out){
Node<N,E> t = o.getTargetNode();
if (getSettled().contains(t)) continue;
E d = getComparator().sum(getDistances().get(c), o.getData());
if (getComparator().compare(getDistances().get(t), d) > 0){
getDistances().put(t, d);
getPredecessors().put(t, c);
}
if (!getPriorityQueue().contains(t)){
getPriorityQueue().add(t);
}
}
}
Kruskal:
public void preProcess() throws InvalidInputException
{
AbstractGraph<N,E> g = getGraph();
if (g == null) throw new InvalidInputException("null");
ArrayList<Node<N,E>> nl = g.getNodeList();
if (nl.size() == 0) throw new InvalidInputException("nodes");
ArrayList<Edge<N,E>> el = g.getEdgeList();
if (!(g instanceof UndirectedGraph)) throw new InvalidInputException("undirected");
HashSet<Node<N, E>> set = new HashSet<Node<N, E>>();
ArrayDeque<Node<N, E>> stack = new ArrayDeque<Node<N, E>>();
stack.add(nl.get(0));
while(!stack.isEmpty()) {
Node<N, E> c = stack.pop();
if(!set.add(c)){
continue;
}
for(Edge<N, E> e : c.getFanOut()){
stack.add(e.getTargetNode());
}
}
for(Node<N, E> n : nl) {
if(!set.contains(n)) {
throw new InvalidInputException("coherent");
}
}
setIterations(0);
PriorityQueue<Edge<N,E>> prio = new PriorityQueue<Edge<N,E>>(getQueueComparator());
prio.addAll(getGraph().getEdgeList());
setPriorityQueue(prio);
setUnionFind(new UnionFind<N,E>(nl));
UndirectedGraph<N,E> mst = new UndirectedGraph<N,E>(null);
for (Node<N,E> n: nl){
mst.addNode(n.getData());
}
setMst(mst);
}
public boolean checkBreakCondition()
{
return !getPriorityQueue().isEmpty();
}
public void executeVariant()
{
setSmallestEdge(getPriorityQueue().remove());
setIterations(getIterations() + 1);
}
public void checkInvariant() throws InvalidInvariantException
{
if (getPriorityQueue().size() != getGraph().getEdgeList().size() - getIterations()) throw new InvalidInvariantException("size");
if (UndirectedGraphCycleChecker.hasCycle(getMst())) throw new InvalidInvariantException("cycle");
}
public void doFunctionality()
{
Edge<N,E> se = getSmallestEdge();
Node<N,E> s = se.getSourceNode();
Node<N,E> t = se.getTargetNode();
if (connected(s,t)) return;
union(s,t);
try {getMst().addEdge(s.getId(), t.getId(), se.getData());}
catch (FanOverflowException f) {}
}
public boolean connected(Node<N, E> p, Node<N, E> q)
{
return find(p) == find(q);
}
public void union(Node<N, E> p, Node<N, E> q)
{
HashMap<Node<N,E>, Node<N,E>> pa = getParents();
while(pa.get(p) != p){
p = pa.get(p);
}
while(pa.get(q) != q){
q = pa.get(q);
}
if (p == q) return;
HashMap<Node<N,E>, Integer> ra = getRanks();
if(ra.get(p) > ra.get(q)) {
pa.put(q, p);
ra.put(p, ra.get(p) + 1);
} else {
pa.put(p, q);
ra.put(q, ra.get(q) + 1);
}
}
A*:
public void preProcess() throws InvalidInputException
{
if (getGraph() == null) throw new InvalidInputException("null");
if (getGraph().getNodeList().size() == 0) throw new InvalidInputException("nodes");
if (getSourceNode() == null || !getGraph().getNodeList().contains(getSourceNode())) throw new InvalidInputException("source");
if (getTargetNode() == null || !getGraph().getNodeList().contains(getTargetNode())) throw new InvalidInputException("target");
setPathFound(false);
PriorityQueue<Node<N, E>> p = new PriorityQueue(getQueueComparator());
p.offer(getSourceNode());
setOpenList(p);
setClosedList(new ArrayList<Node<N, E>>());
HashMap<Node<N, E>, Node<N, E>> pre = new HashMap<Node<N, E>, Node<N, E>>();
pre.put(getSourceNode(), null);
setPredecessorMap(pre);
HashMap<Node<N, E>, E> dis = new HashMap<Node<N, E>, E>();
dis.put(getSourceNode(), getComparator().getZero());
setSourceDistanceMap(dis);
}
public void executeVariant()
{
setCurrentNode(getOpenList().poll());
}
public void doFunctionality()
{
Node<N, E> c = getCurrentNode();
if (c == getTargetNode() || c == null) {
setPathFound(true);
return;
}
getClosedList().add(c);
expandNode(c);
}
public void postProcess()
{
ArrayList<Node<N, E>> p = new ArrayList<Node<N, E>>();
setPath(p);
if (!getPredecessorMap().containsKey(getTargetNode())) {
return;
}
for (Node<N, E> c = getTargetNode(); c != null; getPredecessorMap().get(c)) {
p.add(c);
}
reverseCollection(p);
}
public void expandNode(Node<N, E> node)
{
for (Edge<N, E> e : node.getFanOut()) {
Node<N, E> t = e.getTargetNode();
if (getClosedList().contains(t))
continue;
E co = getComparator().sum(getSourceDistanceMap().get(node), e.getData());
E pre = getSourceDistanceMap().get(t);
if (pre == null || getComparator().greaterEqual(pre, co)) {
getSourceDistanceMap().put(t, co);
getPredecessorMap().put(t, node);
if (!getOpenList().contains(t)){
getOpenList().offer(t);
}
}
}
}
Floyd-Warshall:
public void preProcess() throws InvalidInputException
{
if (getGraph() == null) throw new InvalidInputException("Graph");
if (getNodeQueue() == null) throw new InvalidInputException("Queue");
if (getNodeQueue().size() != getGraph().getNodeList().size()) throw new InvalidInputException("size");
if(!getGraph().getNodeList().containsAll(getNodeQueue()) || !getNodeQueue().containsAll(getGraph().getNodeList())) throw new InvalidInputException("nodes");
setIteration(0);
AbstractEdgeComparator<E> com = getGraph().getComparator();
E m = com.getMax();
E z = com.getZero();
E c = m;
for(Node<N, E> n1 : getNodeQueue()) {
int i1 = getMatrixIndex(n1);
for(Node<N, E> n2 : getNodeQueue()) {
int i2 = getMatrixIndex(n2);
c = m;
if(i1 == i2){
c = z;
}
for(Edge<N, E> e : n1.getFanOut()) {
if(e.getTargetNode() == n2) {
c = e.getData();
break;
}
}
setM(i1, i2, c);
}
}
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> com = getGraph().getComparator();
int ci = getMatrixIndex(getCurrentNode());
for(Node<N, E> n1 : getNodeQueue()) {
int i1 = getMatrixIndex(n1);
for(Node<N, E> n2 : getNodeQueue()) {
int i2 = getMatrixIndex(n2);
E c = getM(i1, i2);
E a = com.sum(getM(i1, ci), getM(ci, i2));
setM(i1, i2, com.min(c, a));
}
}
}
Bellman-Ford:
public void preProcess() throws InvalidInputException
{
if(getGraph() == null) throw new InvalidInputException("graph");
setKard_V(getGraph().getNodeList().size());
setM(0);
AbstractEdgeComparator<E> com = getGraph().getComparator();
Matrix<E> m = new Matrix<E>(getKard_V(), getKard_V(), com.getMax());
E val;
for(int i1 = 0; i1 < getKard_V(); i1++) {
Node<N, E> n1 = getGraph().getNodeList().get(i1);
for(int i2 = 0; i2 < getKard_V(); i2++) {
val = com.getMax();
Node<N, E> n2 = getGraph().getNodeList().get(i2);
for(Edge<N, E> e : n1.getFanOut()) {
if(e.getTargetNode() == n2) {
val = e.getData();
}
}
if(i1 == i2)
val = com.getZero();
m.set(i1 + 1, i2 + 1, val);
}
}
setL(m);
appendToM(m);
setI(-1);
}
public boolean checkBreakCondition()
{
return getI() < getKard_V();
}
public void executeVariant()
{
setI(getI() + 1);
}
public void doFunctionality()
{
AbstractEdgeComparator<E> com = getGraph().getComparator();
Matrix<E> o = getM(getI());
Matrix<E> m = new Matrix(getKard_V(), getKard_V(), com.getMax());
E val;
for(int i1 = 1; i1 < getKard_V() + 1; i1++) {
for(int i2 = 1; i2 < getKard_V() + 1; i2++) {
val = o.get(i1, i2);
for(int i3 = 1; i3 < getKard_V() + 1; i3++) {
val = com.min(val, com.sum(o.get(i1, i3), getL().get(i3, i2)));
}
m.set(i1, i2, val);
}
}
appendToM(m);
}
Prim:
public void preProcess() throws InvalidInputException
{
if (getGraph() == null || getStartNode() == null) throw new InvalidInputException("null");
//if (!(getGraph() instanceof DirectedGraph)) throw new InvalidInputException("undirected");
if (getGraph().getNodeList().size() == 0) throw new InvalidInputException("node");
ArrayDeque<Node<N,E>> stack = new ArrayDeque<Node<N,E>>();
HashSet<Node<N,E>> set = new HashSet<Node<N,E>>();
stack.push(getStartNode());
while (!stack.isEmpty()){
Node<N,E> c = stack.pop();
set.add(c);
for (Edge<N,E> e: c.getFanOut()){
Node<N,E> t = e.getTargetNode();
if (!set.contains(t)){
stack.push(t);
}
}
}
if (!(set.size() == getGraph().getNodeList().size())) throw new InvalidInputException("coherent");
setIterations(0);
PriorityQueue<Edge<N,E>> prio = new PriorityQueue<Edge<N,E>>(getQueueComparator());
for (Edge<N,E> e: getStartNode().getFanOut()){
prio.add(e);
}
setPriorityQueue(prio);
setMst(new ArrayList<Edge<N,E>>());
HashSet<Node<N,E>> v = new HashSet<Node<N,E>>();
v.add(getStartNode());
setVisited(v);
}
public boolean checkBreakCondition()
{
return !(getPriorityQueue().isEmpty());
}
public void executeVariant()
{
setSmallestEdge(getPriorityQueue().remove());
setIterations(getIterations() + 1);
}
public void checkInvariant() throws InvalidInvariantException
{
if ((getVisited().size() - 1) != getMst().size()) throw new InvalidInvariantException("size");
if (getVisited().size() != getGraph().getNodeList().size() && getVisited().size() != getIterations()) throw new InvalidInvariantException("iterations");
}
public void doFunctionality()
{
Edge<N,E> s = getSmallestEdge();
getVisited().add(s.getTargetNode());
removeUnnecessaryEdgesOutOfPriorityQueue();
for (Edge<N,E> e : s.getTargetNode().getFanOut()){
Node<N,E> n = e.getTargetNode();
if (!getVisited().contains(n)){
getPriorityQueue().offer(e);
}
}
getMst().add(s);
}
. Ich hoffe das kann noch jemandem weiter helfen.Hier war auch schon mal eine Liste, ich weiß nicht, in wieweit die sich ergänzen, oder nicht: viewtopic.php?f=167&t=36383&p=175672&hi ... ph#p175672