{
"cells": [
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"from AlgoPy import graph\n",
"from AlgoPy.graph import Graph\n",
"from graphviz import Source, Digraph"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"plan = graph.loadNDE('files/digraphRealPlan.gra')\n",
"Source(graph.toDot(plan), engine='neato')"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 23,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"tarj = graph.loadNDE('files/digraphTarjan.gra')\n",
"Source(graph.toDot(tarj), engine='dot')"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def inverseGraph(G):\n",
" G_1 = graph.Graph(G.order, True)\n",
" for s in range(G.order):\n",
" for adj in G.adjLists[s]:\n",
" G_1.addEdge(adj, s)\n",
" return G_1"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"tarj_1 = inverseGraph(tarj)\n",
"Source(graph.toDot(tarj_1), engine='dot')"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"(12, [0, 4, 3, 5, 11, 3, 3, 6, 7, 10, 1, 2, 8, 9])\n",
"(4, [0, 0, 0, 0, 1, 1, 1, 3, 3, 2, 0, 0])\n"
]
}
],
"source": [
"def _dfs(g, src, M, mark = True, stack = None):\n",
" M[src] = mark\n",
" for succ in g.adjLists[src]:\n",
" if M[succ] is None:\n",
" _dfs(g, succ, M, mark, stack)\n",
" if stack != None:\n",
" stack.append(src)\n",
"\n",
"def Kozaraju(g):\n",
" stack = []\n",
" M = [None] * g.order\n",
" for v in range(g.order):\n",
" if M[v] is None:\n",
" _dfs(g, v, M, stack=stack)\n",
" g_1 = inverseGraph(g)\n",
" cc = [None] * g.order\n",
" nbcc = 0\n",
" while len(stack) > 0:\n",
" v = stack.pop()\n",
" if cc[v] is None:\n",
" _dfs(g_1, v, cc, mark=nbcc)\n",
" nbcc += 1\n",
" return nbcc, cc\n",
"\n",
"print(Kozaraju(plan))\n",
"print(Kozaraju(tarj))"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def drawtree(g, v, preorder, tree, c):\n",
" c += 1\n",
" preorder[v] = c\n",
" for s in g.adjLists[v]:\n",
" if preorder[s] is None:\n",
" tree.edge(str(v), str(s))\n",
" c = drawtree(g, s, preorder, tree, c)\n",
" else:\n",
" tree.edge(str(v), str(s), color='red', constraint='false')\n",
" return c\n",
"def span(g):\n",
" tree = Digraph()\n",
" preorder = [None] * g.order\n",
" c = 0\n",
" for v in range(g.order):\n",
" if preorder[v] is None:\n",
" c = drawtree(g, v, preorder, tree, c)\n",
" return tree\n",
"\n",
"span(tarj)"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"(4, [4, 4, 4, 4, 3, 3, 3, 1, 1, 2, 4, 4])"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def zane(g, v, preorder, scc, stack, c, nbscc):\n",
" c += 1\n",
" preorder[v] = c\n",
" stack.append(v)\n",
" high = preorder[v]\n",
" for s in g.adjLists[v]:\n",
" if preorder[s] is None:\n",
" ret, c, nbscc = zane(g, s, preorder, scc, stack, c, nbscc)\n",
" high = min(high, ret)\n",
" else:\n",
" high = min(high, preorder[s])\n",
" if high == preorder[v]:\n",
" nbscc += 1\n",
" x = g.order\n",
" while x != v:\n",
" x = stack.pop()\n",
" scc[x] = nbscc\n",
" preorder[x] = g.order + 1\n",
" return high, c, nbscc\n",
"\n",
"def tarjan(g):\n",
" preorder = [None] * g.order\n",
" scc = [None] * g.order\n",
" stack = []\n",
" c = 0\n",
" nbscc = 0\n",
" for v in range(g.order):\n",
" if preorder[v] is None:\n",
" _, c , nbscc = zane(g, v, preorder, scc, stack, c, nbscc)\n",
" return nbscc, scc\n",
"\n",
"tarjan(tarj)"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"(12, [12, 8, 9, 7, 1, 9, 9, 6, 5, 2, 11, 10, 4, 3])"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"tarjan(plan)"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"train = graph.loadNDE(\"files/train.gra\")\n",
"Source(graph.toDot(train), engine='fdp')"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"g2 = graph.loadNDE('files/digraph_for_condensation.gra')\n",
"Source(graph.toDot(g2), engine='neato')"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"0 : 3\n",
"1 : 3\n",
"2 : 0\n",
"3 : 0\n",
"4 : 0\n",
"5 : 2\n",
"6 : 0\n",
"7 : 0\n",
"8 : 0\n",
"9 : 1\n"
]
}
],
"source": [
"n, scc = tarjan(g2)\n",
"for v in range(g2.order):\n",
" print(v, ':', scc[v] - 1)"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"condensed = graph.loadNDE('files/condensed.gra')\n",
"Source(graph.toDot(condensed), engine='circo')"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def condense(g):\n",
" n, scc = tarjan(g)\n",
" scc = [ x - 1 for x in scc ]\n",
" ng = Graph(n, directed=True)\n",
" for v in range(g.order):\n",
" for s in g.adjLists[v]:\n",
" if scc[v] != scc[s]:\n",
" ng.addEdge(scc[v], scc[s])\n",
" return ng"
]
},
{
"cell_type": "code",
"execution_count": 27,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 27,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"Source(graph.toDot(tarj), engine='fdp')"
]
},
{
"cell_type": "code",
"execution_count": 29,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 29,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"condensed_tarj = condense(tarj)\n",
"Source(graph.toDot(condensed_tarj))"
]
},
{
"cell_type": "code",
"execution_count": 30,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def condense2(g):\n",
" n, scc = tarjan(g)\n",
" scc = [ x - 1 for x in scc ]\n",
" ng = Graph(n, directed=True)\n",
" for v in range(g.order):\n",
" for s in g.adjLists[v]:\n",
" if scc[v] != scc[s]:\n",
" ng.addEdge(scc[v], scc[s])\n",
" return ng, scc"
]
},
{
"cell_type": "code",
"execution_count": 31,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def sourcesAndSinks(g):\n",
" sinks = []\n",
" indeg = [0] * g.order\n",
" for v in range(g.order):\n",
" for s in g.adjLists[v]:\n",
" indeg[s] += 1\n",
" if g.adjLists[v] == []:\n",
" sinks.append(v)\n",
" return [i for i in range(g.order) if indeg[i] == 0], sinks\n"
]
},
{
"cell_type": "code",
"execution_count": 34,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 34,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"gex = graph.loadNDE('files/digraph2src2sinks.gra')\n",
"Source(graph.toDot(gex))"
]
},
{
"cell_type": "code",
"execution_count": 41,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[3, 3, 3, 3, 2, 2, 2, 0, 0, 1, 3, 3]\n",
"[7, 9, 4, 0]\n"
]
}
],
"source": [
"gd, scc = condense2(tarj)\n",
"leaders = [ scc.index(i) for i in range(gd.order) ]\n",
"print(scc)\n",
"print(leaders)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def makeMeStronglyConnected(g):\n",
" # FIX ME for next tuesday\n",
" # send makeMeStronglyConnected.py to marwan.burelle@lse.epita.fr\n",
" # Subject [S4][Algo] login: makeMeStronglyConnected\n",
" # makeMeStronglyConnected(g) returns a copy of g\n",
" # with added edges to make it strongly connected"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"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.0"
}
},
"nbformat": 4,
"nbformat_minor": 2
}