С++

Boost Graph C++

 

 

Граф — абстрактный математический объект, представляющий собой множество вершин графа и набор рёбер, то есть соединений между парами вершин. Например, за множество вершин можно взять множество аэропортов, обслуживаемых некоторой авиакомпанией, а за множество рёбер взять регулярные рейсы этой авиакомпании между городами.

Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах. Многие структуры, представляющие практический интерес в математике и информатике, могут быть представлены графами. Например, строение Википедии можно смоделировать при помощи ориентированного графа, в котором вершины — статьи, а дуги (ориентированные рёбра) — гиперссылки (тематическая карта).

Графы являются основным объектом изучения теории графов.

Ориентированный граф (кратко орграф) — (мульти) граф, рёбрам которого присвоено направление. Направленные рёбра именуются также дугами, а в некоторых источниках и просто рёбрами. Граф, ни одному ребру которого не присвоено направление, называется неориентированным графом или неорграфом.

 

1. Создание ориентированного графа

Первое, что вам вероятно нужно изучить с точки зрения программирования с Boost graph, это использование списка смежности для создания соединений ребер графа. Вероятно, стоит привыкнуть к использованию typedef, учитывайте объявления Boost могут оказаться длинными.

Объявление списка смежности для ориентированного графа, пример:

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS> DirectedGraph;

Предположим, мы хотим построить следующий взвешенный ориентированный граф:

Мы можем сделать это, делая повторные вызовы add_edge для создания графа. В следующем коде показано, как это можно сделать (не забудьте про -lboost_thread -lboost_system при сборке проекта) :

#include <boost/graph/adjacency_list.hpp>
#include <iostream>

typedef boost::property<boost::edge_weight_t, int> EdgeWeightProperty;
typedef boost::adjacency_list<boost::listS, boost::vecS, boost::directedS, boost::no_property, EdgeWeightProperty > DirectedGraph;
typedef boost::graph_traits<DirectedGraph>::edge_iterator edge_iterator;

int main()
{
    DirectedGraph g;

    boost::add_edge (0, 1, 3, g);
    boost::add_edge (0, 2, 1, g);
    boost::add_edge (0, 3, 7, g);
    boost::add_edge (1, 3, 6, g);
    boost::add_edge (2, 3, 9, g);


    std::pair<edge_iterator, edge_iterator> ei = edges(g);

    std::cout << "Количество ребер = " << num_edges(g) << "\n";
    std::cout << "Список ребер:\n";

    std::copy( ei.first, ei.second,
              std::ostream_iterator<boost::adjacency_list<>::edge_descriptor>{
                  std::cout, "\n"});

    std::cout << std::endl;

    return 0;
}

Спискок смежности

  template <class OutEdgeListS = vecS, // a Sequence or an AssociativeContainer
            class VertexListS = vecS, // a Sequence or a RandomAccessContainer
            class DirectedS = directedS,
            class VertexProperty = no_property,
            class EdgeProperty = no_property,
            class GraphProperty = no_property,
            class EdgeListS = listS>
  class adjacency_list
    : public detail::adj_list_gen<
      adjacency_list<OutEdgeListS,VertexListS,DirectedS,
                     VertexProperty,EdgeProperty,GraphProperty,EdgeListS>,
      VertexListS, OutEdgeListS, DirectedS,
      VertexProperty, EdgeProperty,
      GraphProperty, EdgeListS>::type,
      // Support for named vertices
      public graph::maybe_named_graph<
        adjacency_list<OutEdgeListS,VertexListS,DirectedS,
                       VertexProperty,EdgeProperty,GraphProperty,EdgeListS>,
        typename adjacency_list_traits<OutEdgeListS, VertexListS, DirectedS,
                                       EdgeListS>::vertex_descriptor,
        VertexProperty>

Получаем следующий результат:

Количество ребер = 5
Лист ребер:
(0,1)
(0,2)
(0,3)
(1,3)
(2,3)

2. Создание неориентированного графа

Пример неориентированного графа

Который мы строим аналогичным образом, но на этот раз предусматривая использование свойства boost:: undirectedS:

#include <boost/graph/adjacency_list.hpp>
#include <iostream>

typedef boost::property<boost::edge_weight_t, int> EdgeWeightProperty;
typedef boost::adjacency_list<boost::listS, boost::vecS,boost::undirectedS,boost::no_property,EdgeWeightProperty> UndirectedGraph;
typedef boost::graph_traits<UndirectedGraph>::edge_iterator edge_iterator;

int main()
{
    UndirectedGraph g;

    boost::add_edge (0, 1, 5, g);
    boost::add_edge (0, 7, 4, g);
    boost::add_edge (7, 2, 3, g);
    boost::add_edge (7, 8, 1, g);
    boost::add_edge (2, 8, 2, g);
    boost::add_edge (8, 6, 7, g);
    boost::add_edge (8, 3, 2, g);
    boost::add_edge (6, 5, 9, g);
    boost::add_edge (5, 4, 8, g);
    boost::add_edge (3, 4, 6, g);


    std::pair<edge_iterator, edge_iterator> ei = edges(g);

    std::cout << "Количество ребер = " << num_edges(g) << "\n";
    std::cout << "Список ребер:\n";

    for (edge_iterator it = ei.first; it != ei.second; ++it )
    {
        std::cout << *it << std::endl;
    }

    std::cout << std::endl;

    return 0;
}

Получаем следующий результат:

Количество ребер = 10
Список ребер:
(0,1)
(0,7)
(7,2)
(7,8)
(2,8)
(8,6)
(8,3)
(6,5)
(5,4)
(3,4)

3. Вывод веса ребер неориентированного графа

Рассмотрим следующее связующее дерево:

Получите отображение между ребрами и их соответствующими весами с помощью boost_property_map:

boost::property_map<UndirectedGraph, boost::edge_weight_t>::type EdgeWeightMap = get(boost::edge_weight_t(), g);

Полный код:

#include <boost/graph/adjacency_list.hpp>
#include <iostream>

typedef boost::property<boost::edge_weight_t, double> EdgeWeight;
typedef boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS, boost::no_property, EdgeWeight> UndirectedGraph;
typedef boost::graph_traits<UndirectedGraph>::edge_iterator edge_iterator;
int main()
{
    UndirectedGraph g;

    boost::add_edge (0, 1, 1, g);
    boost::add_edge (0, 2, 2, g);
    boost::add_edge (1, 2, 9, g);
    boost::add_edge (0, 3, 8, g);
    boost::add_edge (1, 3, 5, g);
    boost::add_edge (2, 3, 7, g);
    boost::add_edge (3, 4, 6, g);
    boost::add_edge (3, 5, 7, g);

    boost::property_map<UndirectedGraph, boost::edge_weight_t>::type EdgeWeightMap = get(boost::edge_weight_t(), g);

    std::pair<edge_iterator, edge_iterator> edgePair;
    for (edgePair = edges(g); edgePair.first != edgePair.second; ++edgePair.first)
    {
        std::cout << *edgePair.first << " " << EdgeWeightMap[*edgePair.first] << std::endl;
    }

    return 0;

}

(0,1) 1
(0,2) 2
(1,2) 9
(0,3) 8
(1,3) 5
(2,3) 7
(3,4) 6
(3,5) 7

4. Нахождение минимального пути, алгоритм Дейкстры

Алгоритм Дейкстры  — алгоритм на графах, изобретённый нидерландским учёным Эдсгером Дейкстрой в 1959 году. Находит кратчайшие пути от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его используют протоколы маршрутизации OSPF и IS-IS.

В этой демонстрации мы используем метод dijkstra_shortest_paths для получения не только дерева кратчайших путей, но и вывода пути между выбранной парой источник-приемник.

#include <boost/config.hpp>
#include <iostream>
#include <fstream>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/property_map/property_map.hpp>

int main(int, char *[])
{
    typedef boost::adjacency_list <boost::listS, boost::vecS, boost::directedS, boost::no_property,
      boost::property<boost::edge_weight_t, int> > graph_t;
    typedef boost::graph_traits<graph_t>::vertex_descriptor vertex_descriptor;
    typedef std::pair<int, int> Edge;

    const int num_nodes = 6;
    enum nodes { A, B, C, D, E, F };
    char name[] = "ABCDEF";
    Edge edge_array[] = {
        Edge(C, A),
        Edge(A, B),
        Edge(A, E),
        Edge(F, A),
        Edge(B, C),
        Edge(B, D),
        Edge(E, C),
        Edge(E, F),
        Edge(D, F),
        Edge(D, E),
        Edge(F, B)
    };

    int weights[] = { 10, 7, 8, 6, 8, 12, 10, 8, 1, 13, 5 };
    int num_arcs = sizeof(edge_array) / sizeof(Edge);

    // Graph created from the list of edges
    graph_t g(edge_array, edge_array + num_arcs, weights, num_nodes);

    // Create property_map from edges to weights
    boost::property_map<graph_t, boost::edge_weight_t>::type weightmap = get(boost::edge_weight, g);

    // Create vectors to store the predecessors (p) and the distances from the root (d)
    std::vector<vertex_descriptor> p(num_vertices(g));
    std::vector<int> d(num_vertices(g));

    // Create descriptor for the source node
    vertex_descriptor s = vertex(A, g);
    vertex_descriptor goal = vertex(F, g);

    // Evaluate Dijkstra on graph g with source s, predecessor_map p and distance_map d
    boost::dijkstra_shortest_paths(g, s,
      boost::predecessor_map(&p[0]).distance_map(&d[0]));

    //p[] is the predecessor map obtained through dijkstra
    //name[] is a vector with the names of the vertices
    //s and goal are vertex descriptors
    std::vector<boost::graph_traits<graph_t>::vertex_descriptor > path;
    boost::graph_traits<graph_t>::vertex_descriptor current = goal;

    while(current!=s)
    {
        path.push_back(current);
        current = p[current];
    }
    path.push_back(s);

    // Prints the path obtained in reverse
    std::cout << "Path from " << name[s] << " to " << name[goal] << std::endl;
    std::vector<boost::graph_traits<graph_t>::vertex_descriptor >::reverse_iterator it;

    for (it = path.rbegin(); it != path.rend(); ++it) {
        std::cout << name[*it] << " ";
    }
    std::cout << std::endl;

    return EXIT_SUCCESS;
}

Находим короткий путь между узлами A и F.

Путь A -> F
A E F

5. Поиск минимальных остовных деревьев с использованием алгоритма Крускала

Алгоритм Краскала — эффективный алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Также алгоритм используется для нахождения некоторых приближений для задачи Штейнера.

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/kruskal_min_spanning_tree.hpp>
#include <iostream>
#include <fstream>

int main()
{
    typedef boost::adjacency_list< boost::vecS, boost::vecS, boost::undirectedS,
                                  boost::no_property, boost::property<boost::edge_weight_t, int> > Graph;

    typedef boost::graph_traits <Graph>::edge_descriptor Edge;
    typedef boost::graph_traits <Graph>::vertex_descriptor Vertex;
    typedef std::pair<int, int> P;

    const int num_nodes = 6;
    P edge_array[] = {
        P(0, 4),
        P(4, 2),
        P(2, 1),
        P(1, 5),
        P(5, 0),
        P(5, 3),
        P(3, 2),
        P(1, 3),
        P(4, 1),
        P(0, 1)
    };

    int weights[] = { 8, 1, 5, 7, 1, 3, 2, 6, 4, 2 };
    std::size_t num_edges = sizeof(edge_array) / sizeof(P);

    Graph g(edge_array, edge_array + num_edges, weights, num_nodes);

    boost::property_map<Graph, boost::edge_weight_t >::type weight = get(boost::edge_weight, g);
    std::vector < Edge > spanning_tree;

    boost::kruskal_minimum_spanning_tree(g, std::back_inserter(spanning_tree));

    std::cout << "Print the edges in the MST:" << std::endl;

    for (std::vector < Edge >::iterator ei = spanning_tree.begin();
         ei != spanning_tree.end(); ++ei)
  {
        std::cout << source(*ei, g)
              << " <--> "
                  << target(*ei, g)
                  << " with weight of "
                  << weight[*ei]
                  << std::endl;
    }

    return 0;
}

Минимальное остовное дерево:
4 < –> 2 вес 1
5 < –> 0 вес 1
3 < –> 2 вес 2
0 < –> 1 вес 2
5 < –> 3 вес 3

6. Проблема максимального потока DIMACS

DIMACS (Center for Discrete Mathematics and Theoretical Computer Science) – центр дискретной математики и теоретической информатики.

В теории оптимизации и теории графов, задача о максимальном потоке заключается в нахождении такого потока по транспортной сети, что сумма потоков из истока, или, что то же самое, сумма потоков в сток максимальна.

Задача о максимальном потоке является частным случаем более трудных задач, как например задача о циркуляции.

Пример задачи о максимальном потоке.

dimacs.txt

c This is a simple example file to demonstrate the DIMACS
c input file format for maximum flow problems. The solution
c vector is [5,10,5,0,5,5,10,5] with cost at 15.
c Problem line (nodes, links)
p max 6 8
c source
n 1 s
c sink
n 6 t
c Arc descriptor lines (from, to, capacity)
a 1 2 5
a 1 3 15
a 2 4 5
a 2 5 5
a 3 4 5
a 3 5 5
a 4 6 15
a 5 6 5
c
c End of file

Строки, начинающиеся с “c”, являются строками комментариев. Строка задачи начинается с буквы “p” и представляет обозначение задачи (max, min и т. д.), количество ребер (8) и количество вершин (6). Строки, начинающиеся с “n”, являются дескрипторами узла-идентификатора – узел ID и является ли узел источником (“s”) или приемником (“t”). Наконец, строки “a” являются дескрипторами, дающими взаимосвязи узлов и их весового значения. В следующем графическом представлении примера задачи сетевого потока показаны не только сетевые соединения и веса, но и потоки на каналах:

#include <boost/config.hpp>
#include <iostream>
#include <fstream>
#include <string>
 
#include <boost/graph/edmonds_karp_max_flow.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/read_dimacs.hpp>
#include <boost/graph/graph_utility.hpp>
 
int main()
{
    typedef boost::adjacency_list_traits<boost::vecS, boost::vecS, boost::directedS > Traits;
    typedef boost::adjacency_list<boost::listS, boost::vecS, boost::directedS,
        boost::property<boost::vertex_name_t, std::string >,
        boost::property<boost::edge_capacity_t, long,
        boost::property<boost::edge_residual_capacity_t, long,
        boost::property<boost::edge_reverse_t, Traits::edge_descriptor>>>> Graph;
 
    Graph g;
 
    boost::property_map<Graph, boost::edge_capacity_t>::type
        capacity = get(boost::edge_capacity, g);
    boost::property_map<Graph, boost::edge_reverse_t>::type rev = get(boost::edge_reverse, g);
    boost::property_map<Graph, boost::edge_residual_capacity_t>::type
        residual_capacity = get(boost::edge_residual_capacity, g);
 
    Traits::vertex_descriptor s, t;
     
    // Use a DIMACS network flow file as stdin:
    std::ifstream is ("dimacs.txt", std::ios::in);
    read_dimacs_max_flow(g, capacity, rev, s, t, is);
 
#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
  std::vector<default_color_type> color(num_vertices(g));
  std::vector<Traits::edge_descriptor> pred(num_vertices(g));
  long flow = edmunds_karp_max_flow
    (g, s, t, capacity, residual_capacity, rev, &color[0], &pred[0]);
#else
  long flow = edmonds_karp_max_flow(g, s, t);
#endif
 
    std::cout << "c  The total flow:" << std::endl;
    std::cout << "s " << flow << std::endl << std::endl;
    std::cout << "c flow values:" << std::endl;
 
    boost::graph_traits<Graph>::vertex_iterator u_iter, u_end;
    boost::graph_traits<Graph>::out_edge_iterator ei, e_end;
   
    for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter)
        for (boost::tie(ei, e_end) = out_edges(*u_iter, g); ei != e_end; ++ei)
            if (capacity[*ei] > 0)
                std::cout << "f " << *u_iter << " " << target(*ei, g) << " "
                          << (capacity[*ei] - residual_capacity[*ei]) 
                          << std::endl;
 
    return EXIT_SUCCESS;
}

c Общий поток:
s 15

c значения потока:
f 0 1 5
f 0 2 10
f 1 3 5
f 1 4 0
f 2 3 5
f 2 4 5
f 3 5 10
f 4 5 5

Как и предполагалось, вектор решения выходных переменных составляет [5, 10, 5, 0, 5, 5, 10, 5].

Leave a Reply

Your email address will not be published. Required fields are marked *