It occurs to me that this could serve as a good example of the usefulness of "grade" (as opposed to sort): you can sort your adjacency matrix, saving the grade vector, then check if it's triangular; if it is, you can use the same grade vector to re-arrange your nodes to match the new AM if you want to keep forms consistent. You could also use the grade vector to re-arrange either of the two other forms mentioned so far: vertex array or nodes;edges (see http://www.jsoftware.com/jwiki/DevonMcCormick/Graphs/graphPlay.ijs).
On Wed, Mar 21, 2012 at 11:00 AM, Raul Miller <rauldmil...@gmail.com> wrote: > Yes: if you can sort your connection matrix so it is upper triangular, > you can also sort it so that it is lower triangular. > > -- > Raul > > On Wed, Mar 21, 2012 at 10:48 AM, Devon McCormick <devon...@gmail.com> wrote: >> So Raul, according to what you said >> >> On Wed, Mar 21, 2012 at 9:25 AM, Raul Miller <rauldmil...@gmail.com> wrote: >> ... >>> I should also note that a "directed acyclic graph" means that the data >>> can be sorted such that the connection matrix is lower-triangular. >> >> I think that answers my question below about whether my example is a >> DAG - if I swap the labels for nodes 3 & 5, the adjacency matrix would >> be triangular, though upper-triangular which I assume is conceptually >> the same (because we can convert one to the other by swapping node "n" >> with "5-n"). >> >> NB.* egDAG: example picture of a directed acyclic graph with the >> NB. characters "V>" (and, potentially, "^<") representing directional >> NB. arrowheads; "V>" together means a split both down and to the right. >> egDAG=: 0 : 0 >> 0->2->5 >> | | >> | V >> V>--->4 >> | >> V >> 1 >> | >> V >> 3 >> ) >> NB. Is this a DAG if you can reach "4" by two different paths? >> >> NB. The picture above corresponds to this adjacency matrix representation. >> amDAGeg=: ".&><;._2 ] 0 : 0 >> 0 1 1 0 0 0 >> 0 0 0 1 0 0 >> 0 0 0 0 0 1 >> 0 0 0 0 0 0 >> 0 0 0 0 0 0 >> 0 0 0 0 1 0 >> ) >> >> NB. Vertex Array representation of same graph as above. >> vaDAGeg=: ,&.>(1 2);(3);(5);(i.0);(i.0);<4 >> >> NB. A (nodes);(edges) representation of the above DAG. >> neDAGeg=: (0 1 2 3 4 5);<|:0 1,0 2,1 3,2 5,:5 4 >> >> -- >> Devon McCormick, CFA >> ^me^ at acm. >> org is my >> preferred e-mail >> ---------------------------------------------------------------------- >> 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
