Einführung in die Programmierung HS23 - Bonus 8 Lösungen

public class Graphs {
  public static Node cube(int n) {
    return genCube(n)[0];
  }

  static Node[] genCube(int n) {
    if (n == 0) {
      return new Node[] { new Node() };
    } else {
      Node[] a = genCube(n - 1);
      Node[] b = genCube(n - 1);
      Node[] result = new Node[2 * a.length];
      for (int i = 0; i < a.length; i++) {
        a[i].addNeighbor(b[i]);
        b[i].addNeighbor(a[i]);
        result[i] = a[i];
        result[i + a.length] = b[i];
      }
        
      return result;
    }
  }

  ...
}

public class Node {	
	int testing = -1;
	
	private LinkedNodeList neighbors = new LinkedNodeList();
	
	public void addNeighbor(Node neighbor) {
		this.neighbors.addLast(neighbor);
	}
	
	public Node[] getNeighbors() {
		return this.neighbors.toArray();
	}
}

public class Graphs {

	public static Node cube(int n) {
		return cubeContainer(n).first();
	}
	
	private static NodeContainer cubeContainer(int n) {
		if (n == 0) {
			return NodeContainer.empty();
		}
		
		NodeContainer left = cubeContainer(n - 1);
		NodeContainer right = cubeContainer(n - 1);
		left.merge(right);
		return left;
	}

  ...
}

public class Node {	
	int testing = -1;
	
	private LinkedNodeList neighbors = new LinkedNodeList();
	
	public void addNeighbor(Node neighbor) {
		this.neighbors.addLast(neighbor);
	}
	
	public Node[] getNeighbors() {
		return this.neighbors.toArray();
	}
}

import java.util.HashMap;

public class NodeContainer {
	private HashMap<String, Node> labels = new HashMap<String, Node>();
		
	public Node first() {
		for (var node : this.labels.values()) {
			return node;
		}
		
		return null;
	}
	
	public void merge(NodeContainer other) {
		HashMap<String, Node> newLabels = new HashMap<String, Node>();
		for (String label : this.labels.keySet()) {
			Node left = this.labels.get(label);
			Node right = other.labels.get(label);
			
			left.addNeighbor(right);
			right.addNeighbor(left);
			
			newLabels.put("0" + label, left);
			newLabels.put("1" + label, right);
		}
		
		this.labels = newLabels;
	}
	
	public static NodeContainer empty() {
		NodeContainer empty = new NodeContainer();
		empty.labels.put("", new Node());
		return empty;
	}
}

public class Graphs {

	public static Node cube(int n) {
		Node[] nodes = new Node[1 << n];
		for (int i = 0; i < nodes.length; i++) {
			nodes[i] = new Node(n);
		}

		for (int node = 0; node < nodes.length; node++) {
		    for (int adj = 0; adj < n; adj++) {
		        nodes[node].neighbors[adj] = nodes[node ^ (1 << adj)];
		    }
		}
		return nodes[0];
	}

  ...
}

public class Node {
	
	int testing = -1;
	
	public Node[] neighbors;
	
	public Node(int n) {
		this.neighbors = new Node[n];
	}
	
	public Node[] getNeighbors() {
		return this.neighbors;
	}
}

public class Graphs {

	public static Node cube(int n) {
		// Labels
		String[] labels = new String[(int) Math.pow(2, n)];
		generateLabels(n, labels);

		// Nodes
		Node[] nodes = new Node[(int) Math.pow(2, n)];
		for (int i = 0; i < Math.pow(2, n); i++) {
			String label = Integer.toBinaryString(i);
			while (label.length() < n) {
				label = "0" + label;
			}
			nodes[i] = new Node(label);
		}

		// Neighbors
		for (int i = 0; i < Math.pow(2, n); i++) {
			for (int j = i + 1; j < Math.pow(2, n); j++) {
				if(isNeighbour(nodes[i].label, nodes[j].label)) {
					nodes[i].neighbors.addLast(nodes[j]);
					nodes[j].neighbors.addLast(nodes[i]);
				}
			}
		}
		
		printGraph(nodes[0]);
		return nodes[0];
	}

	public static void generateLabels(int n, String[] label) {
		for (int i = 0; i < Math.pow(2, n); i++) {
			String string = Integer.toBinaryString(i);
			while (string.length() != n) {
				string = "0" + string;
			}
			label[i] = string;
		}
	}

	public static boolean isNeighbour(String label1, String label2) {
		int count = 0;
		for (int i = 0; i < label1.length(); i++) {
			if (label1.charAt(i) != label2.charAt(i)) {
				count++;
			}
		}
		return count == 1;
	}

  ...
}

public class Node {

	int testing = -1;
	public String label;
	public LinkedNodeList neighbors;

	Node(String label) {
		this.label = label;
		neighbors = new LinkedNodeList();
	}

	Node[] getNeighbors() {
		return sort(neighbors.toArray());
	}

	public Node[] sort(Node[] s) {
		Node[] r = new Node[s.length];
		for (int i = 0; i < s.length; i++) {
			r[getIndex(s[i].label)] = s[i];
		}
		return r;
	}

	int getIndex(String str) {
		int i = 0;
		while (label.charAt(i) == str.charAt(i)) {
			i++;
		}
		return i;
	}

	public String toString() {
		return label;
	}
}