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 <tikk...@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 <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 -- Devon McCormick, CFA ^me^ at acm. org is my preferred e-mail ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
