ANN: GraphWriter 3.0 available
Albert Graef
version 3.0 of the one and only calc-based graph editor has been
released. This version fixes some remaining compatibility issues with
the 49G+/50G calculators (including a TTRM in the graph browser of the
editor, so upgrading is strongly recommended). Also, as suggested by
John H Meyers, there is now only one library which works on all
supported calculators (49G/49G+/50G).
More information and downloads are available here:
http://www.musikwissenschaft.uni-mainz.de/~ag/hp49/
Direct download link:
http://www.musikwissenschaft.uni-mainz.de/~ag/hp49/grw-3.0.zip
The new package should also soon show up on hpcalc.org.
Enjoy. :)
Albert
--
Dr. Albert Gr"af
Dept. of Music-Informatics, University of Mainz, Germany
Email: Dr.G...@t-online.de, a...@muwiinfa.geschichte.uni-mainz.de
WWW: http://www.musikinformatik.uni-mainz.de/ag
Albert Graef
some of you might still remember that when I first released GraphWriter
several years ago, I promised to do a kind of tutorial on using this
library to do cool graph theory stuff with the 49G (then the latest and
greatest HP calc). Well, unfortunately I got busy with other things and
could never deliver that. So I now take the release of GraphWriter 3.0
as an excuse to make up for this and show you how to use GraphWriter
with a relatively simple but still (I hope) interesting example, namely
searching cliques in graphs.
The idea is that at least some of you might enjoy this mini tutorial
enough to be motivated to implement your own graph algorithms using
GraphWriter. In that case it would be nice if you could send me your
programs and examples or post them to this thread. I'd like to put
together a little collection of examples to be included in the next
GraphWriter release, and as soon as I have some time I'll also format
this text and put it up along with the examples on Michael's new HP 50G
wiki.
So, in case anyone still wonders what this GraphWriter is all about, it
is both a graph editor and a library of common graph operations which
lets you code most usual graph algorithms in RPL quite easily. I have to
confess that it's always a nice thing for me to see such combinatorial
algorithms come to live on the these devices, considering that the first
calculators I programmed (quite a little while ago) were just barely
capable to play a good game of "guess the number". ;-)
NB: If you forgot all your graph theory then it's time to review it now,
you'll need it (just the basics)! The GraphWriter manual contains a
introduction to what graphs are and how they are represented in the
GraphWriter library, that should be enough information to get you started.
The GraphWriter package already includes Dijkstra's shortest path
algorithm as an example, which is also described in the manual contained
in the package. As another example for a combinatorial graph problem,
here is an implementation of Carraghan's and Pardalos' clique algorithm
which computes completely connected subgraphs of a graph (i.e., each
pair of distinct nodes in the clique is connected by an edge). This
problem arises in various applications (e.g., clustering problems) and
is also related to the famous graph coloring problem.
Here's the user RPL program implementing the algorithm. You can transfer
this to your calc using ASCII transfer as usual, and store it in a
variable named 'CLIQUE'.
@ CLIQUE ( graph int -> 0. | nodelist 1. )
@ Takes a graph and the desired clique size, returns a clique of the
@ given size and 1. if found, 0. otherwise.
@ This is an RPL implementation of the standard backtracking algorithm
@ for the clique problem. The original algorithm can be found in
@ R. Carraghan and P.M. Pardalos: An exact algorithm for the maximum
@ clique problem, Operations Research Letters 9, 1990, pp. 375-382.
@ Note that the algorithm takes exponential time in the worst case,
@ but usually performs rather well in practice if input graphs are not
@ too large. (In fact, the clique problem is known to be NP-complete
@ and thus a polynomial-time solution probably doesn't exist.) Also
@ note that the variation of the algorithm presented here searches for
@ cliques of a given size rather than always enumerating all solutions
@ in order to find a maximum clique.
@ Description of the algorithm: When entering each iteration, the
@ current clique C and set of candidate nodes V is on level 2 and
@ 1. Starting with C = {} and V = NODES(G), the invariant maintained
@ during execution of the algorithm is that C is always a clique and
@ the nodes in V are adjacent to all nodes in C. Past intermediate
@ solutions leading up to the current one are kept on higher levels
@ the calculator stack, so that we can perform backtracking if the
@ current candidate leads to a "dead end". If SIZE(C)+SIZE(V) is still
@ at least the desired clique size then the current clique is extended
@ with the head element from V, otherwise we perform backtracking and
@ consider the next solution candidate. The algorithm terminates as
@ soon as C has the desired size or if no more solution candidates are
@ available, returning the found clique and 1., or just 0.,
@ respectively.
\<< \-> G K
\<<
{ } G NODES
WHILE \-> C V
\<<
IF C SIZE V SIZE + K \>= THEN
IF C SIZE K \>= THEN
@ Solution found, clean up the stack and push results.
K DUP + DROPN C 1. 0.
ELSE
@ Extend the current solution with the head element from V.
V TAIL V HEAD DUP G SWAP GETNODE \-> U X XN
@ U = TAIL(V), X = HEAD(V), XN = the corresponding node info
\<<
C U C X + DUP 1. DISP
@ Remove from U all nodes not adjacent to X.
@ (See separate FILTER function.)
U \<< XN SWAP ADJ? \>> FILTER
\>> 1.
END
ELSE
@ Perform backtracking and consider the next solution @
candidate.
IF C SIZE 0. > THEN 1.
ELSE 0. 0. @ No more solutions, bail out.
END
END
\>>
REPEAT
END
\>>
\>>
To run this you'll also need the following little helper function FILTER
which filters a list with a given predicate:
@ FILTER: list prog -> list'
@ Filters a list (on level 2) with a given predicate (on level 1).
@ The function applies the program on level 1 to each member of the
@ list on level 2 in turn, and returns the list of all original list
@ members for which the program returned nonzero a.k.a. "true".
@ Example: { 1. -2. 3. -4. } \<< 0. > \>> FILTER => { 1. 3. }
\<< \-> X P
\<< X OBJ\-> DUP { } \-> N Y
\<<
WHILE 0. > REPEAT
IF DUP P EVAL THEN
'Y' STO+
ELSE
DROP
END
'N' DECR
END Y
\>>
\>>
\>>
(NB: John, you surely know a better way to do this, so please let me
know. ;-) I actually thought that there *must* be a builtin function
which provides the filter functionality, but couldn't find any.)
Ok, it's time to take the CLIQUE program for a spin now, so whip out
your 49G/+/50G calcs (or start the emulators) and get ready!
First install the latest GraphWriter library (available here:
http://www.musikwissenschaft.uni-mainz.de/~ag/hp49/), if you haven't
already done so, and make sure that the library is attached (either 557
ATTACH or a quick reboot using [ON]+[C] should do this for you). Once
the library is installed, you can transfer the CLIQUE and FILTER
functions to your calc. Finally, here's a graph to play with:
{ { (.05,.91) 2. 3. 4. } { (.29,.88) 1. 3. 7. 9. }
{ (.29,.66) 1. 2. 4. 7. } { (.14,.58) 1. 3. 5. }
{ (.34,.48) 4. 6. } { (.56,.55) 5. 7. 8. 10. 11. 13. }
{ (.49,.73) 2. 3. 6. 8. 10. 11. } { (.56,.87) 6. 7. 9. 10. 11. }
{ (.66,.98) 2. 8. 10. 11. } { (.85,.87) 6. 7. 8. 9. 11. 12. }
{ (.8,.67) 6. 7. 8. 9. 10. 12. 13. } { (1.04,.74) 11. 13. 10. }
{ (.91,.48) 6. 11. 12. } }
Transfer that list to your calc, too, and store it in a variable, say
'G'. The graph represented by this list (which is just the "adjacency
list" of the graph, augmented with the graph's 2D embedding, see the
GraphWriter manual for details) contains a clique of size 5 which is
computed with the following keypresses (with the graph G, CLIQUE and
FILTER all in the current directory):
[VAR] [G] 5. [CLIQUE]
The CLIQUE program will start searching and shows the current candidate
clique in display line 1 as it walks the space of possible solutions.
After a while the calc should display the following result:
{ 6. 7. 8. 10. 11. }
1.
The value 1. on level 1 just indicates that a clique has been found, the
clique itself is on level 2. We can drop the 1. value and recall the
graph to the stack to take a look at the solution:
[DROP] [G] [RS->][LIB] [GRW] [GRED]
(NB: For those of you who haven't got the hang of the 49 series calcs
yet, [DROP] can be entered most quickly with the "backspace" button
right below the cursor keys.)
After the graph has been displayed, go to the second page of the
GraphWriter menu and recall the selection:
[NXT] [->MARK]
This will mark the computed clique in the displayed graph for you. Ah,
there it is, right, it's a 5-clique.
Is this actually a largest clique in the graph? After exiting
GraphWriter with [CANCEL], you can check that as follows:
[VAR] 6. [CLIQUE]
This time the result is 0., indicating that no clique of size 6 was
found, and thus 5 is indeed the maximum clique size.
Ok, that concludes the RPL clique algorithm example and this mini
tutorial. Hope you enjoyed it. To be continued...
Cheers,
Albert Graef
Hmm, are there no graph theory afficionados left in this ng? Anyway, to
finish it up here are a few remarks and improvements to the clique
algorithm discussed in my previous post.
1. RPN versus Algebraic Mode
You probably noticed that GraphWriter is meant to be used with RPN, so
that's what I did the examples in the mini tutorial and the manual with.
Of course, it's possible to invoke the GraphWriter functions from
algebraic mode, too, but you'll notice that the graph editor then won't
be able to pick up a previously computed node list from the stack then
(which is quite useful to visualize results).
Anyway, if you want to run the CLIQUE function in algebraic mode, then
it's convenient to modify the function so that it returns NOVAL (instead
of 0.) if no clique of the desired size has been found, and just the
clique (without the 1. value) otherwise. The necessary modifications are
trivial. Here is the modified program:
@ CLIQUE, "algebraic" version
\<< \-> G K
\<< { } G NODES
WHILE \-> C V
\<<
IF C SIZE V SIZE + K \>=
THEN
IF C SIZE K \>=
THEN K DUP + DROPN C 0.
ELSE V TAIL V HEAD DUP G SWAP GETNODE \-> U X XN
\<< C U C X + DUP 1. DISP U
\<< XN SWAP ADJ?
\>> FILTER
\>> 1.
END
ELSE
IF C SIZE 0. >
THEN 1.
ELSE NOVAL 0.
END
END
\>>
REPEAT
END
\>>
\>>
2. The FILTER Function
The list filtering function proposed in the previous post is kind of
slow, so you might wish to use the following improved version instead:
@ FILTER, faster version
\<< \-> P
\<< { } SWAP
IF DUP2 ==
THEN DROP
ELSE 1.
\<<
IF DUP P EVAL NOT
THEN DROP
END
\>> DOLIST
IF DUP { } \=/
THEN NIP
END
END
\>>
\>>
3. A Maximum Clique Algorithm
As already mentioned, the necessary modifications to turn CLIQUE into a
maximum clique algorithm are also straightforward. Here is a program
which always returns a clique of maximum size in the input graph:
@ MAXCLIQUE: graph -> nodes
\<< { } \-> G C0
\<< C0 G NODES
WHILE \-> C V
\<<
IF C SIZE V SIZE + C0 SIZE >
THEN
IF V { } ==
THEN C 'C0' STO 1.
ELSE V TAIL V HEAD DUP G SWAP GETNODE \-> U X XN
\<< C U C X + DUP 1. DISP U
\<< XN SWAP ADJ?
\>> FILTER
\>> 1.
END
ELSE
IF C { } \=/
THEN 1.
ELSE C0 0.
END
END
\>>
REPEAT
END
\>>
\>>
4. Further Performance Tweaks
In their 1990 Operations Research Letters paper, Carraghan and Pardalos
also discuss changing the order in which the nodes are traversed during
the algorithm. In particular, a node order which turns out to be useful
for larger and "dense" graphs (graphs with a high average node degree)
is the so-called (recursive) "smallest-first order" (SFO) which
considers a node of minimum degree first. (The degree of a node is the
number of edges emanating from it.) The rationale behind this is that we
want to consider the "hardest" nodes first, in order to better prune the
search tree already in early stages of the algorithm. SFOs of a graph G
are formally defined as follows:
- If G is the empty graph, then its SFO is the empty node list {}.
- If G has at least one node, then an SFO { x1, ..., xn } of G satisfies
the conditions (i) x1 is a node of minimum degree in G, and (ii) { x2,
..., xn } is an SFO of G-x1, where G-x1 is the graph G with node x1 (and
all incident edges) removed.
This recursive definition readily translates into the following RPL program:
@ SFO: graph -> nodes
\<<
IF DUP { } \=/ THEN
@ Save the original node numbers as node labels. Note that the
@ actual node numbers change during processing as nodes are
@ successively removed from the graph.
DUP NODES 2.
\<< \-> X N
\<< X NODE\-> SWAP DROP N "" \->TAG 1. \->LIST SWAP \->NODE \>>
\>> DOLIST
{ } \-> ORD \<<
@ Find the node with the smallest degree, append it to ORD and
@ remove it from the graph. Wash, rinse, repeat.
DO \-> G \<<
IF G SIZE 1. > THEN
G 1. \<< ADJ SIZE \>> DOLIST DUP \<< MIN \>> STREAM POS
ELSE 1.
END
\-> N \<<
'ORD' G N GETNODE "" GETLABEL STO+ G N DELNODE
\>>
\>>
UNTIL DUP { } ==
END
DROP ORD
\>>
END
\>>
You can use this function to reorder the nodes of a graph using the
SUBGRAPH function in the GraphWriter library as follows (taking the
graph G from the previous post as an example):
G DUP SFO SUBGRAPH
(The SUBGRAPH operation can be found on the 4th page of the GraphWriter
menu.)
This takes a little while, so this step will make finding cliques with a
subsequent invokation of CLIQUE or MAXCLIQUE quicker only if the graphs
are fairly dense and large.
It is also possible to have the CLIQUE and MAXCLIQUE programs always use
an LFO by replacing the instructions G NODES near the beginning of the
algorithm by G LFO.
Ok, that's it for now... Any comments?
Veli-Pekka Nousiainen
news:eo8pv9$dbu$03$1...@news.t-online.com...
X
> Anyway, if you want to run the CLIQUE function in algebraic mode, then
> it's convenient to modify the function so that it returns NOVAL (instead
> of 0.) if no clique of the desired size has been found, and just the
> clique (without the 1. value) otherwise.
> Ok, that's it for now... Any comments?
Is it possible to make the programs the same
eg. RPN could also return NOVAL
and test for NOVAL instead of 0.
I would love to C these slow programs in fast ARM C
Thanks anyway - they seem nice
and may lure students into to the Matrix...I mean Graph
blueel...@hotmail.com
<Dr.G...@t-online.de> wrote:
>
>Hmm, are there no graph theory afficionados left in this ng? Anyway, to
>finish it up here are a few remarks and improvements to the clique
>algorithm discussed in my previous post.
>
Dr. Graef,
I downloaded the SW and have been spending some time reading through
the documentation and working through the example in the
documentation. I got stuck on the first example (Dijkstra's
Algorithm) but I get an error about DOLIST (using code provided in d/l
package). It seems that my calc thinks "NODES" is a global variable
instead of the ROMPTR. Perhaps it's a transfer/compile issue on the
calculator.
Anyway, I would like to better understand this as and am looking
forward to learning more. I'm an electrical engineering student and I
love to program. Computer Science is not my major, but I will be
involved more than a little in both math and computers within my
field. In particular, the "shortest path" routine looks particularly
interesting as I've had to create a "shortest path" type routine for a
multiple-beam antenna configuration in order to minimize losses in the
microwave switches. I have yet to understand the mysical power that
came over me while my client was on the phone for me to come up with
such a bizarre routine :) [well, it worked, but I have no idea what
proper "method" it used].
In the long run, I certainly didn't want to go without saying "thank
you," as your program seems very comprehensive and stable and well
designed. Plus, I enjoyed your documentation and its presentation and
layout. It is obvious that you have spent a good amount of time and
energy putting this together and although I may not fully understand
it, I do appreciate quality workmanship and dedication.
Best regards,
Scott
John H Meyers
> RPN versus Algebraic Mode
> if you want to run the CLIQUE function in algebraic mode, then
> it's convenient to modify the function so that it returns NOVAL
> (instead of 0.) if no clique of the desired size has been found,
> and just the clique (without the 1. value) otherwise.
> The necessary modifications are trivial.
Any RPL/RPN command which returns a True/False can be called
from a "wrapper" command to convert it to Results/NOVAL
General "wrapper" command:
\<< EVAL NOT NOVAL IFT \>> 'TF' STO
Example of use in ALGebraic mode:
Without wrapper:
`CHOOSE("Title",{11,22,33},3)`
Returns: 0. or { 33 1. }
With wrapper:
`TF(CHOOSE("Title",{11,22,33},3))`
Returns: NOVAL or 33
[r->] [OFF]
Albert Graef
> Is it possible to make the programs the same
> eg. RPN could also return NOVAL
> and test for NOVAL instead of 0.
Well, of course you can use my second version of CLIQUE (the one that
returns NOVAL instead of 0.) just as well in RPN mode.
> I would love to C these slow programs in fast ARM C
You mean the GraphWriter library operations? I wouldn't say that they
are slow (compared to the rest of the RPL system, anyway), they are
already 100% SysRPL and so the speed on the 50G is quite acceptable. I
did consider to rewrite the graph editor in C, though. I think that's
the part that would benefit most from a C implementation, although it's
certainly usable on the 50G in its present form. But first I have to
find out how far along hpgcc's "win" library is.
Albert Graef
> I downloaded the SW and have been spending some time reading through
> the documentation and working through the example in the
> documentation. I got stuck on the first example (Dijkstra's
> Algorithm) but I get an error about DOLIST (using code provided in d/l
> package). It seems that my calc thinks "NODES" is a global variable
> instead of the ROMPTR. Perhaps it's a transfer/compile issue on the
> calculator.
Yes, that sounds like a compile issue. Are you sure that you transferred
the DIJKSTRA program *after* installing and attaching the library? Also
please check that you don't have any other libraries with the same
number (557).
> Anyway, I would like to better understand this as and am looking
> forward to learning more. I'm an electrical engineering student and I
> love to program. Computer Science is not my major, but I will be
> involved more than a little in both math and computers within my
> field.
Well, then GraphWriter should be your friend. I think it's fairly
well-suited for educational purposes, if you're out to learn some
algorithmic graph theory stuff. Which AFAICT plays a major role in EE,
just think of chip layout problems. Of course you can't solve any
real-world problems with gazillions of nodes on a calculator, but the
50G makes for a nice algorithmic scratchpad which enables you to explore
algorithms and do a little rapid prototyping "on the go". And [PRG]
[DEBUG] is also very helpful at times. ;-)
> In the long run, I certainly didn't want to go without saying "thank
> you," as your program seems very comprehensive and stable and well
> designed.
Thanks for the kind words, and for trying the program!
Greetings,
Albert Graef
Another tip: If you want to quickly create random test graphs which
aren't just the mess that RANGRAPH2 usually produces, the following
UDGRAPH function might be handy. Given a number of nodes N and a model
radius R, the function creates a random "unit disk" graph with N nodes
whose nodes are random points in the plane, where two distinct nodes
with points (x1,y1) and (x2,y2) are connected by an edge iff
ABS((x1,y1),(x2,y2)) <= R. The current version creates random
coordinates in the range [0.,1.] which matches the default size of the
graph editor's "canvas".
@ UDGRAPH: int float -> graph
@ Example: 12. 0.4 UDGRAPH creates a unit disk graph with 12 nodes and
@ model radius 0.4 (i.e., edges between nodes at most 0.4 apart).
\<< \-> N R
\<<
IF N 0. >
THEN 1. N
START RAND RAND i \->NUM * + 2. RND 1. \->LIST
NEXT N \->LIST 1. \-> G I
\<< G 1.
\<< 1. \-> X J
\<< X POINT G 1.
\<< \-> Y
\<<
IF I J \=/
THEN
IF X POINT Y POINT - ABS R \<=
THEN J
END
END 'J' INCR DROP
\>>
\>> DOLIST
IF DUP TYPE 1. ==
THEN { }
END + 'I' INCR DROP
\>>
\>> DOLIST
\>>
ELSE { }
END
\>>
\>>
NB: UD graphs are also known as the "intersection graphs of unit circles
in the Euclidean plane". They arise, e.g., as simplified models of
broadcast networks. As it turns out, the clique problem for this class
of graphs can actually be solved in polynomial time using bipartite
matching techniques, but I'll leave that as an exercise for the
interested reader. ;-)
Albert Graef
> START RAND RAND i \->NUM * + 2. RND 1. \->LIST
Well, of course you can also change that to:
START RAND RAND R\->C 2. RND 1. \->LIST
Albert Graef
> It is also possible to have the CLIQUE and MAXCLIQUE programs always use
> an LFO by replacing the instructions G NODES near the beginning of the
> algorithm by G LFO.
s/LFO/SFO/