Method Subgraph

ext/src/spoa/src/graph.cpp:541–595

}

Graph Graph::Subgraph(
    std::uint32_t begin,
    std::uint32_t end,
    std::vector<const Node*>* subgraph_to_graph) const {
  if (!subgraph_to_graph) {
    throw std::invalid_argument(
        "[spoa::Graph::Subgraph] error: invalid ptr to subgraph_to_graph");
  }

  auto is_in_subgraph = ExtractSubgraph(nodes_[end].get(), nodes_[begin].get());

  // init subgraph
  Graph subgraph{};
  subgraph.num_codes_ = num_codes_;
  subgraph.coder_ = coder_;
  subgraph.decoder_ = decoder_;
  // subgraph.sequences_ = TODO(rvaser) maybe add sequences

  // create a map from subgraph nodes to graph nodes and vice versa
  subgraph_to_graph->clear();
  subgraph_to_graph->resize(nodes_.size(), nullptr);

  std::vector<Node*> graph_to_subgraph(nodes_.size(), nullptr);

  for (const auto& it : nodes_) {
    if (!is_in_subgraph[it->id]) {
      continue;
    }
    subgraph.AddNode(it->code);
    graph_to_subgraph[it->id] = subgraph.nodes_.back().get();
    (*subgraph_to_graph)[subgraph.nodes_.back()->id] = it.get();
  }

  // connect nodes
  for (const auto& it : nodes_) {
    if (!is_in_subgraph[it->id]) {
      continue;
    }
    auto jt = graph_to_subgraph[it->id];
    for (const auto& kt : it->inedges) {
      if (graph_to_subgraph[kt->tail->id]) {
        subgraph.AddEdge(graph_to_subgraph[kt->tail->id], jt, kt->weight);
      }
    }
    for (const auto& kt : it->aligned_nodes) {
      if (graph_to_subgraph[kt->id]) {
        jt->aligned_nodes.emplace_back(graph_to_subgraph[kt->id]);
      }
    }
  }

  subgraph.TopologicalSort();

  return subgraph;
}

void Graph::UpdateAlignment(
    const std::vector<const Node*>& subgraph_to_graph,