[R--gR] Graph computations

[Svend Kreiner]

Dear Steffen and other gR-sig members,

I am sure that the other graphical programs have procedures taking care of
the graph computations, and that they probably are more efficient than the
procedures in DIGRAM. Below follows nevertheless a checklist of the things
you can find in DIGRAM including a few other suggestions.


Svend


1. Visual display and interactions with graphs
----------------------------------------------

Add, delete, nodes and links           	all of this is in DIGRAM

Move nodes around, links following     	in DIGRAM

Label and type nodes and links:

nodes can be square, diamond,circle, 
oval, double circle, hollow, filled	NOT in DIGRAM

links can be 
     directed,				in DIGRAM
     bidirected,				NOT in DIGRAM
     undirected,				in DIGRAM
     coloured,				NOT in DIGRAM
     thin, thick				in DIGRAM 

Good printing facilities for graphs	Graphs can be printed. I am not
satisfied with the quality.


In addition to the above DIGRAM includes the following facilities for graph
interaction and editing.

    Default nodes are named by a single letter label. This label can be
replaced by a variable name.
    
    The size of the nodes and the size of the text of labels and variable
names can be changed.

    Easy horizontal and vertical allignment of nodes.

    Rightclicking on links produces a short report on properties relating
to the link (test statistics,             collapsibility properties etc.).    

    Rightclicking on a node produces a short report on variable properties
and a dialogue where you can change 
    some of the information defining variables.

    Partial correlation coefficients can be displayed for all links in the
graph.

    Subgraphs for specific subsets of nodes can be shown.

    Subgraphs for all neighbors to a specific node can be shown.

    Graphs for marginal models can be shown.



2. Simple graph operations
>---------------------------

Specify graphs by incidence matrices, by parent-child relations, by
neighbour relations, by list of links and list of nodes, by GUI         in
DIGRAM

Compute simple graph things like

ne(A) (neighbours of set of nodes A)					in DIGRAM				
pa(A) (parents of set of nodes A)						in DIGRAM
ch(A)  (children of sets of nodes A)					in DIGRAM
de(A)  descendants of A							not in DIGRAM
an(A)  ancestors of A							not in DIGRAM

g(A) subgraph induced by vertex set A		                 	in DIGRAM
u(g,h) graph obtained by union of graphs g and h			not in DIGRAM
i(g,h) graph obtained by intersection of g and h			not in DIGRAM
s(g) undirected version of graph g (also known as skeleton)		in DIGRAM
m(g) moralisation of g (a bit special, see eg lauritzen (1996))	not in DIGRAM


3. More complex graph computations
>-------------------------------------------
comp(a) smallest connected component containing vertex a		in DIGRAM
conn(G) connected components of graph G					in DIGRAM
ch(G) chain components of chain graph G					in DIGRAM
An(A)   smallest ancestral set containing A 				not in DIGRAM
sep(a,b) minimal cutset separating A and B				in DIGRAM
cliques(g) find maximal cliques of g  (NP complete in general, good
algos for chordal and other special graphs)				in DIGRAM
g(H) graph generated by hypergraph H (2-section) ("inverse" to above)not in
DIGRAM
t(g) find chordal cover of g (NP-complete, however, good algos exist)not in
DIGRAM
p(g) find prime components (wrt decomposition by complete separators)not in
DIGRAM
lex(g) number the vertices for possible perfect elimination		not in DIGRAM
maxcard(g) as above, but has bad properties when g is not chordal	not in
DIGRAM
coll(A) find minimal set $S\superset A$ so a graph g is A-collapsible in
DIGRAM
jtree(G) construct junction tree of cliques of chordal graph G.	not in DIGRAM

In addition to the above list DIGRAM has procedures for:

Identifying the smallest connected component containing a specific link
between two nodes
such that this node do not lie in theboundary between the component and the
remaining
nodes of the graph.

Finding the shortest paths between nodes.

Identifying the independence graph of marginal models.

Identifying the loglinear structure of marginal models. (A marginal model
does not have to be graphical
in the strictest sense. The marginal model of ABC in the ABC four-cycle
 

                           A ---- B
                           |      |
                           |      |
                           C------D

is a loglinear model, AB,AC,BC, with no higher order interaction.


4. Graph queries
----------------
isgraph(x), where x is any of connected, 
chordal, undirected, acyclic,tree, A-collapsible etc...    I do not
understand this queri

sep(A,B|S) are A and B separated by S				in DIGRAM

d-sep(A,B|S) are A and B d-separated by S (for DAGs)		not in DIGRAM





Svend Kreiner
Associate professor
Department of Biostatistics  
University of Copenhagen 
Blegdamsvej 3  
DK-2200 Copenhagen N
DENMARK

Email: S.Kreiner at biostat.ku.dk
Phone: (+45) 35 32 75 97     

Fax: (+45) 35 32 79 07