Boost logo

Boost :

Subject: Re: [boost] GSOC 2010 - BGL Graph Connectives.
From: Tri Nguyen (nvutri_at_[hidden])
Date: 2010-03-28 23:06:04

On 3/25/2010 12:25 PM, Andrew Sutton wrote:
>> My first question is: How big is the graph? Or students will try to do as
>> big as possible.
>> My second question is: What type of data-structures (matrix or list) will
>> be used?
>> I attached my ideas in the PDF file below. Please have a look.
>> I appreciate all responses,
> Hi Tri,
> The BGL is generic so the expectation is that the algorithms should also be
> generic and made efficient for either adjacency matrices or adjacency lists.
> The size of the graphs is variable.
> Good proposals will demonstrate that you understand the design organization
> of the BGL as much as the theoretical background required for the project.
> Andrew Sutton
> andrew.n.sutton_at_[hidden]
> _______________________________________________
> Unsubscribe& other changes:

Dear Mr Sutton,

Thank you for your reply; it helped me a lot.

Based on your suggestion, I have tried to work on the Graph Connectives
Union. However, I changed the Complexity from
square (min (V_1 , V_2 ) ) to square (V_1 ) + square
(V_2 ).

I attached my header file and example file below. Please have a look.

In the following lines, I present my pseudo-code.


Pseudo-code for the graph_union:

graph_union (G1, G2, &G)

         G = G1;

         inc_position = num_vertices (G1);

*for* each vertex /u/ in V[G2]

* for *each vertex /v/ adjacent to /u/

                 add_edge( /u/, /v, /G);

// With G1 and G2 are two graphs which are supposed to unite

// G is the union graph of (G1, G2)


I look forward to your feedback,

Thank you so much,

Tri Nguyen.

Boost list run by bdawes at, gregod at, cpdaniel at, john at