[FEATURE] In-house minimum degree reordering

[TonyXiang8787]

Introduction

Currently we use boost::minimum_degree_ordering to re-order the nodes in the cyclic part of the grid. It has some shortcomings:

1. The library is long not maintained with many compilation warnings. We have to tweak a lot on the compiler.
2. The documentation is not very clear about some settings.
3. We also need the list of fill-ins after the reordering. The function does not products that output. So we need to build the graph again with the re-ordered vertices and manually track the fill-ins.

Proposal

We would like to implement our in-house minimum degree ordering to replace the boost::minimum_degree_ordering. Essentially, replace the following code snippert to a separate function module of our own in-house solution.

power-grid-model/power_grid_model_c/power_grid_model/include/power_grid_model/topology.hpp

Lines 313 to 404 in 9521280

	for (GraphIdx i = 0; i != n_cycle_node; ++i) {
	node_status_[cyclic_node[i]] = static_cast<Idx>(i);
	}
	// build graph lambda
	auto const build_graph = [&](ReorderGraph& g) {
	// add edges
	for (GraphIdx i = 0; i != n_cycle_node; ++i) {
	// loop all edges of vertex i
	auto const global_i = static_cast<GraphIdx>(cyclic_node[i]);
	BGL_FORALL_ADJ(global_i, global_j, global_graph_, GlobalGraph) {
	// skip if j is not part of cyclic sub graph
	if (node_status_[global_j] == -1) {
	continue;
	}
	auto const j = static_cast<GraphIdx>(node_status_[global_j]);
	if (!boost::edge(i, j, g).second) {
	boost::add_edge(i, j, g);
	}
	}
	}
	};
	ReorderGraph meshed_graph{n_cycle_node};
	build_graph(meshed_graph);
	// start minimum degree ordering
	std::vector<std::make_signed_t<GraphIdx>> perm(n_cycle_node);
	std::vector<std::make_signed_t<GraphIdx>> inverse_perm(n_cycle_node);
	std::vector<std::make_signed_t<GraphIdx>> degree(n_cycle_node);
	std::vector<std::make_signed_t<GraphIdx>> supernode_sizes(n_cycle_node, 1);
	boost::vec_adj_list_vertex_id_map<boost::no_property, std::make_signed_t<GraphIdx>> const id{};
	int const delta = 0;
	boost::minimum_degree_ordering(meshed_graph, boost::make_iterator_property_map(degree.begin(), id),
	boost::make_iterator_property_map(inverse_perm.begin(), id),
	boost::make_iterator_property_map(perm.begin(), id),
	boost::make_iterator_property_map(supernode_sizes.begin(), id), delta, id);
	// re-order cyclic node
	std::vector<Idx> const cyclic_node_copy{cyclic_node};
	for (GraphIdx i = 0; i != n_cycle_node; ++i) {
	cyclic_node[i] = cyclic_node_copy[perm[i]];
	}
	// copy back to dfs node
	std::copy(cyclic_node.cbegin(), cyclic_node.cend(), std::back_inserter(dfs_node));
	// analyze and record fill-ins
	// re-assign temporary bus number as increasing from 0, 1, 2, ..., n_cycle_node - 1
	for (GraphIdx i = 0; i != n_cycle_node; ++i) {
	node_status_[cyclic_node[i]] = static_cast<Idx>(i);
	}
	// re-build graph with reordered cyclic node
	meshed_graph.clear();
	meshed_graph = ReorderGraph{n_cycle_node};
	build_graph(meshed_graph);
	// begin to remove vertices from graph, create fill-ins
	BGL_FORALL_VERTICES(i, meshed_graph, ReorderGraph) {
	// double loop to loop all pairs of adjacent vertices
	BGL_FORALL_ADJ(i, j1, meshed_graph, ReorderGraph) {
	// skip for already removed vertices
	if (j1 < i) {
	continue;
	}
	BGL_FORALL_ADJ(i, j2, meshed_graph, ReorderGraph) {
	// no self edges
	assert(i != j1);
	assert(i != j2);
	// skip for already removed vertices
	if (j2 < i) {
	continue;
	}
	// only keep pair with j1 < j2
	if (j1 >= j2) {
	continue;
	}
	// if edge j1 -> j2 does not already exists
	// it is a fill-in
	if (!boost::edge(j1, j2, meshed_graph).second) {
	// anti edge should also not exist
	assert(!boost::edge(j2, j1, meshed_graph).second);
	// add both edges to the graph
	boost::add_edge(j1, j2, meshed_graph);
	boost::add_edge(j2, j1, meshed_graph);
	// add to fill-in
	fill_in.push_back({static_cast<Idx>(j1), static_cast<Idx>(j2)});
	}
	}
	}
	}
	// offset fill-in indices by n_node - n_cycle_node
	auto const offset = static_cast<Idx>(dfs_node.size() - n_cycle_node);
	std::for_each(fill_in.begin(), fill_in.end(), [offset](BranchIdx& b) {
	b[0] += offset;
	b[1] += offset;
	});
	return fill_in;