Introduction
OK, the problem is, given a strongly connected (directed) graph, find a strongly connected spanning subgraph (SCSS) with the minimum size (i.e., the number of edges). This problem is NP-hard (can be seen by induction from the Hamilton Cycle). No efficient algorithm is known to compute a minimum solution exactly.
In paper "A nearly linear time 5/3-approximation of the minimum strongly connected spanning subgraph", we have found an almost linear time algorithm that can find an SCSS with edges at most 5/3 times of the minimum (it is linear time in real life!). I decided to implement the algorithm, which is Project findSCSS. Here comes an implement of JAVA applet (application), which took me three weeks to release the first version (0.1). And after a two-days work, I proudly improved it to version 0.2.
New 2002/09/12. The algorithm can be further improved to run in linear time. Due to the overhead of implementation, however, we still use the old one.
Feature
- Platform independent: it is written in JAVA. You only need a browser with JAVA2 support.
- Simple: draw a graph and get the SCSS. I tried to make the program as simple as possible.
- Fast: I have tested (drawn) a graph with 51 nodes and 150 edges, and it returns in less than 1 second (see screenshots draw graph, find SCSS).
- Other: you can repeatedly replace the graph by the computed SCSS and compute again. This often yields better solutions.
ToDo
- Faster implement. Now I use variable array to hold the graph, which is convenient but slower than a static array.
- Load/Save function, etc.
Try it
Try it and please report any problem or suggestion to me. The souce code is also available, contact me too.
version 0.4
This is the inline version (i.e., the applet will appear in the browser area. If you want a more flexible one, use version 0.5 please.
version 0.5
Begin from version 0.5, the calculation frame is a pop-up windows. Thus you can get the most flexibility since you can resize it (which is impossible for an inline version such as version 0.4).
what't new
- 2003/01/24, version 0.5: now a pop-up windows is used to increase flexibility.
- 2002/09/12, version 0.4: better drawing method. Now there is no flicker when drawing. SWING is great.
- 2002/07/22, version 0.3: when the graph is not strongly connected, the program can now give the user an advice for adding an edge. There are also some bug-fixes which may give wrong result if the start node of DFS is not 0.