Graph Manipulations

This is one of the GSoC 2009 Projects .

For the current code see http://code.assembla.com/graphmanipulations/subversion/nodes

Further see our Timeline for the planned work and its status.

Discussion, code reviews and the like are done over on the Tcllib Development Mailing List , see also the Archives .

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 modeling 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 shortest 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 – throughput, 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:
• - shortests 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 for 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 realize 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.

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 availability: 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