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.] If you are working with fewer than 100 nodes, or if you are just developing the algorithms, I would strongly encourage you to use this approach. Changing from this representation to other more efficient representations (if they exist for your graphs) has been straightforward in my experience. The point here is to get your architecture right. As for "more efficient representations", that depends on the number of nodes in your graph (a connection matrix needs O(n^2) space), the density of your graph (a dense graph will also need O(n^2) space), and the size of the representation of each of your nodes. To give you an idea: #3!:1]100 3$a: 16848 #3!:1]100 100$1 10056 On my machine, a 100 by 3 array of empty boxes seems bulkier than a 100 by 100 connection matrix. That said, I would not concern myself with bulk until it became a "factor of 2" issue. And the big advantage of the connection matrix is algorithmic simplicity. And note that there are a variety of ways you can transform a connection matrix into alternate representations -- but most of them involve I. used monadically. The one you choose is roughly equivalent to: dm,. (<@I. ,. <@I.@|:) cm where dm represents the data at each node (which I have assumed to be an array of boxes, one box per node), and cm represents the connection matrix which connects those nodes. I should also note that a "directed acyclic graph" means that the data can be sorted such that the connection matrix is lower-triangular. That does not relate directly to your question or the things you have said about your data, but it does relate to understanding the connection matrix. I hope some of this helps. 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. -- Raul On Tue, Mar 20, 2012 at 7:17 PM, Alexander Mikhailov <avm...@yahoo.com> wrote: > Hi, > > I need an implementation of a directed acyclic graph. Both nodes and links > should contain DAG user info, and 2 nodes may have 0 or more (acyclic) links > between them. What could be a good implementation in J? Having a node I need > to (efficiently) find both "following" and "preceding" nodes. > > > So far the best I have is an array of items, each item having 3 boxes. Item > correspond to a node, first box contain node user info (actually, an integer > - index in the separate array of user node data), second box contains the > array of preceding nodes' indexes (integers, indexes in this same graph > array, and integers may repeat as a preceding node may be connected by more > than a single link) and the third box contains array of pairs "index of > following node - index of link's user data in a separate array". So, third > box contains N*2 integers, where N is the number of links, starting in this > node. > > Doesn't look like particularly J style. Do you have any suggestions? > > Thank you, > > Alexander > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
