Computer Science-QA175

Computer Science-QA175 Online Services

 

Context
 
Graphs apply to many problems and are common in issues of connectivity and networks. For this assignment we are imagining ourselves as professional programmers already and have taken on a client, a Ms. Fathima Arda Moor. Ms. Moor runs a large wheat farm in western Victoria (Australia) and has recently purchased some of her neighbouring farms; she wishes to combine together the water systems to allow for more e_cient irrigation of each farm’s crops.
Fortunately each of these farms had their piping systems mapped in blueprints (which are relatively easy to digitise); Unfortunately some of these farms include multiple separate piping systems for handling irrigation so she has turned to you for help.
 

1 Simple Graph-Joining

 
In this task you will be considering di_erent ways of combining two graphs together into a single graph. This will help Fathima connect together some of the more straightforward piping systems between farms. For each of the problems in this task, you can expect to receive weighted graphs in adjacency matrix format (with the weight representing the relative likelihood of that pipe breaking), for example the graph G (found in G.txt)
 

1.1 Interpreting fille input
 
The assignment will include several example graphs to test your code with, each will be found within their own _le with each _le representing an adjacency matrix and the format followed is as such:
 
firstVertexName:…:lastVertexName
space separated values for edges from firstVertexName
…
space separated values for edges from lastVertexName

Prepare a python program (graphFileOps.py) which accepts a _le name and produces an adjacency matrix based on the data in that _le. Make sure that you can identify vertices by their name (which need not be one character) and be sure to close the _le when you are done with it.
 

1.2 Writing to a file
 
Later on in this assignment you will be required to write adjacency matrices to a _le. Add to your existing python _le (graphFileOps.py) a program which accepts a _le name and a table representing an adjacency matrix which writes the adjacency matrix to that _le. This should follow the same format as the input _les. A good way to test this would be to read in one of the input _les and write to another _le. If you code is correct, these _les should be identical. Be sure to close the _le when you are done with it.
 
1.3 Intersection
 
Write a python program (intersection.py) which accepts two _le names (representing graphs) and _nds the intersection of both graphs. In this context, the intersection refers to set of vertices and edges that are shared by any two graphs. Where an edge is shared but has deferent weights in each graph, the weight of the edge in the intersection graph is the larger of the weights. Where an intersection includes a vertex with no edges, that vertex is removed from the intersection
 

G and H share the following vertices: a,c,w and Q
G and H share the following edges: , and
As the intersection does not include any edges connecting Q, the vertex Q is not included in the intersection Once your program has determined the intersection between two graphs, it should write the resultant graph to a _le; this _le should be named in the following format: graphOne_and_graphTwo.txt so for example if graph G and H were input (from _les G.txt and H.txt respectively), the resultant graph would write the following
 
a:c:w
0 19 1
19 0 6
1 6 0
to the _le named G_and_H.txt The intersection graph will allow Ms. Moor to remove the most unreliable pipes from the system where they are duplicated.
 

1.4 Union
 
Write a python program (union.py) which accepts two _le names (representing graphs) and _nds the union of both graphs. In this context, the union refers to set of vertices and edges that are in either of the two graphs. Where an edge is shared but has di_erent weights in each graph, the weight of the edge in the union graph is the smaller of the weights. the union graph of G and H includes all of the vertices and edges of the graphs G and H however the graphs share the following edges: , and and so only the cheaper of these edges is included in the _nal union graph. Once your program has determined the union between two graphs, it should write the resultant graph to a file; this _le should be named in the following format: graphOne_or_graphTwo.txt so for example if graph G and H were input, the resultant graph would write the following
 
a:c:g:w:Q:front:Z
0 1 2 1 9 12 0
1 0 0 2 0 0 0
2 0 0 15 2 0 0
1 2 15 0 7 2 0
9 0 2 7 0 3 5
12 0 0 2 3 0 2
0 0 0 0 5 2 0
 
to the _le named G_or_H.txt The union graph gives Ms. Moor insight into the complete piping network across a set of farms.
 

1.5 Deference
 
Write a python program (difference.py) which accepts two _le names (representing graphs) and _nds the di_erence between both graphs. In this context, the di_erence refers to set of edges that are in only one of the two graphs. Where a vertex has no edges in the di_erence it is not included in the resultant graph.
 
The di_erence graph of G and H includes all of the vertices of the graphs G and H however the graphs share the following edges: , and and so these edges are removed from the _nal di_erence graph (regardless of their weight). Since removal of these edges results in c having no edges, c is not included in the di_erence graph
Once your program has determined the di_erence between two graphs, it should write the resultant graph to a _le; this _le should be named in the following format: graphOne_xor_graphTwo.txt so for example if graph G and H were input, the resultant graph would write the following
 
a:g:w:Q:front:Z
0 2 0 9 12 0
2 0 15 2 0 0
0 15 0 7 2 0
9 2 7 0 3 5
12 0 2 3 0 2
0 0 0 5 2 0
to the _le named G_xor_H.txt This will show Ms. Moor what new piping is introduced between two systems.
 

You can read more about our case study assignment help services here.
 

 

2 Advanced Graph-Joining

 
This section will have you looking at some methods from connecting two graphs via another (intermediate) graph. In each of these cases you will consider three graphs as input A,B and C (where A \ C = ; but A\B 6= ; and B \C 6= ;). In this case ; represents a graph which is empty (has no edges or vertices). In other words, graphs A and C have no edges or vertices in common but both have edges and vertices in common with graph B. The purpose of this is to produce a means of connecting vertices in graph A with vertices in graph C.

 

Note: that this will only be guaranteed where A, B and C are themselves connected graphs, you are not expected to _nd ways to join disjoint graphs together via other disjoint graphs as this may not be successful.
 

2.1 Super-graph
 
Write a program (supergraph.py) which accepts three _le names for di_erent graphs and, using your work from previous sections, creates a super-graph. In this context a super-graph of N graphs is a graph which includes all of the vertices and edges from all N graphs (using the cheapest edge where edges are shared).
 

2.2 checking connectivity
 
Now that you have code in place to produce a super-graph, we should con_rm that this super-graph actually does allow the vertices in the _rst graph to reach vertices in the last graph via the intermediate graph. Write a program (connectivity.py) which reads in a supergraph (or any combined graph) and the base graphs (that it was developed from) and determines whether any vertex in any of these base graphs can reach any other vertex in any other according to the combined graph. If this is possible, you should write to a _le “graph IS connected”, otherwise you should write to a _le
“graph IS NOT connected”. In both cases the _lename should be the _lename of the combined graph with “connectivity” at the end.
 
For example given the supergraph GHI and G, H, and I as input we would write: graph IS connected
to a _le named supergraphGHIconnectivity.txt
 

2.3 Cheapest Connection
 
Like in the previous part where you were asked to produce a supergraph, this part focuses on ways to connect two graphs together. In this case however we do not wish to include every single edge. Instead, using edges found in B but not A or C, create a graph with all of the vertices and edges of A and C with a single connecting path between vertices in A and vertices in C. We also want the weight of this path (likelihood of breakage) to be minimal. Where an edge is included in multiple base graphs, like with the union, we only include the cheapest weight edge.
 

2.3.1 Greedy
 
Write a program (greedy.py) that accepts three graphs as input (via their _le-names) and follows a greedy approach to determine the cheapest path from the intermediate graph to connect the other two graphs together. As mentioned your program should write to _les for the resultant graph, the connectivity and path cost.
 
You should name these _les as:
greedyGraphOneGraphTwoGraphThree.txt
greedyGraphOneGraphTwoGraphThreeconnectivity.txt
greedyGraphOneGraphTwoGraphThreepathCost.txt
In the case of the graphs G, I, and K that would be:
greedyGKI.txt
greedyGKIconnectivity.txt
greedyGKIpathCost.txt
 

In addition, you should include with your submission a pdf called “greedyDiscussion.pdf” (you may include an .rtf _le if you prefer) where you describe what your approach was and why you chose it. Finally, you should also include in your discussion if and where any issues might arise with your application of greed (as greedy algorithms are not guaranteed to yield optimal results for all problems). Make sure you include your full name and student ID in this _le.
 

2.3.2 Brute-Force
 
Write a program (bruteforce.py) that accepts three graphs as input (via their _le-names) and applies brute- force to determine the cheapest path from the intermediate graph to connect the other two graphs together. As mentioned your program should write to _les for the resultant graph, the connectivity and path cost.
 
You should name these _les as
 
bruteforceGraphOneGraphTwoGraphThree.txt
bruteforceGraphOneGraphTwoGraphThreeconnectivity.txt
bruteforceGraphOneGraphTwoGraphThreepathCost.txt
In the case of the graphs G, I, and K that would be:
bruteforceGKI.txt
bruteforceGKIconnectivity.txt
bruteforceGKIpathCost.txt

 

Product code: Computer science-QA175
 
Looking for best Computer science-QA175 online ,please click here