Redundancy Checking In Java
(see also the C++ solution)
import java.io.*;
import java.util.*;
class Cell
{
Object object;
Cell next;
Cell(Object obj, Cell lst) { object = obj; next = lst; }
Object getObject() { return object; }
void setNext(Cell lst) { next = lst; }
Cell getNext() { return next; }
}
class Stacker
{
Cell head;
Stacker() { head = null; }
void push(Object obj)
{
if (obj == null) return;
Cell h = new Cell(obj, head);
head = h;
}
Object pop()
{
if (head == null) return null;
Object obj = head.getObject();
head = head.getNext();
return obj;
}
void display()
{
if (head == null) { System.out.println("(empty)"); return; }
for (Cell t=head ; t != null ; t=t.getNext())
((City)(t.getObject())).city();
System.out.println();
}
boolean empty() { return head == null; }
}
class City
{
int cty;
int prnt;
City (int c, int p) { cty = c; prnt = p; }
int parent() { return prnt; }
int city() { return cty; }
}
public class Cycles
{
/***-------------------------------------------------***/
/*** Redundancy: ***/
/*** Input: A network (n by n array of 0-1 values) ***/
/*** A number of cities (n above) ***/
/*** Output: 1 if network is redundant ***/
/*** 0 otherwise ***/
/*** Checks network links for redundant connections ***/
/***-------------------------------------------------***/
static int redundancy(boolean links[][], int cities)
{
Stacker s = new Stacker();
boolean visited[] = new boolean[cities+1];
int i;
City current;
s.push(new City(0, -1));
while (!s.empty())
{
current = (City)s.pop();
if (visited[current.city()]) continue;
visited[current.city()] = true;
for (i=0 ; i < = cities ; i++)
{
if (!links[current.city()][i] || current.city() == i) continue;
if (!visited[i])
s.push(new City(i, current.city()));
else
if (i != current.parent()) return 1;
}
}
return 0;
}
static void display(boolean link[][], int n)
{
int i, j;
for (i=0 ; i < n ; i++)
{
for (j=0 ; j < n ; j++)
System.out.print((link[i][j] ? 1 : 0) + " ");
System.out.println();
}
}
static int ReadData(boolean links[][], String filename)
{
int city1, city2, cities=0;
try
{
DataInputStream is = new DataInputStream(new FileInputStream(filename));
while (true)
{
String s = is.readLine();
try
{
StringTokenizer t = new StringTokenizer(s," ");
city1 = Integer.parseInt(t.nextToken());
city2 = Integer.parseInt(t.nextToken());
links[city1][city2] = true;
if (city1 > cities) cities = city1;
if (city2 > cities) cities = city2;
}
catch (NullPointerException e){ break; }
}
}
catch (IOException e) {}
return cities;
}
public static void main(String argv[])
{
boolean links[][] = new boolean[200][200];
int city1, city2, cost, cities=0;
cities = ReadData(links, argv[0]);
display(links, cities+1);
System.out.println("<<"+redundancy(links,cities)+">>");
}
}