如何刪除升壓圖

Question

下面的代碼是從boost family tree example

採取我正在尋找一種簡單的方法來刪除子

enum family { Jeanie, Debbie, Rick, John, Amanda, Margaret, Benjamin, N }; 
int main() 
{ 
    using namespace boost; 
    const char *name[] = { "Jeanie", "Debbie", "Rick", "John", "Amanda", 
    "Margaret", "Benjamin" 
    }; 

    adjacency_list <> g(N); 
    add_edge(Jeanie, Debbie, g); 
    add_edge(Jeanie, Rick, g); 
    add_edge(Jeanie, John, g); 
    add_edge(Debbie, Amanda, g); 
    add_edge(Rick, Margaret, g); 
    add_edge(John, Benjamin, g); 

    // some code 

    // Rick and his family left - I want to remove them from the chart 

    return 0; 
} 

Answer 1

它不能在這個例子中完成的子圖。枚舉族是圖中頂點容器中的索引。所以通過去除瑞克，約翰就成了瑞克。

但是，如果將圖的定義更改爲使用enum值，則會出現以下解決方案。

enum family { Jeanie, Debbie, Rick, John, Amanda, Margaret, Benjamin, N }; 
const char *name[] = { "Jeanie", "Debbie", "Rick", "John", "Amanda", 
         "Margaret", "Benjamin" 
        }; 
typedef boost::adjacency_list <boost::vecS 
          , boost::vecS 
          , boost::bidirectionalS 
          , family> Graph; 

struct VisitorBFS : public boost::default_bfs_visitor { 
    VisitorBFS(
     std::vector<boost::graph_traits<Graph>::vertex_descriptor>& container 
    ) 
    : container(container) {} 

    template <class Vertex, class Graph> 
    void discover_vertex(const Vertex& v, const Graph& g) const 
    { 
     container.push_back(v); 
    } 

    std::vector<boost::graph_traits<Graph>::vertex_descriptor>& container; 
}; 

void printFamily(const Graph& g) 
{ 
    using namespace boost; 
    graph_traits <Graph>::vertex_iterator i, end; 
    graph_traits <Graph>::adjacency_iterator ai, a_end; 

    for (boost::tie(i, end) = vertices(g); i != end; ++i) { 
     std::cout << name[g[*i]]; 
     boost::tie(ai, a_end) = adjacent_vertices(*i, g); 
     if (ai == a_end) 
      std::cout << " has no children"; 
     else 
      std::cout << " is the parent of "; 
     for (; ai != a_end; ++ai) { 
      std::cout << name[g[*ai]]; 
      if (boost::next(ai) != a_end) 
       std::cout << ", "; 
     } 
     std::cout << std::endl; 
    } 
} 

int main() 
{ 
    using namespace boost; 

    Graph g; 
    add_vertex(Jeanie, g); 
    add_vertex(Debbie, g); 
    add_vertex(Rick, g); 
    add_vertex(John, g); 
    add_vertex(Amanda, g); 
    add_vertex(Margaret, g); 
    add_vertex(Benjamin, g); 

    add_edge(Jeanie, Debbie, g); 
    add_edge(Jeanie, Rick, g); 
    add_edge(Jeanie, John, g); 
    add_edge(Debbie, Amanda, g); 
    add_edge(Rick, Margaret, g); 
    add_edge(John, Benjamin, g); 

    printFamily(g); 

    // Rick and his family left - I want to remove them from the chart 

    // First, find a subgraph from vertex Rick. Algorithm breadth_first_search 
    // also goes through the start vertex, so Rick is included in result. 
    std::vector<graph_traits<Graph>::vertex_descriptor> vertexes; 
    breadth_first_search(g, Rick, visitor(VisitorBFS(vertexes))); 

    // Then remove incoming edges because they are not removed automatically 
    // along with vertexes, then remove vertexes. 
    for (std::vector<graph_traits<Graph>::vertex_descriptor>::iterator it = vertexes.begin(); it != vertexes.end(); ++it) { 
     clear_in_edges(*it, g); 
     remove_vertex(*it, g); 
    } 

    printFamily(g); 

    return 0; 
}