lexicographic.dfs <- function (graph)
{
  nnodes = dim(graph)[2]
  orderSets = rep(1, nnodes) # all nodes are in set ID 1 to begin with
  for (i in 1:nnodes) {
    currentSet       = orderSets[i]                         # set ID to be redistributed
    nodesInSet       = c(1:nnodes)[orderSets == currentSet] # nodes in current set
    nodeNeighbors    = neighbors(graph, i)                  # all current neighbors
    setNeighbors     = intersect(nodesInSet, nodeNeighbors) # neighbors in current set
    setNonNeighbors  = setdiff(nodesInSet, nodeNeighbors)   # nodes in set that are not neighbors
    orderSets[setNeighbors] = max(orderSets) + 1            # move all neighbors to new set
    orderSets[setNonNeighbors] = max(orderSets) + 1         # move all non neighbors to new set
    orderSets[i] = currentSet                               # keep current node in own set
  }
  return (orderSets)
}

is.chordal <- function (graph)
{
  ordering = lexicographic.dfs(graph)
  n        = length(ordering)
  cliques  = cliques(as.igraph(graph))
  for (i in 1:(n-1)) {
    currentNeighbors = neighbors(graph, i)
    foundNeighbors = intersect(ordering[c((i+1):n)], currentNeighbors)
    if (!is.element(foundNeighbors, cliques)) { # <- does not work??? :(
      return (FALSE)
    }
  }
  return (TRUE)
}