On Wed, Mar 21, 2012 at 3:37 PM, Alexander Mikhailov <avm...@yahoo.com> wrote: > ----- > > Date: Wed, 21 Mar 2012 09:25:19 -0400 > From: Raul Miller <rauldmil...@gmail.com> > > The "natural" J data structure here would be two items: > > 1. A list representing data at each node. > 2. A connection matrix. > > [And I saw some other messages in this thread advocating this kind of > approach -- there's good reasons for that.] > > ----- > > How to store link-associated data then? And how to specify that there are 3 > links from node 4 to node 5?
Ick.. ok, if you want to do that, you are going to need a separate list with one element for each link. Then your "connection matrix" is not boolean but integer, and it expresses the count of how many links you have between two nodes. And the "link associated data" has a length which is the sum of the ravel of your "connection matrix". I do not know what operations you are performing, and I have not thought through where the transition points are, for efficient representation. I basically do not know enough about what you are trying to do to say anything in depth about this system. > To be honest, I've tried two implementations. One is I've described, another > is sparse table. In the latter case the implementation is indeed shorter. > However, I've got 2 concerns regarding that. First, storing multiple links > (their data actually) between same nodes; I had to put array of boxes into > the table's cells, which, I guess now, is ok, but then it looked rather > weird. Second, my graph grows during program run, so sparse array has to > grow, and it somehow wasn't actually "sparse" - J decided to keep all > elements, even empty ones, there, which defeated hoped-for memory savings. > For some cases, I guess, adjacency matrix can be rather big, but not very > dense, so sparse arrays looked interesting. Sparse arrays in J become dense if you perform certain operations on them. You need to carefully study the documentation if you want to be using them. > ----- > If you want further discussion of alternate representations of either > the data or of operations on the data, it would help if you were more > specific about what you were trying to accomplish. For example, to > come up with a "more efficient" representation of the data we need to > understand the constraints and perhaps even the use cases. > ----- > > Sure. I'm trying to build a Tomita parser driver (generalized LR parsing), > where are no shift-reduce or reduce-reduce conflicts, instead all possible > ways of parsing the input are tried (hence the graph instead of stack). The > idea is to solve RosettaCode's EBNF ( http://rosettacode.org/wiki/Parse_EBNF > ) task. Oh!... In that case, I think I would eliminate the use of integers in the connection matrix. And instead of saying "there are three links from this node to that node" I would instead say "there is one link from this node to that node, and it has these three supported options". I think that I would perform the three operations in parallel on the set of existing states and then strip out the results which achieved an invalid state. -- Raul ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
