I have a connected graph A (level 0) and I want to populate the next level with graphs B,C,D... by iteratively removing one edge at a time in A. Here is how my code begins:
struct VertexData
{
long ID;
};
typedef boost::adjacency_list<boost::listS, boost::listS, boost::undirectedS,VertexData, property< edge_index_t, int > >> SimpleGraph;
typedef boost::graph_traits<SimpleGraph>::vertex_descriptor vertex_t;
typedef boost::graph_traits<SimpleGraph>::edge_descriptor edge_t;
int main(){
SimpleGraph A;
}
I have tried looping over the edges of A and removing an edge at a time after having copied graph A:
SimpleGraph tempStructure;
vector<SimpleGraph> newStructures;
vector<long> parentList;
// loop over the edges
auto es = boost::edges(A);
pred = A.ID;
for (auto eit = es.first; eit != es.second; ++eit){
// 1. copy structure
cout << "Copy structure." <<endl;
boost::copy_graph(A, tempStructure);
// 2. remove a particular edge
cout << "Remove edge." << endl;
boost::remove_edge(*eit, tempStructure);
// 3. save structure
cout << "Saving structure." << endl;
newStructures.push_back(tempStructure);
// 4. save parent of old structure]
cout << "Saving parent." << endl;
parentList.push_back(pred);
}
But as I have read here, I understand this is a very naive attempt. I have found the following solution ( Boost filtered graph with blacklisted edges) and seen that a filtered graph seems the way to go. However, I am having trouble implementing it...
Is it possible to filter out one edge at a time in the parent graph so that the children graphs are filtered versions of A that lack one edge in A?
Thanks to the discussion on this question (here), I was able to come up with a solution to my problem. I took the same approach as in the thread and decided to 'blacklist' each edge individually:
typedef std::pair <int, int> Edge;
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, boost::no_property, boost::no_property> SimpleGraph;
struct BlackListEdgeConstraint{
private:
Edge blackList;
SimpleGraph* g;
public:
BlackListEdgeConstraint() : blackList(), g(NULL) {}; // constructor with initialization
BlackListEdgeConstraint(Edge& list, SimpleGraph* gM) : blackList(list), g(gM){}
// the actual predicate function
bool operator()(const boost::graph_traits<SimpleGraph>::edge_descriptor& e) const {
Edge edge(source(e, *g), target(e, *g));
if (edge == blackList){
return false;
}
else{
return true;
}
}
};
And then, I use this predicate as follows:
auto es = boost::edges(parentStructure);
for (auto eit = es.first; eit != es.second; ++eit){
// we filter the current edge -- blacklist it
Edge edge(source(*eit, parentStructure), target(*eit, parentStructure));
BlackListEdgeConstraint filter(edge, &parentStructure);
// get filtered graph where this connection is missing
boost::filtered_graph<SimpleGraph, BlackListEdgeConstraint> tempStructureFILT(parentStructure, filter);
}
I am sure this can be done in a more elegant - less time-consuming way, but for the moment, this solution serves my purpose. I would be happy to hear any feedback on how to improve it :)