Monthly Archives: April 2010

Graph data structures

Recently, I’m trying to re-implement the naive Belief Propagation algorithm on image girds, and then extend it to general graphs. It took me a while to figure out that I need some graph data structures to represent the general graph. It is easy to implement the algorithm on grids, since the girds have fixed pattern, that is, every node has four neighbours except the boundary nodes. While for the general graph, I need to define some graph data structures, such as Adjacency Matrix, adjacency list, or edge list (http://www.boost.org/doc/libs/1_42_0/libs/graph/doc/graph_theory_review.html). Or I can use some other graph libraries, such Boost Graph Library (GBL) and CGAL ( a good extension of GBL). GBL has integrated some graph algorithms already, such as max-flow and minimum spanning tree.