Advanced Graph-Joining:
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 dierent 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).
For example, we shall introduce the graph I which is as follows:
| tank1 | tank2 | |||
| 3 | 45 | 50 | ||
| 100 | 200 | |||
10
front Z tank3
Figure 6: graph I
A comparison of Graphs G and I side by side:
| 9 | ||||||||||
| a | 2 | g | 2 | Q | tank1 | tank2 | ||||
| 15 | 3 | |||||||||
| 1 | 7 | 45 | 50 | |||||||
| 1 | 100 | 200 | ||||||||
| c | 6 | w | front | 10 | Z | tank3 | ||||
Figure 7: graph G and I in one diagram
As you can see, graphs G and I do not have any shared vertices or edges.
The resultant super graph of G and I via H would be:
| 9 | ||||||||
| a | 2 | g | 2 | Q | tank1 | tank2 | ||
| 12 | 15 | 5 | 3 | |||||
| 1 | 1 | 7 | 3 | 45 | 100 | 200 | 50 | |
| c | w | front | 2 | Z | tank3 | |||
| 2 | 2 | |||||||
Figure 8: super-graph of graphs G,H, and I
Once you have computed the super-graph for any three graphs you should write it to a le; named format: supergraphGraphOne-TwoIntermediateGraphTwo-Three.txt where the graphs are listed in order received but with the intermediary graph in the middle. For example, for the graphs G, H and I we would write:
7
a:c:g:w:Q:front:Z:tank1:tank2:tank3
| 0 | 1 | 2 | 1 | 9 | 12 | 0 | 0 | 0 | 0 | ||
| 1 | 0 | 0 | 2 | 0 | 0 | 0 | 0 | 0 | 0 | ||
| 2 | 0 | 0 | 15 | 2 | 0 | 0 | 0 | 0 | 0 | ||
| 1 | 2 | 15 | 0 | 7 | 2 | 0 | 0 | 0 | 0 | ||
| 9 | 0 | 2 | 7 | 0 | 3 | 5 | 0 | 0 | 0 | ||
| 12 | 0 | 0 | 2 | 3 | 0 | 2 | 3 | 0 | 0 | ||
| 0 | 0 | 0 | 0 | 5 | 2 | 0 | 45 | 100 | 0 | ||
| 0 | 0 | 0 | 0 | 0 | 3 | 45 | 0 | 0 | 200 | ||
| 0 | 0 | 0 | 0 | 0 | 0 | 100 | 0 | 0 | 50 | ||
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 200 | 50 | 0 | ||
to the le named supergraphGHI.txt . If we received the graphs in a dierent order (eg. G, I, H and H, I,G) we would write to a le called supergraphGHI.txt and supergraphIHG.txt respectively as H is the intermediate
graph. If there is no intermediate graph, you may simply list them in the order received.
The supergraph gives Ms. Moor a full piping system covering multiple systems wither everything (ideally) connected (although it does include superuous pipes).
8 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 base graphs to reach each other via the intermediate graph.
Write a program (connectivity.py ) which reads in a supergraph (or any combined graph) and determines whether every vertex in this combined graph can reach every other vertex in that 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 as input we would write:
graph IS connected
to a le named supergraphGHIconnectivity.txt
As another example, let’s consider graph J which is as follows:
| c | w | front | 2 | Z | |
| 4 | |||||
20
R
Figure 9: graph J
The supergraph GJI would look like this:
| 9 | |||||||||
| a | 2 | g | 2 | Q | tank1 | tank2 | |||
| 15 | 3 | ||||||||
| 1 | 3 | 1 | 7 | 45 | 100 | 200 | 50 | ||
| c | 6 | w | front | 2 | Z | tank3 | |||
| 4 | |||||||||
20
R
Figure 10: super-graph of graphs G,J, and I
Given the supergraph GJI and G, J, and I as input we would write:
graph IS NOT connected
to a le named supergraphGJIconnectivity.txt This is as there are some vertices which cannot reach other vertices in the supergraph (ex. a cannot reach Z).
Note: we can run connectivity on any combined graph; this means for example you can run it on G_or_I.txt by using passing that graph in (eg. GorI as input) which would print:
graph IS NOT connected
to the le G_or_Iconnectivity.txt
The connectivity checking allows Ms. Moor to be convinced that the network suggested doesn’t leave any sections isolated.
9
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 (eg. appearing in both A and B), like with the union, we only include the cheapest weight edge.
To illustrate, let us introduce one nal graph K.
| Q1 | 1 | Q2 | |
| 7 | 5 | 9 | |
4
Q tank1
12 12
2
- front
12
| w1 | 100 w2 | ||||||||||
| Figure 11: graph K | |||||||||||
| Q1 | 1 | Q2 | |||||||||
| 9 | 7 | 5 | 9 | ||||||||
| a | 2 | g | 2 | Q | 4 | tank1 | tank2 | ||||
| 15 | 12 | 3 | |||||||||
| 1 | 1 | 2 | 45 | 100 | 200 | 50 | |||||
| c | 6 | w | front | 10 | Z | tank3 | |||||
- 2
w1 100 w2
Figure 12: super-graph of graphs G,K, and I
There are many paths to connect the graphs G and I together, we could use the edge < Q,front> for a cost of 12, or the path <w,w2>,<w2,w1>,<w1,tank1> for a cost of 1 + 100 + 2 = 103 but the cheapest way to connect these graphs together is with the path < Q,Q2>,<Q2,Q1><Q1,tank1> for a cost of 4 + 1 + 5 = 10 This makes the cheapest connection graph: 10
| Q1 | 1 | Q2 | ||||||||
| 9 | 5 | |||||||||
| a | 2 | g | 2 | Q | 4 | tank1 | tank2 | |||
| 15 | 3 | |||||||||
| 1 | 1 | 2 | 45 | 100 | 200 | 50 | ||||
| c | 6 | w | front | 10 | Z | tank3 | ||||
| Figure 13: cheapest connection of graphs | G and I via K | |||||||||
Notice how the only edges and vertices added from graph K are those needed to connect the two graphs. Graph K and graph G both include the edge <w,Q> and graph K’s edge is cheaper, so in that case we use the cheaper, however we do not include the vertex w1 or edge <Q,Q2> or any other edges or vertices only found in K, only those that are necessary to connect graphs G and I together
We will ask you to attempt two dierent approaches here: greedy and brute-force.
In both cases your code would be expected to produce three les, one being the adjacency matrix of the resultant graph, another would be the le produced by your connectivity checking code for that resultant graph and the same base les, and the very last le would write to a le the cost of the path chosen.
For example for the graphs G, I, and K the le for the resultant graph would be:
a:c:g:w:Q:Q1:Q2:front:Z:tank1:tank2:tank3
0 1 2 1 9 0 0 0 0 0 0 0
| 1 0 0 6 0 0 0 0 0 0 0 0 | |||||||||||||
| 2 0 0 15 2 0 0 0 0 0 0 0 | |||||||||||||
| 1 6 15 0 2 0 0 0 0 0 0 0 | |||||||||||||
| 9 0 2 2 0 0 4 0 0 0 0 0 | |||||||||||||
| 0 0 0 0 0 0 1 0 0 5 0 0 | |||||||||||||
| 0 0 0 0 4 1 0 0 0 0 0 0 | |||||||||||||
| 0 0 0 0 0 0 0 0 10 3 0 0 | |||||||||||||
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 10 | 0 | 45 | 100 | 0 | ||
| 0 | 0 | 0 | 0 | 0 | 5 | 0 | 3 | 45 | 0 | 0 | 200 | ||
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 100 | 0 | 0 | 50 | ||
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 200 | 50 | 0 | ||
and the connectivity check would say
graph IS connected
and nally the le for the cost of the path chosen would be:
10
The cheapest connection graph will show Fathima the best pipes to use to connect any two existing pipe networks together. 11
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.txtgreedyGraphOneGraphTwoGraphThreepathCost.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 todetermine 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
bruteforceGKIpathCost.txt
No comments:
Post a Comment