Re: [boost] GSOC 2010 - BGL Graph Connectives.

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: http://lists.boost.org/mailman/listinfo.cgi/boost
>    

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.