GSOC 2010 - BGL Graph Connectives.
Hi, I am Tri Nguyen from South Plains College. I am interested in Graph Connectives Project of BGL. In this writing, I would like to ask two questions, and then propose my idea of doing four Connectives: union, join, intersection, and difference. 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, Thank you, Tri Nguyen.
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@gmail.com
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@gmail.com _______________________________________________ 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.
On 3/25/2010 12:25 PM, Andrew Sutton wrote:
Dear Mr Sutton, I want to fix one sentence in my last post: "However, I changed the Complexity from square (min (V_1 , V_2 ) ) to square (V_1 ) + square (V_2 )." What I meant was: I changed the way to solve the problem. At first, I thought I could attach Graph 2 to Graph 1, and then consider Graph 1 as the union graph. Therefore, the complexity, that I proposed in the first post, was square (min (V_1 , V_2 ) ). However, now I believe that creating a new graph, which is the union of graph 1 and 2, is a more convenient way for users. Nevertheless, by this way, the complexity is square (V_1 ) + square (V_2 ). I apologize for my mistake, I am looking forward to your reply, Tri Nguyen.
I am looking forward to your reply,
The approach looks like it might be viable, but it won't work for graphs with non-integral vertex descriptors. This will fail to compile, for example with directed_graph and undirected_graph. Also, how do you propose to manage vertex and edge properties? This algorithm doesn't deal with them. Andrew Sutton andrew.n.sutton@gmail.com
On 3/29/2010 7:57 AM, Andrew Sutton wrote:
The approach looks like it might be viable, but it won't work for graphs with non-integral vertex descriptors. This will fail to compile, for example with directed_graph and undirected_graph. Also, how do you propose to manage vertex and edge properties? This algorithm doesn't deal with them.
Andrew Sutton andrew.n.sutton@gmail.com _______________________________________________ Unsubscribe& other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Dear Mr Sutton, Thanks for your reply. It is true that the above code does not deal with those problems yet; I just wanted to clarify my approach. About dealing with the undirected and directed graph, I think the Union of those will be a mixed graph, which I could not find in BGL. Therefore, I suggest two special situations which happen when programmers try to unite undirected and directed graphs : 1) Union ( undi, di ) returns an undi graph : I will convert the directed graph to undirected by adding arcs. Then, I unite them. 2) Union ( undi, di ) returns a di graph : I will consider the undirected graph as a directed one with two same arcs between vertices. About solving the vertex and edge properties, actually, I am working on it to figure out the best way. However, I want to present the idea that I have come up with: 1) If the Union_graph 's properties is clearly declared, I will use type-casting. Nevertheless, the challenge is to deal with the non-integral data type. 2) If the Union_graph 's property is undeclared, I will try to integrate two properties. In particular, the vertices and edges of graph 1 will still keep their own properties; but they will also have graph_2 's properties, in which values will be initialized as 0. I would like to know your opinion. I look forward to your comment, Thank you so much, Tri Nguyen.
1) Union ( undi, di ) returns an undi graph : I will convert the directed graph to undirected by adding arcs. Then, I unite them.
2) Union ( undi, di ) returns a di graph : I will consider the undirected graph as a directed one with two same arcs between vertices.
Is there any particular reason you are choosing this behavior? What particular use cases does this address? It may be acceptable to not define unions between undirected and directed graphs.
1) If the Union_graph 's properties is clearly declared, I will use type-casting. Nevertheless, the challenge is to deal with the non-integral data type.
Type casting is not a viable solution.
2) If the Union_graph 's property is undeclared, I will try to integrate two properties. In particular, the vertices and edges of graph 1 will still keep their own properties; but they will also have graph_2 's properties, in which values will be initialized as 0.
Properties are never actually "undeclared". There is always a type that represents the vertex and edge properties of a graph. You will have to look a little closer at the implementation of the BGL graph data structures in order to determine an acceptable approach. Andrew Sutton andrew.n.sutton@gmail.com
On 3/31/2010 2:57 PM, Andrew Sutton wrote:
Type casting is not a viable solution.
Andrew Sutton andrew.n.sutton@gmail.com _______________________________________________ Unsubscribe& other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Dear Mr Sutton, Thanks for your comment. I have two questions. 1) Is the union (graph_1, graph_2) is supposed to equal union (graph_2, graph_1) ?. 2) I want to ask if the Covariance theory [1] is applicable to solve the problem of graph properties. In the below example, I want to explain how I will apply the theory: G1 is a graph representing the connection between students. So G1's vertex_property is *student*. G2 is a graph representing the connection between professors. So G2's vertex_property is *professor*. Since both *student* and *professor* are inside *people*, I can use *people* as Union_Graph 's vertex_property. Please let me know your opinion, Thank you, Tri Nguyen. [1] http://en.wikipedia.org/wiki/Covariance_and_contravariance_%28computer_scien...
Thanks for your comment. I have two questions. 1) Is the union (graph_1, graph_2) is supposed to equal union (graph_2, graph_1) ?.
Yes. Union is a commutative operation.
2) I want to ask if the Covariance theory [1] is applicable to solve the problem of graph properties. In the below example, I want to explain how I will apply the theory: G1 is a graph representing the connection between students. So G1's vertex_property is *student*. G2 is a graph representing the connection between professors. So G2's vertex_property is *professor*. Since both *student* and *professor* are inside *people*, I can use *people* as Union_Graph 's vertex_property.
I don't think that this will work particularly well. It's probably easier to assume that vertex and edge properties are either the same type or completely unrelated. Andrew Sutton andrew.n.sutton@gmail.com
Thanks for your reply,
It's probably easier to assume that vertex and edge properties are either the same type or completely unrelated.
Well, I am wondering if it is acceptable to work with the same type only, and ignore the completely unrelated. I look forward to your answer, Tri Nguyen.
It's probably easier to assume that vertex and edge properties are either the same type or completely unrelated.
Well, I am wondering if it is acceptable to work with the same type only, and ignore the completely unrelated.
I think that's a good starting point :) Andrew Sutton andrew.n.sutton@gmail.com
On Fri, Apr 2, 2010 at 4:41 PM, Andrew Sutton <andrew.n.sutton@gmail.com>wrote:
Well, I am wondering if it is acceptable to work with the same type only, and ignore the completely unrelated.
I think that's a good starting point :)
Dear Mr Sutton, I have tried with overloading to test if two types are the same. However, the overloading solution does not work too well. Could you suggest me another idea? I really appreciate that. Regards, Tri Nguyen.
Dear Mr Sutton,
I have tried with overloading to test if two types are the same. However, the overloading solution does not work too well. Could you suggest me another idea? I really appreciate that.
If you don't show me what the first idea is, I can't really suggest another one :) What are you trying to accomplish, and what exactly did you do? Andrew Sutton andrew.n.sutton@gmail.com
If you don't show me what the first idea is, I can't really suggest another one :) What are you trying to accomplish, and what exactly did you do?
I am sorry for my confusing question. I wrote the template like this: ------------------------------------------------------------------------------ template <> // double struct Is_Type<double> { static const int value = 0;}; template <> // int struct Is_Type<int> { static const int value = 1;}; ------------------------------------------------------------------------------ And then, I call Is_Type<typename>::value to compare and figure if two types are different : ------------------------------------------------------------------------------ if ( Is_Type<int>::value == Is_Type<double>::value ) ------------------------------------------------------------------------------ However, I think there is a huge number of types. Therefore, this solution will not be efficient. I would like to ask if you could suggest me a better way. Regards, Tri Nguyen.
AMDG nguyen vu tri wrote:
I am sorry for my confusing question. I wrote the template like this: ------------------------------------------------------------------------------ template <> // double struct Is_Type<double> { static const int value = 0;};
template <> // int struct Is_Type<int> { static const int value = 1;};
------------------------------------------------------------------------------
And then, I call Is_Type<typename>::value to compare and figure if two types are different : ------------------------------------------------------------------------------ if ( Is_Type<int>::value == Is_Type<double>::value ) ------------------------------------------------------------------------------
However, I think there is a huge number of types. Therefore, this solution will not be efficient. I would like to ask if you could suggest me a better way.
boost::is_same<int, double>::value In Christ, Steven Watanabe
participants (4)
-
Andrew Sutton -
nguyen vu tri -
Steven Watanabe -
Tri Nguyen