edu.bsu.cs.algorithm
Class PlanarityTesting

java.lang.Object
  |
  +--edu.bsu.cs.algorithm.Algorithm
        |
        +--edu.bsu.cs.algorithm.Fragments
              |
              +--edu.bsu.cs.algorithm.PlanarityTesting

Direct Known Subclasses:

BlocksMerger

public class PlanarityTesting

extends Fragments

An implementation of the Planarity Testing algorithm.

Since:

Jun 1999

Version:

21 Apr 2001

Author:

Adrian Heinz

Field Summary

Fields inherited from class edu.bsu.cs.algorithm.Fragments

startVertex

Constructor Summary

PlanarityTesting()

PlanarityTesting(JavaGraph jGraph, Vector inputs, Vector animation)

Method Summary

void	callOwnConstructor(JavaGraph jGraph, Vector inputs, Vector animation) This method is called by Jedit for any algorithm it executes and must be used in any working algorithm.
protected boolean	completelyMarked(JavaGraph myGraph) Returns true if all the vertices and edges are marked
protected boolean	doPlanarity(JavaGraph G) Core of the algorithm.
protected boolean	executePlanarity(JavaGraph G) Performrs the testing of planarity.
protected boolean	existDegreeFive(JavaGraph G) Checks if exist at least one vertex with degree five or less
Vector	getAllTheBlocks(JavaGraph G) Returns a vector will all the blocks of the graph.
protected void	planarityTesting(JavaGraph jGraph, Vector inputs, Vector animation) Called by the constructor to do all of the work
protected void	removeUnmark(JavaGraph source, JavaGraph target) Removes all the unmarked vertices and edges of auxGraph
protected void	showAllRegions() Shows all the regions of the graph.
protected void	showRegion(edu.bsu.cs.algorithm.Region myRegion) Shows regions in a text format.
protected void	thatPlanarityTesting()
protected int	theoremCheck(JavaGraph G) Find out if the graph satisfies any of the planarity theorems it returns 1 if G is planar, 2 if G is nonplanar and 0 if it is uncertain

Methods inherited from class edu.bsu.cs.algorithm.Fragments

amountOfFragments, amountOfMarkedVertices, amountOfUnmarkEdges, closeOutOfCyclePaths, executeFragments, existEdge, findCycle, fragments, getFragmentAt, isThisEdgeMarked, that, unMarkGraphAB

Methods inherited from class edu.bsu.cs.algorithm.Algorithm

getCode, getDescription, getName, getType, setCode, setDescription, setFromResources, setName, setType, succeeded, succeeded

Methods inherited from class java.lang.Object

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

Constructor Detail

PlanarityTesting

public PlanarityTesting()

PlanarityTesting

public PlanarityTesting(JavaGraph jGraph,
                        Vector inputs,
                        Vector animation)

Method Detail

thatPlanarityTesting

protected void thatPlanarityTesting()

planarityTesting

protected void planarityTesting(JavaGraph jGraph,
                                Vector inputs,
                                Vector animation)

Called by the constructor to do all of the work

existDegreeFive

protected boolean existDegreeFive(JavaGraph G)

Checks if exist at least one vertex with degree five or less

theoremCheck

protected int theoremCheck(JavaGraph G)

Find out if the graph satisfies any of the planarity theorems it returns 1 if G is planar, 2 if G is nonplanar and 0 if it is uncertain

removeUnmark

protected void removeUnmark(JavaGraph source,
                            JavaGraph target)

Removes all the unmarked vertices and edges of auxGraph

showRegion

protected void showRegion(edu.bsu.cs.algorithm.Region myRegion)

Shows regions in a text format. Just for debugging purposes

completelyMarked

protected boolean completelyMarked(JavaGraph myGraph)

Returns true if all the vertices and edges are marked

showAllRegions

protected void showAllRegions()

Shows all the regions of the graph. Just for debugging purposes

doPlanarity

protected boolean doPlanarity(JavaGraph G)

Core of the algorithm. It returns true if the graph is planar, false otherwise

executePlanarity

protected boolean executePlanarity(JavaGraph G)

Performrs the testing of planarity. This method can be called by the subclasses

getAllTheBlocks

public Vector getAllTheBlocks(JavaGraph G)

Returns a vector will all the blocks of the graph. This method can be called by exterior classes

callOwnConstructor

public void callOwnConstructor(JavaGraph jGraph,
                               Vector inputs,
                               Vector animation)

Description copied from class: Algorithm

This method is called by Jedit for any algorithm it executes and must be used in any working algorithm.

Overrides:

callOwnConstructor in class Fragments

Parameters:

jGraph - the edu.bsu.cs.graph.JavaGraph that the algorithm is performed on

inputs - a Vector of inputs that consists of

• An Integer, if the algorithm uses a single vertex as a starting point
• Two Integers if the algorithm uses two vertices as starting points
• A String if the algorithm starts off of typed input
• Nothing if the algorithm runs automatically on a graph

animation - a Vector that is filled with AnimObjects as the algorithm proceeds. It must be instantiated before this method is called.