我想创建如下图,第一列是顶点,其他的是邻接顶点
- 1 2 3 4 7
- 2 1 3 4
- 3 1 2 4
- 4 1 2 3 5
- 5 4 6 7 8
- 6 5 7 8
- 7 1 5 6 8
- 8 5 6 7
我像这样将边添加到图中
using MinCutG = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS>;
MinCutG graph;
std::vector<std::vector<int> > input{ {1,2,3,4,7}, {2,1,3,4}, {3,1,2,4},
{4,1,2,3,5}, {5,4,6,7,8}, {6,5,7,8}, {7,1,5,6,8}, {8,5,6,7}};
for(auto const &data : input){
auto begin = std::begin(data);
auto end = std::end(data);
if(begin != end){
auto const Vertex = *begin;
++begin;
while(begin != end){
boost::add_edge(Vertex, *begin, graph);
++begin;
}
}
}
打印图表
template<typename Graph>
void print_adjacent_vertex(Graph const &g)
{
for (auto vertex = vertices(g); vertex.first != vertex.second; ++vertex.first){
std::cout << *vertex.first << " is connected with ";
for (auto neighbour = adjacent_vertices(*vertex.first, g);
neighbour.first != neighbour.second; ++neighbour.first){
std::cout << *neighbour.first << " ";
}
std::cout<<std::endl;
}
}
我希望输出与输入相同,但事实并非如此 结果是
- 1 与 2 3 4 7 2 3 4 7 相连
- 2 与 1 1 3 4 3 4 相连
- 3 与 1 2 1 2 4 4 相连
- 4 与 1 2 3 1 2 3 5 5 相连
- 5 与 4 4 6 7 8 6 7 8 相连
- 6 与 5 5 7 8 7 8 相连
- 7 与 1 5 6 1 5 6 8 8 相连
- 8 与 5 6 7 5 6 7 相连
我的预期结果
- 1 与 2 3 4 7 相连
- 2 与 1 3 4 相连
- 3 与 1 2 4 相连
- 4 与 1 2 3 5 相连
- 5 与 4 6 7 8 相连
- 6 与 6 5 7 8 相连
- 7 与 7 1 5 6 8 相连
- 8 与 8 5 6 7 相连
最佳答案
简而言之,对 OutEdgeList
模板参数使用 setS
将禁用平行边,从而产生所需的输出。
第一个模板参数为boost::adjacency_list
是 OutEdgeList
并且它控制某些图形行为,例如允许或禁止平行边。在无向 MinCutG
图的情况下,vecS
用作将启用平行边的 OutEdgeList
。例如,如果无向图支持平行边,则:
add_edge(1, 2, graph); // Vertex 1 and 2 are adjacent to one another via edge A.
add_edge(2, 1, graph); // Vertex 1 and 2 are adjacent to one another via edge B,
// which is parallel to edge A.
adjacent_vertices()
对于顶点 1
将包含顶点 2
两次,每条边一次(A
和 B
)。
如 documentation 中所述,可以通过为 OutEdgeList
使用 setS
或 hash_setS
选择器来禁用平行边。例如,更改:
using MinCutG = boost::adjacency_list<
boost::vecS, // OutEdgeList with parallel edges
boost::vecS,
boost::undirectedS>;
到:
using MinCutG = boost::adjacency_list<
boost::setS, // OutEdgeList with no parallel edges
boost::vecS,
boost::undirectedS>;
这是一个 example使用原始代码,仅将 OutEdgeList
从 vecS
更改为 setS
:
#include <iostream>
#include <vector>
#include <boost/graph/adjacency_list.hpp>
template<typename Graph>
void print_adjacent_vertex(Graph const &g)
{
for (auto vertex = vertices(g); vertex.first != vertex.second;
++vertex.first){
std::cout << *vertex.first << " is connected with ";
for (auto neighbour = adjacent_vertices(*vertex.first, g);
neighbour.first != neighbour.second; ++neighbour.first){
std::cout << *neighbour.first << " ";
}
std::cout<<std::endl;
}
}
int main()
{
using MinCutG = boost::adjacency_list<
boost::setS, boost::vecS, boost::undirectedS>;
MinCutG graph;
std::vector<std::vector<int> > input
{
{1,2,3,4,7},
{2,1,3,4},
{3,1,2,4},
{4,1,2,3,5},
{5,4,6,7,8},
{6,5,7,8},
{7,1,5,6,8},
{8,5,6,7}
};
for(auto const &data : input){
auto begin = std::begin(data);
auto end = std::end(data);
if(begin != end){
auto const Vertex = *begin;
++begin;
while(begin != end){
boost::add_edge(Vertex, *begin, graph);
++begin;
}
}
}
print_adjacent_vertex(graph);
}
产生以下输出:
0 is connected with
1 is connected with 2 3 4 7
2 is connected with 1 3 4
3 is connected with 1 2 4
4 is connected with 1 2 3 5
5 is connected with 4 6 7 8
6 is connected with 5 7 8
7 is connected with 1 5 6 8
8 is connected with 5 6 7
关于c++ - 通过与输入相同的boost图创建无向图,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23979114/