graph algorithms with GraphViz and agraph
% find . ./bin ./bin/cdt.dll ./bin/graph.dll ./bin/sample.gv ./incomings.c ./Makefile %
These are the files from this hello world project. The dlls are from the GraphViz installation directory (from bin/). The task is to collect incoming nodes for a given other node (the ones that have directed edges into the selected one). The good thing in this is that you don’t have to design you own graph markup language and your own parser (NIH). Instead you can use the well defined and supported dot language from GraphViz. I’ve used MingW and MSYS as development environment.
% cat -A Makefile
all:^Iincomings.exe$
$
incomings.exe:^Iincomings.o$
^Ig++ $< -O2 -o bin/$@ `PKG_CONFIG_PATH=c:/Graphviz2.24/lib/pkgconfig/ pkg-confi
g --libs libgvc`$
$
incomings.o:^Iincomings.c$
^Ig++ $< -O2 -c -o $@ `PKG_CONFIG_PATH=c:/Graphviz2.24/lib/pkgconfig/ pkg-config
--cflags libgvc`$
$
clean:$
^Irm -rf incomings.o bin/incomings.exe$
$
test:^Iall$
^Ibin/incomings.exe bin/sample.gv a$
% cat incomings.c
#include<gvc.h>
char* gv_gets(char *buf, int n, FILE* fp)
{
return fgets(buf,n,fp);
}
int main (int argc, char **argv)
{
Agraph_t *g;
Agnode_t *n;
Agedge_t *e;
FILE *fp;
if(argc > 2)
fp=fopen(argv[1],"r");
else
fp=stdin;
aginit();
g=agread_usergets(fp,gv_gets);
for(n=agfstnode(g);n;n=agnxtnode(g,n))
if(strcmp(n->name,argv[argc-1])==0)
for(e=agfstin(g,n);e;e=agnxtin(g,e))
printf("%s\n",e->tail->name);
agclose(g);
return 0;
}
% make
g++ incomings.c -O2 -c -o incomings.o `PKG_CONFIG_PATH=c:/Graphviz2.24/lib/pkgco
nfig/ pkg-config --cflags libgvc`
g++ incomings.o -O2 -o bin/incomings.exe `PKG_CONFIG_PATH=c:/Graphviz2.24/lib/pk
gconfig/ pkg-config --libs libgvc`
% cat bin/sample.gv
digraph G
{
b -> a;
c -> a;
d -> a;
e -> a;
f -> a;
a -> foo;
}
% make test
g++ incomings.o -O2 -o bin/incomings.exe `PKG_CONFIG_PATH=c:/Graphviz2.24/lib/pk
gconfig/ pkg-config --libs libgvc`
bin/incomings.exe bin/sample.gv a
b
c
d
e
f
%
granting a loan; simplified
Based on the net present value term, in case of regular $R incomes and rate as discount rate:
years - 1
---------
\
\ R
NPV = ) -------------
/ i
/ / \
--------- | 1 + rate |
i = 0 \ /
Due to identical cash flows this is the sum of a geometric series, so can be rewritten into a closed form:
years
/ \
| 1 |
1 - | -------- |
| 1 + rate |
\ /
NPV = R ---------------------
1
1 - --------
1 + rate
Or identically:
1
1 - --------
1 + rate
R = NPV ---------------------
years
/ \
| 1 |
1 - | -------- |
| 1 + rate |
\ /
In case duration of the loan tends to infinity then the required yearly income converges to:
/ \
| 1 |
NPV | 1 - -------- |
| 1 + rate |
\ /
which is
rate
NPV --------
1 + rate
and this means that there’s no loan of USD NPV regarding rate as discount rate, where the required yearly pay back is less then this number, e.g. (NPV = $1000000, rate = 0.03):
% ./lx86cl Welcome to Clozure Common Lisp Version 1.4-r13119 (LinuxX8632)! ? (defun limit (npv rate) (* npv (/ rate (+ 1 rate)))) LIMIT ? (limit 1000000 0.03) 29126.213 ? (defun r (npv rate years) (* npv (/ (- 1 (/ 1 (+ 1 rate))) (- 1 (expt (/ 1 (+ 1 rate)) years))))) R ? (loop as i from 1 upto 50 collect (r 1000000 0.03 i)) (1000000.0 507389.3 343233.47 261191.42 211994.77 179220.95 155831.47 138307.22 124693.086 113816.05 104929.58 97536.03 91290.83 85947.914 81326.79 77292.09 73740.32 70590.97 67780.47 65257.973 62982.297 60919.8 59042.617 57327.58 55755.207 54309.016 52974.95 51740.992 50596.758 49533.246 48542.637 47618.066 46753.5 45943.64 45183.758 44469.687 43797.676 43164.387 42566.824 42002.29 41468.336 40962.766 40483.58 40028.957 39597.234 39186.906 38796.586 38425.0 38070.984 37733.465) ? (with-open-file (s #P"r.dat" :direction :output :if-exists :supersede) (loop as val in * do (format s "~A~%" val))) NIL ? (quit) % echo set term png \; plot \'r.dat\' with lines | gnuplot > r.png
r.png
rebuild cffi foreign bindings
C:\grault>type lib-foo.c
int getone ()
{
return 1;
}
C:\grault>gcc -shared -o lib-foo.dll lib-foo.c
C:\grault>clisp -q -norc -i ..\.clisprc
;; Loading file ..\.clisprc ...
[1]> (setf *load-verbose* nil)
NIL
[2]> (asdf:oos 'asdf:load-op :cffi :verbose nil)
#<ASDF:LOAD-OP (:VERBOSE NIL) #x19C29B55>
[3]> (cffi:load-foreign-library "lib-foo")
#<CFFI::FOREIGN-LIBRARY #x19CCE065>
[4]> (cffi:defcfun "getone" :int)
GETONE
[5]> (getone)
1
[6]> (ext:saveinitmem "foo.mem" :norc t)
Bytes permanently allocated: 92,512
Bytes currently in use: 3,409,664
Bytes available until next GC: 852,166
3409664 ;
852166 ;
92512 ;
38 ;
20303572 ;
2808018
[7]> (quit)
C:\grault>dir/b
foo.mem
lib-foo.c
lib-foo.dll
C:\grault>clisp -q -M foo.mem
[1]> (getone)
WARNING: FFI::FIND-FOREIGN-FUNCTION: no dynamic object named "getone" in library :DEFAULT
*** - FUNCALL: undefined function NIL
The following restarts are available:
USE-VALUE :R1 Input a value to be used instead of (FDEFINITION 'NIL).
RETRY :R2 Retry
STORE-VALUE :R3 Input a new value for (FDEFINITION 'NIL).
ABORT :R4 Abort main loop
Break 1 [2]> :r4
[3]> (cffi:use-foreign-library "lib-foo")
#<CFFI::FOREIGN-LIBRARY #x19FB66AD>
[4]> (getone)
1
[5]> (quit)
C:\grault>
common lisp GUI-application shipment&delivery on windows
First of all, here’s the lisp I’ve used:
% clisp --version | grep -v ^Machine GNU CLISP 2.48 (2009-07-28) (built on stnt067 [192.168.0.1]) Software: GNU C 3.4.5 (mingw-vista special r3) gcc -mno-cygwin -O2 -W -Wswitch -Wcomment -Wpointer-arith -Wimplicit -Wreturn-ty pe -Wmissing-declarations -Wno-sign-compare -Wno-format-nonliteral -O2 -fexpensi ve-optimizations -falign-functions=4 -D_WIN32 -DUNICODE -DDYNAMIC_FFI -I. -lint l -lreadline -ltermcap -lavcall -lcallback -luser32 -lws2_32 -lole32 -loleaut32 -luuid -liconv -lsigsegv SAFETY=0 HEAPCODES STANDARD_HEAPCODES GENERATIONAL_GC SPVW_BLOCKS SPVW_MIXED TRI VIALMAP_MEMORY libsigsegv 2.6 libiconv 1.11 libreadline 5.2 Features: (READLINE REGEXP SYSCALLS I18N LOOP COMPILER CLOS MOP CLISP ANSI-CL COMMON-LISP LISP=CL INTERPRETER SOCKETS GENERIC-STREAMS LOGICAL-PATHNAMES SCREEN FFI GETTEXT UNICODE BASE-CHAR=CHARACTER PC386 WIN32) C Modules: (clisp i18n syscalls regexp readline) Installation directory: C:\Program Files\clisp-2.48\ User language: ENGLISH %
I have also MingW (5.1.6) and MSYS (1.0.1) installed, Witchs Hat icon downloaded, CLisp dlls copied from the base subdirectory under the installation path. This is the development tree in clean form:
% find . ./bootstrapper.cc ./bootstrapper.rc ./clisp-dlls ./clisp-dlls/libiconv-2.dll ./clisp-dlls/libintl-8.dll ./clisp-dlls/readline5.dll ./Makefile ./message.lisp ./witchs-hat.ico %
Under clisp-dlls, there are the mentioned dlls of CLisp. The file message.lisp contains the program you’d like to run (or ship or whatever). Finally, the bootstrapper files are up to provide an exe with company info, icon, copyright, etc. as an entry to the lisp program. The important bit here is that you don’t want a command prompt window popping up before startup.
Let’s see the files:
% cat message.lisp
(use-package "FFI")
(def-call-out messagebox
(:name "MessageBoxA") (:library "user32.dll")
(:arguments (hwnd int) (text c-string) (capt c-string) (type uint))
(:return-type int)
(:language :stdc))
(defun main ()
(messagebox 0 "Your hacking starts... NOW!" "Demo MsgBox" 0)
(quit))
% cat -A Makefile
all:^Imsgbox-app.exe msgbox-app.img$
^Imkdir -p shipment$
^Icp msgbox-app.exe shipment$
^Icp msgbox-app.img shipment$
^Icp clisp-dlls/* shipment$
$
msgbox-app.img:^Imsgbox-app.img.exe$
^Icp $< $@$
$
msgbox-app.img.exe:^Imessage.lisp$
^Iclisp -q -norc -x \$
"(load \"message.lisp\") \$
(ext:saveinitmem #P\"./msgbox-app.img.exe\" \$
:executable t \$
:norc t \$
:init-function #'main)"$
$
bootstrapper.res:^Ibootstrapper.rc witchs-hat.ico$
^Iwindres $< -O coff -o $@$
^I$
msgbox-app.exe:^Ibootstrapper.cc bootstrapper.res$
^Ig++ -mwindows $^ -o $@$
$
clean:$
^Irm -rf msgbox-app.exe bootstrapper.res \$
^Imsgbox-app.img msgbox-app.img.exe shipment$
% cat bootstrapper.rc
ID ICON "witchs-hat.ico"
1 VERSIONINFO
FILEVERSION 1,0,0,0
PRODUCTVERSION 1,0,0,0
BEGIN
BLOCK "StringFileInfo"
BEGIN
BLOCK "080904E4"
BEGIN
VALUE "CompanyName", "MsgBox Products"
VALUE "FileDescription", "Demo MsgBox"
VALUE "FileVersion", "1.0"
VALUE "InternalName", "msgbox-app"
VALUE "LegalCopyright", "Grault"
VALUE "OriginalFilename", "msgbox-app.exe"
VALUE "ProductName", "Demo MsgBox"
VALUE "ProductVersion", "1.0"
END
END
BLOCK "VarFileInfo"
BEGIN
VALUE "Translation", 0x809, 1252
END
END
% cat bootstrapper.cc
#include <windows.h>
int WinMain(HINSTANCE a0, HINSTANCE a1, LPSTR a2, int a3)
{
STARTUPINFO si;
PROCESS_INFORMATION pi;
ZeroMemory(&si,sizeof(STARTUPINFO));
si.cb = sizeof(STARTUPINFO);
CreateProcess("msgbox-app.img", "",
NULL,NULL,TRUE,CREATE_NO_WINDOW,NULL,
NULL,&si,&pi);
// version and company details are in the bootstrapper exe
// it's kinda better to show these e.g. in process explorer
// and image file as a subprocess
// feel free to comment the following line to leave img only
WaitForSingleObject(pi.hProcess, INFINITE);
return 0;
}
%
These are the files, and here are the results of a make:
% make
windres bootstrapper.rc -O coff -o bootstrapper.res
g++ -mwindows bootstrapper.cc bootstrapper.res -o msgbox-app.exe
clisp -q -norc -x \
"(load \"message.lisp\") \
(ext:saveinitmem #P\"./msgbox-app.img.exe\" \
:executable t \
:norc t \
:init-function #'main)"
;; Loading file message.lisp ...
;; Loaded file message.lisp
T
;; Wrote the memory image into .\msgbox-app.img.exe (5,088,157 bytes)
Bytes permanently allocated: 92,512
Bytes currently in use: 2,188,704
Bytes available until next GC: 544,546
2188704 ;
544546 ;
92512 ;
1 ;
52160 ;
156001
cp msgbox-app.img.exe msgbox-app.img
mkdir -p shipment
cp msgbox-app.exe shipment
cp msgbox-app.img shipment
cp clisp-dlls/* shipment
% find
.
./bootstrapper.cc
./bootstrapper.rc
./bootstrapper.res
./clisp-dlls
./clisp-dlls/libiconv-2.dll
./clisp-dlls/libintl-8.dll
./clisp-dlls/readline5.dll
./Makefile
./message.lisp
./msgbox-app.exe
./msgbox-app.img
./msgbox-app.img.exe
./shipment
./shipment/libiconv-2.dll
./shipment/libintl-8.dll
./shipment/msgbox-app.exe
./shipment/msgbox-app.img
./shipment/readline5.dll
./witchs-hat.ico
Here’s a picture how this all looks like on a Windows Server 2003 Standard Edition without any kind of lisp installed. And the entries in Process Explorer.
Some sort of shipment : )
show up in Process Explorer
Obviously one can develop a much more sophisticated bootstrapper. This one represents only the possibility of releasing software written in Lisp. Assembling these output files together into an installer could be the next step : ))
And finally, you can get either the binaries or the source files by sending a mail to:
% echo gra.rtebsrpehbf.ferfh@gyhnet | rev | tr '[a-z]' '[n-za-m]'
7zip loads of files in a single folder
I’ve met with a folder with around 400000 files on Windows. Listing the files takes more than 5 minutes for an explorer window which is infinity in IT terms : ) Setting the working directory to this one in a cmd window works. Great. Starting a dir command in cmd leads to this infinity of silence also. Suprisingly if your file names are structured enough to hash them with a prefix, then `dir prefix1*’ is relatively fast. Therefore creating directories for the values and moving the groups to these solves the problem somewhat. I also decided to zip these folders of grouped files (by a hash on their names). 7z run time somehow depends on the nr of files in current directory even if you’re up to compress the files in a single subdirectory into a file which is in the current working one. This can be an issue when you have hundreds of thousands files in a single directory. So it’s better to separate the files first and compress them after.
Here’s the batch file I’ve used to solve this.
set list=^ 200801 200802 200803 200804 200805 200806 ^ 200807 200808 200809 200810 200811 200812 ^ 200901 200902 200903 200904 200905 200906 ^ 200907 200908 200909 for %%i in (%list%) do ( md archive_%%i move someprefix%%i* archive_%%i\ ) for %%i in (%list%) do ( 7z a archive_%%i.7z archive_%%i\ )
manipulate k-th column in file with sed & friends
$ echo $0 bash $
Which means that all the stuff below holds at least when using Bash. One of the important features in it is “Process Substitution”. Not so efficient (due to extra bash processes spawned), but I just don’t care at the moment..
The first use case is to manipulate the k-th column of a file. Let’s see our test file:
$ cat -A if1.txt a^Ib^Ic^Id^Ie^If^Ig^Ih$ b^Ic^Id^Ie^If^Ig^Ih^Ia$ c^Id^Ie^If^Ig^Ih^Ia^Ib$ d^Ie^If^Ig^Ih^Ia^Ib^Ic$ e^If^Ig^Ih^Ia^Ib^Ic^Id$ f^Ig^Ih^Ia^Ib^Ic^Id^Ie$ g^Ih^Ia^Ib^Ic^Id^Ie^If$ h^Ia^Ib^Ic^Id^Ie^If^Ig$ $ cat if1.txt a b c d e f g h b c d e f g h a c d e f g h a b d e f g h a b c e f g h a b c d f g h a b c d e g h a b c d e f h a b c d e f g $
The problem is to search and replace with sed, but only in a given column.
The first solution is done by using paste, cut.
$ paste <(cut -f-4 if1.txt) <(cut -f5 if1.txt | sed 's/h/x/g') <(cut -f6- if1.txt) a b c d e f g h b c d e f g h a c d e f g h a b d e f g x a b c e f g h a b c d f g h a b c d e g h a b c d e f h a b c d e f g $
The second one uses the bash language and its read command which is able to fill an array with values read from a line.
$ cat if1.txt | while read -a line; do
> line[4]=$(echo ${line[4]} | sed 's/h/x/')
> echo -e ${line[*]} | sed 's/\ /\t/g'
> done
a b c d e f g h
b c d e f g h a
c d e f g h a b
d e f g x a b c
e f g h a b c d
f g h a b c d e
g h a b c d e f
h a b c d e f g
$
Note that this multiline command can be written into a single line as well (obviously by removing the secondary prompt characters).
Now what if you want to do computations based on other columns. Here’s the same approach for this (removing 2nd and 4th columns and introducing a new 3rd one which should be the sum of the two deleted ones):
$ cat -A if2.txt
a^I1^Id^I2$
b^I3^Ie^I4$
c^I5^If^I6$
$ cat if2.txt
a 1 d 2
b 3 e 4
c 5 f 6
$ paste <(cut -f1,3 if2.txt) <(cut -f2,4 if2.txt | sed 's/$/ + p/' | dc)
a d 3
b e 7
c f 11
$ cat if2.txt | while read -a line; do
> echo -e ${line[0]}\\t${line[2]}\\t$(echo ${line[1]} ${line[3]} + p | dc)
> done
a d 3
b e 7
c f 11
$
moving from ucw to wui (& cl-dwim)
As per the UCW repository the project seems to be abandoned a bit. There’s a new upcoming lisp based web development framework called cl-dwim with it’s own demo site.
WUI (a subproject of cl-dwim) has numerous asdf dependencies, so collecting the right version of these can be a bit time consuming, but AFAIK there will be some kind of boxset version as for UCW. I was able to start up the server and write some sort of hello world program with it, screencast is coming soon.
url shortening APIs into cl-twitter
Some hacks with cl-twitter:
$ darcs whatsnew
hunk ./twitter.lisp 81
-(defun send-tweet (text &rest args &key (tiny-url-p t) &allow-other-keys)
- (let ((newtext (if tiny-url-p (convert-to-tinyurl text) text)))
+(defun send-tweet (text &rest args &key (tiny-url-p t)
+ (shortener #'get-tinyurl) &allow-other-keys)
+ (let ((newtext (if tiny-url-p
+ (convert-to-short-url text :shortener shortener) text)))
hunk ./twitter.lisp 87
- (rem-keywords args '(:tiny-url-p)))))
+ (rem-keywords args '(:tiny-url-p :shortener)))))
hunk ./twitter.lisp 148
+(defparameter *cligs-url* "http://cli.gs/api/v1/cligs/create")
+(defparameter *bit-ly-url* "http://api.bit.ly/shorten")
hunk ./twitter.lisp 165
-(defun convert-to-tinyurl (text)
+(defun get-cligs-url (url)
+ "Get a Cligs for the given URL. Uses the Cligs API service.
+ (c) by ... via cl-twit"
+ (multiple-value-bind (body status-code)
+ (http-request *cligs-url*
+ :parameters `(("url" . ,url)))
+ (if (= status-code +http-ok+)
+ body
+ (error 'http-error
+ :status-code status-code
+ :url url
+ :body body))))
+
+(defun bit-ly-shortener-of (login api-key)
+ (lambda (url)
+ "Get a bit.ly for the given URL. Uses the bit.ly API service.
+ (c) by ... via cl-twit"
+ (multiple-value-bind (body status-code)
+ (http-request *bit-ly-url*
+ :parameters `(("version" . "2.0.1")
+ ("longUrl" . ,url)
+ ("login" . ,login)
+ ("apiKey" . ,api-key)))
+ (if (= status-code +http-ok+)
+ (third
+ (ppcre:split
+ "\\\""
+ (car (ppcre:all-matches-as-strings
+ "shortUrl\\\": \\\"[^\\s\\)\\]\\'\\\"]+" body))))
+ (error 'http-error
+ :status-code status-code
+ :url url
+ :body body)))))
+
+(defun convert-to-short-url (text &key (shortener #'get-tinyurl))
hunk ./twitter.lisp 206
- (get-tinyurl (subseq result start end))))))))
+ (funcall shortener (subseq result start end))))))))
+
$
static executables with lisp
In case you’re planning to write desktop applications in lisp (for example SBCL) and provide installers or create debian or rpm packages with your product, this solution can come handy.
$ sbcl --noinform * (defun main () (progn (format t "HELLO~%") 0)) MAIN * (main) HELLO 0 * (sb-ext:save-lisp-and-die #P"test.img" :toplevel #'main :executable t) [undoing binding stack and other enclosing state... done] [saving current Lisp image into /home/grault/test.img: writing 3432 bytes from the read-only space at 0x01000000 writing 2256 bytes from the static space at 0x01100000 writing 25616384 bytes from the dynamic space at 0x09000000 done] $ ls -Fs test.img 25624 test.img* $ ./test.img HELLO $
