boost::graph学习

boost::graph API简单小结

boost::graph是boost为图算法提供的API，简单易用。

API说明

1. boost::add_vertex
   创建一个顶点。

2. boost::add_edge
   创建一条边。

3. boost::edges
   获取所有的边。

4. boost::vertices
   获取所有的顶点。

5. graph.operator[vertex_descriptor]
   获取顶点的属性Property。

6. graph.operator[edge_descriptor]
   获取边的属性Property。

7. boost::out_edges
   获取顶点的“出边”（out edges），即以当前顶点为出发点的边。

参考文档：
https://theboostcpplibraries.com/boost.graph-algorithms
https://zhuanlan.zhihu.com/p/338279100
https://www.boost.org/doc/libs/1_83_0/libs/graph/doc/quick_tour.html
https://www.boost.org/doc/libs/1_83_0/libs/graph/doc/adjacency_list.html
https://www.technical-recipes.com/2015/getting-started-with-the-boost-graph-library/
https://blog.csdn.net/Augusdi/article/details/105757441

代码示例：

#include "PSParametricModelingEngine.h"#include <QDebug>
#include <algorithm>
#include <iostream>
#include <iterator>
#include <utility>using namespace std;
using namespace boost;namespace
{struct VertexProperty{int id;string name;};struct EdgeProperty{int id;int weight;};typedef boost::adjacency_list<vecS,           // 使用数组来存储vertex vecS,vecS,           // 使用数组来存储vertex vecS,directedS,      // 申明为有向图，可以访问其out-edge,若要都能访问VertexProperty, // 定义顶点属性EdgeProperty    // 定义边的属性>PSGraph;typedef graph_traits<PSGraph>::vertex_descriptor vertex_descriptor_t;void printVertices(){boost::adjacency_list<> g;boost::adjacency_list<>::vertex_descriptor v1 = boost::add_vertex(g);boost::adjacency_list<>::vertex_descriptor v2 = boost::add_vertex(g);boost::adjacency_list<>::vertex_descriptor v3 = boost::add_vertex(g);boost::adjacency_list<>::vertex_descriptor v4 = boost::add_vertex(g);std::cout << v1 << ", " << v2 << ", " << v3 << ", " << v4 << '\n';}void printEdgeVector(){boost::adjacency_list<> g;boost::adjacency_list<>::vertex_descriptor v1 = boost::add_vertex(g);boost::adjacency_list<>::vertex_descriptor v2 = boost::add_vertex(g);boost::add_vertex(g);boost::add_vertex(g);std::pair<boost::adjacency_list<>::edge_descriptor, bool> p = boost::add_edge(v1, v2, g);std::cout.setf(std::ios::boolalpha);std::cout << p.second << '\n';p = boost::add_edge(v1, v2, g);std::cout << p.second << '\n';p = boost::add_edge(v2, v1, g);std::cout << p.second << '\n';std::pair<boost::adjacency_list<>::edge_iterator, boost::adjacency_list<>::edge_iterator> es = boost::edges(g);std::copy(es.first, es.second, std::ostream_iterator<boost::adjacency_list<>::edge_descriptor>{std::cout, "\n"});for (boost::adjacency_list<>::edge_iterator iterator = es.first; iterator != es.second; iterator++){std::stringstream ss;ss << (*iterator);qDebug() << QString::fromUtf8(ss.str().c_str());}}void printEdgeSet(){typedef boost::adjacency_list<boost::setS, boost::vecS, boost::undirectedS> graph;graph g;boost::adjacency_list<>::vertex_descriptor v1 = boost::add_vertex(g);boost::adjacency_list<>::vertex_descriptor v2 = boost::add_vertex(g);boost::add_vertex(g);boost::add_vertex(g);std::pair<graph::edge_descriptor, bool> p = boost::add_edge(v1, v2, g);std::cout.setf(std::ios::boolalpha);std::cout << p.second << '\n';p = boost::add_edge(v1, v2, g);std::cout << p.second << '\n';p = boost::add_edge(v2, v1, g);std::cout << p.second << '\n';std::pair<graph::edge_iterator, graph::edge_iterator> es = boost::edges(g);std::copy(es.first, es.second, std::ostream_iterator<graph::edge_descriptor>{std::cout, "\n"});for (graph::edge_iterator iterator = es.first; iterator != es.second; iterator++){std::stringstream ss;ss << (*iterator);qDebug() << QString::fromUtf8(ss.str().c_str());}}int printDirectedGraph(){// 定义图类型，使用vector存放顶点和边，有向图typedef adjacency_list<vecS, vecS, directedS> graph_t;// 产生图对象，有6个顶点graph_t g(6);// 加入边add_edge(1, 2, g);add_edge(1, 5, g);add_edge(2, 2, g);add_edge(2, 0, g);add_edge(3, 4, g);add_edge(4, 3, g);add_edge(5, 0, g);// 显示所有的顶点// 顶点迭代器类型typedef graph_traits<graph_t>::vertex_iterator vertex_iter;// 得到所有顶点，vrange中的一对迭代器分别指向第一个顶点和最后的一个顶点之后。std::pair<vertex_iter, vertex_iter> vrange = vertices(g);for (vertex_iter itr = vrange.first; itr != vrange.second; ++itr)qDebug() << *itr;// 显示所有的边// 边迭代器类型typedef graph_traits<graph_t>::edge_iterator edge_iter;// 得到所有边，erange中的一对迭代器分别指向第一条边和最后的一条边之后std::pair<edge_iter, edge_iter> erange = edges(g);for (edge_iter itr = erange.first; itr != erange.second; ++itr)qDebug() << source(*itr, g) << "-->" << target(*itr, g);return 0;};void printPSGraph(){PSGraph g; // 声明一个图VertexProperty vertex1{101, "Vertex 1"};VertexProperty vertex2{102, "Vertex 2"};VertexProperty vertex3{103, "Vertex 3"};VertexProperty vertex4{104, "Vertex 4"};EdgeProperty edge1{101, 1};EdgeProperty edge2{102, 2};EdgeProperty edge3{103, 3};EdgeProperty edge4{104, 4};EdgeProperty edge5{105, 5};EdgeProperty edge6{106, 6};vertex_descriptor_t vert1 = boost::add_vertex(vertex1, g);vertex_descriptor_t vert2 = boost::add_vertex(vertex2, g);vertex_descriptor_t vert3 = boost::add_vertex(vertex3, g);vertex_descriptor_t vert4 = boost::add_vertex(vertex4, g);auto e1 = boost::add_edge(vert1, vert2, edge1, g);auto e2 = boost::add_edge(vert2, vert3, edge2, g);auto e3 = boost::add_edge(vert3, vert4, edge3, g);auto e4 = boost::add_edge(vert4, vert1, edge4, g);auto e5 = boost::add_edge(vert4, vert2, edge5, g);auto e6 = boost::add_edge(vert4, vert3, edge6, g);typedef graph_traits<PSGraph>::vertex_iterator vertex_iter;std::pair<vertex_iter, vertex_iter> vrange = vertices(g);for (vertex_iter itr = vrange.first; itr != vrange.second; ++itr){auto prop = g[*itr];qDebug() << *itr << ": {" << prop.id << ", " << QString::fromUtf8(prop.name.c_str()) << "}";typedef graph_traits<PSGraph> GraphTraits;typename GraphTraits::out_edge_iterator out_i, out_end;typename GraphTraits::edge_descriptor e;for (boost::tie(out_i, out_end) = out_edges(*itr, g); out_i != out_end; ++out_i){e = *out_i;auto prop = g[e];qDebug() << source(e, g) << "-->" << target(e, g) << ": {" << prop.id << ", " << prop.weight << "}";}}typedef graph_traits<PSGraph>::edge_iterator edge_iter;std::pair<edge_iter, edge_iter> erange = edges(g);for (edge_iter itr = erange.first; itr != erange.second; ++itr){auto prop = g[*itr];qDebug() << source(*itr, g) << "-->" << target(*itr, g) << ": {" << prop.id << ", " << prop.weight << "}";}}
} // namespacevoid main()
{// printEdgeSet();// printDirectedGraph();printPSGraph();
}