Nested unordered_map for storing a directed graph's adjacency list
I am working with a nested unordered_map, i.e., std::unordered_map<int,std::unordered_map<int,int>> adjList, for representing a directed graph's adjacency list.
If I am given the edges E=(u,v),(u,w),(u,z), how do I go about inserting these into the nested unordered_map? Part of my ignorance is I think I am having a hard time visualizing the nested unordered_map and how it works here. If someone could explain in words, and maybe programmatically, that would be great.
c++ graph nested unordered-map adjacency-list
asked Nov 12 '18 at 3:37
IamanonIamanon
1037
|
show 8 more comments
I am working with a nested unordered_map, i.e., std::unordered_map<int,std::unordered_map<int,int>> adjList, for representing a directed graph's adjacency list.
If I am given the edges E=(u,v),(u,w),(u,z), how do I go about inserting these into the nested unordered_map? Part of my ignorance is I think I am having a hard time visualizing the nested unordered_map and how it works here. If someone could explain in words, and maybe programmatically, that would be great.
c++ graph nested unordered-map adjacency-list
asked Nov 12 '18 at 3:37
IamanonIamanon
1037
Can you explain a bit about what the template variables in yourstd::unordered_map<int,std::unordered_map<int,int>> adjListare supposed to represent
– AndyG
Nov 12 '18 at 3:40
This is meant to be for a directed graph. So I am letting the template variables represent the start and end node IDs (integers) for a given edge.
– Iamanon
Nov 12 '18 at 3:41
So the key is the edge ID? I guess I don't follow why the "value" is anunordered_map?
– AndyG
Nov 12 '18 at 3:43
No, the key is what I am calling a "node id." I was told that an efficient way to represent an adjacency list could be with a nestedunordered_mapwhere the value of the key-value pair is represented as anunordered_map. So I'm trying to implement this but it's confusing me.
– Iamanon
Nov 12 '18 at 3:45
1
In both an adjacency matrix and adjacency list this amounts to walking the row forv. They both have complexity O(V).
– AndyG
Nov 12 '18 at 15:40
|
show 8 more comments
I am working with a nested unordered_map, i.e., std::unordered_map<int,std::unordered_map<int,int>> adjList, for representing a directed graph's adjacency list.
If I am given the edges E=(u,v),(u,w),(u,z), how do I go about inserting these into the nested unordered_map? Part of my ignorance is I think I am having a hard time visualizing the nested unordered_map and how it works here. If someone could explain in words, and maybe programmatically, that would be great.
c++ graph nested unordered-map adjacency-list
asked Nov 12 '18 at 3:37
IamanonIamanon
1037
I am working with a nested unordered_map, i.e., std::unordered_map<int,std::unordered_map<int,int>> adjList, for representing a directed graph's adjacency list.
If I am given the edges E=(u,v),(u,w),(u,z), how do I go about inserting these into the nested unordered_map? Part of my ignorance is I think I am having a hard time visualizing the nested unordered_map and how it works here. If someone could explain in words, and maybe programmatically, that would be great.
c++ graph nested unordered-map adjacency-list
c++ graph nested unordered-map adjacency-list
asked Nov 12 '18 at 3:37
IamanonIamanon
1037
asked Nov 12 '18 at 3:37
IamanonIamanon
1037
asked Nov 12 '18 at 3:37
IamanonIamanon
1037
asked Nov 12 '18 at 3:37
IamanonIamanon
1037
asked Nov 12 '18 at 3:37
IamanonIamanon
1037
1037
Can you explain a bit about what the template variables in yourstd::unordered_map<int,std::unordered_map<int,int>> adjListare supposed to represent
– AndyG
Nov 12 '18 at 3:40
This is meant to be for a directed graph. So I am letting the template variables represent the start and end node IDs (integers) for a given edge.
– Iamanon
Nov 12 '18 at 3:41
So the key is the edge ID? I guess I don't follow why the "value" is anunordered_map?
– AndyG
Nov 12 '18 at 3:43
No, the key is what I am calling a "node id." I was told that an efficient way to represent an adjacency list could be with a nestedunordered_mapwhere the value of the key-value pair is represented as anunordered_map. So I'm trying to implement this but it's confusing me.
– Iamanon
Nov 12 '18 at 3:45
1
In both an adjacency matrix and adjacency list this amounts to walking the row forv. They both have complexity O(V).
– AndyG
Nov 12 '18 at 15:40
|
show 8 more comments
Can you explain a bit about what the template variables in yourstd::unordered_map<int,std::unordered_map<int,int>> adjListare supposed to represent
– AndyG
Nov 12 '18 at 3:40
This is meant to be for a directed graph. So I am letting the template variables represent the start and end node IDs (integers) for a given edge.
– Iamanon
Nov 12 '18 at 3:41
So the key is the edge ID? I guess I don't follow why the "value" is anunordered_map?
– AndyG
Nov 12 '18 at 3:43
No, the key is what I am calling a "node id." I was told that an efficient way to represent an adjacency list could be with a nestedunordered_mapwhere the value of the key-value pair is represented as anunordered_map. So I'm trying to implement this but it's confusing me.
– Iamanon
Nov 12 '18 at 3:45
1
In both an adjacency matrix and adjacency list this amounts to walking the row forv. They both have complexity O(V).
– AndyG
Nov 12 '18 at 15:40
Can you explain a bit about what the template variables in your
std::unordered_map<int,std::unordered_map<int,int>> adjList are supposed to represent– AndyG
Nov 12 '18 at 3:40
Can you explain a bit about what the template variables in your
std::unordered_map<int,std::unordered_map<int,int>> adjList are supposed to represent– AndyG
Nov 12 '18 at 3:40
This is meant to be for a directed graph. So I am letting the template variables represent the start and end node IDs (integers) for a given edge.
– Iamanon
Nov 12 '18 at 3:41
This is meant to be for a directed graph. So I am letting the template variables represent the start and end node IDs (integers) for a given edge.
– Iamanon
Nov 12 '18 at 3:41
So the key is the edge ID? I guess I don't follow why the "value" is an
unordered_map?– AndyG
Nov 12 '18 at 3:43
So the key is the edge ID? I guess I don't follow why the "value" is an
unordered_map?– AndyG
Nov 12 '18 at 3:43
No, the key is what I am calling a "node id." I was told that an efficient way to represent an adjacency list could be with a nested
unordered_map where the value of the key-value pair is represented as an unordered_map. So I'm trying to implement this but it's confusing me.– Iamanon
Nov 12 '18 at 3:45
No, the key is what I am calling a "node id." I was told that an efficient way to represent an adjacency list could be with a nested
unordered_map where the value of the key-value pair is represented as an unordered_map. So I'm trying to implement this but it's confusing me.– Iamanon
Nov 12 '18 at 3:45
1
1
In both an adjacency matrix and adjacency list this amounts to walking the row for
v. They both have complexity O(V).– AndyG
Nov 12 '18 at 15:40
In both an adjacency matrix and adjacency list this amounts to walking the row for
v. They both have complexity O(V).– AndyG
Nov 12 '18 at 15:40
|
show 8 more comments
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "1"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53255655%2fnested-unordered-map-for-storing-a-directed-graphs-adjacency-list%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53255655%2fnested-unordered-map-for-storing-a-directed-graphs-adjacency-list%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Can you explain a bit about what the template variables in your
std::unordered_map<int,std::unordered_map<int,int>> adjListare supposed to represent– AndyG
Nov 12 '18 at 3:40
This is meant to be for a directed graph. So I am letting the template variables represent the start and end node IDs (integers) for a given edge.
– Iamanon
Nov 12 '18 at 3:41
So the key is the edge ID? I guess I don't follow why the "value" is an
unordered_map?– AndyG
Nov 12 '18 at 3:43
No, the key is what I am calling a "node id." I was told that an efficient way to represent an adjacency list could be with a nested
unordered_mapwhere the value of the key-value pair is represented as anunordered_map. So I'm trying to implement this but it's confusing me.– Iamanon
Nov 12 '18 at 3:45
1
In both an adjacency matrix and adjacency list this amounts to walking the row for
v. They both have complexity O(V).– AndyG
Nov 12 '18 at 15:40