如何在C++中获取和存储一个图的子图？
提问于 2019-03-26 10:19:32
我实现了一个图结构(对于具有大约30,000个节点和大约300,000条边的图)如下：
class graph;
class node;
class edge;
class graph
{
public:
graph(){};
vector nodeS;
vector edgeS;
};
class node
{
public:
node(){};
vector my_edgeS;
double weight;
};
class edge
{
public:
edge(){};
node *start, *end;
double weight;
};在nodeS存储节点的情况下，edgeS包含边缘，start和end分别指向特定边缘的起始节点和结束节点，权重是节点(边缘)权重，my_edgeS由与给定节点相关的边缘组成。
我想得到许多由它的一些边定义的原图的子图(边的偶数不变，原始图的所有节点都包含在子图中)。如何以最有效的方式在my_edgeS中构建和存储这些子图(特别是它们的C++向量)？还是有其他更适合于从图中导出子图的结构？
回答 1
Software Engineering用户
回答已采纳
发布于 2019-03-27 02:45:53
我建议将my_edgeS数据成员从node中删除。将其替换为graph中的一个方法D3。这样，一个子图中就包含了指向同一个nodes的一些指针，以及它们对应的edges。
我强烈建议你不要使用原始指针。
作为素描
struct node
{
double data;
};
using node_ptr = std::shared_ptr;
struct edge
{
node_ptr start, end;
double weight;
};
using edge_ptr = std::shared_ptr;
struct graph
{
vector nodes;
vector edges;
std::vector edges_for(node_ptr n)
{
std::vector result;
std::copy_if(edges.begin(), edges.end(), [n](edge_ptr e) { return (e->start == n) || (e->end == n); });
return result;
}
std::vector in_edges_for(node_ptr n)
{
std::vector result;
std::copy_if(edges.begin(), edges.end(), [n](edge_ptr e) { return e->end == n; });
return result;
}
std::vector out_edges_for(node_ptr n)
{
std::vector result;
std::copy_if(edges.begin(), edges.end(), [n](edge_ptr e) { return e->start == n; });
return result;
}
graph subgraph(std::vector sub_nodes)
{
std::vector sub_edges;
for (node_ptr n : sub_nodes)
{
auto n_edges = in_edges_for(n);
sub_edges.insert(n_edges.begin(), n_edges.end());
}
return { sub_nodes, sub_edges };
}
graph subgraph(std::vector sub_edges)
{
std::unordered_set sub_nodes;
std::transform(sub_edges.begin(), sub_edges.end(), std::inserter(sub_nodes, sub_nodes.end()), [](edge_ptr e){ return e->start; });
return { { sub_nodes.begin(), sub_nodes.end() }, sub_edges };
}
};页面原文内容由Software Engineering提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://softwareengineering.stackexchange.com/questions/389242
复制
腾讯云开发者
