{"id":3486,"date":"2017-12-31T12:36:36","date_gmt":"2017-12-31T07:06:36","guid":{"rendered":"http:\/\/theoryofprogramming.azurewebsites.net\/?p=3486"},"modified":"2017-12-31T12:36:36","modified_gmt":"2017-12-31T07:06:36","slug":"adjacency-list-string-vertices-using-c-stl","status":"publish","type":"post","link":"https:\/\/theoryofcoding.com\/index.php\/2017\/12\/31\/adjacency-list-string-vertices-using-c-stl\/","title":{"rendered":"Adjacency List with String vertices using C++ STL"},"content":{"rendered":"<p>Hello people..! This is a special extension for my discussion on <strong><a href=\"http:\/\/theoryofprogramming.azurewebsites.net\/2014\/12\/24\/graph-theory-an-introduction\/\">Graph Theory Basics<\/a><\/strong>. Here, I give you the code for implementing the Adjacency List using C++ STL where each vertex is a string instead of and integer. This code has been requested many times, so I decided to create a separate page for it. Some of the features of this code are &#8211;<\/p>\n<ul>\n<li>The Adjacency List is an unordered map of list. Where each list item is a pair, from the utility header file. This pair stores two values, the destination vertex (string), (V<sub>2<\/sub> in an edge V<sub>1<\/sub> \u2192 V<sub>2<\/sub>) and the weight (integer) of the edge.<\/li>\n<li>For adding an edge, all we have to do is to call push_back() function. Although it does not represent our addEdge() in the initial discussion where we had head insertion, it is tail insertion which is an O(1) insertion operation.<\/li>\n<li>The vector representing the vertices is 1-indexed.<\/li>\n<\/ul>\n<pre class=\"brush: cpp; title: ; notranslate\" title=\"\">\n#include &lt;iostream&gt;\n#include &lt;string&gt;\n#include &lt;unordered_map&gt;\n#include &lt;list&gt;\n\nusing namespace std;\n\nint main()\n{\n    int vertices, edges, weight;\n    string v1, v2;\n     \n    printf(&quot;Enter the Number of Vertices -\\n&quot;);\n    cin &gt;&gt; vertices;\n     \n    printf(&quot;Enter the Number of Edges -\\n&quot;);\n    cin &gt;&gt; edges;\n     \n    \/\/ Adjacency List is a map of &lt;string, list&gt;.\n    \/\/ Where each element in the list is pair&lt;string, int&gt;\n    \/\/ pair.first -&gt; the edge's destination (string)\n    \/\/ pair.second -&gt; edge's weight\n    unordered_map&lt; string, list&lt; pair&lt;string, int&gt; &gt; &gt; adjacencyList(vertices + 1);\n     \n    printf(&quot;Enter the Edges V1 -&gt; V2, of weight W\\n&quot;);\n    for (int i = 1; i &lt;= edges; ++i) {\n        cin &gt;&gt; v1 &gt;&gt; v2 &gt;&gt; weight;\n         \n        \/\/ Adding Edge to the Directed Graph\n        adjacencyList&#x5B;v1].push_back(make_pair(v2, weight));\n    }\n    \n    \/\/ Printing Adjacency List\n    cout &lt;&lt; endl &lt;&lt; &quot;The Adjacency List-&quot; &lt;&lt; endl;\n    for (auto&amp; value : adjacencyList) {\n        string vertex = value.first;\n        list&lt; pair&lt;string, int&gt; &gt; adjacentVertices = value.second;\n        list&lt; pair&lt;string, int&gt; &gt;::iterator itr = adjacentVertices.begin();\n        \n        cout &lt;&lt; &quot;adjacencyList&#x5B;&quot; &lt;&lt; vertex &lt;&lt; &quot;]&quot;;\n         \n        while (itr != adjacentVertices.end()) {\n        \tcout &lt;&lt; &quot; -&gt; &quot; &lt;&lt; (*itr).first &lt;&lt; &quot; (&quot; &lt;&lt; (*itr).second &lt;&lt; &quot;)&quot;;\n            ++itr;\n        }\n        \n        cout &lt;&lt; endl;\n    }\n\t\n    return 0;\n}\n<\/pre>\n<p>Feel free to comment if you have any doubts..! Keep practicing..! Happy Coding..! \ud83d\ude00<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Hello people..! This is a special extension for my discussion on Graph Theory Basics. Here, I give you the code for implementing [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[6],"tags":[17,50],"class_list":["post-3486","post","type-post","status-publish","format-standard","hentry","category-graph-theory","tag-adjacency-list","tag-graph-theory"],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/posts\/3486","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/comments?post=3486"}],"version-history":[{"count":0,"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/posts\/3486\/revisions"}],"wp:attachment":[{"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/media?parent=3486"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/categories?post=3486"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/theoryofcoding.com\/index.php\/wp-json\/wp\/v2\/tags?post=3486"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}