edu.bsu.cs.algorithm
Class Fragments

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

Direct Known Subclasses:

PlanarityTesting

public class Fragments

extends Algorithm

An animated implementation of the Fragments algorithm.

Since:

May 1999

Version:

21 Apr 2001

Author:

Adrian Heinz

Field Summary

protected int

startVertex

Constructor Summary

Fragments()

Fragments(JavaGraph jGraph, Vector inputs, Vector animation)

Method Summary

protected int	amountOfFragments()
protected int	amountOfMarkedVertices(JavaGraph G) Returns the number of marked vertices in G
protected int	amountOfUnmarkEdges(JavaGraph G, int vertexNumber) Returns the number of edges that are incident to vertexNumber and are not martked
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 JavaGraph	closeOutOfCyclePaths(JavaGraph G) Marks all the edges of the vertices that cannot be in the cycle, this avoids getting stacked .
protected int	executeFragments(JavaGraph jGraph, JavaGraph myCycle)
protected boolean	existEdge(JavaGraph myGraph, int v1, int v2)
protected JavaGraph	findCycle(JavaGraph jGraph) Finds any cycle in the graph
protected void	fragments(JavaGraph jGraph, Vector inputs, Vector animation) Called by the constructor to do all of the work
protected JavaGraph	getFragmentAt(int i) Returns the fragment contain at position i
protected boolean	isThisEdgeMarked(JavaGraph G, int x, int y) Returns true if the edge x->y or y->x is marked, false otherwise
protected void	that()
protected JavaGraph	unMarkGraphAB(JavaGraph target, JavaGraph B, JavaGraph C) Unmark all the edges and vertices in A which are marked in B.

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

Field Detail

startVertex

protected int startVertex

Constructor Detail

Fragments

public Fragments()

Fragments

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

Method Detail

that

protected void that()

fragments

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

Called by the constructor to do all of the work

getFragmentAt

protected JavaGraph getFragmentAt(int i)

Returns the fragment contain at position i

amountOfFragments

protected int amountOfFragments()

existEdge

protected boolean existEdge(JavaGraph myGraph,
                            int v1,
                            int v2)

amountOfUnmarkEdges

protected int amountOfUnmarkEdges(JavaGraph G,
                                  int vertexNumber)

Returns the number of edges that are incident to vertexNumber and are not martked

closeOutOfCyclePaths

protected JavaGraph closeOutOfCyclePaths(JavaGraph G)

Marks all the edges of the vertices that cannot be in the cycle, this avoids getting stacked . The value of startVertex tell us the number of the vertex in which we need to start in order to find the cycle.

findCycle

protected JavaGraph findCycle(JavaGraph jGraph)

Finds any cycle in the graph

unMarkGraphAB

protected JavaGraph unMarkGraphAB(JavaGraph target,
                                  JavaGraph B,
                                  JavaGraph C)

Unmark all the edges and vertices in A which are marked in B. However, if a vertex is mark in C, then it will not be modified.

amountOfMarkedVertices

protected int amountOfMarkedVertices(JavaGraph G)

Returns the number of marked vertices in G

executeFragments

protected int executeFragments(JavaGraph jGraph,
                               JavaGraph myCycle)

isThisEdgeMarked

protected boolean isThisEdgeMarked(JavaGraph G,
                                   int x,
                                   int y)

Returns true if the edge x->y or y->x is marked, false otherwise

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.

Specified by:

callOwnConstructor in class Algorithm

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.