gRapHD (version 0.2.5)

findEd: Finds add-eligible edges

Description

Finds the edges that can be added to a (strongly) triangulated graph such that the result is also (strongly) triangulated.

Usage

findEd(edges,p,previous=NULL,numCat,from=0,exact=FALSE,join=FALSE)

Arguments

edges

matrix with 2 columns, each row representing one edge, and each column one of the vertices in the edge.

p

number of vertices.

previous

result of a previous run of findEd.

numCat

vector with number of levels for each variable (0 if continuous).

from

initial vertex to be used in MCS.

exact

logical indicating if the exact algorithm for finding add-eligible edges is to be used. Default is FALSE.

join

logical indicating if the disjoint components can be joined. Default is FALSE.

Value

A list with:

edges.to.test

matrix (k by 5), with columns: 1 - first vertex of the tested edge 2 - second vertex (the two values are ordered) 3 - index for the separator in S 4 - change in the LR by adding this edge 5 - number of parameters for that edge

S

list with the separators.

Details

Returns all add-eligible edges for a given triangulated graph, that is, edges that preserve the triangulated property when added. In the case of a mixed graph, only edges that do not result in forbidden paths are returned. The argument from can be used to indicate the initial vertex used in the MCS algorithm. If 0, the first vertex is used. If exact is FALSE, the edge list may contain a few edges that are not add-eligible. Further tests (for example mcs) will be required before adding edges. Otherwise, the list contains only edges that preserve triangularity. That is, each edge that may be added to the graph such that the resulting graph is triangulated. For graphs with both discrete and continuous vertices, the graph should be triangulated and contain no forbidden paths, and the edges that may be added preserving both properties are returned. See Lauritzen (1996), p. 11-13.

References

Lauritzen, S.L. (1996) Graphical Models, Oxford University Press.

Examples

# NOT RUN {
edges <- matrix(c(1,2,2,3,2,4,2,5,2,6,3,4,4,5,5,6),ncol=2,byrow=TRUE)
addEligible <- findEd(edges=edges,p=6,previous=NULL,numCat=rep(0,6),
                      from=1)
#    > str(addEligible)
#    List of 2
#     $ edges: num [1:7, 1:5] 1 1 3 1 4 3 1 3 4 5 ...
#     $ S    :List of 6
#      ..$ : int 2
#      ..$ : int [1:2] 2 4
#      ..$ : int 2
#      ..$ : int [1:2] 2 5
#      ..$ : int 2
#      ..$ : int 2
#    > addEligible$edges
#         [,1] [,2] [,3] [,4] [,5]
#    [1,]    1    3    1    0    0
#    [2,]    1    4    1    0    0
#    [3,]    3    5    2    0    0
#    [4,]    1    5    3    0    0
#    [5,]    4    6    4    0    0
#    [6,]    3    6    5    0    0
#    [7,]    1    6    6    0    0

# the columns in addEligible$edges
#    1: first vertex in the edge
#    2: second vertex in the edge
#    3: index os the separator in addEligible$S
#    4: change in the LRT for the edge (used if previous != NULL)
#    5: number of parameters for the edge (used if previous != NULL)

# note that the edge 3-6 (row 6) is actually a "false positive". 
# If it's used from=3,4,5, or 6, this does not happen.
# }