spanning tree computation

calculate the spanning tree for the intersite connection. this patch is in
accord with the section [MS-ADTS] 7.2.2.3.4.4.

1 files changed, 1692 insertions, 0 deletions

diff --git a/source4/dsdb/kcc/kcc_topology.c b/source4/dsdb/kcc/kcc_topology.c
index 50a1fee49b..ea303b9076 100644
--- a/source4/dsdb/kcc/kcc_topology.c
+++ b/source4/dsdb/kcc/kcc_topology.c
@@ -27,10 +27,16 @@
 
 #define FLAG_CR_NTDS_DOMAIN 0x00000002
 
+#define NTDSDSA_OPT_IS_GC 0x00000001
+
+#define NTDSSETTINGS_OPT_IS_TOPL_DETECT_STALE_DISABLED 0x00000008
+#define NTDSSETTINGS_OPT_IS_RAND_BH_SELECTION_DISABLED 0x00000100
 #define NTDSSETTINGS_OPT_W2K3_BRIDGES_REQUIRED 0x00001000
 
 #define NTDSTRANSPORT_OPT_BRIDGES_REQUIRED 0x00000002
 
+#define DS_BEHAVIOR_WIN2008 3
+
 /** replication parameters of a graph edge */
 struct kcctpl_repl_info {
 	uint32_t cost;
@@ -130,6 +136,160 @@ struct message_list {
 };
 
 /**
+ * sort internal edges based on:
+ * - descending red_red,
+ * - ascending repl_info.cost,
+ * - descending available time in repl_info.schedule,
+ * - ascending v1id,
+ * - ascending v2id,
+ * - ascending type.
+ *
+ * this function is used in 'kcctpl_kruskal'.
+ */
+static int kcctpl_sort_internal_edges(const void *internal_edge1,
+				      const void *internal_edge2)
+{
+	const struct kcctpl_internal_edge *ie1, *ie2;
+	int cmp_red_red;
+
+	ie1 = (const struct kcctpl_internal_edge *) internal_edge1;
+	ie2 = (const struct kcctpl_internal_edge *) internal_edge2;
+
+	cmp_red_red = ie2->red_red - ie1->red_red;
+	if (cmp_red_red == 0) {
+		int cmp_cost = ie1->repl_info.cost - ie2->repl_info.cost;
+
+		if (cmp_cost == 0) {
+			uint32_t available1, available2, i;
+			int cmp_schedule;
+
+			available1 = available2 = 0;
+			for (i = 0; i < 84; i++) {
+				if (ie1->repl_info.schedule[i] == 0) {
+					available1++;
+				}
+
+				if (ie2->repl_info.schedule[i] == 0) {
+					available2++;
+				}
+			}
+			cmp_schedule = available2 - available1;
+
+			if (cmp_schedule == 0) {
+				int cmp_v1id = GUID_compare(&ie1->v1id,
+							    &ie2->v1id);
+
+				if (cmp_v1id == 0) {
+					int cmp_v2id = GUID_compare(&ie1->v2id,
+								    &ie2->v2id);
+
+					if (cmp_v2id == 0) {
+						return GUID_compare(&ie1->type,
+								    &ie2->type);
+					} else {
+						return cmp_v2id;
+					}
+				} else {
+					return cmp_v1id;
+				}
+			} else {
+				return cmp_schedule;
+			}
+		} else {
+			return cmp_cost;
+		}
+	} else {
+		return cmp_red_red;
+	}
+}
+
+/**
+ * sort vertices based on the following criteria:
+ * - ascending color (RED < BLACK),
+ * - ascending repl_info.cost,
+ * - ascending id.
+ *
+ * this function is used in 'kcctpl_process_edge'.
+ */
+static int kcctpl_sort_vertices(const void *vertex1, const void *vertex2)
+{
+	const struct kcctpl_vertex *v1, *v2;
+	int cmp_color;
+
+	v1 = (const struct kcctpl_vertex *) vertex1;
+	v2 = (const struct kcctpl_vertex *) vertex2;
+
+	cmp_color = v1->color - v2->color;
+	if (cmp_color == 0) {
+		int cmp_cost = v1->repl_info.cost - v2->repl_info.cost;
+		if (cmp_cost == 0) {
+			return GUID_compare(&v1->id, &v2->id);
+		} else {
+			return cmp_cost;
+		}
+	} else {
+		return cmp_color;
+	}
+}
+
+/**
+ * sort bridgehead elements (nTDSDSA) based on the following criteria:
+ * - GC servers precede non-GC servers
+ * - ascending objectGUID
+ *
+ * this function is used in 'kcctpl_get_all_bridgehead_dcs'.
+ */
+static int kcctpl_sort_bridgeheads(const void *bridgehead1,
+				   const void *bridgehead2)
+{
+	const struct ldb_message *bh1, *bh2;
+	uint64_t bh1_opts, bh2_opts, cmp_gc;
+
+	bh1 = (const struct ldb_message *) bridgehead1;
+	bh2 = (const struct ldb_message *) bridgehead2;
+
+	bh1_opts = samdb_result_int64(bh1, "options", 0);
+	bh2_opts = samdb_result_int64(bh2, "options", 0);
+
+	cmp_gc = (bh1_opts & NTDSDSA_OPT_IS_GC) -
+		 (bh2_opts & NTDSDSA_OPT_IS_GC);
+
+	if (cmp_gc == 0) {
+		struct GUID bh1_id, bh2_id;
+
+		bh1_id = samdb_result_guid(bh1, "objectGUID");
+		bh2_id = samdb_result_guid(bh2, "objectGUID");
+
+		return GUID_compare(&bh1_id, &bh2_id);
+	} else {
+		return cmp_gc;
+	}
+}
+
+/**
+ * sort bridgehead elements (nTDSDSA) in a random order.
+ *
+ * this function is used in 'kcctpl_get_all_bridgehead_dcs'.
+ */
+static void kcctpl_shuffle_bridgeheads(struct message_list bridgeheads)
+{
+	uint32_t i;
+
+	srandom(time(NULL));
+
+	for (i = bridgeheads.count; i > 1; i--) {
+		uint32_t r;
+		struct ldb_message tmp;
+
+		r = random() % i;
+
+		tmp = bridgeheads.data[i - 1];
+		bridgeheads.data[i - 1] = bridgeheads.data[r];
+		bridgeheads.data[r] = tmp;
+	}
+}
+
+/**
  * find a graph vertex based on its GUID.
  */
 static struct kcctpl_vertex *kcctpl_find_vertex_by_guid(struct kcctpl_graph *graph,
@@ -193,6 +353,22 @@ static struct kcctpl_multi_edge *kcctpl_find_edge_by_vertex_guid(struct kcctpl_g
 }
 
 /**
+ * search for an occurrence of a GUID inside a list of GUIDs.
+ */
+static bool kcctpl_guid_list_contains(struct GUID_list list, struct GUID guid)
+{
+	uint32_t i;
+
+	for (i = 0; i < list.count; i++) {
+		if (GUID_equal(&list.data[i], &guid)) {
+			return true;
+		}
+	}
+
+	return false;
+}
+
+/**
  * get the Transports DN
  * (CN=Inter-Site Transports,CN=Sites,CN=Configuration,DC=<domain>).
  */
@@ -248,6 +424,44 @@ static struct ldb_message *kcctpl_local_site(struct ldb_context *ldb,
 	return res->msgs[0];
 }
 
+/*
+ * compare two internal edges for equality. every field of the structure will be
+ * compared.
+ */
+static bool kcctpl_internal_edge_equal(struct kcctpl_internal_edge *edge1,
+				       struct kcctpl_internal_edge *edge2)
+{
+	if (!edge1 || !edge2) {
+		return false;
+	}
+
+	if (!GUID_equal(&edge1->v1id, &edge2->v1id)) {
+		return false;
+	}
+
+	if (!GUID_equal(&edge1->v2id, &edge2->v2id)) {
+		return false;
+	}
+
+	if (edge1->red_red != edge2->red_red) {
+		return false;
+	}
+
+	if (edge1->repl_info.cost != edge2->repl_info.cost ||
+	    edge1->repl_info.interval != edge2->repl_info.interval ||
+	    edge1->repl_info.options != edge2->repl_info.options ||
+	    memcmp(&edge1->repl_info.schedule,
+		   &edge2->repl_info.schedule, 84) != 0) {
+		return false;
+	}
+
+	if (!GUID_equal(&edge1->type, &edge2->type)) {
+		return false;
+	}
+
+	return true;
+}
+
 /**
  * create a kcctpl_graph instance.
  */
@@ -747,6 +961,324 @@ static NTSTATUS kcctpl_setup_graph(struct ldb_context *ldb, TALLOC_CTX *mem_ctx,
 }
 
 /**
+ * determine whether a given DC is known to be in a failed state.
+ */
+static NTSTATUS kcctpl_bridgehead_dc_failed(struct ldb_context *ldb,
+					    struct GUID guid,
+					    bool detect_failed_dcs,
+					    bool *_failed)
+{
+	TALLOC_CTX *tmp_ctx;
+	struct ldb_dn *settings_dn;
+	struct ldb_result *res;
+	const char * const attrs[] = { "options", NULL };
+	int ret;
+	struct ldb_message *settings;
+	uint64_t settings_opts;
+	bool failed;
+
+	tmp_ctx = talloc_new(ldb);
+	NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
+
+	settings_dn = samdb_ntds_settings_dn(ldb);
+	if (!settings_dn) {
+		DEBUG(1, (__location__ ": failed to find our own NTDS Settings "
+			  "DN\n"));
+		talloc_free(tmp_ctx);
+		return NT_STATUS_INTERNAL_DB_CORRUPTION;
+	}
+
+	ret = ldb_search(ldb, tmp_ctx, &res, settings_dn, LDB_SCOPE_BASE, attrs,
+			"objectClass=nTDSSiteSettings");
+	if (ret != LDB_SUCCESS) {
+		DEBUG(1, (__location__ ": failed to find site settings object "
+			  "%s: %s\n", ldb_dn_get_linearized(settings_dn),
+			  ldb_strerror(ret)));
+		talloc_free(tmp_ctx);
+		return NT_STATUS_INTERNAL_DB_CORRUPTION;
+	}
+	if (res->count == 0) {
+		DEBUG(1, ("failed to find site settings object %s\n",
+			  ldb_dn_get_linearized(settings_dn)));
+		talloc_free(tmp_ctx);
+		return NT_STATUS_INTERNAL_DB_CORRUPTION;
+	}
+
+	settings = res->msgs[0];
+
+	settings_opts = samdb_result_int64(settings, "options", 0);
+	if (settings_opts & NTDSSETTINGS_OPT_IS_TOPL_DETECT_STALE_DISABLED) {
+		failed = false;
+	} else if (true) { /* TODO: how to get kCCFailedLinks and
+			      kCCFailedConnections? */
+		failed = true;
+	} else {
+		failed = detect_failed_dcs;
+	}
+
+	*_failed = failed;
+	talloc_free(tmp_ctx);
+	return NT_STATUS_OK;
+}
+
+/**
+ * get all bridgehead DCs satisfying the given criteria.
+ */
+static NTSTATUS kcctpl_get_all_bridgehead_dcs(struct ldb_context *ldb,
+					      TALLOC_CTX *mem_ctx,
+					      struct GUID site_guid,
+					      struct ldb_message *cross_ref,
+					      struct ldb_message *transport,
+					      bool partial_replica_okay,
+					      bool detect_failed_dcs,
+					      struct message_list *_bridgeheads)
+{
+	struct message_list bridgeheads, all_dcs_in_site;
+	TALLOC_CTX *tmp_ctx;
+	struct ldb_result *res;
+	struct ldb_dn *sites_dn, *schemas_dn;
+	const char * const attrs[] = { "options", NULL };
+	int ret;
+	struct ldb_message *site, *schema;
+	const char * const dc_attrs[] = { "objectGUID", "options", NULL };
+	struct ldb_message_element *el;
+	uint32_t i;
+	bool rodc;
+	const char *transport_name, *transport_address_attr;
+	uint64_t site_opts;
+
+	ZERO_STRUCT(bridgeheads);
+
+	tmp_ctx = talloc_new(mem_ctx);
+	NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
+
+	sites_dn = samdb_sites_dn(ldb, tmp_ctx);
+	if (!sites_dn) {
+		DEBUG(1, (__location__ ": failed to find our own Sites DN\n"));
+
+		talloc_free(tmp_ctx);
+		return NT_STATUS_INTERNAL_DB_CORRUPTION;
+	}
+
+	ret = ldb_search(ldb, tmp_ctx, &res, sites_dn, LDB_SCOPE_ONELEVEL,
+			 attrs, "(&(objectClass=site)(objectGUID=%s))",
+			 GUID_string(tmp_ctx, &site_guid));
+	if (ret != LDB_SUCCESS) {
+		DEBUG(1, (__location__ ": failed to find site object %s: %s\n",
+			  GUID_string(tmp_ctx, &site_guid),
+			  ldb_strerror(ret)));
+
+		talloc_free(tmp_ctx);
+		return NT_STATUS_INTERNAL_DB_CORRUPTION;
+	}
+	if (res->count == 0) {
+		DEBUG(1, (__location__ ": failed to find site object %s\n",
+			  GUID_string(tmp_ctx, &site_guid)));
+
+		talloc_free(tmp_ctx);
+		return NT_STATUS_INTERNAL_DB_CORRUPTION;
+	}
+	site = res->msgs[0];
+
+	schemas_dn = samdb_schema_dn(ldb);
+	if (!schemas_dn) {
+		DEBUG(1, (__location__ ": failed to find our own Schemas DN\n"));
+
+		talloc_free(tmp_ctx);
+		return NT_STATUS_INTERNAL_DB_CORRUPTION;
+	}
+
+	ret = ldb_search(ldb, tmp_ctx, &res, schemas_dn, LDB_SCOPE_SUBTREE,
+			 NULL,
+			"(&(lDAPDisplayName=nTDSDSA)(objectClass=classSchema))");
+	if (ret != LDB_SUCCESS) {
+		DEBUG(1, (__location__ ": failed to find classSchema object :"
+			  "%s\n", ldb_strerror(ret)));
+
+		talloc_free(tmp_ctx);
+		return NT_STATUS_INTERNAL_DB_CORRUPTION;
+	}
+	if (res->count == 0) {
+		DEBUG(1, (__location__ ": failed to find classSchema "
+			  "object\n"));
+
+		talloc_free(tmp_ctx);
+		return NT_STATUS_INTERNAL_DB_CORRUPTION;
+	}
+	schema = res->msgs[0];
+
+	ZERO_STRUCT(all_dcs_in_site);
+
+	ret = ldb_search(ldb, tmp_ctx, &res, site->dn, LDB_SCOPE_SUBTREE,
+			dc_attrs, "objectCategory=%s",
+			ldb_dn_get_linearized(schema->dn));
+	if (ret != LDB_SUCCESS) {
+		DEBUG(1, (__location__ ": failed to find DCs objects :%s\n",
+			  ldb_strerror(ret)));
+
+		talloc_free(tmp_ctx);
+		return NT_STATUS_INTERNAL_DB_CORRUPTION;
+	}
+
+	el = ldb_msg_find_element(transport, "bridgeheadServerListBL");
+
+	rodc = samdb_rodc(ldb);
+
+	transport_name = samdb_result_string(transport, "name", NULL);
+	if (!transport_name) {
+		DEBUG(1, (__location__ ": failed to find name attribute of "
+			  "object %s\n", ldb_dn_get_linearized(transport->dn)));
+
+		talloc_free(tmp_ctx);
+		return NT_STATUS_INTERNAL_DB_CORRUPTION;
+	}
+
+	transport_address_attr = samdb_result_string(transport,
+						     "transportAddressAttribute",
+						     NULL);
+	if (!transport_address_attr) {
+		DEBUG(1, (__location__ ": failed to find "
+			  "transportAddressAttribute attribute of object %s\n",
+			  ldb_dn_get_linearized(transport->dn)));
+
+		talloc_free(tmp_ctx);
+		return NT_STATUS_INTERNAL_DB_CORRUPTION;
+	}
+
+	site_opts = samdb_result_int64(site, "options", 0);
+
+	for (i = 0; i < res->count; i++) {
+		struct ldb_message *dc, *new_data;
+		uint32_t j;
+		struct ldb_dn *parent_dn;
+		uint64_t behavior_version;
+		const char *dc_transport_address;
+		struct ldb_result *parent_res;
+		const char *parent_attrs[] = { transport_address_attr, NULL };
+		NTSTATUS status;
+		struct GUID dc_guid;
+		bool failed;
+
+		dc = res->msgs[i];
+
+		parent_dn = ldb_dn_get_parent(tmp_ctx, dc->dn);
+		if (!parent_dn) {
+			DEBUG(1, (__location__ ": failed to get parent DN of "
+				  "%s\n", ldb_dn_get_linearized(dc->dn)));
+
+			talloc_free(tmp_ctx);
+			return NT_STATUS_INTERNAL_DB_CORRUPTION;
+		}
+
+		if (el && (el->num_values >= 1)) {
+			bool contains = false;
+
+			for (j = 0; j < el->num_values; j++) {
+				struct ldb_val val;
+				struct ldb_dn *dn;
+
+				val = el->values[j];
+
+				dn = ldb_dn_from_ldb_val(tmp_ctx, ldb, &val);
+				if (!dn) {
+					DEBUG(1, (__location__ ": failed to read a DN "
+						  "from bridgeheadServerListBL "
+						  "attribute of %s\n",
+						  ldb_dn_get_linearized(transport->dn)));
+
+					talloc_free(tmp_ctx);
+					return NT_STATUS_INTERNAL_DB_CORRUPTION;
+				}
+
+				if (ldb_dn_compare(dn, parent_dn) == 0) {
+					contains = true;
+					break;
+				}
+			}
+
+			if (!contains) {
+				continue;
+			}
+		}
+
+		/* TODO: if dc is in the same site as the local DC */
+		if (true) {
+			/* TODO: if a replica of cr!nCName is not in the set of
+			 * NC replicas that "should be present" on 'dc' */
+			/* TODO: a partial replica of the NC "should be
+			   present" */
+			if (true || (true && !partial_replica_okay)) {
+				continue;
+			}
+		} else {
+			/* TODO: if an NC replica of cr!nCName is not in the set
+			 * of NC replicas that "are present" on 'dc' */
+			/* TODO: a partial replica of the NC "is present" */
+			if (true || (true && !partial_replica_okay)) {
+				continue;
+			}
+		}
+
+		behavior_version = samdb_result_int64(dc,
+						      "msDS-Behavior-Version", 0);
+		/* TODO: cr!nCName corresponds to default NC */
+		if (rodc && true && behavior_version < DS_BEHAVIOR_WIN2008) {
+			continue;
+		}
+
+		ret = ldb_search(ldb, tmp_ctx, &parent_res, parent_dn,
+				LDB_SCOPE_BASE, parent_attrs , NULL);
+
+		dc_transport_address = samdb_result_string(parent_res->msgs[0],
+							   transport_address_attr,
+							   NULL);
+
+		if (strncmp(transport_name, "IP", 2) != 0 &&
+		    dc_transport_address == NULL) {
+			continue;
+		}
+
+		dc_guid = samdb_result_guid(dc, "objectGUID");
+
+		status = kcctpl_bridgehead_dc_failed(ldb, dc_guid,
+						     detect_failed_dcs,
+						     &failed);
+		if (NT_STATUS_IS_ERR(status)) {
+			DEBUG(1, (__location__ ": failed to check if "
+				  "bridgehead DC has failed: %s\n",
+				  nt_errstr(status)));
+
+			talloc_free(tmp_ctx);
+			return status;
+		}
+
+		if (failed) {
+			continue;
+		}
+
+		new_data = talloc_realloc(tmp_ctx, bridgeheads.data,
+					  struct ldb_message,
+					  bridgeheads.count + 1);
+		NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data, tmp_ctx);
+		new_data[bridgeheads.count + 1] = *dc;
+		bridgeheads.data = new_data;
+		bridgeheads.count++;
+	}
+
+	if (site_opts & NTDSSETTINGS_OPT_IS_RAND_BH_SELECTION_DISABLED) {
+		qsort(bridgeheads.data, bridgeheads.count,
+		      sizeof(struct ldb_message), kcctpl_sort_bridgeheads);
+	} else {
+		kcctpl_shuffle_bridgeheads(bridgeheads);
+	}
+
+	talloc_steal(mem_ctx, bridgeheads.data);
+	*_bridgeheads = bridgeheads;
+	talloc_free(tmp_ctx);
+	return NT_STATUS_OK;
+}
+
+/**
  * get a bridgehead DC.
  */
 static NTSTATUS kcctpl_get_bridgehead_dc(struct ldb_context *ldb,
@@ -758,6 +1290,21 @@ static NTSTATUS kcctpl_get_bridgehead_dc(struct ldb_context *ldb,
 					 bool detect_failed_dcs,
 					 struct ldb_message **_dsa)
 {
+	struct message_list dsa_list;
+	NTSTATUS status;
+
+	status = kcctpl_get_all_bridgehead_dcs(ldb, mem_ctx,
+					       site_guid, cross_ref, transport,
+					       partial_replica_okay,
+					       detect_failed_dcs, &dsa_list);
+	if (NT_STATUS_IS_ERR(status)) {
+		DEBUG(1, (__location__ ": failed to get all bridgehead DCs: "
+			  "%s\n", nt_errstr(status)));
+		return status;
+	}
+
+	*_dsa = (dsa_list.count == 0) ? NULL : &dsa_list.data[0];
+
 	return NT_STATUS_OK;
 }
 
@@ -974,3 +1521,1148 @@ static NTSTATUS kcctpl_color_vertices(struct ldb_context *ldb,
 	talloc_free(tmp_ctx);
 	return NT_STATUS_OK;
 }
+
+/**
+ * setup the fields of the vertices that are relevant to Phase I (Dijkstra's
+ * Algorithm). for each vertex, set up its cost, root vertex and component. this
+ * defines the shortest-path forest structures.
+ */
+static void kcctpl_setup_vertices(struct kcctpl_graph *graph)
+{
+	uint32_t i;
+
+	for (i = 0; i < graph->vertices.count; i++) {
+		struct kcctpl_vertex *vertex = &graph->vertices.data[i];
+
+		if (vertex->color == WHITE) {
+			vertex->repl_info.cost = UINT32_MAX;
+			vertex->root_id = vertex->component_id = GUID_zero();
+		} else {
+			vertex->repl_info.cost = 0;
+			vertex->root_id = vertex->component_id = vertex->id;
+		}
+
+		vertex->repl_info.interval = 0;
+		vertex->repl_info.options = 0xFFFFFFFF;
+		ZERO_STRUCT(vertex->repl_info.schedule);
+		vertex->demoted = false;
+	}
+}
+
+/**
+ * demote one vertex if necessary.
+ */
+static void kcctpl_check_demote_one_vertex(struct kcctpl_vertex *vertex,
+					   struct GUID type)
+{
+	if (vertex->color == WHITE) {
+		return;
+	}
+
+	if (!kcctpl_guid_list_contains(vertex->accept_black, type) &&
+	    !kcctpl_guid_list_contains(vertex->accept_red_red, type)) {
+		vertex->repl_info.cost = UINT32_MAX;
+		vertex->root_id = GUID_zero();
+		vertex->demoted = true;
+	}
+}
+
+/**
+ * clear the demoted state of a vertex.
+ */
+static void kcctpl_undemote_one_vertex(struct kcctpl_vertex *vertex)
+{
+	if (vertex->color == WHITE) {
+		return;
+	}
+
+	vertex->repl_info.cost = 0;
+	vertex->root_id = vertex->id;
+	vertex->demoted = false;
+}
+
+/**
+ * returns the id of the component containing 'vertex' by traversing the up-tree
+ * implied by the component pointers.
+ */
+static struct GUID kcctpl_get_component_id(struct kcctpl_graph *graph,
+					   struct kcctpl_vertex *vertex)
+{
+	struct kcctpl_vertex *u;
+	struct GUID root;
+
+	u = vertex;
+	while (!GUID_equal(&u->component_id, &u->id)) {
+		u = kcctpl_find_vertex_by_guid(graph, u->component_id);
+	}
+
+	root = u->id;
+
+	u = vertex;
+	while (!GUID_equal(&u->component_id, &u->id)) {
+		struct kcctpl_vertex *w;
+
+		w = kcctpl_find_vertex_by_guid(graph, u->component_id);
+		u->component_id = root;
+		u = w;
+	}
+
+	return root;
+}
+
+/**
+ * copy all spanning tree edges from 'output_edges' that contain the vertex for
+ * DCs in the local DC's site.
+ */
+static NTSTATUS kcctpl_copy_output_edges(struct ldb_context *ldb,
+					 TALLOC_CTX *mem_ctx,
+					 struct kcctpl_graph *graph,
+					 struct kcctpl_multi_edge_list output_edges,
+					 struct kcctpl_multi_edge_list *_copy)
+{
+	struct kcctpl_multi_edge_list copy;
+	TALLOC_CTX *tmp_ctx;
+	struct ldb_message *site;
+	struct GUID site_guid;
+	uint32_t i;
+
+	ZERO_STRUCT(copy);
+
+	tmp_ctx = talloc_new(ldb);
+	NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
+
+	site = kcctpl_local_site(ldb, tmp_ctx);
+	if (!site) {
+		DEBUG(1, (__location__ ": failed to find our own local DC's "
+			  "site\n"));
+
+		talloc_free(tmp_ctx);
+		return NT_STATUS_INTERNAL_DB_CORRUPTION;
+	}
+	site_guid = samdb_result_guid(site, "objectGUID");
+
+	for (i = 0; i < output_edges.count; i++) {
+		struct kcctpl_multi_edge *edge;
+		struct kcctpl_vertex *vertex1, *vertex2;
+
+		edge = &output_edges.data[i];
+
+		vertex1 = kcctpl_find_vertex_by_guid(graph,
+						     edge->vertex_ids.data[0]);
+		if (!vertex1) {
+			DEBUG(1, (__location__ ": failed to find vertex %s\n",
+				  GUID_string(tmp_ctx,
+					      &edge->vertex_ids.data[0])));
+			talloc_free(tmp_ctx);
+			return NT_STATUS_INTERNAL_DB_CORRUPTION;
+		}
+
+		vertex2 = kcctpl_find_vertex_by_guid(graph,
+						     edge->vertex_ids.data[1]);
+		if (!vertex2) {
+			DEBUG(1, (__location__ ": failed to find vertex %s\n",
+				  GUID_string(tmp_ctx,
+					      &edge->vertex_ids.data[1])));
+			talloc_free(tmp_ctx);
+			return NT_STATUS_INTERNAL_DB_CORRUPTION;
+		}
+
+		if (GUID_equal(&vertex1->id, &site_guid) ||
+		    GUID_equal(&vertex2->id, &site_guid)) {
+			struct kcctpl_multi_edge *new_data;
+
+			if ((vertex1->color == BLACK ||
+			     vertex2->color == BLACK) &&
+			    vertex1->dist_to_red != UINT32_MAX) {
+
+				edge->directed = true;
+
+				if (vertex2->dist_to_red <
+				    vertex1->dist_to_red) {
+					struct GUID tmp;
+
+					tmp = edge->vertex_ids.data[0];
+					edge->vertex_ids.data[0] = edge->vertex_ids.data[1];
+					edge->vertex_ids.data[1] = tmp;
+				}
+			}
+
+			new_data = talloc_realloc(tmp_ctx, copy.data,
+						  struct kcctpl_multi_edge,
+						  copy.count + 1);
+			NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data, tmp_ctx);
+			new_data[copy.count + 1] = *edge;
+			copy.data = new_data;
+			copy.count++;
+		}
+	}
+
+	talloc_steal(mem_ctx, copy.data);
+	*_copy = copy;
+	return NT_STATUS_OK;
+}
+
+/**
+ * build the initial sequence for use with Dijkstra's algorithm. it will contain
+ * the red and black vertices as root vertices, unless these vertices accept no
+ * edges of the current 'type', or unless black vertices are not being
+ * including.
+ */
+static NTSTATUS kcctpl_setup_dijkstra(TALLOC_CTX *mem_ctx,
+				      struct kcctpl_graph *graph,
+				      struct GUID type, bool include_black,
+				      struct kcctpl_vertex_list *_vertices)
+{
+	struct kcctpl_vertex_list vertices;
+	uint32_t i;
+
+	kcctpl_setup_vertices(graph);
+
+	ZERO_STRUCT(vertices);
+
+	for (i = 0; i < graph->vertices.count; i++) {
+		struct kcctpl_vertex *vertex = &graph->vertices.data[i];
+
+		if (vertex->color == WHITE) {
+			continue;
+		}
+
+		if ((vertex->color == BLACK && !include_black) ||
+		    !kcctpl_guid_list_contains(vertex->accept_black, type) ||
+		    !kcctpl_guid_list_contains(vertex->accept_red_red, type)) {
+			vertex->repl_info.cost = UINT32_MAX;
+			vertex->root_id = GUID_zero();
+			vertex->demoted = true;
+		} else {
+			struct kcctpl_vertex *new_data;
+
+			new_data = talloc_realloc(mem_ctx, vertices.data,
+						  struct kcctpl_vertex,
+						  vertices.count + 1);
+			NT_STATUS_HAVE_NO_MEMORY(new_data);
+			new_data[vertices.count] = *vertex;
+			vertices.data = new_data;
+			vertices.count++;
+		}
+	}
+
+	*_vertices = vertices;
+	return NT_STATUS_OK;
+}
+
+/**
+ * merge schedules, replication intervals, options and costs.
+ */
+static bool kcctpl_combine_repl_info(struct kcctpl_graph *graph,
+				     struct kcctpl_repl_info *ria,
+				     struct kcctpl_repl_info *rib,
+				     struct kcctpl_repl_info *ric)
+{
+	uint8_t schedule[84];
+	bool is_available;
+	uint32_t i;
+	int32_t ric_cost;
+
+	is_available = false;
+	for (i = 0; i < 84; i++) {
+		schedule[i] = ria->schedule[i] & rib->schedule[i];
+
+		if (schedule[i] == 1) {
+			is_available = true;
+		}
+	}
+	if (!is_available) {
+		return false;
+	}
+
+	ric_cost = ria->cost + rib->cost;
+	ric->cost = (ric_cost < 0) ? UINT32_MAX : ric_cost;
+
+	ric->interval = MAX(ria->interval, rib->interval);
+	ric->options = ria->options & rib->options;
+	memcpy(&ric->schedule, &schedule, 84);
+
+	return true;
+}
+
+/**
+ * helper function for Dijkstra's algorithm. a new path has been found from a
+ * root vertex to vertex 'vertex2'. this path is ('vertex1->root, ..., vertex1,
+ * vertex2'). 'edge' is the edge connecting 'vertex1' and 'vertex2'. if this new
+ * path is better (in this case cheaper, or has a longer schedule), update
+ * 'vertex2' to use the new path.
+ */
+static NTSTATUS kcctpl_try_new_path(TALLOC_CTX *mem_ctx,
+				    struct kcctpl_graph *graph,
+				    struct kcctpl_vertex_list vertices,
+				    struct kcctpl_vertex *vertex1,
+				    struct kcctpl_multi_edge *edge,
+				    struct kcctpl_vertex *vertex2)
+{
+	struct kcctpl_repl_info new_repl_info;
+	bool intersect;
+	uint32_t i, new_duration, old_duration;
+
+	ZERO_STRUCT(new_repl_info);
+
+	intersect = kcctpl_combine_repl_info(graph, &vertex1->repl_info,
+					     &edge->repl_info, &new_repl_info);
+
+	if (new_repl_info.cost > vertex2->repl_info.cost) {
+		return NT_STATUS_OK;
+	}
+
+	if (new_repl_info.cost < vertex2->repl_info.cost && !intersect) {
+		return NT_STATUS_OK;
+	}
+
+	new_duration = old_duration = 0;
+	for (i = 0; i < 84; i++) {
+		if (new_repl_info.schedule[i] == 1) {
+			new_duration++;
+		}
+
+		if (vertex2->repl_info.schedule[i] == 1) {
+			old_duration++;
+		}
+	}
+
+	if (new_repl_info.cost < vertex2->repl_info.cost ||
+	    new_duration > old_duration) {
+		struct kcctpl_vertex *new_data;
+
+		vertex2->root_id = vertex1->root_id;
+		vertex2->component_id = vertex1->component_id;
+		vertex2->repl_info = new_repl_info;
+
+		new_data = talloc_realloc(mem_ctx, vertices.data,
+					  struct kcctpl_vertex,
+					  vertices.count + 1);
+		NT_STATUS_HAVE_NO_MEMORY(new_data);
+		new_data[vertices.count + 1] = *vertex2;
+		vertices.data = new_data;
+		vertices.count++;
+	}
+
+	return NT_STATUS_OK;
+}
+
+/**
+ * run Dijkstra's algorithm with the red (and possibly black) vertices as the
+ * root vertices, and build up a shortest-path forest.
+ */
+static NTSTATUS kcctpl_dijkstra(struct kcctpl_graph *graph, struct GUID type,
+				bool include_black)
+{
+	TALLOC_CTX *tmp_ctx;
+	struct kcctpl_vertex_list vertices;
+	NTSTATUS status;
+
+	tmp_ctx = talloc_new(graph);
+	NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
+
+	status = kcctpl_setup_dijkstra(tmp_ctx, graph, type, include_black,
+				       &vertices);
+	if (NT_STATUS_IS_ERR(status)) {
+		DEBUG(1, (__location__ ": failed to build the initial sequence "
+			  "for Dijkstra's algorithm: %s\n", nt_errstr(status)));
+
+		talloc_free(tmp_ctx);
+		return status;
+	}
+
+	while (vertices.count > 0) {
+		uint32_t minimum_cost, minimum_index, i;
+		struct kcctpl_vertex *minimum_vertex, *new_data;
+
+		minimum_cost = UINT32_MAX;
+		minimum_index = -1;
+		minimum_vertex = NULL;
+		for (i = 0; i < vertices.count; i++) {
+			struct kcctpl_vertex *vertex = &vertices.data[i];
+
+			if (vertex->repl_info.cost < minimum_cost) {
+				minimum_cost = vertex->repl_info.cost;
+				minimum_vertex = vertex;
+				minimum_index = i;
+			} else if (vertex->repl_info.cost == minimum_cost &&
+				   GUID_compare(&vertex->id,
+					        &minimum_vertex->id) < 0) {
+				minimum_vertex = vertex;
+				minimum_index = i;
+			}
+		}
+
+		if (minimum_index < vertices.count - 1) {
+			memcpy(&vertices.data[minimum_index + 1],
+			       &vertices.data[minimum_index],
+			       vertices.count - minimum_index - 1);
+		}
+		new_data = talloc_realloc(tmp_ctx, vertices.data,
+					  struct kcctpl_vertex,
+					  vertices.count - 1);
+		NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data, tmp_ctx);
+		talloc_free(vertices.data);
+		vertices.data = new_data;
+		vertices.count--;
+
+		for (i = 0; i < graph->edges.count; i++) {
+			struct kcctpl_multi_edge *edge = &graph->edges.data[i];
+
+			if (kcctpl_guid_list_contains(minimum_vertex->edge_ids,
+						      edge->id)) {
+				uint32_t j;
+
+				for (j = 0; j < edge->vertex_ids.count; j++) {
+					struct GUID vertex_id;
+					struct kcctpl_vertex *vertex;
+
+					vertex_id = edge->vertex_ids.data[j];
+					vertex = kcctpl_find_vertex_by_guid(graph,
+									    vertex_id);
+					if (!vertex) {
+						DEBUG(1, (__location__
+							  ": failed to find "
+							  "vertex %s\n",
+							  GUID_string(tmp_ctx,
+								      &vertex_id)));
+
+						talloc_free(tmp_ctx);
+						return NT_STATUS_INTERNAL_DB_CORRUPTION;
+					}
+
+					kcctpl_try_new_path(tmp_ctx, graph,
+							    vertices,
+							    minimum_vertex,
+							    edge, vertex);
+				}
+			}
+		}
+	}
+
+	talloc_free(tmp_ctx);
+	return NT_STATUS_OK;
+}
+
+/**
+ * add an edge to the list of edges that will be processed with Kruskal's. the
+ * endpoints are in fact the root of the vertices to pass in, so the endpoints
+ * are always colored vertices.
+ */
+static NTSTATUS kcctpl_add_int_edge(TALLOC_CTX *mem_ctx,
+				    struct kcctpl_graph *graph,
+				    struct kcctpl_internal_edge_list internal_edges,
+				    struct kcctpl_multi_edge *edge,
+				    struct kcctpl_vertex *vertex1,
+				    struct kcctpl_vertex *vertex2)
+{
+	struct kcctpl_vertex *root1, *root2;
+	bool red_red, found;
+	struct kcctpl_repl_info repl_info1, repl_info2;
+	struct kcctpl_internal_edge new_internal_edge, *new_data;
+	uint32_t i;
+
+	root1 = kcctpl_find_vertex_by_guid(graph, vertex1->root_id);
+	if (!root1) {
+		TALLOC_CTX *tmp_ctx = talloc_new(graph);
+		NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
+
+		DEBUG(1, (__location__ ": failed to find vertex %s\n",
+			  GUID_string(tmp_ctx, &vertex1->root_id)));
+
+		talloc_free(tmp_ctx);
+		return NT_STATUS_INTERNAL_DB_CORRUPTION;
+	}
+
+	root2 = kcctpl_find_vertex_by_guid(graph, vertex2->root_id);
+	if (!root2) {
+		TALLOC_CTX *tmp_ctx = talloc_new(graph);
+		NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
+
+		DEBUG(1, (__location__ ": failed to find vertex %s\n",
+			  GUID_string(tmp_ctx, &vertex2->root_id)));
+
+		talloc_free(tmp_ctx);
+		return NT_STATUS_INTERNAL_DB_CORRUPTION;
+	}
+
+	red_red = (root1->color == RED && root2->color == RED);
+
+	if (red_red) {
+		if (!kcctpl_guid_list_contains(root1->accept_red_red,
+					       edge->type) ||
+		    !kcctpl_guid_list_contains(root2->accept_red_red,
+					       edge->type)) {
+			return NT_STATUS_OK;
+		}
+	} else if (!kcctpl_guid_list_contains(root1->accept_black,
+					      edge->type) ||
+		   !kcctpl_guid_list_contains(root2->accept_black,
+					      edge->type)) {
+		return NT_STATUS_OK;
+	}
+
+	if (!kcctpl_combine_repl_info(graph, &vertex1->repl_info,
+				      &vertex2->repl_info, &repl_info1) ||
+	    !kcctpl_combine_repl_info(graph, &repl_info1, &edge->repl_info,
+				      &repl_info2)) {
+		return NT_STATUS_OK;
+	}
+
+	new_internal_edge.v1id = root1->id;
+	new_internal_edge.v2id = root2->id;
+	new_internal_edge.red_red = red_red;
+	new_internal_edge.repl_info = repl_info2;
+	new_internal_edge.type = edge->type;
+
+	if (GUID_compare(&new_internal_edge.v1id,
+			 &new_internal_edge.v2id) > 0) {
+		struct GUID tmp_guid = new_internal_edge.v1id;
+
+		new_internal_edge.v1id = new_internal_edge.v2id;
+		new_internal_edge.v2id = tmp_guid;
+	}
+
+	found = false;
+	for (i = 0; i < internal_edges.count; i++) {
+		struct kcctpl_internal_edge *ie = &internal_edges.data[i];
+
+		if (kcctpl_internal_edge_equal(ie, &new_internal_edge)) {
+			found = true;
+		}
+	}
+	if (found) {
+		return NT_STATUS_OK;
+	}
+
+	new_data = talloc_realloc(mem_ctx, internal_edges.data,
+				  struct kcctpl_internal_edge,
+				  internal_edges.count + 1);
+	NT_STATUS_HAVE_NO_MEMORY(new_data);
+	new_data[internal_edges.count + 1] = new_internal_edge;
+	internal_edges.data = new_data;
+	internal_edges.count++;
+
+	return NT_STATUS_OK;
+}
+
+/**
+ * after running Dijkstra's algorithm, this function examines a multi-edge and
+ * adds internal edges between every tree connected by this edge.
+ */
+static NTSTATUS kcctpl_process_edge(TALLOC_CTX *mem_ctx,
+				    struct kcctpl_graph *graph,
+				    struct kcctpl_multi_edge *edge,
+				    struct kcctpl_internal_edge_list internal_edges)
+{
+	TALLOC_CTX *tmp_ctx;
+	struct kcctpl_vertex_list vertices;
+	uint32_t i;
+	struct kcctpl_vertex *best_vertex;
+
+	ZERO_STRUCT(vertices);
+
+	tmp_ctx = talloc_new(mem_ctx);
+	NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
+
+	for (i = 0; i < edge->vertex_ids.count; i++) {
+		struct GUID id;
+		struct kcctpl_vertex *vertex, *new_data;
+
+		id = edge->vertex_ids.data[i];
+
+		vertex = kcctpl_find_vertex_by_guid(graph, id);
+		if (!vertex) {
+			DEBUG(1, (__location__ ": failed to find vertex %s\n",
+				  GUID_string(tmp_ctx, &id)));
+
+			talloc_free(tmp_ctx);
+			return NT_STATUS_INTERNAL_DB_CORRUPTION;
+		}
+
+		new_data = talloc_realloc(tmp_ctx, vertices.data,
+					  struct kcctpl_vertex,
+					  vertices.count + 1);
+		NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data, tmp_ctx);
+		new_data[vertices.count] = *vertex;
+		vertices.data = new_data;
+		vertices.count++;
+	}
+
+	qsort(vertices.data, vertices.count, sizeof(struct kcctpl_vertex),
+	      kcctpl_sort_vertices);
+
+	best_vertex = &vertices.data[0];
+
+	for (i = 0; i < edge->vertex_ids.count; i++) {
+		struct GUID id, empty_id = GUID_zero();
+		struct kcctpl_vertex *vertex = &graph->vertices.data[i];
+
+		id = edge->vertex_ids.data[i];
+
+		vertex = kcctpl_find_vertex_by_guid(graph, id);
+		if (!vertex) {
+			DEBUG(1, (__location__ ": failed to find vertex %s\n",
+				  GUID_string(tmp_ctx, &id)));
+
+			talloc_free(tmp_ctx);
+			return NT_STATUS_INTERNAL_DB_CORRUPTION;
+		}
+
+		if (!GUID_equal(&vertex->component_id, &empty_id) &&
+		    !GUID_equal(&vertex->root_id, &empty_id)) {
+			continue;
+		}
+
+		if (!GUID_equal(&best_vertex->component_id,
+				&empty_id) &&
+		    !GUID_equal(&best_vertex->root_id, &empty_id) &&
+		    !GUID_equal(&vertex->component_id, &empty_id) &&
+		    !GUID_equal(&vertex->root_id, &empty_id) &&
+		    !GUID_equal(&best_vertex->component_id,
+				&vertex->component_id)) {
+			NTSTATUS status;
+
+			status = kcctpl_add_int_edge(mem_ctx, graph,
+						     internal_edges,
+						     edge, best_vertex,
+						     vertex);
+			if (NT_STATUS_IS_ERR(status)) {
+				DEBUG(1, (__location__ ": failed to add an "
+					  "internal edge for %s: %s\n",
+					  GUID_string(tmp_ctx, &vertex->id),
+					  nt_errstr(status)));
+				talloc_free(tmp_ctx);
+				return status;
+			}
+		}
+	}
+
+	talloc_free(tmp_ctx);
+	return NT_STATUS_OK;
+}
+
+/**
+ * after running Dijkstra's algorithm to determine the shortest-path forest,
+ * examine all edges in this edge set. find all inter-tree edges, from which to
+ * build the list of 'internal edges', which will later be passed on to
+ * Kruskal's algorithm.
+ */
+static NTSTATUS kcctpl_process_edge_set(TALLOC_CTX *mem_ctx,
+					struct kcctpl_graph *graph,
+					struct kcctpl_multi_edge_set *set,
+					struct kcctpl_internal_edge_list internal_edges)
+{
+	uint32_t i;
+
+	if (!set) {
+		for (i = 0; i < graph->edges.count; i++) {
+			struct kcctpl_multi_edge *edge;
+			uint32_t j;
+			NTSTATUS status;
+
+			edge = &graph->edges.data[i];
+
+			for (j = 0; j < edge->vertex_ids.count; j++) {
+				struct GUID id;
+				struct kcctpl_vertex *vertex;
+
+				id = edge->vertex_ids.data[j];
+
+				vertex = kcctpl_find_vertex_by_guid(graph, id);
+				if (!vertex) {
+					TALLOC_CTX *tmp_ctx;
+
+					tmp_ctx = talloc_new(mem_ctx);
+					NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
+
+					DEBUG(1, (__location__ ": failed to "
+						  "find vertex %s\n",
+						  GUID_string(tmp_ctx, &id)));
+
+					talloc_free(tmp_ctx);
+					return NT_STATUS_INTERNAL_DB_CORRUPTION;
+				}
+
+				kcctpl_check_demote_one_vertex(vertex,
+							       edge->type);
+			}
+
+			status = kcctpl_process_edge(mem_ctx, graph, edge,
+						     internal_edges);
+			if (NT_STATUS_IS_ERR(status)) {
+				TALLOC_CTX *tmp_ctx = talloc_new(mem_ctx);
+				NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
+
+				DEBUG(1, (__location__ ": failed to process "
+					  "edge %s: %s\n",
+					  GUID_string(tmp_ctx, &edge->id),
+					  nt_errstr(status)));
+
+				talloc_free(tmp_ctx);
+				return status;
+			}
+
+			for (j = 0; j < edge->vertex_ids.count; j++) {
+				struct GUID id;
+				struct kcctpl_vertex *vertex;
+
+				id = edge->vertex_ids.data[j];
+
+				vertex = kcctpl_find_vertex_by_guid(graph, id);
+				if (!vertex) {
+					TALLOC_CTX *tmp_ctx;
+
+					tmp_ctx = talloc_new(mem_ctx);
+					NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
+
+					DEBUG(1, (__location__ ": failed to "
+						  "find vertex %s\n",
+						  GUID_string(tmp_ctx, &id)));
+
+					talloc_free(tmp_ctx);
+					return NT_STATUS_INTERNAL_DB_CORRUPTION;
+				}
+
+				kcctpl_undemote_one_vertex(vertex);
+			}
+		}
+	} else {
+		for (i = 0; i < graph->edges.count; i++) {
+			struct kcctpl_multi_edge *edge = &graph->edges.data[i];
+
+			if (kcctpl_guid_list_contains(set->edge_ids,
+						      edge->id)) {
+				NTSTATUS status;
+
+				status = kcctpl_process_edge(mem_ctx, graph,
+							     edge,
+							     internal_edges);
+				if (NT_STATUS_IS_ERR(status)) {
+					TALLOC_CTX *tmp_ctx;
+
+					tmp_ctx = talloc_new(mem_ctx);
+					NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
+
+					DEBUG(1, (__location__ ": failed to "
+						  "process edge %s: %s\n",
+						  GUID_string(tmp_ctx,
+							      &edge->id),
+						  nt_errstr(status)));
+
+					talloc_free(tmp_ctx);
+					return status;
+				}
+			}
+		}
+	}
+
+	return NT_STATUS_OK;
+}
+
+/**
+ * a new edge, 'internal_edge', has been found for the spanning tree edge. add
+ * this edge to the list of output edges.
+ */
+static NTSTATUS kcctpl_add_out_edge(TALLOC_CTX *mem_ctx,
+				    struct kcctpl_graph *graph,
+				    struct kcctpl_multi_edge_list output_edges,
+				    struct kcctpl_internal_edge *internal_edge)
+{
+	struct kcctpl_vertex *vertex1, *vertex2;
+	TALLOC_CTX *tmp_ctx;
+	struct kcctpl_multi_edge *new_edge, *new_data;
+	struct GUID *new_data_id;
+
+	tmp_ctx = talloc_new(mem_ctx);
+	NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
+
+	vertex1 = kcctpl_find_vertex_by_guid(graph, internal_edge->v1id);
+	if (!vertex1) {
+		DEBUG(1, (__location__ ": failed to find vertex %s\n",
+			  GUID_string(tmp_ctx, &internal_edge->v1id)));
+
+		talloc_free(tmp_ctx);
+		return NT_STATUS_INTERNAL_DB_CORRUPTION;
+	}
+
+	vertex2 = kcctpl_find_vertex_by_guid(graph, internal_edge->v2id);
+	if (!vertex2) {
+		DEBUG(1, (__location__ ": failed to find vertex %s\n",
+			  GUID_string(tmp_ctx, &internal_edge->v2id)));
+
+		talloc_free(tmp_ctx);
+		return NT_STATUS_INTERNAL_DB_CORRUPTION;
+	}
+
+	new_edge = talloc(tmp_ctx, struct kcctpl_multi_edge);
+	NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_edge, tmp_ctx);
+
+	new_edge->id = GUID_random(); /* TODO: what should be new_edge->GUID? */
+	new_edge->directed = false;
+
+	new_edge->vertex_ids.data = talloc_array(new_edge, struct GUID, 2);
+	NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_edge->vertex_ids.data, tmp_ctx);
+
+	new_edge->vertex_ids.data[0] = vertex1->id;
+	new_edge->vertex_ids.data[1] = vertex2->id;
+	new_edge->vertex_ids.count = 2;
+
+	new_edge->type = internal_edge->type;
+	new_edge->repl_info = internal_edge->repl_info;
+
+	new_data = talloc_realloc(tmp_ctx, output_edges.data,
+				  struct kcctpl_multi_edge,
+				  output_edges.count + 1);
+	NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data, tmp_ctx);
+	new_data[output_edges.count + 1] = *new_edge;
+	output_edges.data = new_data;
+	output_edges.count++;
+
+	new_data_id = talloc_realloc(vertex1, vertex1->edge_ids.data,
+				     struct GUID, vertex1->edge_ids.count);
+	NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data_id, tmp_ctx);
+	new_data_id[vertex1->edge_ids.count] = new_edge->id;
+	talloc_free(vertex1->edge_ids.data);
+	vertex1->edge_ids.data = new_data_id;
+	vertex1->edge_ids.count++;
+
+	new_data_id = talloc_realloc(vertex2, vertex2->edge_ids.data,
+				     struct GUID, vertex2->edge_ids.count);
+	NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data_id, tmp_ctx);
+	new_data_id[vertex2->edge_ids.count] = new_edge->id;
+	talloc_free(vertex2->edge_ids.data);
+	vertex2->edge_ids.data = new_data_id;
+	vertex2->edge_ids.count++;
+
+	talloc_steal(graph, new_edge);
+	talloc_steal(mem_ctx, output_edges.data);
+	talloc_free(tmp_ctx);
+	return NT_STATUS_OK;
+}
+
+/**
+ * run Kruskal's minimum-cost spanning tree algorithm on the internal edges
+ * (that represent shortest paths in the original graph between colored
+ * vertices).
+ */
+static NTSTATUS kcctpl_kruskal(TALLOC_CTX *mem_ctx, struct kcctpl_graph *graph,
+			       struct kcctpl_internal_edge_list internal_edges,
+			       struct kcctpl_multi_edge_list *_output_edges)
+{
+	uint32_t i, num_expected_tree_edges, cst_edges;
+	struct kcctpl_multi_edge_list output_edges;
+
+	num_expected_tree_edges = 0;
+	for (i = 0; i < graph->vertices.count; i++) {
+		struct kcctpl_vertex *vertex = &graph->vertices.data[i];
+
+		talloc_free(vertex->edge_ids.data);
+		ZERO_STRUCT(vertex->edge_ids);
+
+		if (vertex->color == RED || vertex->color == WHITE) {
+			num_expected_tree_edges++;
+		}
+	}
+
+	qsort(internal_edges.data, internal_edges.count,
+	      sizeof(struct kcctpl_internal_edge), kcctpl_sort_internal_edges);
+
+	cst_edges = 0;
+
+	ZERO_STRUCT(output_edges);
+
+	while (internal_edges.count > 0 &&
+	       cst_edges < num_expected_tree_edges) {
+		struct kcctpl_internal_edge *edge, *new_data;
+		struct kcctpl_vertex *vertex1, *vertex2;
+		struct GUID comp1, comp2;
+
+		edge = &internal_edges.data[0];
+
+		vertex1 = kcctpl_find_vertex_by_guid(graph, edge->v1id);
+		if (!vertex1) {
+			TALLOC_CTX *tmp_ctx = talloc_new(mem_ctx);
+			NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
+
+			DEBUG(1, (__location__ ": failed to find vertex %s\n",
+				  GUID_string(tmp_ctx, &edge->v1id)));
+
+			talloc_free(tmp_ctx);
+			return NT_STATUS_INTERNAL_DB_CORRUPTION;
+		}
+
+		vertex2 = kcctpl_find_vertex_by_guid(graph, edge->v2id);
+		if (!vertex2) {
+			TALLOC_CTX *tmp_ctx = talloc_new(mem_ctx);
+			NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
+
+			DEBUG(1, (__location__ ": failed to find vertex %s\n",
+				  GUID_string(tmp_ctx, &edge->v2id)));
+
+			talloc_free(tmp_ctx);
+			return NT_STATUS_INTERNAL_DB_CORRUPTION;
+		}
+
+		comp1 = kcctpl_get_component_id(graph, vertex1);
+		comp2 = kcctpl_get_component_id(graph, vertex2);
+
+		if (!GUID_equal(&comp1, &comp2)) {
+			NTSTATUS status;
+			struct kcctpl_vertex *vertex;
+
+			cst_edges++;
+
+			status = kcctpl_add_out_edge(mem_ctx, graph,
+						     output_edges, edge);
+			if (NT_STATUS_IS_ERR(status)) {
+				TALLOC_CTX *tmp_ctx = talloc_new(mem_ctx);
+				NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
+
+				DEBUG(1, (__location__ ": failed to add an "
+					  "output edge between %s and %s: %s\n",
+					  GUID_string(tmp_ctx, &edge->v1id),
+					  GUID_string(tmp_ctx, &edge->v2id),
+					  nt_errstr(status)));
+
+				talloc_free(tmp_ctx);
+				return status;
+			}
+
+			vertex = kcctpl_find_vertex_by_guid(graph, comp1);
+			if (!vertex) {
+				TALLOC_CTX *tmp_ctx = talloc_new(mem_ctx);
+				NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
+
+				DEBUG(1, (__location__ ": failed to find "
+					  "vertex %s\n", GUID_string(tmp_ctx,
+								     &comp1)));
+
+				talloc_free(tmp_ctx);
+				return NT_STATUS_INTERNAL_DB_CORRUPTION;
+			}
+			vertex->component_id = comp2;
+		}
+
+		internal_edges.data = internal_edges.data + 1;
+		new_data = talloc_realloc(mem_ctx, internal_edges.data,
+					  struct kcctpl_internal_edge,
+					  internal_edges.count - 1);
+		NT_STATUS_HAVE_NO_MEMORY(new_data);
+		talloc_free(internal_edges.data);
+		internal_edges.data = new_data;
+		internal_edges.count--;
+	}
+
+	*_output_edges = output_edges;
+	return NT_STATUS_OK;
+}
+
+/**
+ * count the number of components. a component is considered to be a bunch of
+ * colored vertices that are connected by the spanning tree. vertices whose
+ * component ID is the same as their vertex ID are the root of the connected
+ * component.
+ */
+static uint32_t kcctpl_count_components(struct kcctpl_graph *graph)
+{
+	uint32_t num_components = 0, i;
+
+	for (i = 0; i < graph->vertices.count; i++) {
+		struct kcctpl_vertex *vertex;
+		struct GUID component_id;
+
+		vertex = &graph->vertices.data[i];
+
+		if (vertex->color == WHITE) {
+			continue;
+		}
+
+		component_id = kcctpl_get_component_id(graph, vertex);
+		if (GUID_equal(&component_id, &vertex->id)) {
+			vertex->component_index = num_components;
+			num_components++;
+		}
+	}
+
+	return num_components;
+}
+
+/**
+ * calculate the spanning tree and return the edges that include the vertex for
+ * the local site.
+ */
+static NTSTATUS kcctpl_get_spanning_tree_edges(struct ldb_context *ldb,
+					       TALLOC_CTX *mem_ctx,
+					       struct kcctpl_graph *graph,
+					       uint32_t *_component_count,
+					       struct kcctpl_multi_edge_list *_st_edge_list)
+{
+	TALLOC_CTX *tmp_ctx;
+	struct kcctpl_internal_edge_list internal_edges;
+	uint32_t i, component_count;
+	NTSTATUS status;
+	struct kcctpl_multi_edge_list output_edges, st_edge_list;
+
+	ZERO_STRUCT(internal_edges);
+
+	tmp_ctx = talloc_new(mem_ctx);
+	NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
+
+	for (i = 0; i < graph->edge_sets.count; i++) {
+		struct kcctpl_multi_edge_set *set;
+		struct GUID edge_type;
+		uint32_t j;
+
+		set = &graph->edge_sets.data[i];
+
+		edge_type = GUID_zero();
+
+		for (j = 0; j < graph->vertices.count; j++) {
+			struct kcctpl_vertex *vertex = &graph->vertices.data[j];
+
+			talloc_free(vertex->edge_ids.data);
+			ZERO_STRUCT(vertex->edge_ids.data);
+		}
+
+		for (j = 0; j < set->edge_ids.count; j++) {
+			struct GUID edge_id;
+			struct kcctpl_multi_edge *edge;
+			uint32_t k;
+
+			edge_id = set->edge_ids.data[j];
+			edge = kcctpl_find_edge_by_guid(graph, edge_id);
+			if (!edge) {
+				DEBUG(1, (__location__ ": failed to find a "
+					  "graph edge with ID=%s\n",
+					  GUID_string(tmp_ctx, &edge_id)));
+
+				talloc_free(tmp_ctx);
+				return NT_STATUS_INTERNAL_DB_CORRUPTION;
+			}
+
+			edge_type = edge->type;
+
+			for (k = 0; k < edge->vertex_ids.count; k++) {
+				struct GUID vertex_id, *new_data;
+				struct kcctpl_vertex *vertex;
+
+				vertex_id = edge->vertex_ids.data[k];
+				vertex = kcctpl_find_vertex_by_guid(graph,
+								    vertex_id);
+				if (!vertex) {
+					DEBUG(1, (__location__ ": failed to "
+						  "find a graph vertex with "
+						  "ID=%s\n",
+						  GUID_string(tmp_ctx,
+							      &edge_id)));
+
+					talloc_free(tmp_ctx);
+					return NT_STATUS_INTERNAL_DB_CORRUPTION;
+				}
+
+				new_data = talloc_realloc(tmp_ctx,
+							  vertex->edge_ids.data,
+							  struct GUID,
+							  vertex->edge_ids.count + 1);
+				NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data,
+								  tmp_ctx);
+				new_data[vertex->edge_ids.count] = edge->id;
+				vertex->edge_ids.data = new_data;
+				vertex->edge_ids.count++;
+			}
+		}
+
+		status = kcctpl_dijkstra(graph, edge_type, false);
+		if (NT_STATUS_IS_ERR(status)) {
+			DEBUG(1, (__location__ ": failed to run Dijkstra's "
+				  "algorithm: %s\n", nt_errstr(status)));
+
+			talloc_free(tmp_ctx);
+			return status;
+		}
+
+		status = kcctpl_process_edge_set(tmp_ctx, graph, set,
+						 internal_edges);
+		if (NT_STATUS_IS_ERR(status)) {
+			DEBUG(1, (__location__ ": failed to process edge set "
+				  "%s: %s\n", GUID_string(tmp_ctx, &set->id),
+				  nt_errstr(status)));
+
+			talloc_free(tmp_ctx);
+			return status;
+		}
+
+		status = kcctpl_dijkstra(graph, edge_type, true);
+		if (NT_STATUS_IS_ERR(status)) {
+			DEBUG(1, (__location__ ": failed to run Dijkstra's "
+				  "algorithm: %s\n", nt_errstr(status)));
+
+			talloc_free(tmp_ctx);
+			return status;
+		}
+
+		status = kcctpl_process_edge_set(tmp_ctx, graph, set,
+						 internal_edges);
+		if (NT_STATUS_IS_ERR(status)) {
+			DEBUG(1, (__location__ ": failed to process edge set "
+				  "%s: %s\n", GUID_string(tmp_ctx, &set->id),
+				  nt_errstr(status)));
+
+			talloc_free(tmp_ctx);
+			return status;
+		}
+	}
+
+	kcctpl_setup_vertices(graph);
+
+	status = kcctpl_process_edge_set(tmp_ctx, graph, NULL, internal_edges);
+	if (NT_STATUS_IS_ERR(status)) {
+		DEBUG(1, (__location__ ": failed to process empty edge set: "
+			  "%s\n", nt_errstr(status)));
+
+		talloc_free(tmp_ctx);
+		return status;
+	}
+
+	status = kcctpl_kruskal(tmp_ctx, graph, internal_edges, &output_edges);
+	if (NT_STATUS_IS_ERR(status)) {
+		DEBUG(1, (__location__ ": failed to run Kruskal's algorithm: "
+			  "%s\n", nt_errstr(status)));
+
+		talloc_free(tmp_ctx);
+		return status;
+	}
+
+	for (i = 0; i < graph->vertices.count; i++) {
+		struct kcctpl_vertex *vertex = &graph->vertices.data[i];
+
+		if (vertex->color == RED) {
+			vertex->dist_to_red = 0;
+		} else if (true) { /* TODO: if there exists a path from 'vertex'
+				    to a RED vertex */
+			vertex->dist_to_red = -1; /* TODO: the length of the
+						     shortest such path */
+		} else {
+			vertex->dist_to_red = UINT32_MAX;
+		}
+	}
+
+	component_count = kcctpl_count_components(graph);
+
+	status = kcctpl_copy_output_edges(ldb, tmp_ctx, graph, output_edges,
+					  &st_edge_list);
+	if (NT_STATUS_IS_ERR(status)) {
+		DEBUG(1, (__location__ ": failed to copy edge list: %s\n",
+			  nt_errstr(status)));
+
+		talloc_free(tmp_ctx);
+		return status;
+	}
+
+	*_component_count = component_count;
+	talloc_steal(mem_ctx, st_edge_list.data);
+	*_st_edge_list = st_edge_list;
+	talloc_free(tmp_ctx);
+	return NT_STATUS_OK;
+}