2 Replies - 1672 Views - Last Post: 08 November 2009 - 07:33 PM Rate Topic: -----

#1 esf36  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 07-November 09

Displaying sets of connected circles

Posted 07 November 2009 - 07:16 PM

I know there is a lot of info but I need your help..I know I have to send the circles to a list and store them so they can be seporate...and if the circles touch combine the circles....well I know what to do but how to do it in Java I need help doing that. The code at the bottom in red is list class stuff...

Below is the instructions for my project

(Displaying sets of connected circles) Modify ConnectedCircles.java to display sets of connected circles in different random colors, i.e., if two circles are connected, they are displayed using the same color; otherwise, they are not in same color.

I know there is stuff that needs to be removed but this project is a 5 part one and whats not used now will me in the next....

Code:

import java.util.List;
import java.util.ArrayList;
import javax.swing.*;
import java.awt.*;
import java.awt.event.*;
import java.util.*;

public class ConnectedCircles extends JApplet {
  // Circles are stored in a list
  private List<Circle> circles = new ArrayList<Circle>();

  public ConnectedCircles() {
	add (new CirclePanel()); // Add to circle panel to applet
  }

  /** Panel for displaying circles */
  class CirclePanel extends JPanel {
			public CirclePanel() {
			  addMouseListener(new MouseAdapter() {
						public void mouseClicked(MouseEvent e) {
						  if (!isInsideACircle(e.getPoint())) { // Add a new circle
									circles.add(new Circle(e.getX(), e.getY()));
									repaint();
				  }
						}
			  });
			}

			/** Returns true if the point is inside an existing circle */
			private boolean isInsideACircle(Point p) {
			  for (Circle circle: circles)
						if (circle.contains(p)) return true;

			  return false;
			}

			protected void paintComponent(Graphics g) {
			  if (circles.size() == 0) return; // Nothing to paint

			  super.paintComponent(g);

			  // Build the edges
			  List<AbstractGraph.Edge> edges
				= new ArrayList<AbstractGraph.Edge>();
			  for (int i = 0; i < circles.size(); i++)
						for (int j = i + 1; j < circles.size(); j++)
						  if (circles.get(i).overlaps(circles.get(j))) {
									 edges.add(new AbstractGraph.Edge(i, j));
									 edges.add(new AbstractGraph.Edge(j, i));
						  }

			  // Create a graph with circles as vertices
			  Graph<Circle> graph
				= new UnweightedGraph<Circle>(edges, circles);
			  AbstractGraph<Circle>.Tree tree = graph.dfs(0); // a DFS tree
			  boolean isAllCirclesConnected =
						circles.size() == tree.getNumberOfVerticesFound();

			  for (Circle circle: circles) {
						int radius = circle.radius;
						if (isAllCirclesConnected) { // All circles are connected
							Random rand;
							rand = new Random();
   g.setColor(new Color(rand.nextInt(256),rand.nextInt(256),rand.nextInt(256)));
						  g.fillOval(circle.x - radius, circle.y - radius,
							2 * radius, 2 * radius);
						}
						else // circles are not all connected
						  g.drawOval(circle.x - radius, circle.y - radius,
							2 * radius, 2 * radius);
			  }
			}
  }

  private static class Circle {
			int radius = 20;
			int x, y;

			Circle(int x, int y) {
			  this.x = x;
			  this.y = y;
			}

			public boolean contains(Point p) {
			  double d = distance(x, y, p.x, p.y);
	  return d <= radius;
	}

			public boolean overlaps(Circle circle) {
			  return distance(this.x, this.y, circle.x, circle.y)
				<= radius + circle.radius;
			}

			private static double distance(int x1, int y1, int x2, int y2) {
			  return Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
			}
  }

  public static void main(String[] args) {
	JFrame frame = new JFrame();
	JApplet applet = new ConnectedCircles();
	frame.add(applet);
	frame.setTitle("ConnectedCircles");
	frame.setLocationRelativeTo(null);
	frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
	frame.setSize(400, 300);
	frame.setVisible(true);
  }
}
 interface Graph<V> {
  /** Return the number of vertices in the graph */
  public int getSize();

  /** Return the vertices in the graph */
  public java.util.List<V> getVertices();

  /** Return the object for the specified vertex index */
  public V getVertex(int index);

  /** Return the index for the specified vertex object */
  public int getIndex(V v);

  /** Return the neighbors of vertex with the specified index */
  public java.util.List<Integer> getNeighbors(int index);

  /** Return the degree for a specified vertex */
  public int getDegree(int v);

  /** Print the edges */
  public void printEdges();

  /** Clear graph */
  public void clear();

  /** Add a vertex to the graph */
  public void addVertex(V vertex);

  /** Add an edge to the graph */
  public void addEdge(int u, int v);

  /** Obtain a depth-first search tree */
  public AbstractGraph<V>.Tree dfs(int v);

  /** Obtain a breadth-first search tree */
  public AbstractGraph<V>.Tree bfs(int v);
}

 

 abstract class AbstractGraph<V> implements Graph<V> {
  protected List<V> vertices = new ArrayList<V>(); // Store vertices
  protected List<List<Integer>> neighbors
	= new ArrayList<List<Integer>>(); // Adjacency lists

  /** Construct an empty graph */
  protected AbstractGraph() {
  }

  /** Construct a graph from edges and vertices stored in arrays */
  protected AbstractGraph(int[][] edges, V[] vertices) {
	for (int i = 0; i < vertices.length; i++)
	  this.vertices.add(vertices[i]);

	createAdjacencyLists(edges, vertices.length);
  }

  /** Construct a graph from edges and vertices stored in List */
  protected AbstractGraph(List<Edge> edges, List<V> vertices) {
	  for (int i = 0; i < vertices.size(); i++)
		this.vertices.add(vertices.get(i));

	  createAdjacencyLists(edges, vertices.size());
  }

  /** Construct a graph for integer vertices 0, 1, 2 and edge list */
  protected AbstractGraph(List<Edge> edges, int numberOfVertices) {
	for (int i = 0; i < numberOfVertices; i++) {
	  vertices.add((V)(new Integer(i))); // vertices is {0, 1, ...}
	}
	createAdjacencyLists(edges, numberOfVertices);
  }

  /** Construct a graph from integer vertices 0, 1, and edge array */
  protected AbstractGraph(int[][] edges, int numberOfVertices) {
	for (int i = 0; i < numberOfVertices; i++) {
	  vertices.add((V)(new Integer(i))); // vertices is {0, 1, ...}
	}
	createAdjacencyLists(edges, numberOfVertices);
  }

  /** Create adjacency lists for each vertex */
  private void createAdjacencyLists(
	  int[][] edges, int numberOfVertices) {
	// Create a linked list
	for (int i = 0; i < numberOfVertices; i++) {
	  neighbors.add(new ArrayList<Integer>());
	}

	for (int i = 0; i < edges.length; i++) {
	  int u = edges[i][0];
	  int v = edges[i][1];
	  neighbors.get(u).add(v);
	}
  }

  /** Create adjacency lists for each vertex */
  private void createAdjacencyLists(
	  List<Edge> edges, int numberOfVertices) {
	// Create a linked list for each vertex
	for (int i = 0; i < numberOfVertices; i++) {
	  neighbors.add(new ArrayList<Integer>());
	}

	for (Edge edge: edges) {
	  neighbors.get(edge.u).add(edge.v);
	}
  }

  /** Return the number of vertices in the graph */
  public int getSize() {
	return vertices.size();
  }

  /** Return the vertices in the graph */
  public List<V> getVertices() {
	return vertices;
  }

  /** Return the object for the specified vertex */
  public V getVertex(int index) {
	return vertices.get(index);
  }

  /** Return the index for the specified vertex object */
  public int getIndex(V v) {
	return vertices.indexOf(v);
  }

  /** Return the neighbors of vertex with the specified index */
  public List<Integer> getNeighbors(int index) {
	return neighbors.get(index);
  }

  /** Return the degree for a specified vertex */
  public int getDegree(int v) {
	return neighbors.get(v).size();
  }

  /** Print the edges */
  public void printEdges() {
	for (int u = 0; u < neighbors.size(); u++) {
	  System.out.print(getVertex(u) + " (" + u + "): ");
	  for (int j = 0; j < neighbors.get(u).size(); j++) {
		System.out.print("(" + u + ", " +
		  neighbors.get(u).get(j) + ") ");
	  }
	  System.out.println();
	}
  }

  /** Clear graph */
  public void clear() {
	  vertices.clear();
	  neighbors.clear();
  }

  /** Add a vertex to the graph */
  public void addVertex(V vertex) {
	vertices.add(vertex);
	neighbors.add(new ArrayList<Integer>());
  }

  /** Add an edge to the graph */
  public void addEdge(int u, int v) {
	neighbors.get(u).add(v);
	neighbors.get(v).add(u);
  }

  /** Edge inner class inside the AbstractGraph class */
  public static class Edge {
	public int u; // Starting vertex of the edge
	public int v; // Ending vertex of the edge

	/** Construct an edge for (u, v) */
	public Edge(int u, int v) {
	  this.u = u;
	  this.v = v;
	}
  }

  /** Obtain a DFS tree starting from vertex v */
  /** To be discussed in Section 27.6 */
  public Tree dfs(int v) {
	List<Integer> searchOrders = new ArrayList<Integer>();
	int[] parent = new int[vertices.size()];
	for (int i = 0; i < parent.length; i++)
	  parent[i] = -1; // Initialize parent[i] to -1

	// Mark visited vertices
	boolean[] isVisited = new boolean[vertices.size()];

	// Recursively search
	dfs(v, parent, searchOrders, isVisited);

	// Return a search tree
	return new Tree(v, parent, searchOrders);
  }

  /** Recursive method for DFS search */
  private void dfs(int v, int[] parent, List<Integer> searchOrders,
	  boolean[] isVisited) {
	// Store the visited vertex
	searchOrders.add(v);
	isVisited[v] = true; // Vertex v visited

	for (int i : neighbors.get(v)) {
	  if (!isVisited[i]) {
		parent[i] = v; // The parent of vertex i is v
		dfs(i, parent, searchOrders, isVisited); // Recursive search
	  }
	}
  }

  /** Starting bfs search from vertex v */
  /** To be discussed in Section 27.7 */
  public Tree bfs(int v) {
	List<Integer> searchOrders = new ArrayList<Integer>();
	int[] parent = new int[vertices.size()];
	for (int i = 0; i < parent.length; i++)
	  parent[i] = -1; // Initialize parent[i] to -1

	java.util.LinkedList<Integer> queue =
	  new java.util.LinkedList<Integer>(); // list used as a queue
	boolean[] isVisited = new boolean[vertices.size()];
	queue.offer(v); // Enqueue v
	isVisited[v] = true; // Mark it visited

	while (!queue.isEmpty()) {
	  int u = queue.poll(); // Dequeue to u
	  searchOrders.add(u); // u searched
	  for (int w : neighbors.get(u)) {
		if (!isVisited[w]) {
		  queue.offer(w); // Enqueue w
		  parent[w] = u; // The parent of w is u
		  isVisited[w] = true; // Mark it visited
		}
	  }
	}

	return new Tree(v, parent, searchOrders);
  }

  /** Tree inner class inside the AbstractGraph class */
  /** To be discussed in Section 27.5 */
  public class Tree {
	private int root; // The root of the tree
	private int[] parent; // Store the parent of each vertex
	private List<Integer> searchOrders; // Store the search order

	/** Construct a tree with root, parent, and searchOrder */
	public Tree(int root, int[] parent, List<Integer> searchOrders) {
	  this.root = root;
	  this.parent = parent;
	  this.searchOrders = searchOrders;
	}

	/** Return the root of the tree */
	public int getRoot() {
	  return root;
	}

	/** Return the parent of vertex v */
	public int getParent(int v) {
	  return parent[v];
	}

	/** Return an array representing search order */
	public List<Integer> getSearchOrders() {
	  return searchOrders;
	}

	/** Return number of vertices found */
	public int getNumberOfVerticesFound() {
	  return searchOrders.size();
	}

	/** Return the path of vertices from a vertex index to the root */
	public List<V> getPath(int index) {
	  ArrayList<V> path = new ArrayList<V>();

	  do {
		path.add(vertices.get(index));
		index = parent[index];
	  }
	  while (index != -1);

	  return path;
	}

	/** Print a path from the root to vertex v */
	public void printPath(int index) {
	  List<V> path = getPath(index);
	  System.out.print("A path from " + vertices.get(root) + " to " +
		vertices.get(index) + ": ");
	  for (int i = path.size() - 1; i >= 0; i--)
		System.out.print(path.get(i) + " ");
	}

	/** Print the whole tree */
	public void printTree() {
	  System.out.println("Root is: " + vertices.get(root));
	  System.out.print("Edges: ");
	  for (int i = 0; i < parent.length; i++) {
		if (parent[i] != -1) {
		  // Display an edge
		  System.out.print("(" + vertices.get(parent[i]) + ", " +
			vertices.get(i) + ") ");
		}
	  }
	  System.out.println();
	}
  }

  /** Return a Hamiltonian path from the specified vertex object
   * Return null if the graph does not contain a Hamiltonian path */
  public List<Integer> getHamiltonianPath(V vertex) {
	return getHamiltonianPath(getIndex(vertex));
  }

  /** Return a Hamiltonian path from the specified vertex label
   * Return null if the graph does not contain a Hamiltonian path */
  public List<Integer> getHamiltonianPath(int v) {
	// A path starts from v. (i, next[i]) represents an edge in
	// the path. isVisited[i] tracks whether i is currently in the
	// path.
	int[] next = new int[getSize()];
	for (int i = 0; i < next.length; i++)
	  next[i] = -1; // Indicate no subpath from i is found yet

	boolean[] isVisited = new boolean[getSize()];

	// The vertices in the Hamiltonian path are stored in result
	List<Integer> result = null;

	// To speed up search, reorder the adjacency list for each
	// vertex so that the vertices in the list are in increasing
	// order of their degrees
	for (int i = 0; i < getSize(); i++)
	  reorderNeigborsBasedOnDegree(neighbors.get(i));

	if (getHamiltonianPath(v, next, isVisited)) {
	  result = new ArrayList<Integer>(); // Create a list for path
	  int vertex = v; // Starting from v
	  while (vertex != -1) {
		result.add(vertex); // Add vertex to the result list
		vertex = next[vertex]; // Get the next vertex in the path
	  }
	}

	return result; // return null if no Hamiltonian path is found
  }

  /** Reorder the adjacency list in increasing order of degrees */
  private void reorderNeigborsBasedOnDegree(List<Integer> list) {
	for (int i = list.size() - 1; i >= 1; i--) {
	  // Find the maximum in the list[0..i]
	  int currentMaxDegree = getDegree(list.get(0));
	  int currentMaxIndex = 0;

	  for (int j = 1; j <= i; j++) {
		if (currentMaxDegree < getDegree(list.get(j))) {
		  currentMaxDegree = getDegree(list.get(j));
		  currentMaxIndex = j;
		}
	  }

	  // Swap list[i] with list[currentMaxIndex] if necessary;
	  if (currentMaxIndex != i) {
		int temp = list.get(currentMaxIndex);
		list.set(currentMaxIndex, list.get(i));
		list.set(i, temp);
	  }
	}
  }

  /** Return true if all elements in array isVisited are true */
  private boolean allVisited(boolean[] isVisited) {
	boolean result = true;

	for (int i = 0; i < getSize(); i++)
	  result = result && isVisited[i];

	return result;
  }

  /** Search for a Hamiltonian path from v */
  private boolean getHamiltonianPath(int v, int[] next,
	  boolean[] isVisited) {
	isVisited[v] = true; // Mark vertex v visited

	if (allVisited(isVisited))
	  return true; // The path now includes all vertices, thus found

	for (int i = 0; i < neighbors.get(v).size(); i++) {
	  int u = neighbors.get(v).get(i);
	  if (!isVisited[u] &&
		  getHamiltonianPath(u, next, isVisited)) {
		next[v] = u; // Edge (v, u) is in the path
		return true;
	  }
	}

	isVisited[v] = false; // Backtrack, v is marked unvisited now
	return false; // No Hamiltonian path exists from vertex v
  }
}

 class UnweightedGraph<V> extends AbstractGraph<V> {
  /** Construct an empty graph */
  public UnweightedGraph() {
  }

  /** Construct a graph from edges and vertices stored in arrays */
  public UnweightedGraph(int[][] edges, V[] vertices) {
	super(edges, vertices);
  }

  /** Construct a graph from edges and vertices stored in List */
  public UnweightedGraph(List<Edge> edges, List<V> vertices) {
	super(edges, vertices);
  }

  /** Construct a graph for integer vertices 0, 1, 2 and edge list */
  public UnweightedGraph(List<Edge> edges, int numberOfVertices) {
	super(edges, numberOfVertices);
  }

  /** Construct a graph from integer vertices 0, 1, and edge array */
  public UnweightedGraph(int[][] edges, int numberOfVertices) {
	super(edges, numberOfVertices);
  }
}

class MyGraph<V> extends UnweightedGraph<V> {
	  /** Construct an empty graph */
	  public MyGraph() {
	  }

		/** Construct a graph from edges and vertices stored in arrays */
		public MyGraph(int[][] edges, V[] vertices) {
		  super(edges, vertices);
		}

		/** Construct a graph from edges and vertices stored in List */
		public MyGraph(List<Edge> edges, List<V> vertices) {
		  super(edges, vertices);
		}

		/** Construct a graph for integer vertices 0, 1, 2 and edge list */
		public MyGraph(List<Edge> edges, int numberOfVertices) {
		  super(edges, numberOfVertices);
		}

		/** Construct a graph from integer vertices 0, 1, and edge array */
		public MyGraph(int[][] edges, int numberOfVertices) {
		  super(edges, numberOfVertices);
		}

	  public List<List<Integer>> getConnectedComponents() {
		List<List<Integer>> list = new ArrayList<List<Integer>>();

		List<Integer> vertexIndices = new ArrayList<Integer>();
		for (int i = 0; i < vertices.size(); i++)
			vertexIndices.add(i);

		while (vertexIndices.size() > 0) {
			Tree tree = dfs(vertexIndices.get(0));
			list.add(tree.getSearchOrders());
			vertexIndices.removeAll(tree.getSearchOrders());
		}

		return list;
	  }
  }

Attached image(s)

  • Attached Image


Is This A Good Question/Topic? 0
  • +

Replies To: Displaying sets of connected circles

#2 Martyr2  Icon User is offline

  • Programming Theoretician
  • member icon

Reputation: 4333
  • View blog
  • Posts: 12,128
  • Joined: 18-April 07

Re: Displaying sets of connected circles

Posted 08 November 2009 - 12:07 AM

When you create the circle, you are going to assign it a random color and assign it to a variable of circle. To go along with this will be a function which will fetch the color from the circle (and set it) as well. So when you determine when a point is in the bounds of an existing circle, you can then ask that circle for its color and assign it to the new circle. That way they share the colors. If they never touch, the random color will be assigned to the circle. Understand?

You can create a random color like so....

Random numGen = new Random();

Color rndColor = new Color(numGen.nextInt(256), numGen.nextInt(256), numGen.nextInt(256));



Then teamed up with a method to get it/set it, you can add that to your point detection code there....

public CirclePanel() {
	 addMouseListener(new MouseAdapter() {
		  public void mouseClicked(MouseEvent e) {
			   drawCircle(e.getPoint());
			   repaint();
		  }
	 });
}

/** Draws circle the same color of intersecting circle or with random color */
private void drawCircle(Point p) {
	 Random numGen = new Random();

	 // Generate a new random color
	 Color circleColor = new Color(numGen.nextInt(256), numGen.nextInt(256), numGen.nextInt(256));

	 // If you find a circle it is touching, get that circle's color through your getColor() method
	 for (Circle circle: circles) {
		  if (circle.contains(p)) {
			   circleColor = circle.getColor(); 
		  }
	 }

	 // Create new circle and set it with random color or color you got from the other circle
	 Circle newCircle = new Circle(p.getX(), p.getY());
	 newCircle.setColor(circleColor);

	 // Add the new circle to the series
	 circles.add(newCircle);
}



As you can see here, we create drawCircle here which 1) Generates a random color 2) Checks if the point was in an existing circle, if so, get that circle's color 3) Create a new circle instance 4) Set its color to the random color we generated or the color we got from the intersecting circle 5) Add the circle to the list.

Hope this makes sense. Enjoy!


"At DIC we be color circle adding code ninjas... we like circles because we have been called squares all our life and it was getting old." :snap:

This post has been edited by Martyr2: 08 November 2009 - 12:07 AM

Was This Post Helpful? 1

#3 esf36  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 07-November 09

Re: Displaying sets of connected circles

Posted 08 November 2009 - 07:33 PM

Ok I added in what Martyr said and it cant find getcolor and set color in his code...how do I pull the random color and set it??


import java.util.List;
import java.util.ArrayList;
import javax.swing.*;
import java.awt.*;
import java.awt.event.*;
import java.util.*;

public class ConnectedCircles extends JApplet {
  // Circles are stored in a list
  private List<Circle> circles = new ArrayList<Circle>();

  public ConnectedCircles() {
	add (new CirclePanel()); // Add to circle panel to applet
  }

  /** Panel for displaying circles */
  class CirclePanel extends JPanel {
			 Random numGen = new Random();

Color rndColor = new Color(numGen.nextInt(256), numGen.nextInt(256), numGen.nextInt(256));

 public CirclePanel() {
	 addMouseListener(new MouseAdapter() {
		  public void mouseClicked(MouseEvent e) {
			   drawCircle(e.getPoint());
			   repaint();
		  }
	 });
}
 
 /** Draws circle the same color of intersecting circle or with random color */
private void drawCircle(Point p) {
	 Random numGen = new Random();

	 // Generate a new random color
	 Color circleColor = new Color(numGen.nextInt(256), numGen.nextInt(256), numGen.nextInt(256));

	 // If you find a circle it is touching, get that circle's color through your getColor() method
	 for (Circle circle: circles) {
		  if (circle.contains(p)) {
			   circleColor = circle.getColor();
		  }
	 }

	 // Create new circle and set it with random color or color you got from the other circle
	 Circle newCircle = new Circle(p.getX(), p.getY());
	 newCircle.setColor(circleColor);

	 // Add the new circle to the series
	 circles.add(newCircle);
}
 
 /** Returns true if the point is inside an existing circle */
			private boolean isInsideACircle(Point p) {
			  for (Circle circle: circles)
						if (circle.contains(p)) return true;

			  return false;
			}

			protected void paintComponent(Graphics g) {
			  if (circles.size() == 0) return; // Nothing to paint

			  super.paintComponent(g);

			  // Build the edges
			  List<AbstractGraph.Edge> edges
				= new ArrayList<AbstractGraph.Edge>();
			  for (int i = 0; i < circles.size(); i++)
						for (int j = i + 1; j < circles.size(); j++)
						  if (circles.get(i).overlaps(circles.get(j))) {
									 edges.add(new AbstractGraph.Edge(i, j));
									 edges.add(new AbstractGraph.Edge(j, i));
						  }

			  // Create a graph with circles as vertices
			  Graph<Circle> graph
				= new UnweightedGraph<Circle>(edges, circles);
			  AbstractGraph<Circle>.Tree tree = graph.dfs(0); // a DFS tree
			  boolean isAllCirclesConnected =
						circles.size() == tree.getNumberOfVerticesFound();

			  for (Circle circle: circles) {
						int radius = circle.radius;
						if (isAllCirclesConnected) { // All circles are connected

   g.fillOval(circle.x - radius, circle.y - radius,
							2 * radius, 2 * radius);
						}
						else // circles are not all connected
						  g.drawOval(circle.x - radius, circle.y - radius,
							2 * radius, 2 * radius);
			  }
			}
  }

  private static class Circle {
			int radius = 20;	  
			int x, y;

			Circle(double x, double y) {
			  this.x = (int) x;
			  this.y = (int) y;
			}

			public boolean contains(Point p) {
			  double d = distance(x, y, p.x, p.y);
	  return d <= radius;
	}

			public boolean overlaps(Circle circle) {
			  return distance(this.x, this.y, circle.x, circle.y)
				<= radius + circle.radius;
			}

			private static double distance(int x1, int y1, int x2, int y2) {
			  return Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
			}

  }

  public static void main(String[] args) {
	JFrame frame = new JFrame();
	JApplet applet = new ConnectedCircles();
	frame.add(applet);
	frame.setTitle("ConnectedCircles");
	frame.setLocationRelativeTo(null);
	frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
	frame.setSize(400, 300);
	frame.setVisible(true);
  }
}
 interface Graph<V> {
  /** Return the number of vertices in the graph */
  public int getSize();

  /** Return the vertices in the graph */
  public java.util.List<V> getVertices();

  /** Return the object for the specified vertex index */
  public V getVertex(int index);

  /** Return the index for the specified vertex object */
  public int getIndex(V v);

  /** Return the neighbors of vertex with the specified index */
  public java.util.List<Integer> getNeighbors(int index);

  /** Return the degree for a specified vertex */
  public int getDegree(int v);

  /** Print the edges */
  public void printEdges();

  /** Clear graph */
  public void clear();

  /** Add a vertex to the graph */
  public void addVertex(V vertex);

  /** Add an edge to the graph */
  public void addEdge(int u, int v);

  /** Obtain a depth-first search tree */
  public AbstractGraph<V>.Tree dfs(int v);

  /** Obtain a breadth-first search tree */
  public AbstractGraph<V>.Tree bfs(int v);
}



 abstract class AbstractGraph<V> implements Graph<V> {
  protected List<V> vertices = new ArrayList<V>(); // Store vertices
  protected List<List<Integer>> neighbors
	= new ArrayList<List<Integer>>(); // Adjacency lists

  /** Construct an empty graph */
  protected AbstractGraph() {
  }

  /** Construct a graph from edges and vertices stored in arrays */
  protected AbstractGraph(int[][] edges, V[] vertices) {
	for (int i = 0; i < vertices.length; i++)
	  this.vertices.add(vertices[i]);

	createAdjacencyLists(edges, vertices.length);
  }

  /** Construct a graph from edges and vertices stored in List */
  protected AbstractGraph(List<Edge> edges, List<V> vertices) {
	  for (int i = 0; i < vertices.size(); i++)
		this.vertices.add(vertices.get(i));

	  createAdjacencyLists(edges, vertices.size());
  }

  /** Construct a graph for integer vertices 0, 1, 2 and edge list */
  protected AbstractGraph(List<Edge> edges, int numberOfVertices) {
	for (int i = 0; i < numberOfVertices; i++) {
	  vertices.add((V)(new Integer(i))); // vertices is {0, 1, ...}
	}
	createAdjacencyLists(edges, numberOfVertices);
  }

  /** Construct a graph from integer vertices 0, 1, and edge array */
  protected AbstractGraph(int[][] edges, int numberOfVertices) {
	for (int i = 0; i < numberOfVertices; i++) {
	  vertices.add((V)(new Integer(i))); // vertices is {0, 1, ...}
	}
	createAdjacencyLists(edges, numberOfVertices);
  }

  /** Create adjacency lists for each vertex */
  private void createAdjacencyLists(
	  int[][] edges, int numberOfVertices) {
	// Create a linked list
	for (int i = 0; i < numberOfVertices; i++) {
	  neighbors.add(new ArrayList<Integer>());
	}

	for (int i = 0; i < edges.length; i++) {
	  int u = edges[i][0];
	  int v = edges[i][1];
	  neighbors.get(u).add(v);
	}
  }

  /** Create adjacency lists for each vertex */
  private void createAdjacencyLists(
	  List<Edge> edges, int numberOfVertices) {
	// Create a linked list for each vertex
	for (int i = 0; i < numberOfVertices; i++) {
	  neighbors.add(new ArrayList<Integer>());
	}

	for (Edge edge: edges) {
	  neighbors.get(edge.u).add(edge.v);
	}
  }

  /** Return the number of vertices in the graph */
  public int getSize() {
	return vertices.size();
  }

  /** Return the vertices in the graph */
  public List<V> getVertices() {
	return vertices;
  }

  /** Return the object for the specified vertex */
  public V getVertex(int index) {
	return vertices.get(index);
  }

  /** Return the index for the specified vertex object */
  public int getIndex(V v) {
	return vertices.indexOf(v);
  }

  /** Return the neighbors of vertex with the specified index */
  public List<Integer> getNeighbors(int index) {
	return neighbors.get(index);
  }

  /** Return the degree for a specified vertex */
  public int getDegree(int v) {
	return neighbors.get(v).size();
  }

  /** Print the edges */
  public void printEdges() {
	for (int u = 0; u < neighbors.size(); u++) {
	  System.out.print(getVertex(u) + " (" + u + "): ");
	  for (int j = 0; j < neighbors.get(u).size(); j++) {
		System.out.print("(" + u + ", " +
		  neighbors.get(u).get(j) + ") ");
	  }
	  System.out.println();
	}
  }

  /** Clear graph */
  public void clear() {
	  vertices.clear();
	  neighbors.clear();
  }

  /** Add a vertex to the graph */
  public void addVertex(V vertex) {
	vertices.add(vertex);
	neighbors.add(new ArrayList<Integer>());
  }

  /** Add an edge to the graph */
  public void addEdge(int u, int v) {
	neighbors.get(u).add(v);
	neighbors.get(v).add(u);
  }

  /** Edge inner class inside the AbstractGraph class */
  public static class Edge {
	public int u; // Starting vertex of the edge
	public int v; // Ending vertex of the edge

	/** Construct an edge for (u, v) */
	public Edge(int u, int v) {
	  this.u = u;
	  this.v = v;
	}
  }

  /** Obtain a DFS tree starting from vertex v */
  /** To be discussed in Section 27.6 */
  public Tree dfs(int v) {
	List<Integer> searchOrders = new ArrayList<Integer>();
	int[] parent = new int[vertices.size()];
	for (int i = 0; i < parent.length; i++)
	  parent[i] = -1; // Initialize parent[i] to -1

	// Mark visited vertices
	boolean[] isVisited = new boolean[vertices.size()];

	// Recursively search
	dfs(v, parent, searchOrders, isVisited);

	// Return a search tree
	return new Tree(v, parent, searchOrders);
  }

  /** Recursive method for DFS search */
  private void dfs(int v, int[] parent, List<Integer> searchOrders,
	  boolean[] isVisited) {
	// Store the visited vertex
	searchOrders.add(v);
	isVisited[v] = true; // Vertex v visited

	for (int i : neighbors.get(v)) {
	  if (!isVisited[i]) {
		parent[i] = v; // The parent of vertex i is v
		dfs(i, parent, searchOrders, isVisited); // Recursive search
	  }
	}
  }

  /** Starting bfs search from vertex v */
  /** To be discussed in Section 27.7 */
  public Tree bfs(int v) {
	List<Integer> searchOrders = new ArrayList<Integer>();
	int[] parent = new int[vertices.size()];
	for (int i = 0; i < parent.length; i++)
	  parent[i] = -1; // Initialize parent[i] to -1

	java.util.LinkedList<Integer> queue =
	  new java.util.LinkedList<Integer>(); // list used as a queue
	boolean[] isVisited = new boolean[vertices.size()];
	queue.offer(v); // Enqueue v
	isVisited[v] = true; // Mark it visited

	while (!queue.isEmpty()) {
	  int u = queue.poll(); // Dequeue to u
	  searchOrders.add(u); // u searched
	  for (int w : neighbors.get(u)) {
		if (!isVisited[w]) {
		  queue.offer(w); // Enqueue w
		  parent[w] = u; // The parent of w is u
		  isVisited[w] = true; // Mark it visited
		}
	  }
	}

	return new Tree(v, parent, searchOrders);
  }

  /** Tree inner class inside the AbstractGraph class */
  /** To be discussed in Section 27.5 */
  public class Tree {
	private int root; // The root of the tree
	private int[] parent; // Store the parent of each vertex
	private List<Integer> searchOrders; // Store the search order

	/** Construct a tree with root, parent, and searchOrder */
	public Tree(int root, int[] parent, List<Integer> searchOrders) {
	  this.root = root;
	  this.parent = parent;
	  this.searchOrders = searchOrders;
	}

	/** Return the root of the tree */
	public int getRoot() {
	  return root;
	}

	/** Return the parent of vertex v */
	public int getParent(int v) {
	  return parent[v];
	}

	/** Return an array representing search order */
	public List<Integer> getSearchOrders() {
	  return searchOrders;
	}

	/** Return number of vertices found */
	public int getNumberOfVerticesFound() {
	  return searchOrders.size();
	}

	/** Return the path of vertices from a vertex index to the root */
	public List<V> getPath(int index) {
	  ArrayList<V> path = new ArrayList<V>();

	  do {
		path.add(vertices.get(index));
		index = parent[index];
	  }
	  while (index != -1);

	  return path;
	}

	/** Print a path from the root to vertex v */
	public void printPath(int index) {
	  List<V> path = getPath(index);
	  System.out.print("A path from " + vertices.get(root) + " to " +
		vertices.get(index) + ": ");
	  for (int i = path.size() - 1; i >= 0; i--)
		System.out.print(path.get(i) + " ");
	}

	/** Print the whole tree */
	public void printTree() {
	  System.out.println("Root is: " + vertices.get(root));
	  System.out.print("Edges: ");
	  for (int i = 0; i < parent.length; i++) {
		if (parent[i] != -1) {
		  // Display an edge
		  System.out.print("(" + vertices.get(parent[i]) + ", " +
			vertices.get(i) + ") ");
		}
	  }
	  System.out.println();
	}
  }

  /** Return a Hamiltonian path from the specified vertex object
   * Return null if the graph does not contain a Hamiltonian path */
  public List<Integer> getHamiltonianPath(V vertex) {
	return getHamiltonianPath(getIndex(vertex));
  }

  /** Return a Hamiltonian path from the specified vertex label
   * Return null if the graph does not contain a Hamiltonian path */
  public List<Integer> getHamiltonianPath(int v) {
	// A path starts from v. (i, next[i]) represents an edge in
	// the path. isVisited[i] tracks whether i is currently in the
	// path.
	int[] next = new int[getSize()];
	for (int i = 0; i < next.length; i++)
	  next[i] = -1; // Indicate no subpath from i is found yet

	boolean[] isVisited = new boolean[getSize()];

	// The vertices in the Hamiltonian path are stored in result
	List<Integer> result = null;

	// To speed up search, reorder the adjacency list for each
	// vertex so that the vertices in the list are in increasing
	// order of their degrees
	for (int i = 0; i < getSize(); i++)
	  reorderNeigborsBasedOnDegree(neighbors.get(i));

	if (getHamiltonianPath(v, next, isVisited)) {
	  result = new ArrayList<Integer>(); // Create a list for path
	  int vertex = v; // Starting from v
	  while (vertex != -1) {
		result.add(vertex); // Add vertex to the result list
		vertex = next[vertex]; // Get the next vertex in the path
	  }
	}

	return result; // return null if no Hamiltonian path is found
  }

  /** Reorder the adjacency list in increasing order of degrees */
  private void reorderNeigborsBasedOnDegree(List<Integer> list) {
	for (int i = list.size() - 1; i >= 1; i--) {
	  // Find the maximum in the list[0..i]
	  int currentMaxDegree = getDegree(list.get(0));
	  int currentMaxIndex = 0;

	  for (int j = 1; j <= i; j++) {
		if (currentMaxDegree < getDegree(list.get(j))) {
		  currentMaxDegree = getDegree(list.get(j));
		  currentMaxIndex = j;
		}
	  }

	  // Swap list[i] with list[currentMaxIndex] if necessary;
	  if (currentMaxIndex != i) {
		int temp = list.get(currentMaxIndex);
		list.set(currentMaxIndex, list.get(i));
		list.set(i, temp);
	  }
	}
  }

  /** Return true if all elements in array isVisited are true */
  private boolean allVisited(boolean[] isVisited) {
	boolean result = true;

	for (int i = 0; i < getSize(); i++)
	  result = result && isVisited[i];

	return result;
  }

  /** Search for a Hamiltonian path from v */
  private boolean getHamiltonianPath(int v, int[] next,
	  boolean[] isVisited) {
	isVisited[v] = true; // Mark vertex v visited

	if (allVisited(isVisited))
	  return true; // The path now includes all vertices, thus found

	for (int i = 0; i < neighbors.get(v).size(); i++) {
	  int u = neighbors.get(v).get(i);
	  if (!isVisited[u] &&
		  getHamiltonianPath(u, next, isVisited)) {
		next[v] = u; // Edge (v, u) is in the path
		return true;
	  }
	}

	isVisited[v] = false; // Backtrack, v is marked unvisited now
	return false; // No Hamiltonian path exists from vertex v
  }
}

 class UnweightedGraph<V> extends AbstractGraph<V> {
  /** Construct an empty graph */
  public UnweightedGraph() {
  }

  /** Construct a graph from edges and vertices stored in arrays */
  public UnweightedGraph(int[][] edges, V[] vertices) {
	super(edges, vertices);
  }

  /** Construct a graph from edges and vertices stored in List */
  public UnweightedGraph(List<Edge> edges, List<V> vertices) {
	super(edges, vertices);
  }

  /** Construct a graph for integer vertices 0, 1, 2 and edge list */
  public UnweightedGraph(List<Edge> edges, int numberOfVertices) {
	super(edges, numberOfVertices);
  }

  /** Construct a graph from integer vertices 0, 1, and edge array */
  public UnweightedGraph(int[][] edges, int numberOfVertices) {
	super(edges, numberOfVertices);
  }
}

class MyGraph<V> extends UnweightedGraph<V> {
	  /** Construct an empty graph */
	  public MyGraph() {
	  }

		/** Construct a graph from edges and vertices stored in arrays */
		public MyGraph(int[][] edges, V[] vertices) {
		  super(edges, vertices);
		}

		/** Construct a graph from edges and vertices stored in List */
		public MyGraph(List<Edge> edges, List<V> vertices) {
		  super(edges, vertices);
		}

		/** Construct a graph for integer vertices 0, 1, 2 and edge list */
		public MyGraph(List<Edge> edges, int numberOfVertices) {
		  super(edges, numberOfVertices);
		}

		/** Construct a graph from integer vertices 0, 1, and edge array */
		public MyGraph(int[][] edges, int numberOfVertices) {
		  super(edges, numberOfVertices);
		}

	  public List<List<Integer>> getConnectedComponents() {
		List<List<Integer>> list = new ArrayList<List<Integer>>();

		List<Integer> vertexIndices = new ArrayList<Integer>();
		for (int i = 0; i < vertices.size(); i++)
			vertexIndices.add(i);

		while (vertexIndices.size() > 0) {
			Tree tree = dfs(vertexIndices.get(0));
			list.add(tree.getSearchOrders());
			vertexIndices.removeAll(tree.getSearchOrders());
		}

		return list;
	  }
  }



Was This Post Helpful? 0
  • +
  • -

Page 1 of 1