private void createNewClusters()
	{
		firstResultingCluster = new OrdinaryCluster(graph, this.firstResultingPIn,
			this.firstExpectedSize);
		secondResultingCluster = new OrdinaryCluster(graph, this.secondResultingPIn,
			this.secondExpectedSize);

		/*
		 * Save intra-cluster edges of initial cluster.
		 * As the iterator returns edges for both directions, only one of
		 * them is actually added.
		 */
		final ArrayList<Edge> storedEdges = new ArrayList<Edge>();
		final Iterator<Edge> intraClusterEdgeIter = initialCluster.intraClusterEdgeIterator();
		while (intraClusterEdgeIter.hasNext())
		{
			final Edge edge = intraClusterEdgeIter.next();
			if (edge.getSource().getGlobalIndex() < edge.getTarget().getGlobalIndex())
			{
				storedEdges.add(edge);
			}
		}

		// inter-cluster edges
		ListUtils.appendTo(initialCluster.interClusterEdgeIterator(), storedEdges);

		final int interClusterEdgeCountBefore = initialCluster.getInterClusterEdgeCount();
		final int intraClusterEdgeCountBefore = initialCluster.getIntraClusterEdgeCount();
		assert storedEdges.size() == intraClusterEdgeCountBefore
			+ interClusterEdgeCountBefore;


		// relabel the nodes so that they belong to their new clusters
		final GroundTruth groundTruth = graph.getGroundTruth();
		groundTruth.apply(this);

		assert initialCluster.isInReferenceClustering();
		assert !initialCluster.isInGroundTruth();
		initialCluster.setCurrentOperation(this);

		assert firstResultingCluster.isInGroundTruth();
		groundTruth.lock(firstResultingCluster, this);

		assert secondResultingCluster.isInGroundTruth();
		groundTruth.lock(secondResultingCluster, this);

		/*
		 * Distribute nodes
		 * via weighted selection
		 */
		final int totalExpectedSize = this.firstExpectedSize + this.secondExpectedSize;
		final Iterator<Node> iter = initialCluster.nodeIterator();

		// Each cluster gets at least one node
		assert iter.hasNext();

		final Node fstBasicNode = iter.next();
		firstResultingCluster.addNodeLocally(fstBasicNode);
		fstBasicNode.setOperationIndex(this.globalIndex);

		assert iter.hasNext();

		final Node sndBasicNode = iter.next();
		secondResultingCluster.addNodeLocally(sndBasicNode);
		sndBasicNode.setOperationIndex(-this.globalIndex);

		while (iter.hasNext())
		{
			final Node node = iter.next();
			if (random.nextInt(totalExpectedSize) < this.firstExpectedSize)
			{
				this.firstResultingCluster.addNodeLocally(node);
				node.setOperationIndex(this.globalIndex);
			}
			else
			{
				this.secondResultingCluster.addNodeLocally(node);
				node.setOperationIndex(-this.globalIndex);
			}
		}

		/*
		 * Remove all edges from the initial cluster
		 * Changes to the cluster will only be local - no information
		 * in the pseudo cluster is affected.
		 * The graph is now in an INCONSISTENT state!
		 */
		initialCluster.clearEdges();

		/*
		 * Add edges to the corresponding clusters
		 */
		final List<Edge> storedEdgesBetweenClusters = new ArrayList<Edge>();
		for (final Edge edge : storedEdges)
		{
			// edge.getCluster() does not work because the resulting
			// cluster may not be involved!
			final Pair<OrdinaryCluster> clusters = edge.getClusters();

			int pos = clusters.find(firstResultingCluster);
			if (pos < 0)
			{
				pos = clusters.find(secondResultingCluster);
			}
			assert pos >= 0 : "cls: " + clusters;
			final OrdinaryCluster cluster = clusters.get(pos);

			assert !cluster.contains(edge) : "dup: " + edge;
			cluster.addEdgeLocally(edge);

			if (edge.isInterClusterEdge(firstResultingCluster, secondResultingCluster))
			{
				final OrdinaryCluster other = clusters.getOther(cluster);

				other.addEdgeLocally(edge);

				storedEdgesBetweenClusters.add(edge);
			}
		}
		this.edgesBetweenClusters = storedEdgesBetweenClusters.size();

		/*
		 * Check conservation of edges
		 */
		final int interClusterEdgeCountAfter = firstResultingCluster.getInterClusterEdgeCount()
			+ secondResultingCluster.getInterClusterEdgeCount();
		final int intraClusterEdgeCountAfter = firstResultingCluster.getIntraClusterEdgeCount()
			+ secondResultingCluster.getIntraClusterEdgeCount();

		assert interClusterEdgeCountAfter == interClusterEdgeCountBefore
			+ 2 * edgesBetweenClusters : "exp: "
			+ (interClusterEdgeCountBefore + edgesBetweenClusters)
			+ " - act: " + interClusterEdgeCountAfter;
		assert intraClusterEdgeCountAfter == intraClusterEdgeCountBefore
			- edgesBetweenClusters : "exp: " + (intraClusterEdgeCountBefore - edgesBetweenClusters)
			+ " - act: " + intraClusterEdgeCountAfter;

		/*
		 * Update dependend information
		 */
		this.firstResultingCluster.updateTreeWeights();
		this.secondResultingCluster.updateTreeWeights();

		// we only need to check the edges which have now become
		// inter-cluster edges
		for (final Edge edge : storedEdgesBetweenClusters)
		{
			graph.getPseudoCluster().updateStatus(edge);
		}

		/*
		 * Calculate expected edge counts
		 */
		updateExpectedEdgeDensities();
	}