Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

[FEATURE] In-house minimum degree reordering #433

Open
TonyXiang8787 opened this issue Nov 21, 2023 · 0 comments · May be fixed by #440
Open

[FEATURE] In-house minimum degree reordering #433

TonyXiang8787 opened this issue Nov 21, 2023 · 0 comments · May be fixed by #440
Labels
feature New feature or request

Comments

@TonyXiang8787
Copy link
Member

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;

@TonyXiang8787 TonyXiang8787 added the feature New feature or request label Nov 21, 2023
@mgovers mgovers linked a pull request Nov 27, 2023 that will close this issue
Draft
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
feature New feature or request
Projects
Power Grid Model
Status: Q3 2024
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Feature/minimum degree topology PowerGridModel/power-grid-model
1 participant
@TonyXiang8787