graph theoryWell, this is a pretty basic tool for playing around with graphs. Just click the “New Graph” button for a window, then shift-click to set vertices anywhere you want. To set an edge between two vertices, ctrl-click on a vertex, which should get an odd blue halo. Now ctrl-click on the vertex you want an edge to. An edge should appear. To delete a vertex, double-right-click on it, and to delete an edge, single-right-click on the box at the edges midpoint. I believe for Mac users holding down the Apple key while clicking will give you the same result, although I’m not sure, since I’m not lucky enough to have a Mac on the desk here, so please Email me with the key that works. To select several vertices or edges (for doing a shortest-path test, getting info on a bunch of ’em at once, etc.) use shift-ctrl-click. You will note more advanced tools,such as graph coloring, cloning, completing, and many other choices, some of which do not begin with the letter ‘c’, available in the oh-so-professional-looking menu bar.

GraphTool version 1.0b is the updated version of my now very old ‘Graphs’ program, which is located here, and although it is actually less functional now than its ancestor is, that will soon change. I hope to, before long, offer GraphTool as an API for those studying graphs, so that anyone who speaks java and who takes the time to understand the (very small) GraphTool API could write a ‘plugin’ to do whatever they were interested in. Network flow analysis, for example. Or some graph matrix operations. Whatever.

GraphTool is written in java. This does not automatically mean that it is an applet, which it is, in fact, not. While the old version of it was an applet, I made the decision that saving files was important enough to warrant moving away from applets and towards actual applications. The fact that there are no java2-compliant browsers, besides maybe Mozilla, made that decision easier – my target audience would have to download a java2 virtual machine anyway. I may sometime in the future make an applet version.

Do you have a PowerMac? Does this not work? Well, lemme tell you, I tried to make it work, Lord knows I tried. But seeing as how this is really not a problem with the program, but rather with Netscape 3.0 (no, really, it is!), I decline to spend any more time on it, especially when all you hafta do to run it is get the MRJ from Apple. See here for more info on it. It works well, if somewhat clumsily, and, frankly, I really don’t think anyone is actually using/desiring to use this stuff. If I’m wrong, please let me know. I suppose if enough people want/need it, I can resume my efforts. So there. Nyaah.

Other Late-Breaking News

The Line Graph generator actually works now.

As it turned out, the coloring algorithm I presented earlier was incorrect. The new algorithm is:

Select a vertex. Check to see if it is the same color as a connecting vertex. If so, increment the chosen vertexes color, then check all the vertices it’s connected to again, continuing to increment when a conflicting color is found.

Select another vertex, and do the same procedure until all vertices have been completely checked.

At this point I should mention that the program doesn’t work reliably if you color the graph, then remove vertices and/or edges then color it again, since the algorithm doesn’t know how to decrement colors, so it’ll add unnecesary colors sometimes.

You may notice a new menu option “Color Graph by Build Method” – what, you ask, is that? Well, it’s another coloring algorithm. Basically, you take the graph and erase all but one vertex. Then you add one in, along with the edge to the other, if one exists. Then, if the color of the one you just added is the same as the first one, you select a color for the new one that doesn’t cause a conflict. Then add a third vertex with the arttendant edges, and repeat the color adjustment. This seems to work pretty well most of the time (certainly better than the other algo), and when it screws up, the colors are much easier to spot. For me, anyway. I’m color-blind, so the other algorithms colors are tough on me. For a long time I was convinced the first algo was infallible because I couldn’t see the difference between a dark brownish and a dark red. Ack.

DISCLAIMER: Due to an alarming number of parents, schoolchildren and primary-school teachers apparently wasting vast amounts of time trying to make this produce a bar or pie graph, I would like to take this opportunity to say: “Hi! This ain’t about that kind of graph! This is a tool for visualizing Graph Theory problems, which are studies of relations between sets. If you need to make a bar graph of something, sorry, but you’ve ended up in the wrong place”.