Module com.aoapps.hodgepodge

Package com.aoapps.hodgepodge.graph

Class SymmetricAcyclicGraphChecker<V,Ex extends Exception>

java.lang.Object

com.aoapps.hodgepodge.graph.SymmetricAcyclicGraphChecker<V,Ex>

Type Parameters:

Ex - An arbitrary exception type that may be thrown

All Implemented Interfaces:

GraphChecker<Ex>

public class SymmetricAcyclicGraphChecker<V,Ex extends Exception>
extends Object
implements GraphChecker<Ex>

A symmetric directed acyclic graph checker.

Author:

AO Industries, Inc.

Constructor Summary

Constructors

Constructor	Description
SymmetricAcyclicGraphChecker(SymmetricMultiGraph<V,?,? extends Ex> graph, boolean isForward)

Method Summary

Modifier and Type	Method	Description
void	checkGraph()	Test the graph for cycles and makes sure that all connections are consistent with back connections.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

SymmetricAcyclicGraphChecker

public SymmetricAcyclicGraphChecker(SymmetricMultiGraph<V,?,? extends Ex> graph,
 boolean isForward)

Method Details

checkGraph

public void checkGraph()
                throws AsymmetricException,
CycleException,
Ex

Test the graph for cycles and makes sure that all connections are consistent with back connections.

Cycle algorithm adapted from: http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/depthSearch.htm http://www.eecs.berkeley.edu/~kamil/teaching/sp03/041403.pdf

In the case of a multigraph, any number of edges one direction is considered a match to any number of edges back. The number does not need to be equal.

Specified by:

checkGraph in interface GraphChecker<V>

Throws:

AsymmetricException - where the edges are not symmetric

CycleException - if there is a cycle in the graph

Ex