'''Title:''' Graph Manipulations '''Student:''' Michał Antoniewski '''Abstract:''' Hi, I'm Michael and I'm 4th year undergraduate in Gdansk University of Technology at faculty of Electronics, Telecommunications and Informatics (ETI) in Poland. What I am going to do is to extend existing solutions with wide set of functions/algorithms to make TCL well-equipped with Graph Operations and to become attractive language from another point of view. '''Content:''' '''SHORT INTRODUCTION''' '''Name:''' Michael '''Surname:''' Antoniewski '''Age:''' 22 '''University:''' I'm 4th year undergraduate in Gdansk University of Technology at faculty of Electronics, Telecommunications and Informatics (ETI) in Poland '''Main Department:''' Department of Algorithms and System Modelling '''Supplementary Department:''' Department of Computer Communications. '''Skills ''' '''GRAPH THEORY AND SIMILAR''' good, wide knowledge about graph theory, artificial intelligence and generally mathematical aspects of informatics. recently bioinformatics too. a lot of problems/algorithms known not only theoretically but also implemented good knowledge about computational complexity, useful data structures. besides programming, my common area of interest. '''TCL ''' not a lot of experience in programming in TCL example of usage: creating simulations of Wireless Networks and testing/comparing capabilities of Wireless Routing Protocols like DSDV and others I've already arranged creating projects during this semester in Tcl, so before June I will surely be ready to program bigger amounts of code in Tcl. '''OTHER LANGUAGES''' '''C/C++''' good knowledge most of algorithm implementations done in C a lot of problems solved at contests: www.spoj.pl (if needed I can attach some code) also done other projects, e.g. B-Tree implementation. as an example I placed some code at http://sites.google.com/site/antoniewskim/ '''WIN32 API ''' used a lot long time ago…:) work example: many games like e.g. chess with graphical interface - enabling playing by net for 2 players gave me good basic for moving into .NET with good understanding mechanisms it works on currently: C#, WPF, WCF. example project in .NET: system of work-time controlling with usage of contactless cards and readers connected by COM ports. '''JAVA''' example project: Application for testing purposes – enables examining people by browser and solving tests created by Admins. It has 2 independent parts: Admin application for creating tests/users and generally managing database, written in J2SE. Web part written in J2EE for clients to solve availible (for them) tests and see scores. '''PYTHON ''' fair knowledge example: Currently, I’m working on graphical application (using QT) with knowledge base. It concerns combinatorial games on graphs and NIM games and enables confronting AI opponents. '''COMPUTER NETWORKS''' nice knowledge about IEEE standards, designing networks, configuring network protocols algorithms used in computer networks gave me nice experience in working with large documentations '''PROJECT''' '''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. Month 1, Week 1 Bellman-Ford Algorithm Johnson's Algorithm Week 2 Floyd-Warshall Algorithm Matrix Muliplication Method Adjacency List Week 3 Metric travelling salesman: 2-approximation + Christofides algorithm MAX-CUT Week 4 Weighted and unweighted metric k-center Vertices Cover Month 2, Week 1 Fulkerson-Ford Algorithm Edmonds-Karp Algorithm Week 2 Busacker and Gowen Spanning Tree problems Week 3 Dinic algorithm Malhotra,Kumar and Maheshwari algorithm Week 4 Heuristics of local searching 2-approximation algorithm 3-approximation algorithm Month 3, till the end Steiner Problems: 2-approximation algorithm Steiner Forest Steiner Tree Max Matching Finishing undone documentation work It's the timeline of implementation period. 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 ---- !!!!!! %| enter categories here |% !!!!!!