alun.graph
Class Decomposition<V>

java.lang.Object
  alun.graph.AbstractGraph<V,E>
      alun.graph.Network<V,E>
          alun.graph.DirectedNetwork<java.util.Set<V>,java.util.Set<V>>
              alun.graph.Decomposition<V>

All Implemented Interfaces:

Graph<java.util.Set<V>,java.util.Set<V>>, MutableGraph<java.util.Set<V>,java.util.Set<V>>

public class Decomposition<V>
extends DirectedNetwork<java.util.Set<V>,java.util.Set<V>>

A Decomposition is a directed graph of sets of vertices of a given graph. Each set contains the vertices in a prime subgraph of the given graph. Each set is connected forward to one other set such that the intersection of the two sets is equal to the intersection of the first set with all other sets later than it in the partial ordering. If the given graph is triangulated then the sets will contain its maximal cliques, and viewed as an undirected graph the Decomposition is a junction tree. The iterator of the vertex set obtained by a call to getVertices() iterates over the prime subgraphs, or cliques, in an order such that running intersection property holds. This is an implementation of the lexicographic search method of Leimer (1992), Discrete Mathematics, 113, 1-25. In peeling terms, as per Thompson, Cannings and Skolnick (1978), iterating over the set of vertices of the Decomposition gives the correctly ordered "invol" sets for a peeling sequence.

Constructor Summary

Decomposition(Graph<V,E> g)

Decomposition(Graph<V,E> h, java.util.Collection<? extends V> kk)

Method Summary

static <T,D> boolean	isClique(Graph<T,D> g, java.util.Set<T> xx)
static <T,D> boolean	isTriangulated(Graph<T,D> g)
DirectedNetwork<java.util.Set<V>,java.util.Set<V>>	junctionTree()
static <T,D> DirectedNetwork<java.util.Set<T>,java.util.Set<T>>	junctionTree(Graph<T,D> g)
static void	main(java.lang.String[] args) Test main.

Methods inherited from class alun.graph.DirectedNetwork

getEdges, getNeighbours, next, toString

Methods inherited from class alun.graph.Network

connect, connection, nConnections, read, read, readAsIntegers, readAsIntegers

Methods inherited from class alun.graph.AbstractGraph

add, clear, connect, connects, contains, disconnect, disconnect, getVertices, inNeighbours, outNeighbours, remove

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface alun.graph.MutableGraph

add, clear, connect, disconnect, remove

Methods inherited from interface alun.graph.Graph

connects, contains, getVertices, inNeighbours, outNeighbours

Constructor Detail

Decomposition

public Decomposition(Graph<V,E> h,
                     java.util.Collection<? extends V> kk)

Decomposition

public Decomposition(Graph<V,E> g)

Method Detail

junctionTree

public DirectedNetwork<java.util.Set<V>,java.util.Set<V>> junctionTree()

isTriangulated

public static <T,D> boolean isTriangulated(Graph<T,D> g)

junctionTree

public static <T,D> DirectedNetwork<java.util.Set<T>,java.util.Set<T>> junctionTree(Graph<T,D> g)

isClique

public static <T,D> boolean isClique(Graph<T,D> g,
                                     java.util.Set<T> xx)

main

public static void main(java.lang.String[] args)

Test main.