logicchains / lpathbench Goto Github PK

The writeup describes this problem as NP-complete, but it cannot be since it is not a decision problem. It is in fact NP-Hard. The introduction on Wikipedia to the problem covers this.

There's a much clear version of the Haskell implementation at http://lpaste.net/121012.

See the discussion at http://haskell.1045720.n5.nabble.com/Haskell-implementation-of-longest-path-algorithm-td5765786.html.

I thought I'd write a C implementation to compare to the C++. I decided to start blind rather than looking at the other implementations. Everything I did was taking much longer than your benchmarks, and I was consistently getting a higher number than your code.

Eventually I started printing intermediate values, and I noticed that your answer matched the number I got starting from starting from node 0, but I had been looking for the "longest node in the graph" as the text said. Since I was looping over every start point in keeping with the brute force theme, my runtimes were about 15x what I thought I'd achieve. Finally I looked at the source for some other implementations, and they seemed to be checking only from starts at node 0.

Is this correct, or am I doing something stupid? If correct, perhaps you could change the writeup to reflect this?

I offer a version written in C for inclusion in the benchmark:
https://gist.github.com/nkurz/5e49ba0ddb04e23de03f

I've only tested on Haswell under Linux, but results are good when compiled with gcc-4.8 -O2:
// 8981 LANGUAGE C 623
// 8981 LANGUAGE C++/clang 734
// 8981 LANGUAGE C++/gcc 755

I have tested, but I think the implementation should continue to perform well with larger graph sizes.

The first version of the page I saw had a (slightly disappointing wrt. x86-64) result for OCaml-ARM which I don't see in the writeup anymore. Is it a simple omission or are there technical problems that prevents the results to be recomputed?

Hello, i need to find the longest path in a graph. I've found your code and i'm trying to implement something like it on my own. But i can't make it print what is the longest path. It only prints the weight.
Can you show me in your python code how you could print the longest path nodes?

rustc rs.rs -C opt-level=3 -C no-stack-check
rs.rs:24:49: 24:50 error: unexpected token: `]`
rs.rs:24             unsafe { mem::transmute(self.routes[]) }

BTW, I had to change --opt-level=3 to -C opt-level=3 in makefile

I'm not really sure if I'm missing something, but why are you using case to pattern match on a boolean in the Haskell source, when all of those

case isVisited of
  True -> ...
  False -> ...

could be replaced by simple if isVisited then ... else ...?

Maybe? :P

I'm looking at D's results on x86-64 and how they varied today between the runs (1894 1799 2214 1959) without (as far as I could tell) D's code or command line changing between these specific commits.

It might be beneficial to take either the best out of 10 runs, or the average of 10 runs to smooth out the differences and get more consistent results.

Are you interested in adding a Factor (http://factorcode.org/) implementation for the benchmark? I wrote one here: https://github.com/bjourne/playground-factor/blob/master/lpath/lpath.factor