graph theory

Got a LiveCode personal license? Are you a beginner, hobbyist or educator that's new to LiveCode? This forum is the place to go for help getting started. Welcome!

Moderators: Klaus, FourthWorld, heatherlaine, kevinmiller

Post Reply
mattmaier
Posts: 109
Joined: Fri Apr 19, 2013 2:49 am

graph theory

Post by mattmaier » Mon Sep 29, 2014 12:46 am

I've got a network of nodes and links that I want to work with. It's turning out to be hard to search for any previous work anyone might have done on the subject because words like "graph" and "network" and whatnot are so popular in other subjects.

Has anyone seen anything in livecode where someone worked with a bunch of vertices all connected together? Like, for the traveling salesman problem, once you have the list of nodes and links you'd walk the graph to find the shortest route connecting all nodes. Stuff like that.

Simon
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 3901
Joined: Sat Mar 24, 2007 2:54 am
Location: Palo Alto

Re: graph theory

Post by Simon » Mon Sep 29, 2014 2:15 am

Hi mattmaier,
Are you asking about an A* algorithm?
http://lessons.runrev.com/s/lessons/m/4 ... e-Using-A-

Simon
I used to be a newbie but then I learned how to spell teh correctly and now I'm a noob!

mattmaier
Posts: 109
Joined: Fri Apr 19, 2013 2:49 am

Re: graph theory

Post by mattmaier » Mon Sep 29, 2014 4:35 am

I'm not really sure. Maybe? I think I can follow it enough to see that it's trying to find the shortest path between a beginning state and an end state, which seems like it must be walking a graph (each unique board being a state and the move transitioning between boards being a link), but I don't see a data structure for the graph.

What I have is a data structure and at the moment I'm just trying to edit and display it visually. I know that I'll have to get into search algorithms eventually, but I'm not there yet.

I'm looking for something more like this http://reference.wolfram.com/language/t ... ction.html
Are you aware of any projects that have already been done in livecode that work with the data structure for a network, or that figure out how to generate coordinates for displaying an arbitrary network in an understandable way?

[-hh]
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 2262
Joined: Thu Feb 28, 2013 11:52 pm
Location: Göttingen, DE

Re: graph theory

Post by [-hh] » Mon Sep 29, 2014 8:42 am

Currently the RaspberryPi OS "Raspbian" has a pretty much complete Mathematica10/Wolfram version included (free). So you could buy a Raspi and not only draw (postscript/pdf) NetGraphs with it but also solve a lot of optimization and combinatoric problems using algorithms from specialists.
This all is on a Raspi@800 Mhz often faster and more reliable in results than self-made LC algorithms on the fastest Mac/PC, because LC doesn't even has bigNums implemented.

Also, I hope so, we'll have soon a stable version of LC available on the Raspi ...
shiftLock happens

Post Reply

Return to “Getting Started with LiveCode - Complete Beginners”