Hi Andrew,

I'm not sure what you mean by a mixed graph, however.

for mixed graph I mean a graph with both directed and undirected edges. I'm sure there are some valid considerations that devolopers did to not implement it but some real-life problems (I'm thinking to routing algorithms) would benefit from that.

Are you planning to submit these algorithms to the BGL?

I would like to submit to the BGL in particular the euler tour algorithm and the minimum cost maximum matching algorithm because I think they could be very useful. Just now I'm studying what data structures I need to implement it and how visitors could be useful in that algorithm. Do you think it could be useful write an interface to insert in the submission? I think another very useful algorithm could be the one used to find optimum branchings (you can find info about it also searching for edmonds algorithm). What do you think could be more useful? Camillo 2010/4/6 Andrew Sutton <andrew.n.sutton@gmail.com>:

...

I'm developing my thesis using BGL. Now it's some months I'm working on it and this is what I would like to see implemented on BGL and partially what I'm working on in those months:

- check if graph have an euler tour(is eulerian) and find one and/or all possible euler tours - add the support for mixed graph - add the algorithm to find a minimum cost maximum matching

Hi Camillo,

Are you planning to submit these algorithms to the BGL? They seem like they could be very useful. I'm not sure what you mean by a mixed graph, however.

Andrew Sutton andrew.n.sutton@gmail.com _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

2010/4/6 Andrew Sutton <andrew.n.sutton@gmail.com>:

for mixed graph I mean a graph with both directed and undirected

...

edges. I'm sure there are some valid considerations that devolopers did to not implement it but some real-life problems (I'm thinking to routing algorithms) would benefit from that.

I see... That is interesting. How are you proposing to solve this problem? I've never really thought about it :)

I'm still working on it, but at this point I think it's better for me to concentrate on writing a good submission for the algorithms I want to propose, anyway I will write back to you when I think I have a solution.

...

I would like to submit to the BGL in particular the euler tour algorithm and the minimum cost maximum matching algorithm because I think they could be very useful. Just now I'm studying what data structures I need to implement it and how visitors could be useful in that algorithm. Do you think it could be useful write an interface to insert in the submission?

These two algorithms alone would constitute a good GSoC proposal (with an option for the 3rd, perhaps). These algorithms can be very hard to get right. You could suggest an interface in the proposal. It would help show what you're trying to do.

What do you mean with "(with an option for the 3rd, perhaps)"? To propose an alternative 3rd algorithm like "minimum cost perfect matching or optimum branching algorithm" or more probably to add to the submission a 3rd algorithm? What do you think if I add also the optimum branching algorithm? Some months ago I implemented that algorithm but it's an inefficient and incomplete version( O(n^3) and supports only finding arborescence with an arbitrary root ). On internet I found a quite good implementation of that algorithm here: http://edmonds-alg.sourceforge.net; built using the BGL but with complexity of O(n^2) for dense graph. There is no support for the running mode with complexity O(m log n) (better with sparse graph), with m # of edges and n # of vertices; so it seems actually the BGL could benefit from an optimum branching algorithm supporting complexity O(n^2) and O(m log n) and well integrated in the library. Looking forward to have an opinion. Thanks Camillo

Andrew Sutton andrew.n.sutton@gmail.com _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost