[R--gR] Graph computations

[Steffen Lilholt Lauritzen]

Dear Fritz (and others in gR-sig),

Below I have tried to compile a list of things I would like to be able
to do with graphs. Some of them may need a little explanation, but I
thought the first thing to do was to get some key words down.

Ideally, I would for each describe what it takes as input and what it
returns as output, but this may be done in a second round, or I can
explain to someone who actually would like to implement it.

The list is "off the top of my head" so I may have missed out many and
some may be less central. But hopefully the list can provide inspiration
to the gRaph working group.

Please will others supplement

Best regards
Steffen
-- 
Steffen L. Lauritzen
Department of Mathematical Sciences, Aalborg University
Fredrik Bajers Vej 7G, DK-9220 Aalborg, Denmark
phone: +45 9635 8858; fax: +45 9815 8129
email: steffen at math.auc.dk; URL: http://www.math.auc.dk/~steffen
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Computations with graphs:
-------------------------
1. Visual display and interactions with graphs

Add, delete, nodes and links

Move nodes around, links following

Label and type nodes and links (e.g. nodes can be square, diamond,
circle, oval, double circle, hollow, filled) links can be directed,
bidirected undirected, coloured, thin, thick, etc. 

See eg HUGIN Lite (freeware) for a GUI with some (but not all) of these
features
http://www.hugin.com

Good printing facilities for graphs

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

Compute simple graph things like

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

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

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


4. Graph queries
----------------
isgraph(x), where x is any of connected, chordal, undirected, acyclic,
tree, A-collapsible etc...

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