Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw
 
PerlMonks  

Travelling Salesman

by gangulphus (Initiate)
on May 08, 2012 at 15:43 UTC ( [id://969487]=perlquestion: print w/replies, xml ) Need Help??

gangulphus has asked for the wisdom of the Perl Monks concerning the following question:

Dear Perl Monks

I've developed a brute-force solution for a local transfer company which works fine BUT it uses a pure perl encoded version of the Dijkstra algorithm. This works fine, but proves to be the main consumer of CPU time (according to the superb NYTProf profiler)

What I'd like to try is Boost::Graph, but I just cant get it to compile under Windows (Vista Ultimate) either under ActiveState or Strawberry Perl.

So, my question is, if any of you have successfully compiled Boost::Graph under windows and how.

Many Thanks Gangulphus

Replies are listed 'Best First'.
Re: Travelling Salesman
by davido (Cardinal) on May 08, 2012 at 16:56 UTC

    Boost::Graph looks to be fairly badly broken at the moment. The original author made three CPAN releases spread over a six month period in 2006. I would find it difficult to write Perl XS extension code coupling C++ with the Boost libraries, effectively debugged, with all the smoke test kinks worked out over the course of three releases in 2006. The condition of available tools to help in writing C++ extension code for Perl in 2006 was not too good. Looking at the CPAN testers matrix corroborates the theory that the module hasn't been adequately refined for as ambitious a project as it is.

    On my own Windows and Linux systems (one with Boost installed, one without) I get the same failure points. And they seem significant: incorrect number of parameters being passed to functions, etc. Those sorts of things almost lead me to believe that perhaps the Boost libraries, or the way modern C++ compilers work has changed enough since 2006 that the C++ world has moved on leaving the CPAN Boost::Graph module behind. I would need to study the code thoroughly to really understand what is wrong with it... and I'm not interested enough to do so.

    If you're committed to using Boost's graph classes with Perl you might have to do it yourself. Inline::CPP could be used to write your Perl compatible wrappers for the C++ library. Inline::CPP doesn't know how to pass parameters into template classes, so your wrappers would have to encapsulate the existing library such that templated classes aren't exposed directly to Perl. That precludes the use of Inline::CPP's "AUTOWRAP" functionality, so the work would be significant.

    You didn't mention what graph implementation you're currently using. If you're not committed to Boost you could shop around for other implementations. The pure Perl implementations that I would most trust are those ones on CPAN with Jarkko Hietaniemi's name on them: Graph, and its siblings. They're well tested, well designed, and he even co-authored the book Mastering Algorithms with Perl, which devotes a lot of its pages to graphs. The book is a dozen years old, and still the best Perl resource for algorithm theory. ...and his Graph modules are still being maintained. This review of Boost::Graph seems to be an endorsement for Jarkko's Graph module, at least with respect to memory and computational efficiency.

    Since I don't, on first search, find an XS module implementing graphs, if you really need the speed of C or C++, you're probably going to either have to use Inline::CPP to write your own Boost wrappers for the existing Boost graph library, or you are going to need to implement your own (possibly using Inline::C, or Inline::CPP, or some other XS helper). One strategy for implementation would be to profile Jarkko's Graph module, and rewrite only those portions where you find bottlenecks using Inline::C or Inline::CPP. That would minimize the amount of extension code you would have to write, and would probably be the easiest solution since your extension code could follow the existing Perlish implementation.

    Update: As I look over Graph, I think that putting it to work at your specific use-case, and then profiling will probably shed some light on where you might need to focus optimization efforts. It's a big enough module (or set of modules) that you wouldn't want to take on the whole thing, but by profiling your particular application as it uses Graph, you can certainly narrow down the problem areas. With a little luck you will find yourself staring at one subroutine that could be re-implemented in C. That's probably optimistic.

    The Inline::CPP approach may still be worth considering; Implement a C++ class that is composed of a Boost graph, and that exposes to Perl a minimal interface for your program to call upon.


    Dave

      Thanks for your detailed review of Boost::Graph. I think you are correct and I have abandoned any attempt to use it.
Re: Travelling Salesman
by zwon (Abbot) on May 08, 2012 at 16:37 UTC

    It would help if you posted the error message you got. Looking into Directed/Makefile.PL I see:

    use 5.008; use ExtUtils::MakeMaker; $CC = 'g++ -O'; ...
    I don't really familiar with Win, but I suspect that you should replace g++ with the name of your C++ compiler.
Re: Travelling Salesman
by JavaFan (Canon) on May 08, 2012 at 18:07 UTC
    I've developed a brute-force solution for a local transfer company which works fine BUT it uses a pure perl encoded version of the Dijkstra algorithm. This works fine, but proves to be the main consumer of CPU time (according to the superb NYTProf profiler)
    You solved the travelling salesman problem by using Dijkstra's algorithm???

    Seriously man, you shouldn't worry about your CPU time, you should worry about how to contact the Clay Mathematics Institute and cash your million dollar reward.

    You've solved the top problem of the Millennium problems (P =?= NP) as defined by the Clay Mathematics Institute, each of them having a million dollar reward for solving them.

      Humor aside, I think his assumption is that open shortest path first(To wherever salesman wants to go) works for most salesmen. That might not be completely wrong either! This may not solve the 'Traveling salesman problem' but it does solve the problems of many traveling salesmen.
        But, but, but Dijkstra's algorithm solves a completely different task: find the shortest route between two points. And while you can construct graphs where there is a pair of points where the shortest path between them actually visits all other points, that's situation most traveling salesmen won't find themselves in. (Except maybe in Chili)

        Either the OP is solving a different problem than the travelling salesman, or he's using something else than Dijkstra's.

      Alas, I won't be claiming the big prize! I think you missed the preamble to the question, which makes it clear that in the solution to the practical problem I am facing I am using a BRUTE FORCE approach.

      As I'm sure you're aware it is possible to solve the problem by trying every possible permutation of locations to be visited, ONLY if the number of locations is small.

      In my case I am dealing with a maximum of 8 as the people I'm working with run 9 seater mini-buses (driver & 8 passengers).

      So the completely mathematically inelegant approach I'm taking is simply to calculate all possible permutations of the drop off/pick-up points (max 8) and then use the Dijkstzra algorithm to calculate the distance between each successive pair of drop off/pick-up locations and sum these to reach a total distance for each permutation.

      In this way I am guaranteed to find the shortest path.

      The people I'm working with run 20 mini-buses, which can theoretically do 6 trips a day. If each of them were to carry 8 passengers each being picked up/dropped off a a different location, the maximum calculation time on my aging twin core 32bit PC is about 15 minutes.

      This is much quicker than the task can be done manually and of course relies on the person doing it to have an intimate knowledge of the local area.

      In reality, this extreme case is never likely to occur, but I would like to reduce the time the script spends doing the Dijkstra calculations.

Re: Travelling Salesman
by tobyink (Canon) on May 08, 2012 at 15:47 UTC

    You want brute force? Chuck Norris can brute force the travelling salesman problem in O(log n) time.

    perl -E'sub Monkey::do{say$_,for@_,do{($monkey=[caller(0)]->[3])=~s{::}{ }and$monkey}}"Monkey say"->Monkey::do'
Re: Travelling Salesman
by rg0now (Chaplain) on May 10, 2012 at 20:52 UTC
    I would like to call your attention to Lemon::Graph, which I coded up, and use on a daily basis, as an alternative to Boost::Graph. Lemon::Graph is a Perl wrapper around LEMON, a C++ graph library that is thought to have a much saner interface than Boost Graph and provides useful additions like a built-in linear programming API, etc.

    Here is how a simple Dijkstra run would look like in Lemon::Graph

    use Lemon::Graph; # read graph from file with a cost map encoding arc lengths my $graph = Lemon::GraphReader->new("some_graph.lgf")-> arcMap("cost", my $cost)-> run(); my $source = ... some node ...; my $destination = ... some other node ...; # create a shortest path object my $d = Lemon::Dijkstra->new($graph, $cost); # run Dijkstra from $source $d->run($source); # get the distance to $destination my $dist = $d->dist($destination);
    The bad news is that I have never ever tried to compile Lemon::Graph under Windows, but I see no reason why it shouldn't work. Please, report back if you manage to compile it.
      Thanks for drawing my attention to this. I have download the package and am currently working on trying to compile it.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://969487]
Approved by tobyink
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others meditating upon the Monastery: (1)
As of 2024-03-19 03:50 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found