{"id":79124,"date":"2026-11-18T03:31:40","date_gmt":"2026-11-18T03:31:40","guid":{"rendered":"http:\/\/bangla.sitestree.com\/?p=79124"},"modified":"2026-11-18T03:31:40","modified_gmt":"2026-11-18T03:31:40","slug":"graph-mining-1-13-project-prompts-part-1","status":"publish","type":"post","link":"http:\/\/bangla.sitestree.com\/?p=79124","title":{"rendered":"Graph Mining &#8211; 1 | 13. Assignments and Project Prompts \u2014 Part 1 (Worked Answers)"},"content":{"rendered":"<p class=\"wp-block-paragraph\"><strong>AI Generated Answers.<\/strong> Original assignment\/project questions on this blog are attributed to <strong>Sayed Ahmed<\/strong>. The new AI-generated worked solutions and examples are offered for reuse without copyright restrictions asserted by the blog; external datasets and linked resources retain their own rights. These are instructional examples; test code before classroom use.<\/p>\n<p class=\"wp-block-paragraph\"><a href=\"http:\/\/bangla.sitestree.com\/?p=79103\">Graph Mining &#8211; 1 course index<\/a> \u00b7 Original prompt source: <a href=\"http:\/\/bangla.sitestree.com\/?p=22891\">Graph Mining: Misc. Topics to Learn<\/a> \u00b7 This part covers prompts 13.01\u201313.03.<\/p>\n<h3 class=\"wp-block-heading\">Q13.01. Implement graph algorithms from scratch and apply them to a suitably chosen network. The post lists BFS, DFS, single-source and all-pairs shortest paths, Dijkstra\u2019s algorithm, minimum cuts including Karger\u2019s method, and clique algorithms.<\/h3>\n<p class=\"wp-block-paragraph\"><strong>Answer.<\/strong> <strong>Worked solution.<\/strong> Choose a small, reproducible undirected graph. Implement traversal by BFS\/DFS, shortest paths by Dijkstra (nonnegative weights), and all-pairs distances by Floyd\u2013Warshall; implement global min-cut by Karger and clique enumeration by Bron\u2013Kerbosch. Analyze complexity: BFS\/DFS O(V+E), heap Dijkstra O((V+E)log V), Floyd\u2013Warshall O(V\u00b3), and clique enumeration is exponential in the worst case. The code examples below are original didactic implementations; do not treat them as optimized large-graph libraries.<\/p>\n<h3 class=\"wp-block-heading\">Q13.02. Run comparable graph-library implementations on the same datasets. Do they give the same results? Use a library such as NetworkX in Python. Keep the graph and assumptions the same when comparing with your own implementation.<\/h3>\n<p class=\"wp-block-paragraph\"><strong>Answer.<\/strong> <strong>Worked solution.<\/strong> Use identical vertices, edges, directions and weights in handwritten and library versions, and compare results with assertions. BFS traversal order may differ because multiple equal choices are valid; instead compare reachable vertex sets and shortest-path distances. Min-cut size and MST cost are good invariant outputs. A disagreement requires checking node order, self-loops, tie-breaking, and edge-weight meaning.<\/p>\n<h3 class=\"wp-block-heading\">Q13.03. Implement spanning trees and highly connected subgraphs.<\/h3>\n<p class=\"wp-block-paragraph\"><strong>Answer.<\/strong> <strong>Worked solution.<\/strong> Calculate an MST with Prim on a connected weighted graph and partition it by removing k\u22121 highest distance edges. For highly connected subgraphs, repeatedly compute global min-cuts and recurse until \u03bb(H)&gt;|H|\/2. The <a href=\"http:\/\/bangla.sitestree.com\/?p=79116\">MST lesson<\/a> and <a href=\"http:\/\/bangla.sitestree.com\/?p=79118\">HCS lesson<\/a> contain the complete implementations and verified fixture.<\/p>\n<h2 class=\"wp-block-heading\">From-scratch algorithms: BFS, DFS, Dijkstra and Floyd\u2013Warshall<\/h2>\n<pre class=\"wp-block-preformatted\">from collections import deque\nimport heapq\nINF=float(\"inf\")\n\n# Weighted undirected adjacency list\nW = {0:{1:2,2:5}, 1:{0:2,2:1,3:4},\n     2:{0:5,1:1,3:2}, 3:{1:4,2:2}}\n\ndef bfs(adj, source):\n    seen={source}; q=deque([source]); order=[]\n    while q:\n        u=q.popleft(); order.append(u)\n        for v in adj[u]:\n            if v not in seen: seen.add(v); q.append(v)\n    return order\n\ndef dfs(adj, source):\n    seen=set(); order=[]\n    def visit(u):\n        seen.add(u); order.append(u)\n        for v in adj[u]:\n            if v not in seen: visit(v)\n    visit(source)\n    return order\n\ndef dijkstra(adj, source):\n    dist={u:INF for u in adj}; dist[source]=0\n    q=[(0,source)]\n    while q:\n        d,u=heapq.heappop(q)\n        if d!=dist[u]: continue\n        for v,w in adj[u].items():\n            if w<0: raise ValueError(\"Negative weight\")\n            nd=d+w\n            if nd<dist[v]: dist[v]=nd; heapq.heappush(q,(nd,v))\n    return dist\n\ndef floyd_warshall(adj):\n    V=list(adj); D={i:{j:(0 if i==j else\n        adj[i].get(j,INF)) for j in V} for i in V}\n    for k in V:\n        for i in V:\n            for j in V:\n                D[i][j]=min(D[i][j],D[i][k]+D[k][j])\n    return D\n\nprint(\"BFS\",bfs(W,0)); print(\"DFS\",dfs(W,0))\nprint(\"Dijkstra\",dijkstra(W,0))\nprint(\"0-row of Floyd\u2013Warshall\",floyd_warshall(W)[0])\n# Dijkstra(0) \/ Floyd row: {0:0, 1:2, 2:3, 3:5}<\/pre>\n<h2 class=\"wp-block-heading\">From scratch: Bron\u2013Kerbosch maximal cliques<\/h2>\n<pre class=\"wp-block-preformatted\">def maximal_cliques(adj):\n    out=[]\n    def bk(R,P,X):\n        if not P and not X:\n            out.append(set(R)); return\n        for v in list(P):\n            bk(R|{v}, P & set(adj[v]), X & set(adj[v]))\n            P.remove(v); X.add(v)\n    bk(set(),set(adj),set())\n    return out\n\nsimple={u:set(neighbors) for u,neighbors in W.items()}\nprint(\"Maximal cliques:\",maximal_cliques(simple))\n# Maximal sets are {0,1,2} and {1,2,3} only if edge 0-2 exists;\n# here both triangles do exist in W.<\/pre>\n<p class=\"wp-block-paragraph\">For randomized minimum cuts use the full <a href=\"http:\/\/bangla.sitestree.com\/?p=79119\">Karger implementation in lesson 09, Part 3<\/a>. Its repeated trials are important because one contraction run is not guaranteed to find an optimal cut.<\/p>","protected":false},"excerpt":{"rendered":"<p>Graph Mining course assignments part 1: worked answers for source prompts 13.01\u201313.03 with reproducible Python examples and project evaluation guidance.<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":true,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_hide_featured_image":false,"_jetpack_featured_image_duplicate_dismissed":0,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_post_was_ever_published":false},"categories":[1905,1994],"tags":[],"class_list":["post-79124","post","type-post","status-publish","format-standard","hentry","category-graph-mining","category-graph-mining-1","item-wrap"],"jetpack_sharing_enabled":true,"jetpack-related-posts":[{"id":79126,"url":"http:\/\/bangla.sitestree.com\/?p=79126","url_meta":{"origin":79124,"position":0},"title":"Graph Mining &#8211; 1 | 13. Assignments and Project Prompts \u2014 Part 3 (Worked Answers)","author":"Sayed","date":"November 18, 2026","format":false,"excerpt":"Graph Mining course assignments part 3: worked answers for source prompts 13.07\u201313.09 with reproducible Python examples and project evaluation guidance.","rel":"","context":"In &quot;Graph Mining&quot;","block_context":{"text":"Graph Mining","link":"http:\/\/bangla.sitestree.com\/?cat=1905"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":79125,"url":"http:\/\/bangla.sitestree.com\/?p=79125","url_meta":{"origin":79124,"position":1},"title":"Graph Mining &#8211; 1 | 13. Assignments and Project Prompts \u2014 Part 2 (Worked Answers)","author":"Sayed","date":"November 18, 2026","format":false,"excerpt":"Graph Mining course assignments part 2: worked answers for source prompts 13.04\u201313.06 with reproducible Python examples and project evaluation guidance.","rel":"","context":"In &quot;Graph Mining&quot;","block_context":{"text":"Graph Mining","link":"http:\/\/bangla.sitestree.com\/?cat=1905"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":79103,"url":"http:\/\/bangla.sitestree.com\/?p=79103","url_meta":{"origin":79124,"position":2},"title":"Graph Mining &#8211; 1 | Course Index, Source Archive and 415-Question Bank","author":"Sayed","date":"November 18, 2026","format":false,"excerpt":"Complete graph mining blog archive: 33 source posts, 13 distinct question sets, 415 numbered prompts, source links, and selected previously published answer notes.","rel":"","context":"In &quot;Graph Mining&quot;","block_context":{"text":"Graph Mining","link":"http:\/\/bangla.sitestree.com\/?cat=1905"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":79105,"url":"http:\/\/bangla.sitestree.com\/?p=79105","url_meta":{"origin":79124,"position":3},"title":"Graph Mining &#8211; 1 | 01. Graph Mining Foundations \u2014 Questions and Answers","author":"Sayed","date":"November 18, 2026","format":false,"excerpt":"Twenty original Graph Mining Foundations questions, each answered with examples, history, applications, an animated graph and NetworkX exercise.","rel":"","context":"In &quot;Graph Mining&quot;","block_context":{"text":"Graph Mining","link":"http:\/\/bangla.sitestree.com\/?cat=1905"},"img":{"alt_text":"Animated network: vertices A\u2013G form two communities, acquire a connecting bridge, and show a candidate new link.","src":"https:\/\/i0.wp.com\/bangla.sitestree.com\/wp-content\/uploads\/2026\/11\/graph-mining-1-network-growth-original-animation.gif?resize=350%2C200","width":350,"height":200},"classes":[]},{"id":16311,"url":"http:\/\/bangla.sitestree.com\/?p=16311","url_meta":{"origin":79124,"position":4},"title":"Graph Mining: What is Graph Mining? Learn by finding answers to the following questions. Can you answer the following questions?","author":"Sayed","date":"October 9, 2019","format":false,"excerpt":"Graph Mining: What is Graph Mining? Learn by finding answers to the following questions. Can you answer the following questions? What is Graph Mining? What is a Graph anyway? Is Graph mining just a kind of Machine Learning? i.e. is Machine Learning the only primary component of Graph Mining? Does\u2026","rel":"","context":"In &quot;AI ML DS RL DL NN NLP Data Mining Optimization&quot;","block_context":{"text":"AI ML DS RL DL NN NLP Data Mining Optimization","link":"http:\/\/bangla.sitestree.com\/?cat=1910"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":22891,"url":"http:\/\/bangla.sitestree.com\/?p=22891","url_meta":{"origin":79124,"position":5},"title":"Graph Mining: Misc. Topics to Learn: Misc. Resources to Learn From","author":"Sayed","date":"March 21, 2021","format":false,"excerpt":"Graph Mining: Misc. Topics to Learn: Misc. Resources to Learn From Influence\/Virus\/Label Propagation Resources to learn fromPage A presentation on Influence\/Virus PropagationURL Big Data Graph Databases Resources to Learn FromPage Graph DatabaseURL Neo4jPage Big Data Graph Processing Resources to Learn FromPage ToolURL Techniques, Tools and Applications of Graph AnalyticURL Graph\u2026","rel":"","context":"In &quot;Graph Mining&quot;","block_context":{"text":"Graph Mining","link":"http:\/\/bangla.sitestree.com\/?cat=1905"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]}],"jetpack_featured_media_url":"","_links":{"self":[{"href":"http:\/\/bangla.sitestree.com\/index.php?rest_route=\/wp\/v2\/posts\/79124","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/bangla.sitestree.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/bangla.sitestree.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/bangla.sitestree.com\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/bangla.sitestree.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=79124"}],"version-history":[{"count":0,"href":"http:\/\/bangla.sitestree.com\/index.php?rest_route=\/wp\/v2\/posts\/79124\/revisions"}],"wp:attachment":[{"href":"http:\/\/bangla.sitestree.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=79124"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/bangla.sitestree.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=79124"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/bangla.sitestree.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=79124"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}