''This is one of the [Project Ideas for Google Summer of Code 2009%|%GSoC 2009 Projects%|%].'' For the current code see http://code.assembla.com/graphmanipulations/subversion/nodes Further see our [http://wiki.tcl.tk/23203#pagetoc5b58073e%|%Timeline] for the planned work and its status. After the summer is over the results will be integrated back into the regular repository at sourceforge. ---- **GRAPH MANIPULATIONS** '''WHY GRAPH MANIPULATIONS?''' * - graph theory is my common interest and subject well known for me * - opportunity to have my contribution in developing graph operations for TCL is very exciting. * - what I would like to do is to provide for TCL wide set of graph operations, so programmers could use them without getting into details of implementation. * - I think that it would make TCL attractive language from another point of view * - Graph algorithms are widely used in many subjects, e.g. computer networks, bioinformatics, system modelling and many others. **DETAILED DESCRIPTION** What I want to do is extending existing struct::graph and struct::graph::op with wide set of new functionality. So here is the list with some explanations and examples of usage: '''Algorithms:''' * '''1. Bellman-Ford Algorithm – searching paths with one source.''' * '''Why?''' * Basic algorithm for this problem Dijkstra, which is already implemented doesn’t work with non-negative weights on edges. * Hence, it’s time complexity is O(V*E). * '''Usage:''' * Distance-vector Routing protocols in computer networks use it – for example RIP. * '''2. Searching shortests paths between all pairs of vertices.''' * - Johnson’s Algorithm * - Floyd-Warshall Algorithm * - Matrix multiplication method * '''Why?''' * Very common problem. For example Johnson’s algorithm using Dijkstra’s and Bellman-Ford’s algorithms - asympthotic worktime is O(n2logn+n*m), * where n is amount of vertices and m amount of edges. * '''Usage:''' * For example in scheduling, computer networks and a lot more. * '''3.Minimal Diameter Spanning tree with BFS.''' * '''Why?''' * Give nice extension for spanning tree problem. * '''4.Flow network algorithms:''' * '''Max flow:''' * - Fulkerson-Ford Algorithm * - Edmonds-Karp Algorithm: the upgraded version of Fulkerson-Ford * - Dinic + Malhotra, Kumar and Maheshwari Algorithm: combining those two solutions gives us as well max flow of the flow network with O(n3). * '''Min flow:''' * - Busacker and Gowen. * '''Why?''' * All algorithms gives us solution for flow network problems with nice complexity consideration. * '''Usage:''' * Extremely useful in computer networks – throughputs, net construction. * '''5. Max Matching:''' * - Edmonds Algorithm * Important problem, very useful and there is even saved space in struct::graph::op for it:) '''Approximation Algorithms:''' * '''1. Travelling salesman problem''' * - Metric variation: * - 2-approximation algorithm * - 3/2-approximation algorithm (Christofides) * '''Why?''' * Travelling salesman is very common problem widely used in many areas so I consider it as a “must-have” solution. * '''Heuristics of local searching :''' * - 2-approximation algorithm * - generalization to 3-approximation algorithm * '''Why?''' * In practice 3-approximation algorithm is much better than 2-approximation version, however if you need better approximation ratio you can use the * 2-app version. So, both implementations are needed, depends of circumstances. Further algorithms, like 4-approximation, give very small boost in * comparison to 3-approximation, so they are not profitable. * '''Usage:''' * For example optimizing solutions for traveling salesman problem. * '''2. Minimum Degree Spanning Tree '''– extension for spanning tree problem. It gives us A<=2*OPT + log2n + 1, where A is our solution and OPT is * optimal value. * '''3. Steiner Problem''' * - 2-approximation with minimal spanning tree. * - Generalization to Steiner Forest -> 2-approximation algorithm * - Generalization to Steiner Net -> 2-approximation algorithm * '''Usage:''' * Solving problem of projecting durable network, minimal network, a lot of usage cases in bioinformatics, e.g. reading the history of * evolution. Moreover, it reduces to metric version without any lose in approximation. * '''4. MAX-CUT ''' * - 2-approximation algorithm. * Problem concerning cutting the graph into two parts to assure that amount of edges connecting both parts is as big as possible. * '''5. Metric k-center.''' * - 2-approximation algorithm * - Weighted variation – 3-approximation algorithm * '''Usage:''' * for example consider such situation: for the certain set of the cities and distances between each pair of the cities, choose k cities where * we build for example shopping centres. What we want is to minimalize the largest distance between any city and closest shopping centre. * Weighted variation will consider dependence of cost of building a shopping centre and it’s localization. * '''6.Graph coloring.''' * '''Edge coloring:''' * - 2-approximation greedy algorithm. * Very big part of graph theory, also used in many areas. So in my opinion it’s vital to add some solutions for it. This subject is so big that * it could have created library just for itself, so I consider some basic solutions here for now. * '''7.Vertices cover.''' * - 2-approximation algorithm * '''Other optional issues:''' * - shorests paths implementation for weighted, directed, acyclic graphs ( quicker than Dijkstra and Bellman-Ford) * - some extensions for connected components, like strong components. * - Kolmogorov Max Flow * - Planar Graphs Algorithms ( a lot can be done here ) * - More issues concerning Graph Coloring * - Some mechanisms useful fot graph generating (e.g. graph sequences). * - more "cover problems" implementations Above selection was created on my personal beliefs what will be important to add and also after examining solutions in graph libraries from other languages. Of course despite knowing how to implement those algorithms, important matter is to make it work with existing solutions. So preparing to this project I checked all the code of existing solutions to know what and how is implemented for now and to plan how I will have to link my solutions to existing code. Mainly I am going to add functions to struct::graph::op cause it’s main file enabling access to graph operations. I would like to add new data structure to operate on graphs – adjacency list. There currently exist struct::graph::op::toAdjacencyMatrix, so I would like to create struct::graph::op::toAdjacencyList. For some algorithms it is more suitable to operate on Adjacency List so I think it will be desired addition. With adding each new functionality naturally links creating proper test cases, so I will create those to show that those solutions really works. For approximation algorithms I know their Tight Examples which set their approximation ratio, so those tests will also be prepared. Each function should also have some man and description, so that will be also provided. **TIMELINE** * I think the best way to realise above plans is to split each of them in 3 consecutivily done parts: * - implementing * - creating test cases/ checking if it work properly (if not back to first step) * - writing some documentation/manual/example of usage. %| '''Week 1''' | May 24 - May 30 | Status |% &| | Bellman-Ford Algorithm | Done. Reviewed. |& &| | Johnson's Algorithm | Done. Reviewed. |& %| '''Week 2''' | May 31 - Jun 6 | Status |% &| | Floyd-Warshall Algorithm | Done. Reviewed. |& &| | Matrix Muliplication Method | Dropped in favour of graph coloring methods |& &| | Adjacency List | Done. Reviewed. Revised. Reviewed. |& %| '''Week 3''' | Jun 7 - Jun 13 | Status |% &| | Metric travelling salesman: 2-approximation | Done. Reviewed. Revised. Reviewed. |& &| | Metric travelling salesman: Christofides algorithm | Done, Reviewed. Revised. Reviewed. |& &| | MAX-CUT | Done. Reviewed. Revised. Reviewed. |& %| '''Week 4''' | Jun 14 - Jun 20 | Status |% &| | Weighted metric k-center | Done. Reviewed. In revision. |& &| | Unweighted metric k-center | Done. Reviewed. |& &| | Vertices Cover | Done. Reviewed. |& %| '''Week 5''' | Jun 21 - Jun 27 | Status |% &| | Fulkerson-Ford Algorithm | First review. |& &| | Edmonds-Karp Algorithm | Done. Reviewing. |& %| '''Week 6''' | Jun 28 - Jul 4 | Status |% &| | Busacker and Gowen | Done. Reviewing. | Currently being worked on...|& &| | Spanning Tree problems | |& %| '''Week 7''' | Jul 5 - Jul 11 | Status | << Current week| Mid-Term Evaluation (Jul 6 - 14)|% &| | Dinic algorithm | | << Current week|& &| | Malhotra,Kumar and Maheshwari algorithm | | << Current week|& %| '''Week 8''' | Jul 12 - 18 | Status |% &| | Heuristics of local searching | |& &| | 2-approximation algorithm | |& &| | 3-approximation algorithm | |& %| '''Week 9''' | Jul 19 - Jul 25 | Status |% &| | Steiner Problems: 2-approximation algorithm | |& &| | Steiner Problems: Steiner Forest | |& &| | Steiner Problems: Steiner Tree | |& &| | Steiner Problems: Max Matching | |& &| | Finishing undone documentation work | |& %| '''Week 10''' | Jul 26 - Aug 2 | Status |% %| '''Week 11''' | Aug 2 - Aug 8 | Status |% %| '''Week 12''' | Aug 9 - Aug 15 | Status | Soft stop Aug 10 |% %| '''Week 13''' | Aug 16 - Aug 17 | Status | Hard stop Aug 17 |% I would also note that I am open to any suggestions and if you would see any other algorithms, problem solutions or functionality likely to be added, fell free to note them. For now I think my project idea is clear and other possible extensions can be set at the next phase of GSoC. About my time availibility: after I end this semester I'm free and totally focused on GSoC project so it shouldn't be a concern. Best Regards, Michał Antoniewski ---- **Discussion/Comments** ---- !!!!!! %| [Category Graph theory] |% !!!!!!