Does anyone know how to start this C++ programming assignment: For this assignme
ID: 3793086 • Letter: D
Question
Does anyone know how to start this C++ programming assignment:
For this assignment, we will take as input a file containing numerous implicative ("") relationships, and determine if transitivity will provide for additional specific relationships. For example, if our input file includes: A B, A C, A D and D E, we will determine if A E is implied by our set of input relations. Specifically, the input file will describe the direct relationships between up to 26 input elements (named "A," "B," "C," etc.). We will determine if the input implies that the first element ("A") is also related, via some sequence of transitive relationships, to the last element of the input file. Additionally, we will check for such transitive relationships from every fifth element after the first ("F," "K," etc.) to the last element of each input file. Your program will output the results of each relationship search, as follows, either:
– element does not have connectivity to end vertex
– element has connectivity to end vertex
Each input file will include, on the first line, the number of elements for this relationship family Each subsequent line will contain exactly two numbers, representing an implicative relationship from the first to the second element. (For programming convenience, the elements are described by integers rather than letters: A 0, B 1, C 2, etc.) For example, the file: 1 0 0 5 1 1 3 2 3 5 3 6 5 6 6 7 describes 8 data elements (A, B,C,D, E, F, G and H), with the following implicative relationships: A B, A C, A B C, B+ D, B G. C D, D F, F G, For simplification of this problem in all cases BExplanation / Answer
We can model the problem as a graph problem where the implicative "-->" acts as the dircted edge between the node used.
For example A --> B ( there is a directed edge from node A to node B )
To determine tranisitivity between two nodes( X and Y) we need to check whether there is a path from X to Y that can be done using any graph search algorithm like DFS/BFS.
There is a better way to solve the problem using warshall algorithm of computing tranistitive clouser.
Algorithm idea: a path exists between two vertices A, B, iff
there is an edge from A to B; or
there is a path from A to B going through vertex A; or
there is a path from A to B going through vertex A and/or B; or
there is a path from A to B going through vertex A, B, and/or C ... and so on to Z
Example
1 2 3 4 5
1 0 1 1 0 0
2 0 0 0 1 0
3 0 0 0 1 1
4 0 0 0 0 1
5 0 1 0 0 0
Graph(0) = initial matrix above, i.e. this is the matrix showing paths with no intermediate nodes. Graph(1) is the matrix containing all paths from Graph(0) plus all paths with 1 as intermediate node.
Its elements are computed in the following way:
Graph[i][j](1) = 1 if Graph[i][j](0) = 1
Else Graph[i][j](1) = Graph[i][1](0) * Graph[i][j](0)
Thus for all elements that are 0 in Graph(0), we compute the products of the elements in the first column and the first row of Graph(0). Since all elements in the first column are 0, the products will be 0, so Graph(1) will be the same as Graph(0).
Graph(1) =
1 2 3 4 5
1 0 1 1 0 0
2 0 0 0 1 0
3 0 0 0 1 1
4 0 0 0 0 1
5 0 1 0 0 0
Graph(2) will contain all paths computed in Graph(1) plus all paths that contain 2 as an intermediate node
Graph[i][j](2) = 1 if Graph[i][j](1) = 1
Else Graph[i][j](2) = Graph[i][2](1) * Graph[2][j](1)
Here we compute the products of the second column and the second row. The second column contains two non-zero elements, and the second row contains one non-zero element, thus the non-zero products will be:
Graph[1][4](2) = Graph[1][2](1) * Graph[2][4](1) , Graph[5][4](2) = Graph[5][2](1) * Graph[2][4](1)
Graph(2) =
1 2 3 4 5
1 0 1 1 1 0
2 0 0 0 1 0
3 0 0 0 1 1
4 0 0 0 0 1
5 0 1 0 1 0
The new paths are the paths connecting nodes 1 and 4 through node 2, and nodes 5 and 4 through node 2.
Next we compute Graph(3), looking for paths that have intermediate nodes among {1, 2, 3}.
Graph[i][j](3) = 1 if Graph[i][j](2) = 1
Else Graph[i][j](3) = Graph[i][3](2) * Graph[3][j](2)
Here we look at the products of the elements in the third column and the third row. The non-zero products are:
Graph[1][4](3) = Graph[1][3](2) * Graph[1][4](2) , Graph[1][5](3) = Graph[1][3](2) * Graph[1][5](2)
Note that Graph[1][4](2) = 1, which means that we have already found a path between nodes 1 and 2. The new path computed here is the path connecting nodes 1 and 5 through node 3.
Graph(3) =
1 2 3 4 5
1 0 1 1 1 1
2 0 0 0 1 0
3 0 0 0 1 1
4 0 0 0 0 1
5 0 1 0 1 0
Next we compute Graph(4), looking for paths that have intermediate nodes among {1, 2, 3, 4}.
Graph[i][j](4) = 1 if Graph[i][j](3) = 1
Else Graph[i][j](4) = Graph[i][4](3) * Graph[4][j](3)
Similarly we have
Graph(4) =
1 2 3 4 5
1 0 1 1 1 1
2 0 0 0 1 1
3 0 0 0 1 1
4 0 0 0 0 1
5 0 1 0 1 1
Finally, we compute Graph(5)
Graph(5) =
1 2 3 4 5
1 0 1 1 1 1
2 0 1 0 1 1
3 0 1 0 1 1
4 0 1 0 1 1
5 0 1 0 1 1
The matrix shows that no node is connected to node 1. Except node 1, no other node is connected to node 3. Node 1 is connected to all nodes except to itself. All nodes are connected to 2, 4, and 5.
Below is the the C++ implementation for the same idea.
#include <iostream>
using namespace std;
const int sz = 26;
//by default all elements in graph is false
bool graph[sz][sz];
bool compute_transtive_clouser() {
for (int k = 0; k < sz; ++k) {
for (int i = 0; i < sz; ++i) {
for (int j = 0; j < sz; ++j) {
graph[i][j] |= (graph[i][k] & graph[k][j]);
}
}
}
}
int main() {
ifstream fin("input.txt");
int n, u, v;
fin >> n;
for (int i = 0; i < n; ++i) {
fin >> u >> v;
graph[u][v] = 1;
}
compute_transtive_clouser();
//to check the transitivity between any two pair(a,b) we can check the value of graph[a][b] if it is true that mean there is a path from a to b
cout << graph[0][7] << endl;
cout << graph[5][7] << endl;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.