9.1 属性映射

图的抽象数学性质和要解决的具体问题之间主要是靠附加在图的顶点和边上的属性联系起来的，例如距离、容量、权重、颜色等。在数据结构实现方面，有很多方法可以将属性附加到图上，但图算法不必处理属性的实现细节。属性映射概念部分中定义的属性映射接口提供了从图访问属性的通用方法。这是 BGL 算法中用于访问属性的接口。

属性映射接口

属性映射接口指定使用单独的属性映射对象来访问每个属性。在下面的示例中，我们展示了 Dijkstra 最短路径算法中使用的 relax() 函数的实现。在此函数中，我们需要访问边的权重属性和顶点的距离属性。我们将 relax() 编写为模板函数，以便它可以在许多不同的情况下使用。该函数的两个参数（权重和距离）是属性映射对象。一般来说，BGL 算法显式传递函数所需的每个属性的属性映射对象。属性映射接口定义了几个函数，我们在这里使用其中两个函数：get() 和 put()。get() 函数接受属性映射对象，例如距离和键对象。对于距离属性，我们使用顶点对象 u 和 v 作为键。然后 get() 函数返回顶点的属性值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template <class Edge, class Graph,
          class WeightPropertyMap,
          class DistancePropertyMap>
bool relax(Edge e, const Graph& g,
           WeightPropertyMap weight,
           DistancePropertyMap distance)
{
    typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
    Vertex u = source(e,g), v = target(e,g);
    if (get(distance, u) + get(weight, e) < get(distance, v)) {
        put(distance, v, get(distance, u) + get(weight, e));
        return true;
    } else
        return false;
}
C++

函数 get() 返回属性值的副本。属性映射接口中有第三个函数 at()，它返回对属性值的引用（如果映射不可变的，将返回常量引用）。

与 STL 的 iterator_traits 类类似，有一个 property_traits 类可用于推导与属性映射类型关联的类型：键类型和值类型，以及属性映射类别（用于判断映射是否可读、可写或两者兼而有之）。在 relax() 函数中，我们可以使用 property_traits 来声明距离属性类型的局部变量。

1
2
3
4
5
6
7
8
9
10
11
12
13
{
    typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
    Vertex u = source(e,g), v = target(e,g);
    typename property_traits<DistancePropertyMap>::value_type
        du, dv; // 距离属性类型的局部变量
    du = get(distance, u);
    dv = get(distance, v);
    if (du + get(weight, e) < dv) {
        put(distance, v, du + get(weight, e));
        return true;
    } else
        return false;
}
C++

内部属性

以某种方式存储在图对象“内部”，属性值对象的生命周期与图对象的生命周期相同。

外部属性

存储在图对象的“外部”，属性值对象的生命周期与图无关。这对于暂时需要的属性很有用，可能是在特定算法的持续时间内需要的，例如在 breadth_first_search() 中使用的颜色属性。当将外部属性与 BGL 算法一起使用时，外部属性的属性映射对象必须作为参数传递给算法。

内部属性

支持内部属性存储的图类型（例如 adjacency_list）通过 PropertyGraph 中定义的接口提供对其属性映射对象的访问。有一个函数 get(Property, g) 从图中获取属性映射对象。第一个参数是属性类型，用于指定要访问的属性，第二个参数是图形对象。图形类型必须记录它提供对哪些属性（以及标签）的访问。属性映射的类型取决于图的类型和所映射的属性。定义了一个特征类，它提供了推断属性映射类型的通用方法：property_map。以下代码显示了如何获取某种图类型的距离和权重属性的属性映射图。

1
2
3
property_map<Graph, vertex_distance_t>::type d = get(vertex_distance, g);

property_map<Graph, edge_weight_t>::type w = get(edge_weight, g);
C++

一般来说，BGL 算法要求将算法所需的所有属性映射显式传递给算法。例如，BGL Dijkstra 的最短路径算法需要四个属性图：距离、权重、颜色和顶点 ID。

通常，部分或全部属性将位于图的内部，因此可以通过以下方式调用 Dijkstra 算法（给定一些图 g 和源顶点 src）。

1
2
3
4
5
dijkstra_shortest_paths(g, src,
    distance_map(get(vertex_distance, g)).
    weight_map(get(edge_weight, g)).
    color_map(get(vertex_color, g)).
    vertex_index_map(get(vertex_index, g)));
C++

由于指定所有属性映射有点麻烦，BGL 提供了默认值，假设某些属性是内部的，并且可以通过图中的 get(Property, g) 访问，或者如果属性映射仅在内部使用，则 该算法将从数组中为自身创建一个属性映射，并使用图的顶点索引映射作为数组的偏移量。下面我们展示了使用命名参数的所有默认值对 dijkstra_shortest_paths 算法的调用。此调用相当于之前对 Dijkstra 算法的调用。

1
dijkstra_shortest_paths(g, src);
C++

下一个问题是：内部属性首先如何附加到图对象？这取决于您正在使用的图形类。BGL 的 adjacency_list 图类使用属性机制（请参阅内部属性部分）来允许在图的边和顶点上存储任意数量的属性。

外部属性

在本节中，我们将描述两种构建外部属性图的方法，但是可以通过无限多种方式为图创建外部属性。第一种方法使用适配器类 iterator_property_map。此类包装了一个随机访问迭代器，并从中创建了一个属性映射。随机访问迭代器必须指向属性值范围的开头，并且该范围的长度必须是图中的顶点或边的数量（取决于它是顶点还是边属性图）。适配器还必须提供 ID 属性映射，该映射将用于将顶点或边描述符映射到属性值的偏移量（与随机访问迭代器的偏移量）。ID 属性映射通常是图的内部属性映射。以下示例显示如何使用 iterator_property_map 为存储在数组中的容量和流量属性创建外部属性映射。数组按边 ID 进行索引。使用属性将边 ID 添加到图中，并且在将每条边添加到图中时给出 ID 的值。此示例的完整源代码位于 example/exterior_edge_properties.cpp 中。 print_network() 函数打印出带有流量和容量值的图表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
typedef adjacency_list<vecS, vecS, bidirectionalS,
    no_property, property<edge_index_t, std::size_t> > Graph;

const int num_vertices = 9;
Graph G(num_vertices);

int capacity_array[] = { 10, 20, 20, 20, 40, 40, 20, 20, 20, 10 };
int flow_array[] = { 8, 12, 12, 12, 12, 12, 16, 16, 16, 8 };

// Add edges to the graph, and assign each edge an ID number.
add_edge(0, 1, 0, G);
// ...

typedef graph_traits<Graph>::edge_descriptor Edge;
typedef property_map<Graph, edge_index_t>::type EdgeID_Map;

EdgeID_Map edge_id = get(edge_index, G);
iterator_property_map<int*, int, int&, EdgeID_Map>
    capacity(capacity_array, edge_id),
    flow(flow_array, edge_id);

print_network(G, capacity, flow);
C++

第二种方法使用指针类型（指向属性值数组的指针）作为属性映射。 这要求键类型为整数，以便可以用作指针的偏移量。 具有模板参数 VertexList=vecS 的 adjacency_list 类使用整数作为顶点描述符（从零索引到图中的顶点数），因此它们适合作为指针属性映射的键类型。 当 VertexList 不是 vecS 时，则顶点描述符不是整数，并且不能与指针属性映射一起使用。 相反，必须使用上述使用带有 ID 属性的 iterator_property_map 的方法。 Edge_list 类还可以使用整数类型作为顶点描述符，具体取决于如何定义适应的边缘迭代器。示例如下：

指针可以用作属性映射的原因是头boost中有几个重载函数和property_traits的特化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
namespace boost {
    template <class T>
    struct property_traits<T*> {
        typedef T value_type;
        typedef ptrdiff_t key_type;
        typedef lvalue_property_map_tag category;
    };

    template <class T>
    void put(T* pa, std::ptrdiff_t key, const T& value) { pa[key] = value; }

    template <class T>
    const T& get(const T* pa, std::ptrdiff_t key) { return pa[key]; }

    template <class T>
    const T& at(const T* pa, std::ptrdiff_t key) { return pa[key]; }

    template <class T>
    T& at(T* pa, std::ptrdiff_t key) { return pa[key]; }
}
C++

在下面的示例中，我们使用一个数组来存储图中每个顶点的城市名称，并使用一个std::vector来存储调用breadth_first_search()时需要的顶点颜色 。由于std::vector的迭代器 （通过调用begin()获得）是一个指针，因此指针属性映射方法也适用于 std::vector::iterator。此示例的完整源代码位于example/city_visitor.cpp中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// Definition of city_visitor omitted...

int main(int,char*[])
{
    enum { SanJose, SanFran, LA, SanDiego, Fresno, LosVegas, Reno,
           Sacramento, SaltLake, Pheonix, N };

    // An array of vertex name properties
    std::string names[] = { "San Jose", "San Francisco",  "San Jose",
                            "San Francisco", "Los Angeles", "San Diego",
                            "Fresno", "Los Vegas", "Reno", "Sacramento",
                            "Salt Lake City", "Pheonix" };

    // Specify all the connecting roads between cities.
    typedef std::pair<int,int> E;
    E edge_array[] = { E(Sacramento, Reno), ... };

    // Specify the graph type.
    typedef adjacency_list<vecS, vecS, undirectedS> Graph;
    // Create the graph object, based on the edges in edge_array.
    Graph G(N, edge_array, edge_array + sizeof(edge_array)/sizeof(E));

    // DFS and BFS need to "color" the vertices.
    // Here we use std::vector as exterior property storage.
    std::vector<default_color_type> colors(N);

    cout << "*** Depth First ***" << endl;
    depth_first_search(G, city_visitor(names), colors.begin());
    cout << endl;

    // Get the source vertex
    boost::graph_traits<Graph>::vertex_descriptor
        s = vertex(SanJose, G);

    cout << "*** Breadth First ***" << endl;
    breadth_first_search(G, s, city_visitor(names), colors.begin());

    return 0;
}
C++

构造外部属性映射表

1
2
3
4
5
6
7
8
9
10
11
12
13
template <class Iterator, class IDMap>
class iterator_map
{
public:
    typedef typename boost::property_traits<IDMap>::key_type key_type;
    typedef typename std::iterator_traits<Iterator>::value_type value_type;
    typedef boost::lvalue_property_map_tag category;

    iterator_map(Iterator i = Iterator(), const IDMap& id = IDMap())
        : m_iter(i), m_id(id) { }
    Iterator m_iter;
    IDMap m_id;
};
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
template <class Iter, class ID>
typename std::iterator_traits<Iter>::value_type
get(const iterator_map<Iter,ID>& i,
    typename boost::property_traits<ID>::key_type key)
{
    return i.m_iter[i.m_id[key]];
}

template <class Iter, class ID>
void
put(const iterator_map<Iter,ID>& i,
    typename boost::property_traits<ID>::key_type key,
    const typename std::iterator_traits<Iter>::value_type& value)
{
  i.m_iter[i.m_id[key]] = value;
}

template <class Iter, class ID>
typename std::iterator_traits<Iter>::reference
at(const iterator_map<Iter,ID>& i,
    typename boost::property_traits<ID>::key_type key)
{
    return i.m_iter[i.m_id[key]];
}
C++

这就对了。 iterator_map 类是完整的，可以像上一节中的 iterator_property_map 一样使用。

技术 > C++ > 翻译
#C++ #Boost #第三方库
9.1 属性映射
http://example.com/2023/11/01/boost/boost_graph_library/09_Boost Graph Library Tutorial/9.1_属性映射/
作者
QiDianMaker
发布于
2023年10月31日
更新于
2023年10月31日
许可协议