process an undirected graph by traversing it,
applying Kruskal's algorithm and the related
TSP approxmation algorithm, and printing the
results of both algor 

 

Credits: This program implements Mark Weiss’s Random generatorclass to feed raw data into the program

import java.util.*;
public class A5
{

public static boolean LARGE = false;
/** process an undirected graph by traversing it,
applying Kruskal's algorithm and the related
TSP approxmation algorithm, and printing the
results of both algorithms.
@param g the graph
*/
private static void processGraph(TSPUndirectedGraph g) {
if (!g.isComplete()) {
System.out.println("Graph is not complete: test aborted");
System.out.println();
return; }
System.out.println("For the graph with adjacency matrix:");
g.traverse();
if (g.hasTriangleInequalityProperty())
System.out.print("The graph has");
else
System.out.print("... so the graph does not have");
System.out.println(" the triangle inequality property");
System.out.println();
System.out.println(" A minimum cost spanning tree:");
List v=g.kruskal();
g.traverseEdgeList(v,!LARGE);
System.out.println();
System.out.println(" The optimal TSP solution");
v=g.TSP();
g.traverseEdgeList(v,!LARGE);
System.out.println();
System.out.print(" A greedy approximation");
System.out.println(" to the optimal TSP solution");
v=g.GreedyTSPApprox();
g.traverseEdgeList(v,!LARGE);
System.out.println();
System.out.print(" Another approximation");
System.out.println(" to the optimal TSP solution");
v=g.NewTSPApprox();
g.traverseEdgeList(v,!LARGE);
System.out.println();
System.out.println(); }

private static void processLargeGraph(TSPUndirectedGraph g) {
if (!g.isComplete()) {
System.out.println("Graph is not complete: test aborted");
System.out.println();
return; }
System.out.print("For a graph with ");
System.out.println(g.getNumberOfVertices() + " vertices");
if (g.hasTriangleInequalityProperty())
System.out.print("The graph has");
else
System.out.print("... so the graph does not have");
System.out.println(" the triangle inequality property");
System.out.println();
System.out.println(" A minimum cost spanning tree:");
List v=g.kruskal();
g.traverseEdgeList(v,LARGE);
System.out.println();
System.out.print(" A greedy approximation");
System.out.println(" to the optimal TSP solution");
v=g.GreedyTSPApprox();
g.traverseEdgeList(v,LARGE);
System.out.println();
System.out.print(" Another approximation");
System.out.println(" to the optimal TSP solution");
v=g.NewTSPApprox();
g.traverseEdgeList(v,LARGE);
System.out.println();
System.out.println(); }

public static void main(String[] args) {
Random r = new Random(1);
int k,kk;
TSPUndirectedGraph g = new TSPUndirectedGraph(4);
processGraph(g);
g = new TSPUndirectedGraph(5);
for (k=1; k<5; k++)
g.setEdgeCost(k-1,k,1);
processGraph(g);
g = new TSPUndirectedGraph(4,r,1000);
processGraph(g);
g = new TSPUndirectedGraph(7,r,1000);
processGraph(g);
g = new TSPUndirectedGraph(r,7,1000);
processGraph(g);
g = new TSPUndirectedGraph(9,r,1000);
processGraph(g);
Random r2 = new Random(2);
g = new TSPUndirectedGraph(r2,9,100);
for (int i=0; i<9; i++)
for (int j=i; j<9; j++) {
int c = 100 + r2.nextInt(5);
g.setEdgeCost(i,j,c);
g.setEdgeCost(j,i,c); }
g.setEdgeCost(1,4,200);
processGraph(g);
g = new TSPUndirectedGraph(9,r2,1);
for (k=0; k<9; k++)
for (kk=k; kk<9; kk++)
g.setEdgeCost(k,kk,100);
for (k=0; k<8; k++)
g.setEdgeCost(k,k+1,10+k);
g.setEdgeCost(8,0,1000);
processGraph(g);
g = new TSPUndirectedGraph(r,50,1000);
processLargeGraph(g); }
}

import java.util.*;

/**
This implementation of a binary heap is primarily from the
Weiss text.
*/

public class BinaryHeap
{
public Comparable[] getData ()
{
return (array);
}

/** the number of elements in the heap */
protected int currentSize;
/** the array representing the heap */
protected Comparable[] array;



/** the default size of the array */
protected static final int DEFAULT_CAPACITY = 100;

/** The zero argument constructor builds
a heap of the default capacity
*/
public BinaryHeap() {
this(DEFAULT_CAPACITY); }

/**
This binary heap construtor builds
a heap of the given capacity
@param capacity the desired capacity
*/
public BinaryHeap(int capacity) {
currentSize=0;
array=new Comparable[capacity+1]; }

/**
This constructor is not from Weiss.
It takes a vector, converts the vector
to an array, and then calls buildHeap
to turn the array into a heap
@param v the vector
*/
public BinaryHeap(Vector v) {
this(v.size());
currentSize=v.size();
for (int i=0; i<v.size(); i++)
array[i+1]=(Comparable) v.get(i);
buildHeap(); }




/**
Empty the current queue
*/

public void makeEmpty() {
currentSize=0; }

/**
This method is not functional -- it
always returns false. It is provided
only for consistency with Weiss
@return a boolean value indicating
whether the queue is full
*/
public boolean isFull() {
return false; //??
}

/**
This method deterimines whether the
queue is empty
@return a boolean value indicating
whether the queue is empty
*/
public boolean isEmpty() {
return currentSize==0; }

/**
This method inserts an element
into a priority queue. Unlike
Weiss's corresponding method, it
does not check whether the queue
is full, and does not throw an
exception if it is.
@param x the element to insert
*/
// Otherwise the algorithm is that
// of Weiss
public void insert(Comparable x)
// throws Overflow
{
if (isFull())
{} // throw new Overflow();
int hole=++currentSize;
for (; hole>1 &&
x.compareTo(array[hole/2])<0;
hole/=2)
array[hole]=array[hole/2];
array[hole]=x; }

/**
This method finds but does not delete the
minimum element of the heap.
@return the minimum element
in the heap, according to the comparison
method for the implementation of Comparable
*/
public Comparable findMin() {
return array[1];
}

/**
This method deletes an element from
the heap.
@return the deleted element, which will be
the minimum element in the heap,
according to the comparison
method for the implementation of Comparable
*/
public Comparable deleteMin() {
if (isEmpty())
return null;
Comparable minItem=findMin();
array[1]=array[currentSize--];
percolateDown(1);
return minItem; }

/**
Move the element downward in the heap
that is originally located at a given position
@param hole the index representing the initial
position
*/
protected void percolateDown(int hole) {
int child;
Comparable tmp=array[hole];
for (; hole*2<=currentSize; hole=child) {
child=hole*2;
if (child!=currentSize &&
array[child+1].compareTo(array[child])<0)
child++;
if (array[child].compareTo(tmp)<0)
array[hole]=array[child];
else
break; }
array[hole]=tmp; }

/**
This method takes a binary tree without the
heap property, and gives it the heap property.
The resulting heap contains the same elements
as the original tree.
*/
public void buildHeap() {
for (int i=currentSize/2; i>0; i--)
percolateDown(i); }
}

// DisjSetsFast class
//
// CONSTRUCTION: with int representing initial number of sets
//
// ******************PUBLIC OPERATIONS*********************
// void union( root1, root2 ) --> Merge two sets
// int find( x ) --> Return set containing x
// ******************ERRORS********************************
// No error checking is performed

public class DisjSetsFast
{
/**
* Construct the disjoint sets object.
* @param numElements the initial number of disjoint sets.
*/
public DisjSetsFast( int numElements )
{
s = new int [ numElements ];
for( int i = 0; i < s.length; i++ )
s[ i ] = -1;
}
/**
* Union two disjoint sets using the height heuristic.
* For simplicity, we assume root1 and root2 are distinct
* and represent set names.
* @param root1 the root of set 1.
* @param root2 the root of set 2.
*/
public void union( int root1, int root2 )
{
if( s[ root2 ] < s[ root1 ] ) // root2 is deeper
s[ root1 ] = root2; // Make root2 new root
else
{
if( s[ root1 ] == s[ root2 ] )
s[ root1 ]--; // Update height if same
s[ root2 ] = root1; // Make root1 new root
}
}
/**
* Perform a find with path compression.
* Error checks omitted again for simplicity.
* @param x the element being searched for.
* @return the set containing x.
*/
public int find( int x )
{
if( s[ x ] < 0 )
return x;
else
return s[ x ] = find( s[ x ] );
}
private int [ ] s;

}

import java.util.*;
/** This class simply implements a priority queue
under that name, for consistency with the
Weiss implementation of Kruskal's algorithm.
It simply inherits from BinaryHeap without
adding any functionality other than a <code>size()</code>
method.
*/

public class PriorityQueue extends BinaryHeap
{
/** creates an empty priority queue
of a given capacity
@param capacity the capacity
*/
public PriorityQueue(int capacity) {
super(capacity); }

/** creates a priority queue and adds
all elements of a given vector to
the queue. The capacity of the
priority queue will be the size
of the vector -- no elements are
expected to be added
@param v the vector
*/
public PriorityQueue(Vector v) {
super(v); }

public int size() {
return this.currentSize; }

}

import java.util.Random;

// Random class
//
// CONSTRUCTION: with (a) no initializer or (b) an integer
// that specifies the initial state of the generator
//
// ******************PUBLIC OPERATIONS*********************
// Return a random number according to some distribution:
// int randomInt( ) --> Uniform, 1 to 2^31-1
// int random0_1( ) --> Uniform, 0 to 1
// int randomInt( int low, int high ) --> Uniform low..high
// long randomLong( long low, long high ) --> Uniform low..high
// void permute( Object [ ] a ) --> Randomly permutate
/**
* Random number class, using a 31-bit
* linear congruential generator.
* Note that java.util contains a class Random,
* so watch out for name conflicts.
* @author Mark Allen Weiss
*/
public class Random
{
private static final int A = 48271;
private static final int M = 2147483647;
private static final int Q = M / A;
private static final int R = M % A;
private long seed;
/**
* Construct this Random object with
* initial state obtained from system clock.
*/
public Random( )
{
this( (int) ( System.currentTimeMillis( ) % Integer.MAX_VALUE ) );
}
/**
* Construct this Random object with
* specified initial state.
* @param initialValue the initial state.
*/
public Random( int initialValue )
{
if( initialValue < 0 )
initialValue += M;
state = initialValue;
if( state == 0 )
state = 1;
seed = (long) initialValue;
}

/*This function was taken directly from the API and moved in this class for better Random functionality
@param n generates the next random integer
@return val a random int
*/
public int nextInt(int n) {
if (n<=0)
throw new IllegalArgumentException("n must be positive");
if ((n & -n) == n) // i.e., n is a power of 2
return (int)((n * (long)next(31)) >> 31);
int bits, val;
do {
bits = next(31);
val = bits % n;
} while(bits - val + (n-1) < 0);
return val;
}

/*This function was taken directly from the API and moved in this class for better Random functionality
@param used to help calulate Randome values
@return int
*/
public int next(int bits)
{
seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
return (int)(seed >>> (48 - bits));
}
/**
* Return a pseudorandom int, and change the
* internal state.
* @return the pseudorandom int.
*/
public int randomInt( )
{
int tmpState = A * ( state % Q ) - R * ( state / Q );
if( tmpState >= 0 )
state = tmpState;
else
state = tmpState + M;
return state;
}
/**
* Return a pseudorandom int, and change the
* internal state. DOES NOT WORK.
* @return the pseudorandom int.
*/
public int randomIntWRONG( )
{
return state = ( A * state ) % M;
}
/**
* Return a pseudorandom double in the open range 0..1
* and change the internal state.
* @return the pseudorandom double.
*/
public double random0_1( )
{
return (double) randomInt( ) / M;
}
/**
* Return an int in the closed range [low,high], and
* change the internal state.
* @param low the minimum value returned.
* @param high the maximum value returned.
* @return the pseudorandom int.
*/
public int randomInt( int low, int high )
{
double partitionSize = (double) M / ( high - low + 1 );
return (int) ( randomInt( ) / partitionSize ) + low;
}
/**
* Return an long in the closed range [low,high], and
* change the internal state.
* @param low the minimum value returned.
* @param high the maximum value returned.
* @return the pseudorandom long.
*/
public long randomLong( long low, long high )
{
long longVal = ( (long) randomInt( ) << 31 ) + randomInt( );
long longM = ( (long) M << 31 ) + M;
double partitionSize = (double) longM / ( high - low + 1 );
return (long) ( longVal / partitionSize ) + low;
}

}

import java.util.*;
import java.math.*;


/*
Author Daniel Haro
Program TSP solutions
premutation based on Kenneth H. Rosen's,
Discrete Mathematics and Its Applications
This program provide two seperate solution for the TSP problem.
***note the Approx method does not work
*/


class TSPUndirectedGraph extends UndirectedGraph
{

public TSPUndirectedGraph(int n)
{super(n);}

public TSPUndirectedGraph(int n, Random r,int maxCost)
{super(n,r,maxCost);}

public TSPUndirectedGraph(Random r, int n, int maxCost)
{super(r,n,maxCost);}


/*
An attemp to perform an pre prder traversal on a MST, This does not
work but I'm submiting it anyway in hope of partial credit.
I spent many hours actiually days trying different things for this
part all of which lead to dead end.
The idea here was to try to construct a graph by matching up destinations
and source and by keeping a stack, so when needed to back track, the edges
could simply be added to the path, This algorithm works only in speacial cases

@pram myList the list returned from kruskals
@return Vector the new path
*/
private Vector inOrderTraversal(Vector myList)
{
Stack last = new Stack();
int current = 0;
int next = 1;
Edge e1 = (Edge) myList.elementAt(current);
Edge e2 = (Edge) myList.elementAt(next);
Vector path = new Vector();
path.add(e1);

for(current = 0; current < myList.size() ; current++)
{
e1 = (Edge) myList.elementAt(current);
}
if(e1.getDest() == e2.getSource())
{
path.add(e2);
last.push(e1);
e1 = (Edge) myList.elementAt(next);
next++;
e2 = (Edge) myList.elementAt(next);

}
else
{
path.add(e1);
if(!last.empty())
e1 = (Edge) last.pop();
}
return path;
}

/*
This method does not work
Attempted to run kruskals on orginal graph then tryed to do a
in order traversal on it, the traversal is where the problem is
@return The ordered traversal, but fails so returna grabage Vector

*/
public List NewTSPApprox()
{
Vector myVector = new Vector();
Vector temp2 = new Vector();
Vector finalList = new Vector();
Comparable [] heapedData = null;
int i = 0;
int j = 0;
boolean test = false;
if(hasTriangleInequalityProperty())
{
Vector temp = new Vector();
temp = (Vector) kruskal();
//This part not working yet//////////
finalList = inOrderTraversal((Vector) temp);

//note to self////
//don't forget to add 0 node to the end of the list////
}
return (finalList);
}


/*
This function work properly
permutes all of the verticies, after each permutation a solution is
calculated, if the new solution is better then the old soltion the
the best solution is update and stored. After all permutaions the best
path is returned
@return bestPath
*/

public List TSP()
{

Vector output = new Vector();
Vector bestPath = new Vector();
Edge e1 = null;
List myVector = new Vector();
int [] a = new int[adjacency.length];
int temp;
int best = -1;
int numLeft = 1;
int i,j;
int N = adjacency.length ;
int total;

System.out.println("MY TSP");
if(adjacency.length > 10)
{
return null;
}
//set number of permutations n!
for ( int c1 = adjacency.length; c1 > 0; c1--)
{
numLeft = numLeft * c1;
}
//fill an array with citys number from 0 to x
//to be traversed
for(int c1 = 0; c1 < adjacency.length; c1++)
a[c1] = c1;
//traversal
while( numLeft >= 0)
{
for (i = N-2; i >= 0; i--)
{
if (a[i] < a[i+1])
{
int nextLarger = i+1;
for (j = i+2; j < N; j++)
{
if (a[j] > a[i]) //a[j].getCost() > a[i].getCost())
nextLarger = j;
}
temp = a[i];
a[i] = a[nextLarger];
a[nextLarger] = temp;
int left = i+1;
int right = N-1;
while (left < right)
{
temp = a[left];
a[left] = a[right];
a[right] = temp;
left++; right--;
}
break;
}
}
numLeft = numLeft - 1;

////////////////////////
//construct soulition//
//////////////////////
output.clear();
total = 0;
//creates edges and put them into a temp solution
for( int f1 = 0; f1 < a.length - 1; f1++)
output.add(new Edge(a[f1],a[f1+1],adjacency[(a[f1])][(a[f1+1])]));
//returns back to starting node
output.add(new Edge(a [a.length - 1],a[0],adjacency[(a[a.length -1 ])][a[0]]));
//calcs cost
for (int c1 = 0; c1 < output.size(); c1++)
{
e1 = (Edge) output.elementAt(c1);
total = total + e1.getCost();
}
//updates if best
if ( best == -1 || total <= best)
if( total > 0)
{
best = total;
bestPath.clear();
for (int c1 =0; c1 < output.size(); c1++)
{
e1 = (Edge) output.elementAt(c1);
bestPath.add(e1);
}
}
}
return bestPath;
}



/*
This function checks to see if a graph is complete or not
@return boolean true if graph is complete false otherwise

*/
public boolean isComplete()
{
for(int i = 0 ; i < adjacency.length; i++)
for(int j = 0; j< adjacency.length; j++)
if(i != j) //skips the case where a vertex would cycle on itself
if(adjacency[i][j] == 0)
return false;
return true;
}
/*
Checks for trianglar Inequality
@return boolean true if properity exist, false other wise
*/
public boolean hasTriangleInequalityProperty()
{
int [][] myMatrix = adjacency;
for (int a =0; a < myMatrix.length; a++)
for(int c =0; c < myMatrix.length; c++)
for(int b = 0; b < myMatrix.length; b++)
if( a != b && c != b && a < c) // skips previoulsly tested triangles and
//nodes that loop on them selves
if(myMatrix[a][b] + myMatrix[b][c] < myMatrix[a][c])
{ System.out.println("Triangle inequality failed at vertexs " +
a + " , " + b + " , " + c);
return false;
}
return true;
}
}

import java.util.*;

public class UndirectedGraph
{

protected int[][] adjacency;

protected int NUM_VERTICES;

public UndirectedGraph(int n) {
NUM_VERTICES=n;
adjacency=new int[n][n]; }

public UndirectedGraph(int n, Random r,int maxCost) {
int c; // an edge cost
NUM_VERTICES=n;
adjacency=new int[n][n];
for (int i=0; i<n; i++) {
for (int j=i+1; j<n; j++) {
c=1+r.nextInt(maxCost);
adjacency[i][j]=c;
adjacency[j][i]=c; }
adjacency[i][i]=0; } }

public UndirectedGraph(Random r, int n, int maxCost) {
int[] x,y; // for coordinates;
x = new int[n];
y = new int[n];
NUM_VERTICES=n;
adjacency=new int[n][n];

int MAX_COORD = maxCost * 5 / 7;

for (int i=0; i<n; i++) {
x[i] = r.nextInt(MAX_COORD);
y[i] = r.nextInt(MAX_COORD);
adjacency[i][i]=0; }

for (int i=0; i<n; i++) {
for (int j=i+1; j<n; j++) {
int diff1 = x[i]-x[j];
int diff2 = y[i]-y[j];
long c = Math.round(Math.ceil(
Math.sqrt(diff1*diff1+diff2*diff2)));
adjacency[i][j]=(int) c;
adjacency[j][i]=(int) c; } } }

public void traverse() {
int c; // an edge cost
String s; // its String version
for (int i=0; i<NUM_VERTICES; i++) {
for (int j=0; j<NUM_VERTICES; j++) {
c=adjacency[i][j];
s=" "+c;
System.out.print(
s.substring(s.length()-6,s.length())); }
System.out.println(""); } }

/**
@return the number of vertices in the graph
*/
public int getNumberOfVertices() {
return NUM_VERTICES; }

/**
Find an edge given its source and destination.
No check is made for illegal vertex values.
@return the edge.
*/
protected Edge getEdge(int source, int dest) {
return new Edge(source,dest,
adjacency[source][dest]); }

/**
A mutator, but one that might sometimes be necessary
in some applications, that updates the cost of a given
undirected edge. It allows the two endpoints of the
vertices to be equal. No check is made for illegal
vertex values.
@param source one vertex of the edge
@param dest another vertex of the edge
@param cost the new cost
*/
public void setEdgeCost(int source, int dest, int cost) {
adjacency[source][dest] = cost;
adjacency[dest][source] = cost; }

/** Construct a priority queue containing the
edges of a given graph.
@return the priority queue
*/
// note that since the graph is undirected, only
// half the adjacency matrix needs to be read in
protected PriorityQueue readGraphIntoHeap() {
int n=NUM_VERTICES;
Vector v=new Vector(n*n);
for (int i=0; i<n; i++)
for (int j=i+1; j<n; j++) {
Edge e = getEdge(i,j);
if (e.getCost() != 0)
v.add(getEdge(i,j)); }
return new PriorityQueue(v); }

/**
Constructs a minimum cost spanning tree
for the graph
@return a Vector containing the edges
in the spaning tree
*/
// Uses Kruskal's algorithm. This method
// is that of Weiss, p. 324, with a few
// minor changes (e.g, vertices and
// equivalence classes are represented
// by integers).

public List kruskal() {
int edgesAccepted=0;
Vector output=new Vector();
DisjSetsFast s;
PriorityQueue h;
int uset,vset; // result of s.find
Edge e;
h=readGraphIntoHeap(); // calls buildHeap
if (h.size() < NUM_VERTICES)
return output;
s = new DisjSetsFast(NUM_VERTICES);
edgesAccepted=0;
while (edgesAccepted < NUM_VERTICES-1) {
e=(Edge) h.deleteMin();
uset=s.find(e.getSource());
vset=s.find(e.getDest());
if (uset != vset) {
edgesAccepted++;
s.union(uset,vset);
output.add(e); } }
return output; }

/**
Constructs a list of edges representing
an approximate solution to the TSP instance
for the graph
@return the list of edges, or an empty list
if no approximation can be found
*/
// Uses a greedy algorithm is similar to Kruskal's
// The edges are inspected in nondecreasing order
// of cost, and an edge is included in the output
// iff it does not complete a cycle, and both
// endpoints have degree less than 2. For ease
// in checking this (and in finding the last
// edge of the cycle), an array "degree" is
// maintained containing the degrees of each node
// in the solution
// Note that partially constructed solutions may
// be disconnected subgraphs, as in Kruskal's
// algorithm.
// The first n-1 edges of the output cycle are
// constructed this way, and the final edge
// is constructed from the two remaining
// endpoints of degree 1.
public List GreedyTSPApprox() {
int edgesAccepted=0;
int[] degree=new int[NUM_VERTICES];
Vector output=new Vector();
DisjSetsFast s;
PriorityQueue h;
int uset,vset; // result of s.find
int u,v; // vertices
Edge e;
h=readGraphIntoHeap(); // calls buildHeap
s = new DisjSetsFast(NUM_VERTICES);
edgesAccepted=0;
while (edgesAccepted < NUM_VERTICES-1) {
e=(Edge) h.deleteMin();
if (e == null)
return new Vector();
u=e.getSource();
v=e.getDest();
uset=s.find(u);
vset=s.find(v);
if (uset != vset && degree[u]<2 && degree[v]<2) {
edgesAccepted++;
s.union(uset,vset);
degree[u]++;
degree[v]++;
output.add(e); } }
u=-1; // will be endpoints
v=-1; // of the last edge
int i=0; // find these endpoints (of degree < 2)
while (u==-1) {
if (degree[i]<2)
u=i;
i++; }
while (v==-1) {
if (degree[i]<2)
v=i;
i++; }
output.add(new Edge(u,v,adjacency[u][v]));
return output; }

/**
Takes a vector of edges and prints them all
to standard output. Prints the cost
of each edge, as well as the total cost.
It assumes that the total cost is an appropriate
value for a <code>int</code>.
@ param v the vector of edges
@ return the total cost
*/
public static int traverseEdgeList(List v, boolean isDetailWanted) {
Edge e=null;
int totalCost=0;
Iterator it = v.iterator();
while (it.hasNext()) {
e=(Edge) it.next();
totalCost+=e.getCost();
System.out.print(e.getSource());
System.out.print("<->");
System.out.print(e.getDest());
if (isDetailWanted) {
System.out.print(", cost ");
System.out.println(e.getCost()); }
else
System.out.print(" "); }
System.out.print("total cost: ");
System.out.println(totalCost);
return totalCost; }


/** an inner class for representing edges
*/
protected class Edge implements Comparable {
int source;
int dest;
int cost;
boolean visted = false;
/** a basic edge constructor
@param s the desired source vertex
@param d the desired destination vertex
@param c the desired cost
*/

public void vist()
{
visted = true;
}
public boolean done()
{
return visted;
}
public void reset ()
{
visted = false;
}
public Edge(int s, int d, int c) {
source=s;
dest=d;
cost=c; }
/**
@return the source vertex of an edge
*/
int getSource() {
return source; }
/**
@return the destination vertex of an edge
*/
int getDest() {
return dest; }

/**
@return the cost of an edge
*/

int getCost() {
return cost; }

/**
the comparison method for edges --
it simply compares costs
@param e the edge
@return an integer with the
conventional interpretation for
compareTo(Object)
*/
public int compareTo(Object e) {
int ecost=((Edge) e).getCost();
if (cost<ecost)
return -1;
else if (cost>ecost)
return 1;
else
return 0; }
} // end Edge

}

***RESULTS PAGE

 

Graph is not complete: test aborted
Graph is not complete: test aborted
For the graph with adjacency matrix:
0 375 479 725
375 0 321 628
479 321 0 145
725 628 145 0
Triangle inequality failed at vertexs 0 , 2 , 3
... so the graph does not have the triangle inequality property
A minimum cost spanning tree:
2<->3, cost 145
1<->2, cost 321
0<->1, cost 375
total cost: 841
The optimal TSP solution
MY TSP
3<->2, cost 145
2<->1, cost 321
1<->0, cost 375
0<->3, cost 725
total cost: 1566
A greedy approximation to the optimal TSP solution
2<->3, cost 145
1<->2, cost 321
0<->1, cost 375
0<->3, cost 725
total cost: 1566
Another approximation to the optimal TSP solution
Triangle inequality failed at vertexs 0 , 2 , 3
total cost: 0

For the graph with adjacency matrix:
0 747 825 353 454 382 726
747 0 279 82 20 315 315
825 279 0 493 107 333 356
353 82 493 0 879 539 817
454 20 107 879 0 978 708
382 315 333 539 978 0 981
726 315 356 817 708 981 0
Triangle inequality failed at vertexs 0 , 3 , 1
... so the graph does not have the triangle inequality property
A minimum cost spanning tree:
1<->4, cost 20
1<->3, cost 82
2<->4, cost 107
1<->5, cost 315
1<->6, cost 315
0<->3, cost 353
total cost: 1192
The optimal TSP solution
MY TSP
6<->2, cost 356
2<->4, cost 107
4<->1, cost 20
1<->3, cost 82
3<->5, cost 539
5<->0, cost 382
0<->6, cost 726
total cost: 2212
A greedy approximation to the optimal TSP solution
1<->4, cost 20
1<->3, cost 82
2<->4, cost 107
2<->5, cost 333
0<->3, cost 353
0<->6, cost 726
5<->6, cost 981
total cost: 2602
Another approximation to the optimal TSP solution
Triangle inequality failed at vertexs 0 , 3 , 1
total cost: 0

For the graph with adjacency matrix:
0 585 594 327 623 389 383
585 0 78 282 235 197 238
594 78 0 317 158 212 282
327 282 317 0 412 118 56
623 235 158 412 0 294 393
389 197 212 118 294 0 110
383 238 282 56 393 110 0
The graph has the triangle inequality property
A minimum cost spanning tree:
3<->6, cost 56
1<->2, cost 78
5<->6, cost 110
2<->4, cost 158
1<->5, cost 197
0<->3, cost 327
total cost: 926
The optimal TSP solution
MY TSP
6<->3, cost 56
3<->0, cost 327
0<->5, cost 389
5<->4, cost 294
4<->2, cost 158
2<->1, cost 78
1<->6, cost 238
total cost: 1540
A greedy approximation to the optimal TSP solution
3<->6, cost 56
1<->2, cost 78
5<->6, cost 110
2<->4, cost 158
1<->5, cost 197
0<->3, cost 327
0<->4, cost 623
total cost: 1549
Another approximation to the optimal TSP solution
3<->6, cost 56
0<->3, cost 327
total cost: 383

For the graph with adjacency matrix:
0 364 288 3 172 937 481 524 372
364 0 195 996 682 216 919 607 989
288 195 0 352 607 920 472 890 456
3 996 352 0 149 24 403 144 791
172 682 607 149 0 79 261 831 557
937 216 920 24 79 0 292 102 193
481 919 472 403 261 292 0 85 321
524 607 890 144 831 102 85 0 473
372 989 456 791 557 193 321 473 0
Triangle inequality failed at vertexs 0 , 3 , 4
... so the graph does not have the triangle inequality property
A minimum cost spanning tree:
0<->3, cost 3
3<->5, cost 24
4<->5, cost 79
6<->7, cost 85
5<->7, cost 102
5<->8, cost 193
1<->2, cost 195
1<->5, cost 216
total cost: 897
The optimal TSP solution
MY TSP
8<->6, cost 321
6<->7, cost 85
7<->3, cost 144
3<->0, cost 3
0<->4, cost 172
4<->5, cost 79
5<->1, cost 216
1<->2, cost 195
2<->8, cost 456
total cost: 1671
A greedy approximation to the optimal TSP solution
0<->3, cost 3
3<->5, cost 24
4<->5, cost 79
6<->7, cost 85
1<->2, cost 195
4<->6, cost 261
0<->2, cost 288
7<->8, cost 473
1<->8, cost 989
total cost: 2397
Another approximation to the optimal TSP solution
Triangle inequality failed at vertexs 0 , 3 , 4
total cost: 0

For the graph with adjacency matrix:
101 103 102 104 101 104 100 104 104
103 104 101 101 200 101 101 101 100
102 101 103 101 102 100 101 103 102
104 101 101 103 102 103 101 104 101
101 200 102 102 103 102 100 100 101
104 101 100 103 102 104 104 100 100
100 101 101 101 100 104 102 102 104
104 101 103 104 100 100 102 102 104
104 100 102 101 101 100 104 104 104
The graph has the triangle inequality property
A minimum cost spanning tree:
5<->7, cost 100
5<->8, cost 100
2<->5, cost 100
0<->6, cost 100
4<->6, cost 100
4<->7, cost 100
1<->8, cost 100
2<->3, cost 101
total cost: 801
The optimal TSP solution
MY TSP
8<->5, cost 100
5<->7, cost 100
7<->4, cost 100
4<->6, cost 100
6<->0, cost 100
0<->2, cost 102
2<->3, cost 101
3<->1, cost 101
1<->8, cost 100
total cost: 904
A greedy approximation to the optimal TSP solution
5<->7, cost 100
5<->8, cost 100
0<->6, cost 100
4<->6, cost 100
4<->7, cost 100
1<->8, cost 100
2<->3, cost 101
1<->2, cost 101
0<->3, cost 104
total cost: 906
Another approximation to the optimal TSP solution
5<->7, cost 100
2<->3, cost 101
total cost: 201

For the graph with adjacency matrix:
100 10 100 100 100 100 100 100 1000
10 100 11 100 100 100 100 100 100
100 11 100 12 100 100 100 100 100
100 100 12 100 13 100 100 100 100
100 100 100 13 100 14 100 100 100
100 100 100 100 14 100 15 100 100
100 100 100 100 100 15 100 16 100
100 100 100 100 100 100 16 100 17
1000 100 100 100 100 100 100 17 100
Triangle inequality failed at vertexs 0 , 1 , 2
... so the graph does not have the triangle inequality property
A minimum cost spanning tree:
0<->1, cost 10
1<->2, cost 11
2<->3, cost 12
3<->4, cost 13
4<->5, cost 14
5<->6, cost 15
6<->7, cost 16
7<->8, cost 17
total cost: 108
The optimal TSP solution
MY TSP
8<->7, cost 17
7<->0, cost 100
0<->1, cost 10
1<->2, cost 11
2<->3, cost 12
3<->4, cost 13
4<->5, cost 14
5<->6, cost 15
6<->8, cost 100
total cost: 292
A greedy approximation to the optimal TSP solution
0<->1, cost 10
1<->2, cost 11
2<->3, cost 12
3<->4, cost 13
4<->5, cost 14
5<->6, cost 15
6<->7, cost 16
7<->8, cost 17
0<->8, cost 1000
total cost: 1108
Another approximation to the optimal TSP solution
Triangle inequality failed at vertexs 0 , 1 , 2
total cost: 0

For a graph with 50 vertices
The graph has the triangle inequality property
A minimum cost spanning tree:
4<->8 22<->29 15<->22 19<->49 9<->21 6<->27 11<->48 0<->35 13<->38 19<->33 10<->14 1<->40 42<->45 5<->28 2<->31 21<->36 10<->22 17<->21 24<->32 18<->43 25<->49 7<->24 46<->47 20<->23 32<->39 16<->18 9<->41 2<->3 34<->42 11<->36 36<->39 11<->12 1<->8 18<->23 13<->41 5<->34 42<->44 15<->37 17<->46 20<->45 14<->38 4<->25 3<->37 27<->31 27<->35 4<->24 28<->49 26<->30 26<->31 total cost: 3519
A greedy approximation to the optimal TSP solution
4<->8 22<->29 15<->22 19<->49 9<->21 6<->27 11<->48 0<->35 13<->38 19<->33 10<->14 1<->40 42<->45 5<->28 2<->31 21<->36 24<->32 18<->43 10<->29 25<->49 7<->24 46<->47 20<->23 32<->39 9<->17 16<->18 2<->3 34<->42 11<->36 1<->8 13<->41 12<->39 7<->17 5<->34 15<->37 44<->45 16<->23 14<->38 4<->25 3<->37 27<->31 41<->46 33<->47 26<->30 6<->35 26<->43 20<->44 12<->40 0<->30 28<->48 total cost: 4774
Another approximation to the optimal TSP solution
4<->8 26<->31 total cost: 186