{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Graph Class"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The directed graph will be implemented with an adjacency map. The adjacency map is a dictionary of vertex labels pointing to vertices. \n",
"\n",
"Each vertex stores a list of out-edges. An \"out-edge\" is an edge starting at a particular vertex and pointing out to a different vertex."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"class Vertex:\n",
" \n",
" def __init__(self, label):\n",
" self.label = label\n",
" self.edges = []\n",
" # Used to track if this vertex has been visited during depth-first search.\n",
" self.visited = False\n",
" \n",
" \n",
" def addEdge(self, destinationVertex, weight=1):\n",
" '''Adds an edge with optional weighting. Weights ended up not being relevant for this notebook.'''\n",
" self.edges.append((destinationVertex, weight))\n",
" \n",
" \n",
" def __repr__(self):\n",
" return f\"{self.label}\"\n",
" \n",
" \n",
" def __eq__(self, other):\n",
" return self.label == other.label"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [],
"source": [
"class Graph:\n",
" \n",
" def __init__(self):\n",
" self.vertices = {}\n",
" \n",
" \n",
" def addVertex(self, vertexLabel):\n",
" newVertex = Vertex(vertexLabel)\n",
" self.vertices[vertexLabel] = newVertex\n",
" \n",
" \n",
" def addEdge(self, sourceVertexLabel, destinationVertexLabel, weight=1):\n",
" sourceVertex = self.vertices[sourceVertexLabel]\n",
" destinationVertex = self.vertices[destinationVertexLabel]\n",
" sourceVertex.addEdge(destinationVertex, weight)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Test Graph"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
""
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [],
"source": [
"G = Graph()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Vertices"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"['A', ' B', ' C', ' D', ' E', ' F']"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"labels = \"A, B, C, D, E, F\".split(\",\")\n",
"labels"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [],
"source": [
"for label in labels:\n",
" # strip white space from each letter e.g. \" B\" -> \"B\"\n",
" G.addVertex(label.strip())"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"{'A': A, 'B': B, 'C': C, 'D': D, 'E': E, 'F': F}"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"G.vertices"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Edges"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [],
"source": [
"edges = [\n",
" (\"A\", \"C\"),\n",
" (\"B\", \"A\"),\n",
" (\"B\", \"D\"),\n",
" (\"D\", \"C\"),\n",
" (\"C\", \"E\"),\n",
" (\"C\", \"F\")\n",
"]"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [],
"source": [
"for edge in edges:\n",
" G.addEdge(edge[0], edge[1])"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[(C, 1)]"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"G.vertices['A'].edges"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Finding a Central Station\n",
"\n",
"## What is a Central Station?"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"> A **central station** is a vertex that can reach all other vertices in the graph."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Algorithm\n",
"\n",
"Basically:\n",
"\n",
"1. Pick a random vertex.\n",
"2. Perform DFS. Give each vertex a pre and post number.\n",
"3. Run DFS again, this time from the vertex with the largest post number. If this vertex can reach all other vertices, it is a central station. If it cannot, the graph has no central station."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Implementation\n",
"\n",
"As far as the implementation is concerned, there is no real point to labeling each vertex with pre and post numbers. The last node visited will be the node with the highest post number and since this is the only vertex we care about numbering is unnecessary."
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [],
"source": [
"def explore(vertex, count):\n",
" '''Recursive DFS generator used to explore one vertex.'''\n",
" vertex.visited = True\n",
" # previsit\n",
" count[0] = count[0] + 1\n",
" yield (\"previsit\", count[0], vertex)\n",
" \n",
" for edge in vertex.edges:\n",
" child = edge[0]\n",
" if not child.visited:\n",
" # visit children\n",
" yield from explore(child, count)\n",
" \n",
" \n",
" # postvisit\n",
" count[0] = count[0] + 1\n",
" yield (\"postvisit\", count[0], vertex)"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [],
"source": [
"def dfs(graph, vertexLabel):\n",
" '''DFS generator that yields a tuple of data for each vertex\n",
" (pre and post visit). The tuple is:\n",
" ('previsit' or 'postvisit', count, vertex).'''\n",
" \n",
" # For pre and post numbering. Not really needed, but could be helpful to see this.\n",
" # Using a list as a hack to keep count mutable.\n",
" count = [0]\n",
" \n",
" # Set all vertices to unvisited.\n",
" for vertex in graph.vertices.values():\n",
" vertex.visited = False\n",
" \n",
" # Get the starting vertex.\n",
" startingVertex = graph.vertices[vertexLabel]\n",
" \n",
" # Explore the starting vertex.\n",
" yield from explore(startingVertex, count)\n",
" \n",
" # If there are vertices in the graph that are not connected to the starting\n",
" # vertex, they will be missed. Check for this.\n",
" for vertex in graph.vertices.values():\n",
" if not vertex.visited:\n",
" # This vertex hasn't been explored yet.\n",
" yield from explore(vertex, count)"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"('previsit', 1, C)\n",
"('previsit', 2, E)\n",
"('postvisit', 3, E)\n",
"('previsit', 4, F)\n",
"('postvisit', 5, F)\n",
"('postvisit', 6, C)\n",
"('previsit', 7, A)\n",
"('postvisit', 8, A)\n",
"('previsit', 9, B)\n",
"('previsit', 10, D)\n",
"('postvisit', 11, D)\n",
"('postvisit', 12, B)\n"
]
}
],
"source": [
"for v in dfs(G, 'C'):\n",
" print(v)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The vertex with the highest postnumber could be a central station. To ensure that it is, run DFS again from this vertex."
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"('previsit', 1, B)\n",
"('previsit', 2, A)\n",
"('previsit', 3, C)\n",
"('previsit', 4, E)\n",
"('postvisit', 5, E)\n",
"('previsit', 6, F)\n",
"('postvisit', 7, F)\n",
"('postvisit', 8, C)\n",
"('postvisit', 9, A)\n",
"('previsit', 10, D)\n",
"('postvisit', 11, D)\n",
"('postvisit', 12, B)\n"
]
}
],
"source": [
"for v in dfs(G, 'B'):\n",
" print(v)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Since B has the highest post number again, it is a central station."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Wrapping this up into a function:"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [],
"source": [
"def centralStation(graph):\n",
" startingVertex = next(iter(graph.vertices.values()))\n",
" numberOfVertices = len(graph.vertices.values())\n",
" \n",
" # First DFS\n",
" for visit in dfs(graph, startingVertex.label):\n",
" count = visit[1]\n",
" vertex = visit[2]\n",
" if count == numberOfVertices * 2:\n",
" highestPostVertex1 = vertex\n",
" \n",
" \n",
" # Second DFS\n",
" for visit in dfs(graph, highestPostVertex1.label):\n",
" count = visit[1]\n",
" vertex = visit[2]\n",
" if count == numberOfVertices * 2:\n",
" highestPostVertex2 = vertex\n",
" \n",
" \n",
" if highestPostVertex1.label == highestPostVertex2.label:\n",
" return highestPostVertex1\n",
" \n",
" # No central station.\n",
" return None"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"B"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"centralStation(G)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"By hand:\n",
"\n",
""
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python [default]",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.6.2"
}
},
"nbformat": 4,
"nbformat_minor": 2
}