(BOOST) 迭代地过滤掉图形的边缘

Question

我有一个连通图 A（第 0 级），我想用图 B、C、D...填充下一个级别，方法是一次迭代地删除 A 中的一条边。这是我的代码开始的方式:

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;   
}

我试过在复制图 A 后遍历 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);

}

但正如我所读 I understand this is a very naive attempt. I have found the following solution ( Boost filtered graph with blacklisted edges) 并看到过滤图似乎是可行的方法。但是，我在实现它时遇到了问题...

是否可以在父图中一次过滤掉一条边，以便子图是 A 中缺少一条边的过滤版本？

Answer 1

感谢对这个问题的讨论 (here)，我能够找到解决问题的方法。我采用了与线程中相同的方法，并决定 'blacklist' 每个边缘单独：

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;
        }
    }
};

然后，我使用这个谓词如下：

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);
}

我相信这可以用更优雅的方式完成 - 更少 time-consuming，但目前，这个解决方案符合我的目的。我很乐意听到有关如何改进它的任何反馈:)

(BOOST) 迭代地过滤掉图形的边缘

(BOOST) Filter out the edges of a graph iteratively

c++

boost

graph

boost-graph

filtered