src/dynamic_graph/src/dynamic_connectivity.cpp
// Searches on levels `level` and lower for a non-tree edge of maximum level
// that reconnects the endpoints of `edge`. Converts that non-tree edge into a
// tree edge if any such edge is found.
Searches on levels `level` and lower for a non-tree edge of maximum level
that reconnects the endpoints of `edge`. Converts that non-tree edge into a
tree edge if any such edge is found.
Searches on levels ` level ` and lower for a non - tree edge of maximum level that reconnects the endpoints of ` edge ` . Converts that non - tree edge into a tree edge if any such edge is found .
void
DynamicConnectivity::ReplaceTreeEdge(const UndirectedEdge& edge, Level level) {
  auto& spanning_forest{spanning_forests_[level]};
  Vertex u{edge.first};
  Vertex v{edge.second};
  if (spanning_forest.GetSizeOfTree(u) > spanning_forest.GetSizeOfTree(v)) {
    std::swap(u, v);
  }
  const Level next_level = level + 1;
  auto& next_spanning_forest{spanning_forests_[next_level]};
  while (true) {
    const std::optional<const UndirectedEdge> tree_edge{
      spanning_forest.GetMarkedEdgeInTree(u)};
    if (!tree_edge.has_value()) {
      break;
    }
    edges_[*tree_edge].level++;
    spanning_forest.MarkEdge(*tree_edge, false);
    next_spanning_forest.AddEdge(*tree_edge);
    next_spanning_forest.MarkEdge(*tree_edge, true);
  }
  while (true) {
    const std::optional<const Vertex> vertex_with_incident_edges{
      spanning_forest.GetMarkedVertexInTree(u)
    };
    if (!vertex_with_incident_edges.has_value()) {
      break;
    }
    std::unordered_set<Vertex>& adj_list{
      non_tree_adjacency_lists_[level][*vertex_with_incident_edges]
    };
    while (!adj_list.empty()) {
      const auto& adj_it{adj_list.begin()};
      const Vertex endpoint{*adj_it};
      const UndirectedEdge replacement_candidate{
        *vertex_with_incident_edges, endpoint};
      if (spanning_forest.IsConnected(u, endpoint)) {
        edges_[replacement_candidate].level++;
        DeleteEdgeFromAdjacencyList(replacement_candidate, level);
        AddEdgeToAdjacencyList(replacement_candidate, next_level);
      } else {
        edges_[replacement_candidate].type = EdgeType::kTree;
        DeleteEdgeFromAdjacencyList(replacement_candidate, level);
        for (Level l = level; l >= 0; l--) {
          spanning_forests_[l].AddEdge(replacement_candidate);
        }
        spanning_forest.MarkEdge(replacement_candidate, true);
        return;  
      }
    }
  }
  if (level > 0) {
    ReplaceTreeEdge(edge, level - 1);
  } else {
  }
}
void DynamicConnectivity :: ReplaceTreeEdge ( const UndirectedEdge & edge , Level level ) { auto & spanning_forest { spanning_forests_ [ level ] } ; Vertex u { edge . first } ; Vertex v { edge . second } ; if ( spanning_forest . GetSizeOfTree ( u ) > spanning_forest . GetSizeOfTree ( v ) ) { std :: swap ( u , v ) ; } const Level next_level = level + 1 ; auto & next_spanning_forest { spanning_forests_ [ next_level ] } ; while ( true ) { const std :: optional < const UndirectedEdge > tree_edge { spanning_forest . GetMarkedEdgeInTree ( u ) } ; if ( ! tree_edge . has_value ( ) ) { break ; } edges_ [ * tree_edge ] . level ++ ; spanning_forest . MarkEdge ( * tree_edge , false ) ; next_spanning_forest . AddEdge ( * tree_edge ) ; next_spanning_forest . MarkEdge ( * tree_edge , true ) ; } while ( true ) { const std :: optional < const Vertex > vertex_with_incident_edges { spanning_forest . GetMarkedVertexInTree ( u ) } ; if ( ! vertex_with_incident_edges . has_value ( ) ) { break ; } std :: unordered_set < Vertex > & adj_list { non_tree_adjacency_lists_ [ level ] [ * vertex_with_incident_edges ] } ; while ( ! adj_list . empty ( ) ) { const auto & adj_it { adj_list . begin ( ) } ; const Vertex endpoint { * adj_it } ; const UndirectedEdge replacement_candidate { * vertex_with_incident_edges , endpoint } ; if ( spanning_forest . IsConnected ( u , endpoint ) ) { edges_ [ replacement_candidate ] . level ++ ; DeleteEdgeFromAdjacencyList ( replacement_candidate , level ) ; AddEdgeToAdjacencyList ( replacement_candidate , next_level ) ; } else { edges_ [ replacement_candidate ] . type = EdgeType :: kTree ; DeleteEdgeFromAdjacencyList ( replacement_candidate , level ) ; for ( Level l = level ; l >= 0 ; l -- ) { spanning_forests_ [ l ] . AddEdge ( replacement_candidate ) ; } spanning_forest . MarkEdge ( replacement_candidate , true ) ; return ; } } } if ( level > 0 ) { ReplaceTreeEdge ( edge , level - 1 ) ; } else { } }
Searches on levels `level` and lower for a non-tree edge of maximum level
that reconnects the endpoints of `edge`.
Searches on levels ` level ` and lower for a non - tree edge of maximum level that reconnects the endpoints of ` edge ` .
// `u` lives in a relatively small tree. We promote all of its level-`level` // tree edges to level (`level` + 1). Otherwise, we'll fail to maintain the // invariant that `spanning_forests_[level + 1]` is a spanning forest over all // edges of level at least (`level` + 1) once we promote non-tree edges. // Promote the tree edge -- increase its level by one. // Look at level-`level` non-tree edges incident to u's tree for a replacement // edge. // Candidate is not a replacement edge. Promote it to the next // level. // Candidate must be a replacement edge connecting `u`'s tree to // `v`'s tree.  It cannot connect `u`'s tree to any other tree because // that would mean that `spanning_forest` was not actually a spanning // forest over edges of level at least `level` (`{u, endpoint}` could've // been added to the forest). // Change candidate from a non-tree edge to a tree edge. // Replacement edge found. // No replacement edge on level `level` found. // Search on lower level. // There is no replacement edge. `u` and `v` are disconnected.