Title: Graph Manipulations
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
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
OTHER LANGUAGES
C/C++
WIN32 API
JAVA
PYTHON
COMPUTER NETWORKS
PROJECT
WHY GRAPH MANIPULATIONS?
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.
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:
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 |
---|