**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: cinematographer-Intermediate-Threescore 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 supergrass . If we received the graphs in a die rent order (eg. G, I, H and H, I,G) we would write to a le called supergrass and historiographer respectively as H is the intermediate

graph. If there is no intermediate graph, you may simply list them in the order received.

The super graph gives Ms. Moor a full piping system covering multiple systems wither everything (ideally) connected (although it does include superfluous pipes).

8 2.2 checking connectivity

Now that you have code in place to produce a super-graph, we should conrm 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 ) which reads in a super graph (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 enamel should be the enamel of the combined graph with “connectivity” at the end.

For example given the super graph GHEE 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. G_{o}r_{I} _{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

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 (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.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

bruteforceGKIpathCost.txt