edu.bsu.cs.algorithm
Class CanonicalOrdering

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

Direct Known Subclasses:

PlanarityDrawing

public class CanonicalOrdering

extends MaximalPlanar

An animated implementation of the Canonical Ordering algorithm.

Since:

Feb 2001

Version:

21 Apr 2001

Author:

Adrian Heinz

Field Summary

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

auxListRegions, firstVertexEdge, secondVertexEdge

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

firstVertexEdgeBD, secondVertexEdgeBD

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

startVertex

Constructor Summary

CanonicalOrdering()

CanonicalOrdering(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 void	CanonicalOrdering(JavaGraph jGraph, Vector inputs, Vector animation) Called by the constructor to do all of the work
protected edu.bsu.cs.algorithm.Region	findTheCanonical(JavaGraph jGraph) Core of the algorithm.
protected void	generateRegionsForOrderFour() In the case of a Graph with 4 vertices, Planarity Testing will not generate the regions, therefore we have to create them
protected edu.bsu.cs.algorithm.Region	insertRegionAt(JavaGraph jGraph, edu.bsu.cs.algorithm.Region a, edu.bsu.cs.algorithm.Region b, int v) Inserts region b into a replacing vertex v of a
protected void	thatCanonicalOrdering()
protected void	updateListRegionCanonical(Vector theRegions) In the case of being called from an external class, the regions have to be updated

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

addDummyEdges, addTheSameEdges, MaximalPlanar, regionsAfterDummyEdgesAdded, thatMaximalPlanar, updateListRegionsForMaximal

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

BlocksMerger, executeBlocksMerger, thatBlocksMerger

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

completelyMarked, doPlanarity, executePlanarity, existDegreeFive, getAllTheBlocks, planarityTesting, removeUnmark, showAllRegions, showRegion, thatPlanarityTesting, theoremCheck

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

CanonicalOrdering

public CanonicalOrdering()

CanonicalOrdering

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

Method Detail

thatCanonicalOrdering

protected void thatCanonicalOrdering()

generateRegionsForOrderFour

protected void generateRegionsForOrderFour()

In the case of a Graph with 4 vertices, Planarity Testing will not generate the regions, therefore we have to create them

CanonicalOrdering

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

Called by the constructor to do all of the work

insertRegionAt

protected edu.bsu.cs.algorithm.Region insertRegionAt(JavaGraph jGraph,
                                                     edu.bsu.cs.algorithm.Region a,
                                                     edu.bsu.cs.algorithm.Region b,
                                                     int v)

Inserts region b into a replacing vertex v of a

updateListRegionCanonical

protected void updateListRegionCanonical(Vector theRegions)

In the case of being called from an external class, the regions have to be updated

findTheCanonical

protected edu.bsu.cs.algorithm.Region findTheCanonical(JavaGraph jGraph)

Core of the algorithm. It finds the canonical ordering of a maximal planar graph jGraph

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 MaximalPlanar

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.