[Problem Solving #3] Polygon Phobia

[Nuluvius]

In my solution I made use of the inbuilt Point type. Java has one as well, using it may be a nice way for you to keep your X and Ys together more concisely.

[Maximation]

So I have written some more code today, but there are still some problems. I think I understand union-find correctly now, and I also think I implemented it correctly in my code. When I try to execute my code though it gives as output (linesDrawn) the same amount as there are segments. When I feed it input4.txt || input5.txt it goes into a never-ending loop. What did I do wrong this time?

 

/* * Author : maeb * 2014 */import java.util.Scanner;import java.util.LinkedList;import java.awt.Point;public class Main {	public static void main(String[] args) {		Scanner in = new Scanner(System.in);		int linesDrawn = 0;		/* integer on the first line represents the number of segments it will exist out of */		int numSegments = in.nextInt();		Segment[] segments = new Segment[numSegments];		LinkedList<LinkedList<Point>> set = new LinkedList<LinkedList<Point>>();		try {			/* makes a Segment object with its 2 points and stores all the Segment objects in the segments array */			for (int i = 0; i < numSegments; i++) {				int x1 = 0, y1 = 0, x2 = 0, y2 = 0;				for (int j = 0; j < 4; j++) {					if (j == 0)						x1 = in.nextInt();					if (j == 1)						y1 = in.nextInt();					if (j == 2)						x2 = in.nextInt();					if (j == 3)						y2 = in.nextInt();				}				Point p1 = new Point(x1, y1);				Point p2 = new Point(x2, y2);				segments[i] = new Segment(p1, p2);			}		} catch (Exception e) {}		/* sets the parent set of every node to itself */		for (int j = 0; j < segments.length; j++) {			LinkedList<Point> toAdd1 = new LinkedList<Point>();			LinkedList<Point> toAdd2 = new LinkedList<Point>();			toAdd1.add(segments[j].getP1());			toAdd2.add(segments[j].getP2());			set.add(toAdd1);			set.add(toAdd2);		}		for (int k = 0; k < segments.length; k++) {			if (set.get(k).contains(segments[k].getP1()) && set.get(k).contains(segments[k].getP2())) {				// linesDrawn will not get incremented because drawing this segment will complete the cycle			}			else if (set.get(k).contains(segments[k].getP1()) && !set.get(k).contains(segments[k].getP2())) {				LinkedList<Point> toAdd = set.get(k);				toAdd.add(segments[k].getP2());				set.set(k, toAdd);				linesDrawn++;			}			else if (!set.get(k).contains(segments[k].getP1()) && set.get(k).contains(segments[k].getP2())) {				LinkedList<Point> toAdd = set.get(k);				toAdd.add(segments[k].getP1());				set.set(k, toAdd);				linesDrawn++;			}			else if (!set.get(k).contains(segments[k].getP1()) && !set.get(k).contains(segments[k].getP2())) {				LinkedList<Point> toAdd = set.get(k);				toAdd.add(segments[k].getP1());				toAdd.add(segments[k].getP2());				set.set(k, toAdd);				linesDrawn++;			}		}		System.out.println("Lines drawn : " + linesDrawn);	}}

/* *    Author: maeb *    2014 */import java.awt.Point;public class Segment {    private Point p1, p2;    public Segment (Point p1, Point p2) {        this.p1 = new Point(p1);        this.p2 = new Point(p2);    }    public Point getP1() {        return p1;    }    public Point getP2() {        return p2;    }}

[Maximation]

So I have written some more code today, but there are still some problems. I think I understand union-find correctly now, and I also think I implemented it correctly in my code. When I try to execute my code though it gives as output (linesDrawn) the same amount as there are segments. When I feed it input4.txt || input5.txt it goes into a never-ending loop. What did I do wrong this time?

 

 

So I see something I did wrong. In the last else-if-statement the points are being added to the current set, but that is not what is supposed to be done. The two points need to get added together, union.

Wait a sec, maybe I can figure this out.

/* * Author : maeb * 2014 */import java.util.Scanner;import java.util.LinkedList;import java.awt.Point;public class Main {	public static void main(String[] args) {		Scanner in = new Scanner(System.in);		int linesDrawn = 0;		/* integer on the first line represents the number of segments it will exist out of */		int numSegments = in.nextInt();		Segment[] segments = new Segment[numSegments];		LinkedList<LinkedList<Point>> set = new LinkedList<LinkedList<Point>>();		try {			/* makes a Segment object with its 2 points and stores all the Segment objects in the segments array */			for (int i = 0; i < numSegments; i++) {				int x1 = 0, y1 = 0, x2 = 0, y2 = 0;				for (int j = 0; j < 4; j++) {					if (j == 0)						x1 = in.nextInt();					if (j == 1)						y1 = in.nextInt();					if (j == 2)						x2 = in.nextInt();					if (j == 3)						y2 = in.nextInt();				}				Point p1 = new Point(x1, y1);				Point p2 = new Point(x2, y2);				segments[i] = new Segment(p1, p2);			}		} catch (Exception e) {}		/* sets the parent set of every node to itself */		for (int j = 0; j < segments.length; j++) {			LinkedList<Point> toAdd1 = new LinkedList<Point>();			LinkedList<Point> toAdd2 = new LinkedList<Point>();			toAdd1.add(segments[j].getP1());			toAdd2.add(segments[j].getP2());			set.add(toAdd1);			set.add(toAdd2);		}		for (int k = 0; k < segments.length; k++) {			if (set.get(k).contains(segments[k].getP1()) && set.get(k).contains(segments[k].getP2())) {				// linesDrawn will not get incremented because drawing this segment will complete the cycle			}			else if (set.get(k).contains(segments[k].getP1()) && !set.get(k).contains(segments[k].getP2())) {				LinkedList<Point> toAdd = set.get(k);				toAdd.add(segments[k].getP2());				set.set(k, toAdd);				linesDrawn++;			}			else if (!set.get(k).contains(segments[k].getP1()) && set.get(k).contains(segments[k].getP2())) {				LinkedList<Point> toAdd = set.get(k);				toAdd.add(segments[k].getP1());				set.set(k, toAdd);				linesDrawn++;			}			else if (!set.get(k).contains(segments[k].getP1()) && !set.get(k).contains(segments[k].getP2())) {				LinkedList<Point> toAdd = set.get(k);				toAdd.add(segments[k].getP1());				toAdd.add(segments[k].getP2());				set.set(k, toAdd);				linesDrawn++;			}		}		System.out.println("Lines drawn : " + linesDrawn);	}}

/* *    Author: maeb *    2014 */import java.awt.Point;public class Segment {    private Point p1, p2;    public Segment (Point p1, Point p2) {        this.p1 = new Point(p1);        this.p2 = new Point(p2);    }    public Point getP1() {        return p1;    }    public Point getP2() {        return p2;    }}

[Maximation]

Well, I may need some help anyway.

 

EDIT:

 

Main.java

Segment.java

Node.java

/* * Author : maeb * 2014 */import java.util.Scanner;import java.util.LinkedList;public class Main {	public static void main(String[] args) {		Scanner in = new Scanner(System.in);		int linesDrawn = 0;		/* integer on the first line represents the number of segments it will exist out of */		int numSegments = in.nextInt();		Segment[] segments = new Segment[numSegments];		LinkedList<LinkedList<Node>> sets = new LinkedList<LinkedList<Node>>();		try {			/* makes a Segment object with its 2 points/nodes and stores all the Segment objects in the segments array */			for (int i = 0; i < numSegments; i++) {				int x1 = 0, y1 = 0, x2 = 0, y2 = 0;				for (int j = 0; j < 4; j++) {					if (j == 0)						x1 = in.nextInt();					if (j == 1)						y1 = in.nextInt();					if (j == 2)						x2 = in.nextInt();					if (j == 3)						y2 = in.nextInt();				}				Node p1 = new Node(x1, y1);				Node p2 = new Node(x2, y2);				segments[i] = new Segment(p1, p2);			}		} catch (Exception e) {}		/* sets the parent sets of every point/node to itself */		for (int j = 0; j < segments.length; j++) {			LinkedList<Node> toAdd1 = new LinkedList<Node>();			LinkedList<Node> toAdd2 = new LinkedList<Node>();			toAdd1.add(segments[j].getP1());			toAdd2.add(segments[j].getP2());			sets.add(toAdd1);			sets.add(toAdd2);		}		/* sets the parent of each point/node according to their position in the sets list */		for (int n = 0; n < sets.size(); n++) {			Node p = sets.get(n);			p.setParent(n);			sets.set(n, p);		}		for (int k = 0; k < segments.length; k++) {			if (sets.get(k).contains(segments[k].getP1()) && sets.get(k).contains(segments[k].getP2())) {				// linesDrawn will not get incremented because drawing this segment will complete the cycle			}			else {				if (sets.get(segments[k].getP1().getParent()).size() > sets.get(segments[k].getP2().getParent()).size()) {					LinkedList<Node> toAdd = sets.get(segments[k].getP2().getParent());					LinkedList<Node> setToAdd = sets.get(sets.get(segments[k].getP1().getParent())).addAll(toAdd);					sets.set(sets.get(segments[k].getP1().getParent()), setToAdd);					sets.remove(segments[k].getP2().getParent());					linesDrawn++;				}				else {					LinkedList<Node> toAdd = sets.get(segments[k].getP1().getParent());					LinkedList<Node> setToAdd = sets.get(sets.get(segments[k].getP2().getParent())).addAll(toAdd);					sets.set(sets.get(segments[k].getP2().getParent()), setToAdd);					sets.remove(segments[k].getP1().getParent());					linesDrawn++;				}			}		}		System.out.println("Lines drawn : " + linesDrawn);	}}

/* *	Author: maeb *	2014 */public class Segment {	private Node p1, p2;	private int parent;	public Segment (Node p1, Node p2) {		this.p1 = new Node(p1);		this.p2 = new Node(p2);	}	public Node getP1() {		return p1;	}	public Node getP2() {		return p2;	}}

/* *	Author: maeb *	2014 */import java.awt.Point;public class Node extends Point {	private int parent;	public Node () {		super ();	}	public Node (int x, int y) {		super (x, y);	}	public Node(Node n) {		super(n);	}	public void setParent(int p) {		this.parent = p;	}	public int getParent() {		return this.parent;	}}

[wolfsinner]

@Maximation, I'd like to start by recommending you not to go the List of Lists path. Trust me when I tell you that it'll be harder to fix this than to write a different approach. I know what you were attempting to do: model your union-find exactly after its set definition. The problem is that lists aren't sets, so you'll even have trouble with repeated points.
My suggestion is the following (it's the same I suggested before, but I'll elaborate). You'll learn from this approach.
First, understand what a Map is. A Map maps a key to a value. What this means is that you use a unique key to retrieve a value associated to it. This is analogous to looking up a word in a Dictionary (which is often used as an alternative name for a Map), where you would look up a word and get its definition. The difference is that Maps can have any type as their key, and any type as their value. Dictionary example:

Map<String, String> dictionary = new HashMap<String, String>();dictionary.put("Apple", "[insert apple definition]");dictionary.put("Asynchronous", "[insert definition]");//....//Now you could look up any word you added to the map and get its valueSystem.out.println(dictionary.get("Apple")); //this would print the definition of apple

 
Now, how can this be used for union-find? You want to be able to distinguish every point individually (ideally, fast), and get their set representative. The representative is the element of the set that is chosen to represent that set. As you've seen on the page posted by Ciccioo, sub-sets are represented as trees, and the whole set is a forest of trees.
For example, if S = {{1, 2, 3}, {4, 5}}, this could be represented as 2 trees. Let's imagine that, for set {1, 2, 3}, 2 is the set representative: then 1 and 3 would have to be children of 2, directly or indirectly, and representative(1 and 3) = 2.
 
Back to the map. You'll have to agree that a string such as  x + " " + y  unequivocally identifies a single cartesian point. So let's use that as a key on the map. Now what would our value be? We want to be able to, given a point, find its set representative. We can create a structure that holds the necessary data. A Node class that holds the node parent of a given point could be used to iteratively obtain the representative. Something like:

 

So something as simple as this would do:

Great! We have modelled our disjoint-set! How do we go about implementing union-find itself though? Let's start by looking at union. You know that you should "unite" two elements if they don't belong to the same set, ie, if they have different representatives. So, we get the representatives as parameters, we check if they're different. If they are, we unite them!

 

Alright, so now we can join two sets together by changing the parent of one of the representatives! But.. How do we actually get the representatives? Essentially, we iteratively check if Node.getParent() == null. Once it does, we've reached the representative. Let's take a look at a possible find implementation.

 

Nice! We know have a fully functioning version of union-find, that doesn't really check for any validity, but still works if you use it properly. So let's use it to solve the problem! Solving Polygon Phobia is now as trivial as this (pseudo-code):

 

So there you have it. I hope that helps you in understanding a simple union-find implementation. I didn't test any of the code, so I can't guarantee it all works (historically it does), but you get the idea.

Happy coding!

public class Node {     private Node parent; //parent is null if this node is a representative     public Node(){          this.parent = null;      }     public Node(Node parent){          this.parent = parent;     }     public Node getParent(){          return this.parent;     }     public Node setParent(Node parent){          this.parent = parent;     }} 

Map<String, Node> uf = new HashMap<String, Node>();

public void union(Node rep1, Node rep2){     //Notice that we can compare them directly. They are the same representatives if the Node object is the same     if(rep1 != rep2){          rep2.setParent(rep1);     }}/*This code is an overly simplified version of a good union code. If you want a better version please look at the code I supplied a few posts back.*/ 

public Node find(String element){     //First we get the Node that is associated to the element     //we want to find the representative of.     //Notice that it may so happen that the key isn't yet "set" on the map.     //We should check. (Remember that this.uf is the Map we defined earlier)     Node rep = null;     if(this.uf.containsKey(element)){          //If the key IS set, let's find the representative          rep = this.uf.get(element);          while(rep.getParent() != null) rep = rep.getParent();     } else {          //If the key isn't set yet, it means that the point does not belong to any set.          //So let's take this chance to create a set for himself, where he is his own reprepresentative.          rep = new Node();          this.uf.put(element, rep);     }     return rep;}/***Again, this is not super optimized. You could do what is called path compression.Path compression basically means that before you return the representative, you set the node's parent to the representative, so that posterior searches are faster. But this works just fine as well.***/ 

for each Segment s:     String point1 = s.getPoint1.getX() + " " + s.getPoint1.getY();     String point2 = s.getPoint2.getX() + " " + s.getPoint2.getY();     Node rep1 = find(point1);     Node rep2 = find(point2);     if(rep1 != rep2){ //are they on the same set?          //if not, unite them, and draw that line!          union(rep1, rep2);          linesDrawn++;     } 

[Maximation]

-snip-

 

Thank you very much! I have solved this problem with the help of these awesome forum members.

I can add another concept to my list of things I understand, this is an awesome way to learn new concepts and algorithms, thank you very much.

Maybe I can improve my code through implementing some things, but not right now, maybe later.

 

Here is my final code :

(It looks a lot like the code @wolfsinner provided in the previous posts, mainly because he explained it to me brilliantly)

 

 

Special thanks to @wolfsinner and @Ciccioo for helping me out and explaining these new concepts and algorithms to me, it is truly amazing!

/* * Author : maeb * 2014 */import java.util.Scanner;import java.util.Map;import java.util.HashMap;public class Main {	private static Map<String, Node> unionFind = new HashMap<String, Node>();	public static void main(String[] args) {		Scanner in = new Scanner(System.in);		int linesDrawn = 0;		/* integer on the first line represents the number of segments it will exist out of */		int numSegments = in.nextInt();				for (int i = 0; i < numSegments; i++) {			String p1 = in.nextInt() + " " + in.nextInt(); 			String p2 = in.nextInt() + " " + in.nextInt(); 			Node parent1 = find(p1);			Node parent2 = find(p2);			if (parent1 != parent2) {				union(parent1, parent2);				linesDrawn++;			}		}		System.out.println("Lines drawn : " + linesDrawn);	}	private static void union(Node representive1, Node representive2) {		if (representive1 != representive2) {			representive2.setParent(representive1);		}	}	private static Node find(String key) {		Node tmp;		if (unionFind.containsKey(key)) {			tmp = unionFind.get(key);			while (tmp.getParent() != null)				tmp = tmp.getParent();		}		else {			tmp = new Node();			unionFind.put(key, tmp);		}		return tmp;	}}

/* *	Author: maeb *	2014 */public class Node {	private Node parent;	public Node () {		this.parent = null;	}	public Node (Node p) {		this.parent = p;	}	public void setParent(Node p) {		this.parent = p;	}	public Node getParent() {		return this.parent;	}}

[gauvinic]

So I finally finished this one yesterday. First, refused to look at the help here on the thread and came up with

what is exactly the union-find algorithm. However, it was buggy with the longer example input, drawing one more 

line than it should have. The way I organized it was different (only used vectors), so I eventually gave up and looked

online for help. Found an implementation of Union-Find similar to my currently used one, but using hash maps.

Learned they wouldn't work with my struct, so I had to find a way to rewrite all the points as ints. Simple, but after, 

I found I was still getting an error in the same spot. This was all on day one. I gave up for a while, went to HackerRank

to try some of their stuff out, then did other random stuff online for a few days. Came back to look it over once more, and

it turns out I was changing the wrong element's parent... 

 

Long story short, I learned alot with this problem compared to the others. Will start on the last one either tonight or tomorrow.

 

#include <vector>#include <string>#include <unordered_map>#include <iostream>#include <fstream>using namespace std;struct point {	int x, y;	bool operator==(const point& rhs) {		return x == rhs.x && y == rhs.y;	}};class Disjoint_set {public:	Disjoint_set() {}	void setUniverse(vector<int> vec) {		universe = vec;		for (int x : universe) {			PARENT[x] = x;			DEPTH[x] = 0;		}	}	int findParent(int item) {		if (PARENT[item] == item)			return item;		else {			counter++;			return findParent(PARENT[item]);		}	}	void Union(int pt1, int pt2) {		if (DEPTH[pt1] < DEPTH[pt2])			PARENT[findParent(pt2)] = findParent(pt1);		else if (DEPTH[pt1] > DEPTH[pt2])			PARENT[findParent(pt1)] = findParent(pt2);		else {			if (pt1 > pt2) {				PARENT[findParent(pt2)] = findParent(pt1);				DEPTH[pt1]++;			}			else {				PARENT[findParent(pt1)] = findParent(pt2);				DEPTH[pt2]++;			}		}	}	bool completesCycle(int a, int b) {		if (findParent(a) == findParent(b))			return true;		return false;	}private:	int counter = 0;	vector<int> path;	vector<int> universe;	unordered_map<int, int> PARENT;	unordered_map<int, int> DEPTH;};template<class T>bool has(vector<T> vec, T pt);int psuedoPointVal(vector<point> vec, point pt);int draw(vector<vector<int>> psuedo);vector<vector<int>> interpretFile();Disjoint_set art;int main(void) {	for (int i = 0; i < 6; i++)		cout << draw(interpretFile()) << endl;	system("pause");}template<class T>bool has(vector<T> vec, T item) {	for (int i = 0; i < vec.size(); i++) {		if (vec[i] == item)			return true;	}	return false;}int psuedoPointVal(vector<point> vec, point pt) {	for (int i = 0; i < vec.size(); i++) {		if (vec[i] == pt)			return i;	}	return -1;}int draw(vector<vector<int>> lines) {	int a, b, drawn = 0;	for (int i = 0; i < lines.size(); i++) {		a = lines[i][0];		b = lines[i][1];		if (!art.completesCycle(a, b)) {			art.Union(a, b);			drawn++;		}	}	return drawn;}vector<vector<int>> interpretFile() {	vector<point> points;	vector<int> psuedoPoints;	vector<vector<int>> lines;	int size, a, b, c, d;	point pt1, pt2;	string fileName = "";	cout << "Enter filename w/o ext here: ";	cin >> fileName;	fileName += ".txt";	ifstream in(fileName);	in >> size;	for (int i = 0; i < size; i++) {		vector<int> temp;		in >> a >> b >> c >> d;		pt1.x = a;		pt1.y = b;		pt2.x = c;		pt2.y = d;		if (i == 0) {			points.push_back(pt1);			points.push_back(pt2);			psuedoPoints.push_back(psuedoPointVal(points, pt1));			psuedoPoints.push_back(psuedoPointVal(points, pt2));		}		else {			if (!has(points, pt1))				points.push_back(pt1);			if (!has(points, pt2))				points.push_back(pt2);			if (!has(psuedoPoints, psuedoPointVal(points, pt1)))				psuedoPoints.push_back(psuedoPointVal(points, pt1));			if (!has(psuedoPoints, psuedoPointVal(points, pt2)))				psuedoPoints.push_back(psuedoPointVal(points, pt2));		}		temp.push_back(psuedoPointVal(points, pt1));		temp.push_back(psuedoPointVal(points, pt2));		lines.push_back(temp);	}	art.setUniverse(psuedoPoints);	return lines;}