C++ Boost Graph算法超詳細(xì)精講

更新時(shí)間：2022年10月31日 11:45:36 作者：無水先生

這篇文章主要介紹了C++ Boost Graph算法，我門嘗試使用Boost.Graph庫來運(yùn)行Goldberg的最大流算法。 Boost.Graph將其稱為push_relabel_max_flow

Boost.Graph 中的算法類似于標(biāo)準(zhǔn)庫中的算法——它們是通用的并且非常靈活。但是，并不總是很清楚應(yīng)該如何使用它們。

示例 31.8。使用breadth_first_search() 從內(nèi)到外訪問點(diǎn)

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/named_function_params.hpp>
#include <boost/graph/visitors.hpp>
#include <boost/array.hpp>
#include <array>
#include <utility>
#include <iterator>
#include <algorithm>
#include <iostream>
int main()
{
  enum { topLeft, topRight, bottomRight, bottomLeft };
  std::array<std::pair<int, int>, 4> edges{{
    std::make_pair(topLeft, topRight),
    std::make_pair(topRight, bottomRight),
    std::make_pair(bottomRight, bottomLeft),
    std::make_pair(bottomLeft, topLeft)
  }};
  typedef boost::adjacency_list<boost::setS, boost::vecS,
    boost::undirectedS> graph;
  graph g{edges.begin(), edges.end(), 4};
  boost::array<int, 4> distances{{0}};
  boost::breadth_first_search(g, topLeft,
    boost::visitor(
      boost::make_bfs_visitor(
        boost::record_distances(distances.begin(),
          boost::on_tree_edge{}))));
  std::copy(distances.begin(), distances.end(),
    std::ostream_iterator<int>{std::cout, "\n"});
}

Example31.8

示例 31.8 使用算法 boost::breadth_first_search() 從內(nèi)部到外部訪問點(diǎn)。該算法從作為第二個(gè)參數(shù)傳遞的點(diǎn)開始。它首先訪問可以從該點(diǎn)直接到達(dá)的所有點(diǎn)，像波浪一樣工作。

boost::breadth_first_search() 不返回特定結(jié)果。該算法只是訪問點(diǎn)。是否收集和存儲(chǔ)數(shù)據(jù)取決于傳遞給 boost::breadth_first_search() 的訪問者。

訪問者是在訪問點(diǎn)時(shí)調(diào)用其成員函數(shù)的對(duì)象。通過將訪問者傳遞給 boost::breadth_first_search() 之類的算法，您可以決定訪問某個(gè)點(diǎn)時(shí)應(yīng)該發(fā)生什么。訪問者就像函數(shù)對(duì)象，可以傳遞給標(biāo)準(zhǔn)庫的算法。

示例 31.8 使用記錄距離的訪問者。距離是從一個(gè)點(diǎn)到另一個(gè)點(diǎn)必須跨越的線數(shù)，從作為第二個(gè)參數(shù)傳遞給 boost::breadth_first_search() 的點(diǎn)開始。 Boost.Graph 提供了幫助函數(shù) boost::record_distances() 來創(chuàng)建訪問者。還必須傳遞屬性圖和標(biāo)簽。

屬性映射存儲(chǔ)點(diǎn)或線的屬性。 Boost.Graph 描述了屬性映射的概念。由于指針或迭代器被視為屬性映射的開頭，因此詳細(xì)了解屬性映射并不重要。在示例 31.8 中，數(shù)組距離的開頭通過 distances.begin() 傳遞到 boost::record_distances()。這足以將數(shù)組距離用作屬性映射。但是，重要的是數(shù)組的大小不小于圖中的點(diǎn)數(shù)。畢竟，需要存儲(chǔ)到圖中每個(gè)點(diǎn)的距離。

請(qǐng)注意，距離基于 boost::array 而不是 std::array。使用 std::array 會(huì)導(dǎo)致編譯器錯(cuò)誤。

根據(jù)算法，有不同的事件。傳遞給 boost::record_distances() 的第二個(gè)參數(shù)指定應(yīng)通知訪問者哪些事件。 Boost.Graph 定義了空類的標(biāo)簽來給事件命名。示例 31.8 中的標(biāo)簽 boost::on_tree_edge 指定在找到新點(diǎn)時(shí)應(yīng)記錄距離。

事件取決于算法。您必須查看有關(guān)算法的文檔，以了解支持哪些事件以及可以使用哪些標(biāo)簽。

由 boost::record_distances() 創(chuàng)建的訪問者與算法無關(guān)，因此您可以將 boost::record_distances() 與其他算法一起使用。適配器用于綁定算法和訪問者。示例 31.8 調(diào)用 boost::make_bfs_visitor() 來創(chuàng)建這個(gè)適配器。此幫助函數(shù)返回算法 boost::breadth_first_search() 所期望的訪問者。此訪問者定義適合算法支持的事件的成員函數(shù)。例如，boost::make_bfs_visitor() 返回的訪問者定義了成員函數(shù) tree_edge()。如果使用標(biāo)簽 boost::on_tree_edge 定義的訪問者被傳遞給 boost::make_bfs_visitor()（如示例 31.8），則在調(diào)用 tree_edge() 時(shí)會(huì)通知訪問者。這使您可以使用具有不同算法的訪問者，而無需這些訪問者定義所有算法所期望的所有成員函數(shù)。

boost::make_bfs_visitor() 返回的適配器不能直接傳遞給算法 boost::breadth_first_search()。它必須用 boost::visitor() 包裝，然后作為第三個(gè)參數(shù)傳遞。

有兩種算法變體，例如 boost::breadth_first_search()。一種變體期望算法支持的每個(gè)參數(shù)都將被傳遞。另一個(gè)變體支持類似于命名參數(shù)的東西。使用第二個(gè)變體通常更容易，因?yàn)橹恍枰獋鬟f您感興趣的參數(shù)。許多參數(shù)不必傳遞，因?yàn)樗惴ㄊ褂媚J(rèn)值。

示例 31.8 使用了需要命名參數(shù)的 boost::breadth_first_search() 的變體。前兩個(gè)參數(shù)是圖形和起點(diǎn)，它們是必需的。然而，第三個(gè)參數(shù)幾乎可以是一切。在示例 31.8 中，需要傳遞一個(gè)訪問者。為此，boost::make_bfs_visitor() 返回的適配器使用 boost::visitor() 命名?，F(xiàn)在，很明顯第三個(gè)參數(shù)是訪問者。您將在以下示例中看到其他參數(shù)如何按名稱傳遞到 boost::breadth_first_search()。

示例 31.8 顯示數(shù)字 0、1、2 和 1。這些是從左上角到所有點(diǎn)的距離。右上角的字段（索引為 1 的字段）僅一步之遙。右下方的字段（索引為 2 的字段）相距兩步。左下方的字段——索引為 3 的字段——再次只有一步之遙。首先打印的數(shù)字 0 是指左上角的字段。由于它是傳遞給 boost::breadth_first_search() 的起點(diǎn)，因此需要零步才能到達(dá)它。

boost::breadth_first_search() 不設(shè)置數(shù)組中的元素，它只是增加存儲(chǔ)的值。因此，您必須在開始之前初始化數(shù)組距離中的所有元素。

示例 31.9 說明了如何找到最短路徑。

示例 31.9。使用 width_first_search() 查找路徑

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/named_function_params.hpp>
#include <boost/graph/visitors.hpp>
#include <boost/array.hpp>
#include <array>
#include <utility>
#include <algorithm>
#include <iostream>
int main()
{
  enum { topLeft, topRight, bottomRight, bottomLeft };
  std::array<std::pair<int, int>, 4> edges{{
    std::make_pair(topLeft, topRight),
    std::make_pair(topRight, bottomRight),
    std::make_pair(bottomRight, bottomLeft),
    std::make_pair(bottomLeft, topLeft)
  }};
  typedef boost::adjacency_list<boost::setS, boost::vecS,
    boost::undirectedS> graph;
  graph g{edges.begin(), edges.end(), 4};
  boost::array<int, 4> predecessors;
  predecessors[bottomRight] = bottomRight;
  boost::breadth_first_search(g, bottomRight,
    boost::visitor(
      boost::make_bfs_visitor(
        boost::record_predecessors(predecessors.begin(),
          boost::on_tree_edge{}))));
  int p = topLeft;
  while (p != bottomRight)
  {
    std::cout << p << '\n';
    p = predecessors[p];
  }
  std::cout << p << '\n';
}

Example31.9

示例 31.9 顯示 0、1 和 2。這是從左上角到右下角的最短路徑。盡管左下場上的路徑同樣短，但它在右上場上方引導(dǎo)。

再次使用 boost::breadth_first_search() - 這次是為了找到最短路徑。如您所知，此算法只是訪問點(diǎn)。要獲得最短路徑的描述，必須使用適當(dāng)?shù)脑L問者。示例 31.9 調(diào)用 boost::record_predecessors() 來獲取一個(gè)。

boost::record_predecessors() 返回一個(gè)訪問者來存儲(chǔ)每個(gè)點(diǎn)的前任。每當(dāng) boost::breadth_first_search() 訪問一個(gè)新點(diǎn)時(shí)，前一個(gè)點(diǎn)就會(huì)存儲(chǔ)在傳遞給 boost::record_predecessors() 的屬性映射中。由于 boost::breadth_first_search() 從內(nèi)部到外部訪問點(diǎn)，因此找到了最短路徑——從作為第二個(gè)參數(shù)傳遞給 boost::breadth_first_search() 的點(diǎn)開始。示例 31.9 找到從圖中所有點(diǎn)到右下角的最短路徑。

在 boost::breadth_first_search() 返回后，屬性映射前驅(qū)包含每個(gè)點(diǎn)的前驅(qū)。為了在從左上角到右下角時(shí)找到第一個(gè)字段，索引為 0 的元素（左上角字段的索引）在前輩中被訪問。在前輩中找到的值為 1，這意味著下一個(gè)字段位于右上角。訪問索引為 1 的前輩會(huì)返回下一個(gè)字段。在示例 31.9 中，這是右下角的字段 - 索引為 2 的字段。這樣就可以在巨大的圖表中迭代地找到從起點(diǎn)到終點(diǎn)的點(diǎn)。

示例 31.10。使用 width_first_search() 查找距離和路徑

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/named_function_params.hpp>
#include <boost/graph/visitors.hpp>
#include <boost/array.hpp>
#include <array>
#include <utility>
#include <algorithm>
#include <iostream>
int main()
{
  enum { topLeft, topRight, bottomRight, bottomLeft };
  std::array<std::pair<int, int>, 4> edges{{
    std::make_pair(topLeft, topRight),
    std::make_pair(topRight, bottomRight),
    std::make_pair(bottomRight, bottomLeft),
    std::make_pair(bottomLeft, topLeft)
  }};
  typedef boost::adjacency_list<boost::setS, boost::vecS,
    boost::undirectedS> graph;
  graph g{edges.begin(), edges.end(), 4};
  boost::array<int, 4> distances{{0}};
  boost::array<int, 4> predecessors;
  predecessors[bottomRight] = bottomRight;
  boost::breadth_first_search(g, bottomRight,
    boost::visitor(
      boost::make_bfs_visitor(
        std::make_pair(
          boost::record_distances(distances.begin(),
            boost::on_tree_edge()),
          boost::record_predecessors(predecessors.begin(),
            boost::on_tree_edge{})))));
  std::for_each(distances.begin(), distances.end(),
    [](int d){ std::cout << d << '\n'; });
  int p = topLeft;
  while (p != bottomRight)
  {
    std::cout << p << '\n';
    p = predecessors[p];
  }
  std::cout << p << '\n';
}

Example31.10

示例 31.10 顯示了 boost::breadth_first_search() 如何用于兩個(gè)訪問者。要使用兩個(gè)訪問者，您需要使用 std::make_pair() 將它們配對(duì)。如果需要兩個(gè)以上的訪問者，則必須嵌套這些對(duì)。示例 31.10 與示例 31.8 和示例 31.9 一起執(zhí)行相同的操作。

boost::breadth_first_search() 只能在每行具有相同權(quán)重的情況下使用。這意味著跨越點(diǎn)之間的任何線所花費(fèi)的時(shí)間總是相同的。如果線是加權(quán)的，這意味著每條線可能需要不同的時(shí)間來遍歷，那么您需要使用不同的算法來找到最短路徑。

示例 31.11。使用 dijkstra_shortest_paths() 查找路徑

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/named_function_params.hpp>
#include <boost/array.hpp>
#include <array>
#include <utility>
#include <iostream>
int main()
{
  enum { topLeft, topRight, bottomRight, bottomLeft };
  std::array<std::pair<int, int>, 4> edges{{
    std::make_pair(topLeft, topRight),
    std::make_pair(topRight, bottomRight),
    std::make_pair(bottomRight, bottomLeft),
    std::make_pair(bottomLeft, topLeft)
  }};
  typedef boost::adjacency_list<boost::listS, boost::vecS,
    boost::undirectedS, boost::no_property,
    boost::property<boost::edge_weight_t, int>> graph;
  std::array<int, 4> weights{{2, 1, 1, 1}};
  graph g{edges.begin(), edges.end(), weights.begin(), 4};
  boost::array<int, 4> directions;
  boost::dijkstra_shortest_paths(g, bottomRight,
    boost::predecessor_map(directions.begin()));
  int p = topLeft;
  while (p != bottomRight)
  {
    std::cout << p << '\n';
    p = directions[p];
  }
  std::cout << p << '\n';
}

Example31.11

示例 31.11 使用 boost::dijkstra_shortest_paths() 來查找到右下角的最短路徑。如果線被加權(quán)，則使用此算法。示例 31.11 假設(shè)從左上角到右上角越過線所需的時(shí)間是越過任何其他線所需的時(shí)間的兩倍。

在使用 boost::dijkstra_shortest_paths() 之前，必須將權(quán)重分配給行。這是通過數(shù)組權(quán)重完成的。數(shù)組中的元素對(duì)應(yīng)于圖中的線條。因?yàn)閺淖笊辖堑接疑辖堑木€是第一個(gè)，所以 weights 中的第一個(gè)元素被設(shè)置為所有其他元素的兩倍大。

為了給線條分配權(quán)重，數(shù)組權(quán)重開頭的迭代器作為第三個(gè)參數(shù)傳遞給圖形的構(gòu)造函數(shù)。這第三個(gè)參數(shù)可用于初始化線條的屬性。這僅適用于已為線條定義屬性的情況。

示例 31.11 將其他模板參數(shù)傳遞給 boost::adjacency_list。第四個(gè)和第五個(gè)模板參數(shù)指定點(diǎn)和線是否具有屬性以及這些屬性是什么。您可以為線和點(diǎn)指定屬性。

默認(rèn)情況下，boost::adjacency_list 使用 boost::no_property，這意味著點(diǎn)和線都沒有屬性。在示例 31.11 中，boost::no_property 作為第四個(gè)參數(shù)傳遞，用于指定點(diǎn)的無屬性。第五個(gè)參數(shù)使用 boost::property 定義捆綁屬性。

捆綁屬性是內(nèi)部存儲(chǔ)在圖表中的屬性。因?yàn)榭梢远x多個(gè)捆綁屬性，所以 boost::property 需要一個(gè)標(biāo)簽來定義每個(gè)屬性。 Boost.Graph 提供了一些標(biāo)簽，例如 boost::edge_weight_t，來定義算法自動(dòng)識(shí)別和使用的常用屬性。傳遞給 boost::property 的第二個(gè)模板參數(shù)是屬性的類型。在示例 31.11 中，權(quán)重是 int 值。

示例 31.11 有效，因?yàn)?boost::dijkstra_shortest_paths() 自動(dòng)使用類型為 boost::edge_weight_t 的捆綁屬性。

請(qǐng)注意，沒有訪問者被傳遞到 boost::dijkstra_shortest_paths()。該算法不只是訪問點(diǎn)。它尋找最短路徑——這就是為什么它被稱為 boost::dijkstra_shortest_paths()。您無需考慮事件或訪客。你只需要傳遞一個(gè)容器來存儲(chǔ)每個(gè)點(diǎn)的前身。如果您使用需要命名參數(shù)的 boost::dijkstra_shortest_paths() 變體，如示例 31.11 中所示，則使用 boost::predecessor_map() 傳遞容器。這是一個(gè)輔助函數(shù)，它需要一個(gè)指向數(shù)組開頭的指針或迭代器。

示例 31.11 顯示 0、3 和 2：從左上角到右下角的最短路徑通向左下角字段。右上角的路徑比其他可能性具有更大的權(quán)重。

示例 31.12。使用 dijkstra_shortest_paths() 的用戶定義屬性

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/named_function_params.hpp>
#include <boost/array.hpp>
#include <array>
#include <utility>
#include <iostream>
int main()
{
  enum { topLeft, topRight, bottomRight, bottomLeft };
  std::array<std::pair<int, int>, 4> edges{{
    std::make_pair(topLeft, topRight),
    std::make_pair(topRight, bottomRight),
    std::make_pair(bottomRight, bottomLeft),
    std::make_pair(bottomLeft, topLeft)
  }};
  struct edge_properties
  {
    int weight;
  };
  typedef boost::adjacency_list<boost::listS, boost::vecS,
    boost::undirectedS, boost::no_property,
    edge_properties> graph;
  graph g{edges.begin(), edges.end(), 4};
  graph::edge_iterator it, end;
  boost::tie(it, end) = boost::edges(g);
  g[*it].weight = 2;
  g[*++it].weight = 1;
  g[*++it].weight = 1;
  g[*++it].weight = 1;
  boost::array<int, 4> directions;
  boost::dijkstra_shortest_paths(g, bottomRight,
    boost::predecessor_map(directions.begin()).
    weight_map(boost::get(&edge_properties::weight, g)));
  int p = topLeft;
  while (p != bottomRight)
  {
    std::cout << p << '\n';
    p = directions[p];
  }
  std::cout << p << '\n';
}

Example31.12

示例 31.12 的工作方式與上一個(gè)類似，并顯示相同的數(shù)字，但它使用用戶定義的類 edge_properties，而不是預(yù)定義的屬性。

edge_properties 定義成員變量 weight 來存儲(chǔ)線條的重量。如果需要其他屬性，可以添加更多成員變量。

如果您使用線的描述符作為圖形的索引，則可以訪問用戶定義的屬性。因此，該圖的行為類似于一個(gè)數(shù)組。您從 boost::edges() 返回的行迭代器中獲取描述符。這樣就可以為每一行分配一個(gè)權(quán)重。

為了讓 boost::dijkstra_shortest_paths() 理解權(quán)重存儲(chǔ)在 edge_properties 中的權(quán)重中，必須傳遞另一個(gè)命名參數(shù)。這是通過 weight_map() 完成的。請(qǐng)注意，weight_map() 是從 boost::predecessor_map() 返回的對(duì)象的成員函數(shù)。還有一個(gè)名為 boost::weight_map() 的獨(dú)立函數(shù)。如果需要傳遞多個(gè)命名參數(shù)，則必須在第一個(gè)命名參數(shù)（獨(dú)立函數(shù)返回的參數(shù)）上調(diào)用成員函數(shù)。這樣，所有參數(shù)都被打包到一個(gè)對(duì)象中，然后傳遞給算法。

為了告訴 boost::dijkstra_shortest_paths() edge_properties 中的權(quán)重包含權(quán)重，傳遞了一個(gè)指向該屬性的指針。它不會(huì)直接傳遞給 weight_map()。相反，它通過 boost::get() 創(chuàng)建的對(duì)象傳遞?，F(xiàn)在調(diào)用已完成，并且 boost::dijkstra_shortest_paths() 知道要訪問哪個(gè)屬性來獲取權(quán)重。

示例 31.13。在圖形定義處初始化用戶定義的屬性

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/named_function_params.hpp>
#include <boost/array.hpp>
#include <array>
#include <utility>
#include <iostream>
int main()
{
  enum { topLeft, topRight, bottomRight, bottomLeft };
  std::array<std::pair<int, int>, 4> edges{{
    std::make_pair(topLeft, topRight),
    std::make_pair(topRight, bottomRight),
    std::make_pair(bottomRight, bottomLeft),
    std::make_pair(bottomLeft, topLeft)
  }};
  struct edge_properties
  {
    int weight;
  };
  typedef boost::adjacency_list<boost::listS, boost::vecS,
    boost::undirectedS, boost::no_property,
    edge_properties> graph;
  boost::array<edge_properties, 4> props{{2, 1, 1, 1}};
  graph g{edges.begin(), edges.end(), props.begin(), 4};
  boost::array<int, 4> directions;
  boost::dijkstra_shortest_paths(g, bottomRight,
    boost::predecessor_map(directions.begin()).
    weight_map(boost::get(&edge_properties::weight, g)));
  int p = topLeft;
  while (p != bottomRight)
  {
    std::cout << p << '\n';
    p = directions[p];
  }
  std::cout << p << '\n';
}

定義圖形時(shí)可以初始化用戶定義的屬性。您只需將迭代器作為第三個(gè)參數(shù)傳遞給 boost::adjacency_list 的構(gòu)造函數(shù)，它引用用戶定義屬性類型的對(duì)象。因此，您不需要通過描述符訪問行的屬性。示例 31.13 的工作原理與前一個(gè)類似，并顯示相同的結(jié)果。

示例 31.14。帶有 random_spanning_tree() 的隨機(jī)路徑

示例 31.14 中介紹的算法會(huì)找到隨機(jī)路徑。 boost::random_spanning_tree() 類似于 boost::dijkstra_shortest_paths()。它返回通過 boost::predecessor_map 傳遞的容器中的點(diǎn)的前驅(qū)。與 boost::dijkstra_shortest_paths() 相比，起點(diǎn)不直接作為參數(shù)傳遞給 boost::random_spanning_tree()。它必須作為命名參數(shù)傳遞。這就是為什么在 boost::predecessor_map 類型的對(duì)象上調(diào)用 root_vertex()。示例 31.14 查找到左下角字段的隨機(jī)路徑。

因?yàn)?boost::random_spanning_tree() 正在尋找隨機(jī)路徑，所以必須將隨機(jī)數(shù)生成器作為第二個(gè)參數(shù)傳遞。示例 31.14 使用 std::mt19937，它自 C++11 以來一直是標(biāo)準(zhǔn)庫的一部分。您還可以使用 Boost.Random 中的隨機(jī)數(shù)生成器。

示例 31.14 顯示 1、0 和 3 或 1、2 和 3。1 是右上角的字段，3 是左下角的字段。從右上場到左下場只有兩種可能的路徑：通過左上場或通過右下場。 boost::random_spanning_tree() 必須返回這兩個(gè)路徑之一。

練習(xí)

為以下國家/地區(qū)創(chuàng)建具有頂點(diǎn)的圖形：荷蘭、比利時(shí)、法國、德國、瑞士、奧地利和意大利。用共同邊界連接這些國家的頂點(diǎn)。找到從意大利到荷蘭的最短路徑——過境次數(shù)最少的路徑。將所有國家/地區(qū)的名稱寫入您從意大利到荷蘭的途中經(jīng)過的標(biāo)準(zhǔn)輸出。

擴(kuò)展您的計(jì)劃：現(xiàn)在進(jìn)入法國花費(fèi) 10 歐元，進(jìn)入比利時(shí) 15 歐元，進(jìn)入德國 20 歐元?？缭剿衅渌吔缛匀皇敲赓M(fèi)的。找到最短的路徑——過境點(diǎn)最少的路徑——這也是從意大利到荷蘭的最便宜的路徑。將所有國家/地區(qū)的名稱寫入您從意大利到荷蘭的途中經(jīng)過的標(biāo)準(zhǔn)輸出。

到此這篇關(guān)于C++ Boost Graph算法超詳細(xì)精講的文章就介紹到這了,更多相關(guān)C++ Boost Graph 內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: