Codemonkeys-2 Komplettlösung

Dadung
Windoof-User
Windoof-User
Beiträge: 29
Registriert: 7. Mai 2017 13:08

Codemonkeys-2 Komplettlösung

Beitrag von Dadung » 12. Jul 2017 17:16

Ich habe mal alle CM Testat 2 Aufgaben, die ich identifizieren konnte bearbeitet:

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);
    
}
der Code ist unkommentiert und die Variablen nicht sprechend benannt, so dass man schon versuchen muss zu verstehen, was passiert und nicht einfach den Code durchließt und denkt man hat ihn verstanden. :wink: . 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

Zurück zu „Archiv“