Как удалить подграф графа наддува

Это не может быть сделано в этом примере. Семейство Enum — это индекс в контейнере вершин графа. Так что, убрав Рика, Джон стал бы Риком.

Однако, если определение графика будет изменено на значения 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;
}