Have a look at smallhints.seasidehosting.st there's my forcedirected graphalgorithm working in realtime. Graphdata is stored at dabbleDB. Sorry there's no user interface, yet, but if there's a need, I could make a simple one. The graph is based in Avi's seaside-async package, but I'll port it using SUUpdater. The soothnes of the animation depends on yout internetconnecten, for every image/edge is calculated and drawed in realtime on the squeak server image. Let me know if you need any information on this. Cheers Sebasian
October 12, 2008 7:02 pm
Anonymous said...
See the list of graph packages on squeakmap, mentioned at http://wiki.squeak.org/squeak/329.
One of them is a port of Graphs.st goodie by Mario Wolczko.
-- Matthias
October 15, 2008 5:22 pm
Anonymous said...
And there is http://squeak.pbwiki.com/Graphs. -- Matthias
October 15, 2008 5:23 pm
Anonymous said...
Hey Julian! This is Niko. Remember me from ESUG?
I'd be really interested to see some graph algorithms package. These packages, if they exist, aren't very popular here at my university. I'm working on my thesis in the departmen for theoretical computer science and graph theory, and I never see anyone use packages. They hardly ever try out things in practice and if they do, they build everything from scratch.
Mathematica comes with rather poor support for graph algorithms and many interesting problems haven't even got wikipedia articles.
as I'm still writing my thesis, i'd love to try out some stuff frequently without having to implement the algorithms myself every time. just today i was hoping for an algorithm to solve CLOSEST STRING.
then again, it's not enough to just have graph algorithms at hand, for this to be useful for playing around, id'd also need a good set of methods to create instances; good permutation support would definitely help.
Entrepreneurs and innovators are on the rise in this digital age. The one thing that gives them the edge is communication which is why they use the latest trending channels like mass texting service to exchange valuable information with prospects.
I'm not sure what happened. I don't remember finding graph theory particularly interesting in university but over the past month I've had two occasions of simple pleasure while figuring out (pretty basic) directed graph algorithms.
The first was at our last Seaside sprint, where Lukas and I were working out how to modify his Package Dependency tool to mark cycles on Seaside 2.9's dependency graph in red, so we could immediately spot problems. It's not like there aren't already algorithms for this but it was fun just trying to work one out for ourselves.
The other was this Tuesday. I woke up wondering whether I couldn't make the graph a little easier to look at by removing direct edges when we have another indirect path to the same node. In other words, if package A depends on B and package B depends on C, we could omit a dependency from package A to package C because that dependency is already implied through transitivity anyway. I pictured this as the opposite of a Transitive Closure.
It turns out that this operation is called a Transitive Reduction and there are algorithms for it but they don't seem to be very well documented online. I ended up just working something out myself using depth-first searching and path-length tracking to prune shorter paths to objects. I don't know if there's a faster way but it doesn't really need to be that fast in this context anyway. I currently abort if the graph is cyclic but I'm pretty sure you could do something like pick an arbitrary root for the cycle, treat everything within the cycle as being distance zero from each other, and you would get a reasonable (albeit non-deterministic) answer. In our case, we don't want cycles in our graph so, realistically, you would fix the cycle and rerun the dependency checker anyway. Here's the result.
This got me thinking... is there a good implementation of graph theory algorithms in Smalltalk? I would love to be able to create a Graph of my model objects (maybe implement #edges on each one or something) and then call: "graph isCyclic", "graph transitiveReduction", or "graph topologicalSortFrom: aNode". So many things can map to directed graphs and, if you could work out domain-specific solutions by really easily layering generic graphing algorithms, that would be really cool.
Sometimes solving simple problems with definable right answers is so satisfying.
"Graph Theory"
7 Comments -
Hi Julian!
Have a look at smallhints.seasidehosting.st
there's my forcedirected graphalgorithm working in realtime. Graphdata is stored at dabbleDB. Sorry there's no user interface, yet, but if there's a need, I could make a simple one. The graph is based in Avi's seaside-async package, but I'll port it using SUUpdater. The soothnes of the animation depends on yout internetconnecten, for every image/edge is calculated and drawed in realtime on the squeak server image. Let me know if you need any information on this.
Cheers Sebasian
October 12, 2008 7:02 pm
See the list of graph packages on squeakmap, mentioned at http://wiki.squeak.org/squeak/329.
One of them is a port of Graphs.st goodie by Mario Wolczko.
-- Matthias
October 15, 2008 5:22 pm
And there is http://squeak.pbwiki.com/Graphs.
-- Matthias
October 15, 2008 5:23 pm
Hey Julian! This is Niko. Remember me from ESUG?
I'd be really interested to see some graph algorithms package. These packages, if they exist, aren't very popular here at my university. I'm working on my thesis in the departmen for theoretical computer science and graph theory, and I never see anyone use packages. They hardly ever try out things in practice and if they do, they build everything from scratch.
Mathematica comes with rather poor support for graph algorithms and many interesting problems haven't even got wikipedia articles.
as I'm still writing my thesis, i'd love to try out some stuff frequently without having to implement the algorithms myself every time. just today i was hoping for an algorithm to solve CLOSEST STRING.
then again, it's not enough to just have graph algorithms at hand, for this to be useful for playing around, id'd also need a good set of methods to create instances; good permutation support would definitely help.
niko
October 26, 2008 7:29 pm
Entrepreneurs and innovators are on the rise in this digital age. The one thing that gives them the edge is communication which is why they use the latest trending channels like mass texting service to exchange valuable information with prospects.
December 26, 2018 8:38 am
because our prices are competitive not accept the final, because we are cheaper spray companies in insect control companies guide insects in Taif.شركة مكافحة حشرات بالرياض
شركة رش مبيدات بالرياض
افضل شركة مكافحة حشرات
شركة رش مبيدات بالمجمعة
June 15, 2019 9:27 pm
As I read the blog I felt a tug on the heartstrings. it exhibits how much effort has been put into this.
Final Year Project Domains for CSE
Spring Training in Chennai
Project Centers in Chennai for CSE
Spring Framework Corporate TRaining
November 24, 2019 5:08 pm