{"id":78562,"date":"2020-09-12T09:00:29","date_gmt":"2020-09-12T03:30:29","guid":{"rendered":"https:\/\/data-flair.training\/blogs\/?p=78562"},"modified":"2021-05-09T13:13:26","modified_gmt":"2021-05-09T07:43:26","slug":"compressed-sparse-graph-in-scipy","status":"publish","type":"post","link":"https:\/\/data-flair.training\/blogs\/compressed-sparse-graph-in-scipy\/","title":{"rendered":"SciPy CSGraph – Compressed Sparse Graph in SciPy"},"content":{"rendered":"

SciPy consists of the CSGraph module. CSGraph stands for Compressed Sparse Graph. This module consists of operations to work with graphs. The modules use various algorithms to deal with graphs. The algorithms are usually based on sparse matrix representations.<\/p>\n

The concept of sparse matrices is necessary when working with CSGraph. We can work with a variety of graphs. With this article, we can work on sparse matrices. We then represent these matrices as graphs. We can also work with both directed and undirected graphs.<\/p>\n

Sparse Graphs<\/h2>\n

We can consider a graph to be a representation of links between the nodes. These can represent the relationships amongst the nodes. We connect the nodes to their nearest possible neighbors through a link.<\/p>\n

We can represent this with the use of sparse matrices. Consider a matrix G. The matrix is N*N, G[i,j] represents the value of the connection between node \u2018i\u2019 and \u2018j\u2019. These values are most probably zero.<\/p>\n

A zero means no connection. Hence, very few nodes have a connection. We represent the connection with assigning weights to the link.<\/p>\n

We consider the following graph. It consists of three nodes. Node 0 and 1 are by link weight of 2, while 0 and 2 are given weight 1. We can create different representations of the graph. We can represent it as a sparse, dense, or masked graph.<\/p>\n

\u00a0\u00a0\u00a0<\/span>\u00a0 \u00a0 G<\/span><\/p>\n

\u00a0\u00a0\u00a0\u00a0\u00a0(<\/span>0<\/span>)<\/span><\/p>\n

\u00a0\u00a0\u00a0\u00a0\/\u00a0\u00a0\u00a0\\<\/span><\/p>\n

\u00a0\u00a0\u00a0<\/span>1<\/span>\u00a0\u00a0\u00a0\u00a0\u00a0<\/span>2<\/span><\/p>\n

\u00a0\u00a0\/\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\\<\/span><\/p>\n

(<\/span>2<\/span>)\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0(<\/span>1<\/span>)<\/span><\/p>\n

We now implement the three representations of the above graph:<\/p>\n

import numpy as np\r\nimport scipy\r\nfrom scipy.sparse import csr_matrix\r\n \r\n#dense representation\r\nG_dense = np.array([ [0, 2, 1],\r\n                     [2, 0, 0],\r\n                     [1, 0, 0] ])\r\nprint(G_dense,'\\n')\r\n                     \r\n#masked representation\r\nG_masked = np.ma.masked_values(G_dense, 0)\r\nprint(G_masked,'\\n')\r\n \r\n#sparse representation\r\nG_sparse = csr_matrix(G_dense)\r\nprint (G_sparse.data)\r\n<\/pre>\n
Output<\/strong><\/p>\n
[[0 2 1]
\n[2 0 0]
\n[1 0 0]][[– 2 1]
\n[2 — –]
\n[1 — –]][2 1 2 1]<\/div>\n
We now consider a graph having zero edge weights. It becomes slightly challenging in this case. We consider a graph where we connect nodes 0 and 2 with weight 0.<\/p>\n
\u00a0\u00a0\u00a0\u00a0\u00a0G2<\/span><\/p>\n
 <\/p>\n
\u00a0\u00a0\u00a0\u00a0\u00a0(<\/span>0<\/span>)<\/span><\/p>\n
\u00a0\u00a0\u00a0\u00a0\/\u00a0\u00a0\u00a0\\<\/span><\/p>\n
\u00a0\u00a0\u00a0<\/span>0<\/span>\u00a0\u00a0\u00a0\u00a0\u00a0<\/span>2<\/span><\/p>\n
\u00a0\u00a0\/\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\\<\/span><\/p>\n
(<\/span>2<\/span>)\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0(<\/span>1<\/span>)<\/span><\/p>\n
It causes difficulties in case of dense representation. It is difficult to represent non-edges if the value zero has significance. Hence, it is meaningful to use masked or sparse representation.<\/p>\n
import numpy as np\r\nimport scipy\r\nfrom scipy.sparse.csgraph import csgraph_from_dense\r\n \r\nG2_data = np.array([[np.inf, 2,      0     ],\r\n                    [2,      np.inf, np.inf],\r\n                    [0,      np.inf, np.inf]])\r\nprint(G2_data,'\\n')\r\n \r\n#masked representation\r\nG2_masked = np.ma.masked_invalid(G2_data)\r\nprint(G2_masked,'\\n')\r\n \r\n#sparse representation\r\nG2_sparse = csgraph_from_dense(G2_data, null_value=np.inf)\r\nprint(G2_sparse.data)\r\n<\/pre>\n
Output<\/strong><\/p>\n
[[inf 2. 0.]
\n[ 2. inf inf]
\n[ 0. inf inf]][[– 2.0 0.0]
\n[2.0 — –]
\n[0.0 — –]][2. 0. 2. 0.]<\/div>\n
Directed vs. Undirected Graphs<\/h2>\n
The matrices can be either directed or undirected. We can specify using a Boolean value in the SciPy CSGraph module. By default, the graphs are directed.<\/p>\n
In the case of directed graphs, traversal from node I to node j is possible but the reverse is not possible. It means we can traverse over G[i,j] but not across G[j,i]. We can set the Boolean function directed as True or False.<\/p>\n
G_dense = np.array([[0, 1, 0],<\/span><\/p>\n
\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0[2, 0, 3],<\/span><\/p>\n
\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0[0, 4, 0]])<\/span><\/p>\n
When we set directed as TRUE<\/strong> we get the following output,<\/p>\n
—1–> —3–>
\n(0) (1) (2)
\n<–2— <–4—<\/p>\n
When we set directed as FALSE<\/strong> we get an undirected graph,
\n(0)–1–(1)–2–(2)<\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
Sr No.<\/strong><\/td>\nFunction\u00a0<\/strong><\/td>\nDescription<\/strong><\/td>\n<\/tr>\n
1<\/span><\/td>\nbellman_ford<\/span><\/td>\nuses bellman ford algorithm to compute the shortest path.<\/span><\/td>\n<\/tr>\n
2<\/span><\/td>\nbreadth_first_order<\/span><\/td>\ncomputes breadth-first order from a specific node<\/span><\/td>\n<\/tr>\n
3<\/span><\/td>\nbreadth_first_tree<\/span><\/td>\ntree generated form breadth-first order<\/span><\/td>\n<\/tr>\n
4<\/span><\/td>\nconected_components<\/span><\/td>\nanalysis of connected components\u00a0<\/span><\/td>\n<\/tr>\n
5<\/span><\/td>\nconstruct_dist_matrix<\/span><\/td>\nreturns distance matrix from predecessor matrix<\/span><\/td>\n<\/tr>\n
6<\/span><\/td>\ncs_graph_components<\/span><\/td>\nreturns csgraph components<\/span><\/td>\n<\/tr>\n
7<\/span><\/td>\ncsgraph_from_dense<\/span><\/td>\nsparse graph from dense matrix<\/span><\/td>\n<\/tr>\n
8<\/span><\/td>\ncsgraph_from_masked<\/span><\/td>\ncsgraph from masked array<\/span><\/td>\n<\/tr>\n
9<\/span><\/td>\ncsgraph_masked_from_dense<\/span><\/td>\nmasked graph from dense matrix<\/span><\/td>\n<\/tr>\n
10<\/span><\/td>\ncsgraph_to_dense<\/span><\/td>\nsparse graph to dense representation<\/span><\/td>\n<\/tr>\n
11<\/span><\/td>\ndepth_first_order<\/span><\/td>\ndepth-first from a specific node<\/span><\/td>\n<\/tr>\n
12<\/span><\/td>\ndepth_first_tree<\/span><\/td>\nreturn tree by depth-first search<\/span><\/td>\n<\/tr>\n
13<\/span><\/td>\ndijkstra<\/span><\/td>\nusing dijkstra algorithm<\/span><\/td>\n<\/tr>\n
14<\/span><\/td>\nfloyd_warshall<\/span><\/td>\nfloyd warshall for shortest path<\/span><\/td>\n<\/tr>\n
15<\/span><\/td>\njohnson<\/span><\/td>\nuse johnson for shortest path<\/span><\/td>\n<\/tr>\n
16<\/span><\/td>\nlaplacian<\/span><\/td>\nLaplacian matrix of a directed graph<\/span><\/td>\n<\/tr>\n
17<\/span><\/td>\nminimum_spannin_tree<\/span><\/td>\nminimum spanning tree of the undirected graph<\/span><\/td>\n<\/tr>\n
18<\/span><\/td>\nreconstruct_path<\/span><\/td>\na tree from graph and predecessor list<\/span><\/td>\n<\/tr>\n
19<\/span><\/td>\nshortest_path<\/span><\/td>\nshortest path search on a directed or undirected graph<\/span><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
Summary<\/h2>\n
The CSGraph module is a very important feature when dealing with graphs in SciPy. We can perform the functions on sparse matrices. We then concert those matrices into sparse graphs.<\/p>\n
It provides functions to represent the graph in different forms. It also consists of features to help traverse the matrices either directly or indirectly.<\/p>\n","protected":false},"excerpt":{"rendered":"
SciPy consists of the CSGraph module. CSGraph stands for Compressed Sparse Graph. This module consists of operations to work with graphs. The modules use various algorithms to deal with graphs. The algorithms are usually...<\/p>\n","protected":false},"author":6,"featured_media":82099,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[22401],"tags":[23250,23249,23248],"class_list":["post-78562","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-numpy","tag-scipy-compressed-sparse-graph","tag-scipy-compresses-sparse-graph","tag-scipy-csgraph"],"yoast_head":"\nSciPy CSGraph - Compressed Sparse Graph in SciPy - DataFlair<\/title>\n<meta name=\"description\" content=\"SciPy CSGraph - If we desire to find the shortest path between two given words, the sparse graph submodule can help. CSGraph means Compressed Sparse Graph.\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/data-flair.training\/blogs\/compressed-sparse-graph-in-scipy\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"SciPy CSGraph - Compressed Sparse Graph in SciPy - DataFlair\" \/>\n<meta property=\"og:description\" content=\"SciPy CSGraph - If we desire to find the shortest path between two given words, the sparse graph submodule can help. CSGraph means Compressed Sparse Graph.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/data-flair.training\/blogs\/compressed-sparse-graph-in-scipy\/\" \/>\n<meta property=\"og:site_name\" content=\"DataFlair\" \/>\n<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/DataFlairWS\/\" \/>\n<meta property=\"article:published_time\" content=\"2020-09-12T03:30:29+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2021-05-09T07:43:26+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2020\/09\/SciPy-CSGraph.jpg\" \/>\n\t<meta property=\"og:image:width\" content=\"1200\" \/>\n\t<meta property=\"og:image:height\" content=\"628\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/jpeg\" \/>\n<meta name=\"author\" content=\"DataFlair Team\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@DataFlairWS\" \/>\n<meta name=\"twitter:site\" content=\"@DataFlairWS\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"DataFlair Team\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"4 minutes\" \/>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"SciPy CSGraph - Compressed Sparse Graph in SciPy - DataFlair","description":"SciPy CSGraph - If we desire to find the shortest path between two given words, the sparse graph submodule can help. CSGraph means Compressed Sparse Graph.","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/data-flair.training\/blogs\/compressed-sparse-graph-in-scipy\/","og_locale":"en_US","og_type":"article","og_title":"SciPy CSGraph - Compressed Sparse Graph in SciPy - DataFlair","og_description":"SciPy CSGraph - If we desire to find the shortest path between two given words, the sparse graph submodule can help. CSGraph means Compressed Sparse Graph.","og_url":"https:\/\/data-flair.training\/blogs\/compressed-sparse-graph-in-scipy\/","og_site_name":"DataFlair","article_publisher":"https:\/\/www.facebook.com\/DataFlairWS\/","article_published_time":"2020-09-12T03:30:29+00:00","article_modified_time":"2021-05-09T07:43:26+00:00","og_image":[{"width":1200,"height":628,"url":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2020\/09\/SciPy-CSGraph.jpg","type":"image\/jpeg"}],"author":"DataFlair Team","twitter_card":"summary_large_image","twitter_creator":"@DataFlairWS","twitter_site":"@DataFlairWS","twitter_misc":{"Written by":"DataFlair Team","Est. reading time":"4 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/data-flair.training\/blogs\/compressed-sparse-graph-in-scipy\/#article","isPartOf":{"@id":"https:\/\/data-flair.training\/blogs\/compressed-sparse-graph-in-scipy\/"},"author":{"name":"DataFlair Team","@id":"https:\/\/data-flair.training\/blogs\/#\/schema\/person\/2c58ecb4f73a39f0ef993f1ddfcd7b89"},"headline":"SciPy CSGraph – Compressed Sparse Graph in SciPy","datePublished":"2020-09-12T03:30:29+00:00","dateModified":"2021-05-09T07:43:26+00:00","mainEntityOfPage":{"@id":"https:\/\/data-flair.training\/blogs\/compressed-sparse-graph-in-scipy\/"},"wordCount":647,"commentCount":0,"publisher":{"@id":"https:\/\/data-flair.training\/blogs\/#organization"},"image":{"@id":"https:\/\/data-flair.training\/blogs\/compressed-sparse-graph-in-scipy\/#primaryimage"},"thumbnailUrl":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2020\/09\/SciPy-CSGraph.jpg","keywords":["Scipy Compressed Sparse Graph","Scipy Compresses Sparse Graph","SciPy CSGraph"],"articleSection":["NumPy Tutorials"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/data-flair.training\/blogs\/compressed-sparse-graph-in-scipy\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/data-flair.training\/blogs\/compressed-sparse-graph-in-scipy\/","url":"https:\/\/data-flair.training\/blogs\/compressed-sparse-graph-in-scipy\/","name":"SciPy CSGraph - Compressed Sparse Graph in SciPy - DataFlair","isPartOf":{"@id":"https:\/\/data-flair.training\/blogs\/#website"},"primaryImageOfPage":{"@id":"https:\/\/data-flair.training\/blogs\/compressed-sparse-graph-in-scipy\/#primaryimage"},"image":{"@id":"https:\/\/data-flair.training\/blogs\/compressed-sparse-graph-in-scipy\/#primaryimage"},"thumbnailUrl":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2020\/09\/SciPy-CSGraph.jpg","datePublished":"2020-09-12T03:30:29+00:00","dateModified":"2021-05-09T07:43:26+00:00","description":"SciPy CSGraph - If we desire to find the shortest path between two given words, the sparse graph submodule can help. CSGraph means Compressed Sparse Graph.","breadcrumb":{"@id":"https:\/\/data-flair.training\/blogs\/compressed-sparse-graph-in-scipy\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/data-flair.training\/blogs\/compressed-sparse-graph-in-scipy\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/data-flair.training\/blogs\/compressed-sparse-graph-in-scipy\/#primaryimage","url":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2020\/09\/SciPy-CSGraph.jpg","contentUrl":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2020\/09\/SciPy-CSGraph.jpg","width":1200,"height":628,"caption":"SciPy CSGraph"},{"@type":"BreadcrumbList","@id":"https:\/\/data-flair.training\/blogs\/compressed-sparse-graph-in-scipy\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Blog Home","item":"https:\/\/data-flair.training\/blogs\/"},{"@type":"ListItem","position":2,"name":"NumPy Tutorials","item":"https:\/\/data-flair.training\/blogs\/category\/numpy\/"},{"@type":"ListItem","position":3,"name":"SciPy CSGraph – Compressed Sparse Graph in SciPy"}]},{"@type":"WebSite","@id":"https:\/\/data-flair.training\/blogs\/#website","url":"https:\/\/data-flair.training\/blogs\/","name":"DataFlair","description":"Learn Today. Lead Tomorrow.","publisher":{"@id":"https:\/\/data-flair.training\/blogs\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/data-flair.training\/blogs\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"https:\/\/data-flair.training\/blogs\/#organization","name":"DataFlair","url":"https:\/\/data-flair.training\/blogs\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/data-flair.training\/blogs\/#\/schema\/logo\/image\/","url":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2016\/07\/Data-Flair.png","contentUrl":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2016\/07\/Data-Flair.png","width":106,"height":48,"caption":"DataFlair"},"image":{"@id":"https:\/\/data-flair.training\/blogs\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/www.facebook.com\/DataFlairWS\/","https:\/\/x.com\/DataFlairWS","https:\/\/www.linkedin.com\/company\/dataflair-web-services-pvt-ltd\/","https:\/\/www.youtube.com\/user\/DataFlairWS"]},{"@type":"Person","@id":"https:\/\/data-flair.training\/blogs\/#\/schema\/person\/2c58ecb4f73a39f0ef993f1ddfcd7b89","name":"DataFlair Team","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/secure.gravatar.com\/avatar\/1ce4a0e3e542444fc73bbebf83e89e8b73e2d95ccb1fcee64da9945f078b97c5?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/1ce4a0e3e542444fc73bbebf83e89e8b73e2d95ccb1fcee64da9945f078b97c5?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/1ce4a0e3e542444fc73bbebf83e89e8b73e2d95ccb1fcee64da9945f078b97c5?s=96&d=mm&r=g","caption":"DataFlair Team"},"description":"The DataFlair Team provides industry-driven content on programming, Java, Python, C++, DSA, AI, ML, data Science, Android, Flutter, MERN, Web Development, and technology. Our expert educators focus on delivering value-packed, easy-to-follow resources for tech enthusiasts and professionals.","url":"https:\/\/data-flair.training\/blogs\/author\/dfteam2\/"}]}},"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/posts\/78562","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/users\/6"}],"replies":[{"embeddable":true,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/comments?post=78562"}],"version-history":[{"count":8,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/posts\/78562\/revisions"}],"predecessor-version":[{"id":93198,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/posts\/78562\/revisions\/93198"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/media\/82099"}],"wp:attachment":[{"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/media?parent=78562"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/categories?post=78562"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/tags?post=78562"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}