chordalGraph -- chordal completion of a graph

Synopsis

Usage:

chordalGraph(G)

chordalGraph(G,ordering)
Inputs:
- G, an instance of the type Graph
- ordering, a list, (optional)
Outputs:
- an instance of the type ChordalGraph, chordal graph that contains G as a subgraph

Description

This method finds a simple chordal completion of a given graph G. A chordal completion is a supergraph of G that is chordal. If a vertex ordering is given, it completes the graph using this ordering; otherwise it finds one using a minimum degree ordering heuristic.

i1 : G = wheelGraph(6)

o1 = Graph{0 => {1, 2, 3, 4, 5}}
           1 => {0, 2, 5}
           2 => {0, 1, 3}
           3 => {0, 2, 4}
           4 => {0, 3, 5}
           5 => {0, 1, 4}

o1 : Graph

i2 : chordalGraph G

o2 = ChordalGraph{1 => {2, 0, 5} }
                  2 => {0, 3, 5}
                  0 => {3, 4, 5}
                  3 => {4, 5}
                  4 => {5}
                  5 => {}

o2 : ChordalGraph

i3 : G = graph(toList(0..9),{
         {0,{6,7}},{1,{4,9}},{2,{3,5}},{3,{7,8}},
         {4,{5,8}},{5,{8}},{6,{8,9}},{7,{8}},{8,{9}} });

i4 : chordalGraph G

o4 = ChordalGraph{0 => {6, 7}    }
                  1 => {4, 9}
                  2 => {3, 5}
                  3 => {5, 7, 8}
                  4 => {5, 8, 9}
                  5 => {7, 8, 9}
                  6 => {7, 8, 9}
                  7 => {8, 9}
                  8 => {9}
                  9 => {}

o4 : ChordalGraph

Caveat

If the input is a digraph, it must be topologically ordered; no check is made.

Ways to use `chordalGraph` :

"chordalGraph(Digraph)"
"chordalGraph(Graph)"
"chordalGraph(Graph,List)"
"chordalGraph(ElimTree)" -- see ElimTree -- the elimination tree of a chordal graph

For the programmer

The object chordalGraph is a method function.