CHORDAL GRAPHS
----------------------------------------------------------------------
# RECOGNITION

from graphtheory.chordality.peotools import find_peo_mcs
from graphtheory.chordality.peotools import find_maximum_clique_peo
from graphtheory.chordality.peotools import find_all_maximal_cliques
from graphtheory.chordality.peotools import is_peo1, is_peo2

order = find_peo_mcs(G)   # if G is not chordal, then 'order' is not a PEO
assert is_peo1(G, order)   # testing PEO, O(V+E) time
assert is_peo2(G, order)   # testing PEO, O(V+E) time

max_clique = find_maximum_clique_peo(G, order)   # G have to be chordal
print ( max_clique )   # a set of nodes
treewidth = len(max_clique) - 1

cliques = find_all_maximal_cliques(G, order)   # G have to be chordal
print ( cliques )   # a list with sets
----------------------------------------------------------------------
# GENERATORS

from graphtheory.structures.edges import Edge
from graphtheory.structures.graphs import Graph
from graphtheory.chordality.chordaltools import make_random_ktree
from graphtheory.chordality.chordaltools import make_random_chordal

G = make_random_ktree(n=10, k=5)   # PEO = range(n)
G = make_random_chordal(n=10)   # PEO = range(n)
----------------------------------------------------------------------
# MINIMUM DEGREE ORDERING OF CHORDAL GRAPHS

from graphtheory.chordality.mdotools import find_mdo
from graphtheory.chordality.mdotools import find_maximum_clique_mdo

order = find_mdo(G)   # O(V+E) time
print ( order )   # list of nodes (MDO)
max_clique = find_maximum_clique_mdo(G)   # O(V+E) time
print ( max_clique )   # a set of nodes
----------------------------------------------------------------------
# TREE DECOMPOSITION OF CHORDAL GRAPHS

from graphtheory.structures.edges import Edge
from graphtheory.structures.graphs import Graph
from graphtheory.chordality.peotools import find_peo_mcs
from graphtheory.chordality.tdtools import find_td_chordal

G = make_random_chordal(n)   # G is a chordal graph
order = find_peo_mcs(G)   # finding PEO
T = find_td_chordal(G, order)   # finding a tree decomposition
assert isinstance(T, Graph)
bags = list(T.iternodes())   # a list of tuples
treewidth = max(len(bag) for bag in bags) - 1
----------------------------------------------------------------------
# TREE DECOMPOSITION OF GENERAL GRAPHS

from graphtheory.chordality.tdtools import find_td_order
from graphtheory.chordality.tdtools import find_treewidth_min_deg # upper bound
from graphtheory.chordality.tdtools import find_treewidth_mmd # lower bound

# G is a general connected undirected graph.
# 'order' is a selected sequence of nodes.

T = find_td_order(G, order)   # finding a tree decomposition (heuristic)
treewidth = max(len(bag) for bag in bags) - 1

treewidth, order = find_treewidth_min_deg(G) # upper bound for treewidth

treewidth, order = find_treewidth_mmd(G) # lower bound for treewidth
----------------------------------------------------------------------
EOF
