What is the best data structure to represent a multigraph using STL in C++?
up vote
-1
down vote
favorite
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 at 18:48
TheSalamander
328
|
show 5 more comments
up vote
-1
down vote
favorite
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 at 18:48
TheSalamander
328
3
std::mapdoes not provideO(1)lookup, it hasO(logN)lookup. You needstd::unordered_mapforO(1)lookup.
– NathanOliver
Nov 21 at 18:51
You cannot beat an adjacency matrix in terms of sheer speed.
– n.m.
Nov 21 at 18:54
@NathanOliver Thanks!
– TheSalamander
Nov 21 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 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
2 days ago
|
show 5 more comments
up vote
-1
down vote
favorite
up vote
-1
down vote
favorite
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 at 18:48
TheSalamander
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 at 18:48
TheSalamander
328
asked Nov 21 at 18:48
TheSalamander
328
asked Nov 21 at 18:48
TheSalamander
328
asked Nov 21 at 18:48
TheSalamander
328
asked Nov 21 at 18:48
TheSalamander
328
328
3
std::mapdoes not provideO(1)lookup, it hasO(logN)lookup. You needstd::unordered_mapforO(1)lookup.
– NathanOliver
Nov 21 at 18:51
You cannot beat an adjacency matrix in terms of sheer speed.
– n.m.
Nov 21 at 18:54
@NathanOliver Thanks!
– TheSalamander
Nov 21 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 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
2 days ago
|
show 5 more comments
3
std::mapdoes not provideO(1)lookup, it hasO(logN)lookup. You needstd::unordered_mapforO(1)lookup.
– NathanOliver
Nov 21 at 18:51
You cannot beat an adjacency matrix in terms of sheer speed.
– n.m.
Nov 21 at 18:54
@NathanOliver Thanks!
– TheSalamander
Nov 21 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 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
2 days ago
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 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 at 18:51
You cannot beat an adjacency matrix in terms of sheer speed.
– n.m.
Nov 21 at 18:54
You cannot beat an adjacency matrix in terms of sheer speed.
– n.m.
Nov 21 at 18:54
@NathanOliver Thanks!
– TheSalamander
Nov 21 at 18:57
@NathanOliver Thanks!
– TheSalamander
Nov 21 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 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 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
2 days ago
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
2 days ago
|
show 5 more comments
1 Answer
1
active
oldest
votes
up vote
0
down vote
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 18 hours ago
ameed
930520
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
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 18 hours ago
ameed
930520
add a comment |
up vote
0
down vote
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 18 hours ago
ameed
930520
add a comment |
up vote
0
down vote
up vote
0
down vote
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 18 hours ago
ameed
930520
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 18 hours ago
ameed
930520
answered 18 hours ago
ameed
930520
answered 18 hours ago
ameed
930520
answered 18 hours ago
ameed
930520
930520
add a comment |
add a comment |
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 at 18:51
You cannot beat an adjacency matrix in terms of sheer speed.
– n.m.
Nov 21 at 18:54
@NathanOliver Thanks!
– TheSalamander
Nov 21 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 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
2 days ago