----- 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? 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. ----- 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. Alexander ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
