Starting from:
$29.99
Homework 6 Solution
Assignment
Your assignment is to compute independent cycles in a graph using the union- find algorithm.
This will require (I think) you to use map and vector containers, iterators, and some overloaded operators.
ALL GRAPHS FOR THIS ASSIGNMENT ARE ASSUMED TO BE UNDIRECTED GRAPHS.
You must overload the output operator for the Arc class. If you do this Java-like, you can start by writing a toString function, and then your overloading just calls that function. That lets you write code to do the main functionality of the assignment first and deal with the overloading only when you are ready to do that.
Background
Finding cycles in graphs is a hugely important task, although you might not think of it in the abstract. Cycle finding would allow you to determine redundant paths in the USC computer network, for example, or in a larger network. Cycle finding is done in optimizing compilers to detect whether or not assignment of values to variables can be done in independent threads. Chip and board design often require one to verify that electrical loops are dealt with properly. And finding who is communicating with whom would probably be something that could be inferred from the documents Snowden released.
Union-Find
The union-find algorithm is one way to get an independent set of cycles, that is, a set of cycles such that all cycles in a graph can be expressed as a sum of cycles from the independent set.
The input to your program will be one number n that is the number of arcs in the graph. This will be followed by n lines of data, each of which is a pair of integers a, b, representing an arc (a, b) from node a to node b. REMEMBER THIS IS AN UNDIRECTED GRAPH, so a to b is the same as b to a. We will assume that the nodes in the graph are represented by integers so as to simplify things. The integers don’t actually have to be consecutive, but they probably will be.
The algorithm proceeds by building trees that represent paths in the graph. Every node starts by being the root of its own tree. In my code, I represent this as an arc from the node to itself, but you could represent this as an arc from the node to a dummy value for a node. Either works just fine, and the only difference is the comparison you make in your function that returns whether or not a node is the root of its tree.
When you read in an arc (a, b), you call the find function to find the root of the tree in which a lives. Then you call the find function to find the root of the tree in which b lives.
If these two roots are different, then you do a “union” of the two trees so that the new tree now contains the arc. I recommend that you standardize your code as if you had a directed graph and that you write the code as if the arc went from the node with the larger value to the node with the smaller value. The graphs are undirected, and this convention does not affect the correctness of the algorithm, but it will make your coding simpler to have a convention. Otherwise, you would have to think harder about duplication of arcs and paths and you’d have to notice when an arc got turned around from the way it was written in the input file to the way it was represented in the computer. Don’t make life more difficult than it already is.
Now, if you chase up to the root from a and b, and you find that both trees have the same node r as the root, that means that there is a path down from r to a and a path down from r to b, and thus that adding the arc from a to b would create a cycle.
Don’t add the arc to the tree. Instead, output the (a, b) arc, and then the path from a to r and the path b to r. This is the list of arcs forming a cycle.
Examples
Let’s say you have trees
(7, 5)(5, 3)(3, 1)(1, 1),
(4, 2)(2, 2),
(8, 8)
and and you encounter an arc (8, 3).
Chasing the 3 to its root, we get 1. Chasing the 8 to its root, we get 8. These are different, so we do a union. We can think of this as if things were directed, with the 8 as the “from” node and the 3 as the “to” node. What we want to do is to union the (8, 3) arc so that the path to its root is
(8, 3)(3, 1)(1, 1).
That’s really just like setting up a linked list.
Now, if we had then encounter an arc (7, 8), we would chase the 7 and the 8 to the common root 1.
Instead of adding this arc to a tree, we would output
(8, 7)(7, 5)(5, 3)(3, 1),
and
(8, 3)(3, 1).
(In my code I put the cycle-making arc as the first arc of the first path.) BONUS OPPORTUNITY: I will give you full marks if you were to output
(7, 8),
and
(7, 5)(5, 3)(3, 1)(1, 1),
(8, 3)(3, 1)(1, 1).
That is, I will not require you to output ONLY the exact cycle. If you want to quit when you output the existence of the cycle and the information needed to show the complete cycle, that’s ok. I will provide 10 bonus points for trimming back the two paths to roots so as to write only the cycle.
Your assignment is to compute independent cycles in a graph using the union- find algorithm.
This will require (I think) you to use map and vector containers, iterators, and some overloaded operators.
ALL GRAPHS FOR THIS ASSIGNMENT ARE ASSUMED TO BE UNDIRECTED GRAPHS.
You must overload the output operator for the Arc class. If you do this Java-like, you can start by writing a toString function, and then your overloading just calls that function. That lets you write code to do the main functionality of the assignment first and deal with the overloading only when you are ready to do that.
Background
Finding cycles in graphs is a hugely important task, although you might not think of it in the abstract. Cycle finding would allow you to determine redundant paths in the USC computer network, for example, or in a larger network. Cycle finding is done in optimizing compilers to detect whether or not assignment of values to variables can be done in independent threads. Chip and board design often require one to verify that electrical loops are dealt with properly. And finding who is communicating with whom would probably be something that could be inferred from the documents Snowden released.
Union-Find
The union-find algorithm is one way to get an independent set of cycles, that is, a set of cycles such that all cycles in a graph can be expressed as a sum of cycles from the independent set.
The input to your program will be one number n that is the number of arcs in the graph. This will be followed by n lines of data, each of which is a pair of integers a, b, representing an arc (a, b) from node a to node b. REMEMBER THIS IS AN UNDIRECTED GRAPH, so a to b is the same as b to a. We will assume that the nodes in the graph are represented by integers so as to simplify things. The integers don’t actually have to be consecutive, but they probably will be.
The algorithm proceeds by building trees that represent paths in the graph. Every node starts by being the root of its own tree. In my code, I represent this as an arc from the node to itself, but you could represent this as an arc from the node to a dummy value for a node. Either works just fine, and the only difference is the comparison you make in your function that returns whether or not a node is the root of its tree.
When you read in an arc (a, b), you call the find function to find the root of the tree in which a lives. Then you call the find function to find the root of the tree in which b lives.
If these two roots are different, then you do a “union” of the two trees so that the new tree now contains the arc. I recommend that you standardize your code as if you had a directed graph and that you write the code as if the arc went from the node with the larger value to the node with the smaller value. The graphs are undirected, and this convention does not affect the correctness of the algorithm, but it will make your coding simpler to have a convention. Otherwise, you would have to think harder about duplication of arcs and paths and you’d have to notice when an arc got turned around from the way it was written in the input file to the way it was represented in the computer. Don’t make life more difficult than it already is.
Now, if you chase up to the root from a and b, and you find that both trees have the same node r as the root, that means that there is a path down from r to a and a path down from r to b, and thus that adding the arc from a to b would create a cycle.
Don’t add the arc to the tree. Instead, output the (a, b) arc, and then the path from a to r and the path b to r. This is the list of arcs forming a cycle.
Examples
Let’s say you have trees
(7, 5)(5, 3)(3, 1)(1, 1),
(4, 2)(2, 2),
(8, 8)
and and you encounter an arc (8, 3).
Chasing the 3 to its root, we get 1. Chasing the 8 to its root, we get 8. These are different, so we do a union. We can think of this as if things were directed, with the 8 as the “from” node and the 3 as the “to” node. What we want to do is to union the (8, 3) arc so that the path to its root is
(8, 3)(3, 1)(1, 1).
That’s really just like setting up a linked list.
Now, if we had then encounter an arc (7, 8), we would chase the 7 and the 8 to the common root 1.
Instead of adding this arc to a tree, we would output
(8, 7)(7, 5)(5, 3)(3, 1),
and
(8, 3)(3, 1).
(In my code I put the cycle-making arc as the first arc of the first path.) BONUS OPPORTUNITY: I will give you full marks if you were to output
(7, 8),
and
(7, 5)(5, 3)(3, 1)(1, 1),
(8, 3)(3, 1)(1, 1).
That is, I will not require you to output ONLY the exact cycle. If you want to quit when you output the existence of the cycle and the information needed to show the complete cycle, that’s ok. I will provide 10 bonus points for trimming back the two paths to roots so as to write only the cycle.
1 file (309.4KB)
