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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s