What is the best data structure to represent a multigraph using STL in C++?
I'm looking for some data structure to store a multigraph in C++ but I want to make use of the STL as much as possible. Currently I am using something similar to a seperate chaining hash table: std::map<int,std::vector<int>>. The key of the map is the vertex and the value is a std::vector<int> that contains all of the different vertices that form an edge with the key.
I'm mainly interested in O(1) lookups to see whether or not a vertex shares an edge with another vertex. Since this is an unweighted multigraph the vertex could share multiple edges with another vertex.
The graph is guaranteed to have an eulerian circuit and hamiltonian circuit, but I'm not sure if that is relevant or not.
Do you guys have any recommendations for a better data structure using the STL than std::map<int,std::vector<int>>?
c++ data-structures graph
asked Nov 21 '18 at 18:48
TheSalamanderTheSalamander
328
|
show 5 more comments
I'm looking for some data structure to store a multigraph in C++ but I want to make use of the STL as much as possible. Currently I am using something similar to a seperate chaining hash table: std::map<int,std::vector<int>>. The key of the map is the vertex and the value is a std::vector<int> that contains all of the different vertices that form an edge with the key.
I'm mainly interested in O(1) lookups to see whether or not a vertex shares an edge with another vertex. Since this is an unweighted multigraph the vertex could share multiple edges with another vertex.
The graph is guaranteed to have an eulerian circuit and hamiltonian circuit, but I'm not sure if that is relevant or not.
Do you guys have any recommendations for a better data structure using the STL than std::map<int,std::vector<int>>?
c++ data-structures graph
asked Nov 21 '18 at 18:48
TheSalamanderTheSalamander
328
3
std::mapdoes not provideO(1)lookup, it hasO(logN)lookup. You needstd::unordered_mapforO(1)lookup.
– NathanOliver
Nov 21 '18 at 18:51
You cannot beat an adjacency matrix in terms of sheer speed.
– n.m.
Nov 21 '18 at 18:54
@NathanOliver Thanks!
– TheSalamander
Nov 21 '18 at 18:57
@n.m. How can you use an adjacency matrix for a multigraph? I would have used one if it were not a multigraph.
– TheSalamander
Nov 21 '18 at 18:58
1
My first recommendation would be to look for an existing graph library. Documented, publicly tested, probably already optimized. For home-projects, you say you mainly want fast lookup if edges are connected, so ... do you care that it's a multigraph? You can kind of ignore all the extras and use unordered_map<unordered_set>. I mention that option because multiple edges don't matter for "is there an edge".
– Kenny Ostrom
Nov 22 '18 at 15:31
|
show 5 more comments
I'm looking for some data structure to store a multigraph in C++ but I want to make use of the STL as much as possible. Currently I am using something similar to a seperate chaining hash table: std::map<int,std::vector<int>>. The key of the map is the vertex and the value is a std::vector<int> that contains all of the different vertices that form an edge with the key.
I'm mainly interested in O(1) lookups to see whether or not a vertex shares an edge with another vertex. Since this is an unweighted multigraph the vertex could share multiple edges with another vertex.
The graph is guaranteed to have an eulerian circuit and hamiltonian circuit, but I'm not sure if that is relevant or not.
Do you guys have any recommendations for a better data structure using the STL than std::map<int,std::vector<int>>?
c++ data-structures graph
asked Nov 21 '18 at 18:48
TheSalamanderTheSalamander
328
I'm looking for some data structure to store a multigraph in C++ but I want to make use of the STL as much as possible. Currently I am using something similar to a seperate chaining hash table: std::map<int,std::vector<int>>. The key of the map is the vertex and the value is a std::vector<int> that contains all of the different vertices that form an edge with the key.
I'm mainly interested in O(1) lookups to see whether or not a vertex shares an edge with another vertex. Since this is an unweighted multigraph the vertex could share multiple edges with another vertex.
The graph is guaranteed to have an eulerian circuit and hamiltonian circuit, but I'm not sure if that is relevant or not.
Do you guys have any recommendations for a better data structure using the STL than std::map<int,std::vector<int>>?
c++ data-structures graph
c++ data-structures graph
asked Nov 21 '18 at 18:48
TheSalamanderTheSalamander
328
asked Nov 21 '18 at 18:48
TheSalamanderTheSalamander
328
asked Nov 21 '18 at 18:48
TheSalamanderTheSalamander
328
asked Nov 21 '18 at 18:48
TheSalamanderTheSalamander
328
asked Nov 21 '18 at 18:48
TheSalamanderTheSalamander
328
328
3
std::mapdoes not provideO(1)lookup, it hasO(logN)lookup. You needstd::unordered_mapforO(1)lookup.
– NathanOliver
Nov 21 '18 at 18:51
You cannot beat an adjacency matrix in terms of sheer speed.
– n.m.
Nov 21 '18 at 18:54
@NathanOliver Thanks!
– TheSalamander
Nov 21 '18 at 18:57
@n.m. How can you use an adjacency matrix for a multigraph? I would have used one if it were not a multigraph.
– TheSalamander
Nov 21 '18 at 18:58
1
My first recommendation would be to look for an existing graph library. Documented, publicly tested, probably already optimized. For home-projects, you say you mainly want fast lookup if edges are connected, so ... do you care that it's a multigraph? You can kind of ignore all the extras and use unordered_map<unordered_set>. I mention that option because multiple edges don't matter for "is there an edge".
– Kenny Ostrom
Nov 22 '18 at 15:31
|
show 5 more comments
3
std::mapdoes not provideO(1)lookup, it hasO(logN)lookup. You needstd::unordered_mapforO(1)lookup.
– NathanOliver
Nov 21 '18 at 18:51
You cannot beat an adjacency matrix in terms of sheer speed.
– n.m.
Nov 21 '18 at 18:54
@NathanOliver Thanks!
– TheSalamander
Nov 21 '18 at 18:57
@n.m. How can you use an adjacency matrix for a multigraph? I would have used one if it were not a multigraph.
– TheSalamander
Nov 21 '18 at 18:58
1
My first recommendation would be to look for an existing graph library. Documented, publicly tested, probably already optimized. For home-projects, you say you mainly want fast lookup if edges are connected, so ... do you care that it's a multigraph? You can kind of ignore all the extras and use unordered_map<unordered_set>. I mention that option because multiple edges don't matter for "is there an edge".
– Kenny Ostrom
Nov 22 '18 at 15:31
3
3
std::map does not provide O(1) lookup, it has O(logN) lookup. You need std::unordered_map for O(1) lookup.– NathanOliver
Nov 21 '18 at 18:51
std::map does not provide O(1) lookup, it has O(logN) lookup. You need std::unordered_map for O(1) lookup.– NathanOliver
Nov 21 '18 at 18:51
You cannot beat an adjacency matrix in terms of sheer speed.
– n.m.
Nov 21 '18 at 18:54
You cannot beat an adjacency matrix in terms of sheer speed.
– n.m.
Nov 21 '18 at 18:54
@NathanOliver Thanks!
– TheSalamander
Nov 21 '18 at 18:57
@NathanOliver Thanks!
– TheSalamander
Nov 21 '18 at 18:57
@n.m. How can you use an adjacency matrix for a multigraph? I would have used one if it were not a multigraph.
– TheSalamander
Nov 21 '18 at 18:58
@n.m. How can you use an adjacency matrix for a multigraph? I would have used one if it were not a multigraph.
– TheSalamander
Nov 21 '18 at 18:58
1
1
My first recommendation would be to look for an existing graph library. Documented, publicly tested, probably already optimized. For home-projects, you say you mainly want fast lookup if edges are connected, so ... do you care that it's a multigraph? You can kind of ignore all the extras and use unordered_map<unordered_set>. I mention that option because multiple edges don't matter for "is there an edge".
– Kenny Ostrom
Nov 22 '18 at 15:31
My first recommendation would be to look for an existing graph library. Documented, publicly tested, probably already optimized. For home-projects, you say you mainly want fast lookup if edges are connected, so ... do you care that it's a multigraph? You can kind of ignore all the extras and use unordered_map<unordered_set>. I mention that option because multiple edges don't matter for "is there an edge".
– Kenny Ostrom
Nov 22 '18 at 15:31
|
show 5 more comments
1 Answer
1
active
oldest
votes
If the number of vertices N is small, it's probably easiest to use an adjacency matrix unordered_map<int, unordered_map<int, int>> graph, where graph[u][v] is the number of edges from u to v.
If your vertex numbers all range from 0 to N–1, or 1 to N, or similar, you can simplify this to vector<vector<int>> graph, or even int graph if N is known at compile time.
If N is large, and if the graph is sparse, as you indicated (since M ≈ N), it's probably best to use a set for each vertex: unordered_map<int, unordered_set<int>> graph or vector<unordered_set<int>> graph, where graph[u] is the set of all vertices v with an edge from u to v.
Notice that I'm using the unordered_map and unordered_set collections, which provide O(1) access on average. In the worst case, their performance is linear in the size of the map or set, as with any hash-based container.
And if you don't want to deal with all this and want a ready-made solution, consider the Boost Graph Library, NGraph, LEMON, or Google OR-Tools.
answered Nov 24 '18 at 8:53
ameedameed
975521
add a comment |
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%2f53418725%2fwhat-is-the-best-data-structure-to-represent-a-multigraph-using-stl-in-c%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
If the number of vertices N is small, it's probably easiest to use an adjacency matrix unordered_map<int, unordered_map<int, int>> graph, where graph[u][v] is the number of edges from u to v.
If your vertex numbers all range from 0 to N–1, or 1 to N, or similar, you can simplify this to vector<vector<int>> graph, or even int graph if N is known at compile time.
If N is large, and if the graph is sparse, as you indicated (since M ≈ N), it's probably best to use a set for each vertex: unordered_map<int, unordered_set<int>> graph or vector<unordered_set<int>> graph, where graph[u] is the set of all vertices v with an edge from u to v.
Notice that I'm using the unordered_map and unordered_set collections, which provide O(1) access on average. In the worst case, their performance is linear in the size of the map or set, as with any hash-based container.
And if you don't want to deal with all this and want a ready-made solution, consider the Boost Graph Library, NGraph, LEMON, or Google OR-Tools.
answered Nov 24 '18 at 8:53
ameedameed
975521
add a comment |
If the number of vertices N is small, it's probably easiest to use an adjacency matrix unordered_map<int, unordered_map<int, int>> graph, where graph[u][v] is the number of edges from u to v.
If your vertex numbers all range from 0 to N–1, or 1 to N, or similar, you can simplify this to vector<vector<int>> graph, or even int graph if N is known at compile time.
If N is large, and if the graph is sparse, as you indicated (since M ≈ N), it's probably best to use a set for each vertex: unordered_map<int, unordered_set<int>> graph or vector<unordered_set<int>> graph, where graph[u] is the set of all vertices v with an edge from u to v.
Notice that I'm using the unordered_map and unordered_set collections, which provide O(1) access on average. In the worst case, their performance is linear in the size of the map or set, as with any hash-based container.
And if you don't want to deal with all this and want a ready-made solution, consider the Boost Graph Library, NGraph, LEMON, or Google OR-Tools.
answered Nov 24 '18 at 8:53
ameedameed
975521
add a comment |
If the number of vertices N is small, it's probably easiest to use an adjacency matrix unordered_map<int, unordered_map<int, int>> graph, where graph[u][v] is the number of edges from u to v.
If your vertex numbers all range from 0 to N–1, or 1 to N, or similar, you can simplify this to vector<vector<int>> graph, or even int graph if N is known at compile time.
If N is large, and if the graph is sparse, as you indicated (since M ≈ N), it's probably best to use a set for each vertex: unordered_map<int, unordered_set<int>> graph or vector<unordered_set<int>> graph, where graph[u] is the set of all vertices v with an edge from u to v.
Notice that I'm using the unordered_map and unordered_set collections, which provide O(1) access on average. In the worst case, their performance is linear in the size of the map or set, as with any hash-based container.
And if you don't want to deal with all this and want a ready-made solution, consider the Boost Graph Library, NGraph, LEMON, or Google OR-Tools.
answered Nov 24 '18 at 8:53
ameedameed
975521
If the number of vertices N is small, it's probably easiest to use an adjacency matrix unordered_map<int, unordered_map<int, int>> graph, where graph[u][v] is the number of edges from u to v.
If your vertex numbers all range from 0 to N–1, or 1 to N, or similar, you can simplify this to vector<vector<int>> graph, or even int graph if N is known at compile time.
If N is large, and if the graph is sparse, as you indicated (since M ≈ N), it's probably best to use a set for each vertex: unordered_map<int, unordered_set<int>> graph or vector<unordered_set<int>> graph, where graph[u] is the set of all vertices v with an edge from u to v.
Notice that I'm using the unordered_map and unordered_set collections, which provide O(1) access on average. In the worst case, their performance is linear in the size of the map or set, as with any hash-based container.
And if you don't want to deal with all this and want a ready-made solution, consider the Boost Graph Library, NGraph, LEMON, or Google OR-Tools.
answered Nov 24 '18 at 8:53
ameedameed
975521
answered Nov 24 '18 at 8:53
ameedameed
975521
answered Nov 24 '18 at 8:53
ameedameed
975521
answered Nov 24 '18 at 8:53
ameedameed
975521
975521
add a comment |
add a comment |
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.
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%2f53418725%2fwhat-is-the-best-data-structure-to-represent-a-multigraph-using-stl-in-c%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
3
std::mapdoes not provideO(1)lookup, it hasO(logN)lookup. You needstd::unordered_mapforO(1)lookup.– NathanOliver
Nov 21 '18 at 18:51
You cannot beat an adjacency matrix in terms of sheer speed.
– n.m.
Nov 21 '18 at 18:54
@NathanOliver Thanks!
– TheSalamander
Nov 21 '18 at 18:57
@n.m. How can you use an adjacency matrix for a multigraph? I would have used one if it were not a multigraph.
– TheSalamander
Nov 21 '18 at 18:58
1
My first recommendation would be to look for an existing graph library. Documented, publicly tested, probably already optimized. For home-projects, you say you mainly want fast lookup if edges are connected, so ... do you care that it's a multigraph? You can kind of ignore all the extras and use unordered_map<unordered_set>. I mention that option because multiple edges don't matter for "is there an edge".
– Kenny Ostrom
Nov 22 '18 at 15:31