[Jprogramming] DAG implementation?

[Devon McCormick]

How about an N by N boolean with rows being "from" and columns being
"to" with a one for a link and zero for none?  Or a list of node names
and a two row table of 0: "from" and 1: "to" indexes into the node
list, perhaps with a corresponding vector of weights if those are
necessary?

I wrote a little example in J showing how to traverse a DAG here:
www.jsoftware.com/jwiki/NYCJUG/2009-11-10/BreadthFirstGraphTraversal .
 Also, I started to write some code based on a couple of books I've
been reading on graph theory which I've put here:
http://www.jsoftware.com/jwiki/DevonMcCormick/Graphs/graphPlay.ijs .

There's also this example of searching a graph -
http://www.jsoftware.com/jwiki/ProblemSolving - and this -
http://www.jsoftware.com/jwiki/Essays/Floyd - on the "Floyd–Warshall
algorithm" for  computing shortest paths between pairs of "vertices in
a digraph with weighted edges."

On Tue, Mar 20, 2012 at 9:48 PM, Ric Sherlock <tikkanz at gmail.com> wrote:
> I thought I remembered something on the wiki about this and did a
> search on it for acyclic. Didn't find what I was looking for but the
> following pages suggest formats for DAGs:
> http://www.jsoftware.com/jwiki/Essays/Text Formatting
> http://www.jsoftware.com/jwiki/RogerHui/t
>
> On Wed, Mar 21, 2012 at 12:17 PM, Alexander Mikhailov <avmich at 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



-- 
Devon McCormick, CFA
^me^ at acm.
org is my
preferred e-mail