(BOOST) Filter out the edges of a graph iteratively

Question

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?

score 0 · Accepted Answer · answered Sep 23 '20 at 10:07

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 :)

What's the reason for identifying edges by (source,target) instead of using the edge_descriptor (*eit)? Edge-descriptors are designed to be low-cost copyable and directly equality comparable. — sehe, Sep 23 '20 at 21:34
You are completely right -- there is no actual reason. I am just getting started with boost and for me this was easier to understand. I will modify the code carefully to remove this redudancy. Thanks a lot for your input! — ma7642, Sep 24 '20 at 11:42

(BOOST) Filter out the edges of a graph iteratively

1 Answers1