Li Min's Blog

今天因为程序要用，把The Boost Graph Library: User Guide and Reference Manual这本书借了过来，发现作者Lie-Quan Lee竟然是浙江大学物理系毕业的,牛人啊，景仰，因为BGL的代码是在太复杂了。

拿着书看还是很明白的，总结如下：

1. vertex descriptor 和 edge descriptors 就是图中vertex和edge的类型，如果知道一个图的类型为graph_t，总可以通过以下代码得到相应的vertex and edge descriptor

graph_traits< graph_t >::vertex_descriptor
graph_traits< graph_t >::edge_descriptor

2.Porperty Maps。这个比较复杂，我是写了一个例程才明白一二的。

using namespace boost;

typedef adjacency_list < listS, listS, undirectedS,
        property < vertex_name_t, std::string > > graph_t;
typedef property_map < graph_t, vertex_name_t >::type name_map_t;
typedef graph_traits < graph_t >::vertex_descriptor VertexDescrip;

graph_t myG(3);

VertexDescrip a, b, c;
name_map_t vertexNameMap = get(vertex_name, myG);

a = add_vertex(myG); vertexNameMap[a] = std::string("first");
b = add_vertex(myG); vertexNameMap[b] = "second";
c = add_vertex(myG); vertexNameMap[c] = "third";

其中property < vertex_name_t, std::string >就是定义vertex_name_t的类型是std::string. vertex_name_t是内置类型，我们也可以自定义类型，比如property < vertex_color_t, RGB >，只要符合vertex_***_t这个命名规则并且事先注册之就可以了。注册方法如下：

namespace boost {
    enum vertex_color_t    { vertex_color = 123}; // a unique #
    BOOST_INSTALL_PROPERTY(vertex, color);
}

定义好property之后就可以定义vertex和此property之间对应的map

typedef property_map < graph_t, vertex_name_t >::type name_map_t;
...
name_map_t vertexNameMap = get(vertex_name, myG); //实例化

之后就可以通过这个MAP用vertex作为key存取相应的属性值

a = add_vertex(myG); vertexNameMap[a] = std::string("first");

3. 端点和边的遍历

这个例子演示了如何遍历所有vertices

graph_traits< graph_t >::vertex_iterator vi, vi_end;
for (tie(vi, vi_end)= vertices(myG); vi != vi_end; ++vi)
{
    std::cout << vertexNameMap(*vi);
}

还有一种写法

typedef graph_traits< graph_t >::vertex_iterator v_iter_t
for (std::pair< v_iter_t, v_iter_t > p = vertices(myG); p.first!= p.second; ++p.first)
{
    std::cout << vertexNameMap(*p.first);
}

同时用edges(myG)获得所有边

4. 加入点和边。

// Add vertices
vertex1 = add_vertex(g);
vertex2 = add_vertex(g);

// Add edges
typedef graph_traits<graph_t>::edge_descriptor EdgeDescrip;
EdgeDescrip edge1;
bool inserted = false;

tie(edge1, inserted) = add_edge( vertex1, vertex2, g);
assert ( inserted );

5.图的种类和若干算法

一般用adjacency_list表示，若是密度大的图dense graph (if |E| == square(|V|)),可以用adjacency_matrix表示。

• reverse_graph()用来翻转边的指向
• filtered_graph()可以指定条件来过滤某些边或者端点
• depth_first_search()
• breadth_first_search()
• for a vertex, in_edges(), out_edges(), and adjacent_vertices()
• for a edge, source(e, g) and target(e, g)

# posted by Li Min : 10:27 PM  0 comments

General guidelines are listed here.

How do I export STL components? Why do I get an access violation when accessing STL objects created in a DLL?

It is possible to export an instantiation of a Standard Template Library (STL) class. You can also export a class that contains a data member that is an STL object.

Note that you may not export a generalized template. The template must be instantiated, that is, all of the template parameters must be supplied and must be completely defined types at the point of instantiation. For instance "stack;" instantiates the STL stack class. The instantiation forces all members of class stack to be generated.

For details see the following article in the Microsoft Knowledge Base:

ARTICLE-ID: Q168958

TITLE: HOWTO: Exporting STL Components Inside and Outside a Class

When accessing a STL object created in one DLL or EXE through a pointer or reference in a different DLL or EXE, you may experience an access violation or other serious program errors including the appearance of data corruption or data loss. For details see the following article in the Microsoft Knowledge Base:

ARTICLE-ID: Q172396

TITLE PRB: Access Violation Caused when Accessing STL Object in DLL

Generally, NO good solutions for return a STL object from a DLL :(

A more detailed article briefly introduce the history and trend of export feature in C++ (exported Templates)

# posted by Li Min : 5:54 PM  0 comments

1. In Windows Live Writer, Weblog -> Add Weblog Account...
2. Choose Another weblog service
3. Weblog URL enter http://www.blogger.com/, username is your gmail account, e.g. yourname@gmail.com and password is your gmail password, you could choose to store it locally
4. Type of Weblog is Blogger; and the <feed-id> in Remote Posting URL is the number shown in your blogger setting page address, e.g. http://www.blogger.com/blog-options-basic.g?blogID=*******
5. All left are account details. have fun!

A more detail instruction could be found here (maybe somehow out of date), http://sunilbajpai.blogspot.com/2006/10/making-windows-live-writer-work-with.html

# posted by Li Min : 6:08 PM  0 comments