Disjoint set implementation in Python
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ height:90px;width:728px;box-sizing:border-box;
}
I am relatively new to Python. I am studying Disjoint sets, and implemented it as follows:
class DisjointSet:
def __init__(self, vertices, parent):
self.vertices = vertices
self.parent = parent
def find(self, item):
if self.parent[item] == item:
return item
else:
return self.find(self.parent[item])
def union(self, set1, set2):
self.parent[set1] = set2
Now in the driver code:
def main():
vertices = ['a', 'b', 'c', 'd', 'e', 'h', 'i']
parent = {}
for v in vertices:
parent[v] = v
ds = DisjointSet(vertices, parent)
print("Print all vertices in genesis: ")
ds.union('b', 'd')
ds.union('h', 'b')
print(ds.find('h')) # prints d (OK)
ds.union('h', 'i')
print(ds.find('i')) # prints i (expecting d)
main()
So, at first I initialized all nodes as individual disjoint sets. Then unioned bd and hb which makes the set: hbd then hi is unioned, which should (as I assumed) give us the set: ihbd. I understand that due to setting the parent in this line of union(set1, set2):
self.parent[set1] = set2
I am setting the parent of h as i and thus removing it from the set of bd. How can I achieve a set of ihbd where the order of the params in union() won't yield different results?
python-3.x algorithm data-structures disjoint-sets
asked Jan 4 at 13:31
AbrarAbrar
8751229
add a comment |
I am relatively new to Python. I am studying Disjoint sets, and implemented it as follows:
class DisjointSet:
def __init__(self, vertices, parent):
self.vertices = vertices
self.parent = parent
def find(self, item):
if self.parent[item] == item:
return item
else:
return self.find(self.parent[item])
def union(self, set1, set2):
self.parent[set1] = set2
Now in the driver code:
def main():
vertices = ['a', 'b', 'c', 'd', 'e', 'h', 'i']
parent = {}
for v in vertices:
parent[v] = v
ds = DisjointSet(vertices, parent)
print("Print all vertices in genesis: ")
ds.union('b', 'd')
ds.union('h', 'b')
print(ds.find('h')) # prints d (OK)
ds.union('h', 'i')
print(ds.find('i')) # prints i (expecting d)
main()
So, at first I initialized all nodes as individual disjoint sets. Then unioned bd and hb which makes the set: hbd then hi is unioned, which should (as I assumed) give us the set: ihbd. I understand that due to setting the parent in this line of union(set1, set2):
self.parent[set1] = set2
I am setting the parent of h as i and thus removing it from the set of bd. How can I achieve a set of ihbd where the order of the params in union() won't yield different results?
python-3.x algorithm data-structures disjoint-sets
asked Jan 4 at 13:31
AbrarAbrar
8751229
You shouldn't take theparentargument in the constructor, since the caller doesn't have any choice about what to specify. You should populate it in init instead of main()
– Matt Timmermans
Jan 4 at 19:00
add a comment |
I am relatively new to Python. I am studying Disjoint sets, and implemented it as follows:
class DisjointSet:
def __init__(self, vertices, parent):
self.vertices = vertices
self.parent = parent
def find(self, item):
if self.parent[item] == item:
return item
else:
return self.find(self.parent[item])
def union(self, set1, set2):
self.parent[set1] = set2
Now in the driver code:
def main():
vertices = ['a', 'b', 'c', 'd', 'e', 'h', 'i']
parent = {}
for v in vertices:
parent[v] = v
ds = DisjointSet(vertices, parent)
print("Print all vertices in genesis: ")
ds.union('b', 'd')
ds.union('h', 'b')
print(ds.find('h')) # prints d (OK)
ds.union('h', 'i')
print(ds.find('i')) # prints i (expecting d)
main()
So, at first I initialized all nodes as individual disjoint sets. Then unioned bd and hb which makes the set: hbd then hi is unioned, which should (as I assumed) give us the set: ihbd. I understand that due to setting the parent in this line of union(set1, set2):
self.parent[set1] = set2
I am setting the parent of h as i and thus removing it from the set of bd. How can I achieve a set of ihbd where the order of the params in union() won't yield different results?
python-3.x algorithm data-structures disjoint-sets
asked Jan 4 at 13:31
AbrarAbrar
8751229
I am relatively new to Python. I am studying Disjoint sets, and implemented it as follows:
class DisjointSet:
def __init__(self, vertices, parent):
self.vertices = vertices
self.parent = parent
def find(self, item):
if self.parent[item] == item:
return item
else:
return self.find(self.parent[item])
def union(self, set1, set2):
self.parent[set1] = set2
Now in the driver code:
def main():
vertices = ['a', 'b', 'c', 'd', 'e', 'h', 'i']
parent = {}
for v in vertices:
parent[v] = v
ds = DisjointSet(vertices, parent)
print("Print all vertices in genesis: ")
ds.union('b', 'd')
ds.union('h', 'b')
print(ds.find('h')) # prints d (OK)
ds.union('h', 'i')
print(ds.find('i')) # prints i (expecting d)
main()
So, at first I initialized all nodes as individual disjoint sets. Then unioned bd and hb which makes the set: hbd then hi is unioned, which should (as I assumed) give us the set: ihbd. I understand that due to setting the parent in this line of union(set1, set2):
self.parent[set1] = set2
I am setting the parent of h as i and thus removing it from the set of bd. How can I achieve a set of ihbd where the order of the params in union() won't yield different results?
python-3.x algorithm data-structures disjoint-sets
python-3.x algorithm data-structures disjoint-sets
asked Jan 4 at 13:31
AbrarAbrar
8751229
asked Jan 4 at 13:31
AbrarAbrar
8751229
asked Jan 4 at 13:31
AbrarAbrar
8751229
asked Jan 4 at 13:31
AbrarAbrar
8751229
asked Jan 4 at 13:31
AbrarAbrar
8751229
8751229
You shouldn't take theparentargument in the constructor, since the caller doesn't have any choice about what to specify. You should populate it in init instead of main()
– Matt Timmermans
Jan 4 at 19:00
add a comment |
You shouldn't take theparentargument in the constructor, since the caller doesn't have any choice about what to specify. You should populate it in init instead of main()
– Matt Timmermans
Jan 4 at 19:00
You shouldn't take the
parent argument in the constructor, since the caller doesn't have any choice about what to specify. You should populate it in init instead of main()– Matt Timmermans
Jan 4 at 19:00
You shouldn't take the
parent argument in the constructor, since the caller doesn't have any choice about what to specify. You should populate it in init instead of main()– Matt Timmermans
Jan 4 at 19:00
add a comment |
1 Answer
1
active
oldest
votes
Your program is not working correctly because you have misunderstood the algorithm for disjoint set implementation. Union is implemented by modifying the parent of the root node rather than the node provided as input. As you have already noticed, blindly modifying parents of any node you receive in input will just destroy previous unions.
Here's a correct implementation:
def union(self, set1, set2):
root1 = self.find(set1)
root2 = self.find(set2)
self.parent[root1] = root2
I would also suggest reading Disjoint-set data structure for more info as well as possible optimizations.
answered Jan 4 at 13:58
merlynmerlyn
1,77011323
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%2f54039935%2fdisjoint-set-implementation-in-python%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
Your program is not working correctly because you have misunderstood the algorithm for disjoint set implementation. Union is implemented by modifying the parent of the root node rather than the node provided as input. As you have already noticed, blindly modifying parents of any node you receive in input will just destroy previous unions.
Here's a correct implementation:
def union(self, set1, set2):
root1 = self.find(set1)
root2 = self.find(set2)
self.parent[root1] = root2
I would also suggest reading Disjoint-set data structure for more info as well as possible optimizations.
answered Jan 4 at 13:58
merlynmerlyn
1,77011323
add a comment |
Your program is not working correctly because you have misunderstood the algorithm for disjoint set implementation. Union is implemented by modifying the parent of the root node rather than the node provided as input. As you have already noticed, blindly modifying parents of any node you receive in input will just destroy previous unions.
Here's a correct implementation:
def union(self, set1, set2):
root1 = self.find(set1)
root2 = self.find(set2)
self.parent[root1] = root2
I would also suggest reading Disjoint-set data structure for more info as well as possible optimizations.
answered Jan 4 at 13:58
merlynmerlyn
1,77011323
add a comment |
Your program is not working correctly because you have misunderstood the algorithm for disjoint set implementation. Union is implemented by modifying the parent of the root node rather than the node provided as input. As you have already noticed, blindly modifying parents of any node you receive in input will just destroy previous unions.
Here's a correct implementation:
def union(self, set1, set2):
root1 = self.find(set1)
root2 = self.find(set2)
self.parent[root1] = root2
I would also suggest reading Disjoint-set data structure for more info as well as possible optimizations.
answered Jan 4 at 13:58
merlynmerlyn
1,77011323
Your program is not working correctly because you have misunderstood the algorithm for disjoint set implementation. Union is implemented by modifying the parent of the root node rather than the node provided as input. As you have already noticed, blindly modifying parents of any node you receive in input will just destroy previous unions.
Here's a correct implementation:
def union(self, set1, set2):
root1 = self.find(set1)
root2 = self.find(set2)
self.parent[root1] = root2
I would also suggest reading Disjoint-set data structure for more info as well as possible optimizations.
answered Jan 4 at 13:58
merlynmerlyn
1,77011323
answered Jan 4 at 13:58
merlynmerlyn
1,77011323
answered Jan 4 at 13:58
merlynmerlyn
1,77011323
answered Jan 4 at 13:58
merlynmerlyn
1,77011323
1,77011323
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%2f54039935%2fdisjoint-set-implementation-in-python%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
You shouldn't take the
parentargument in the constructor, since the caller doesn't have any choice about what to specify. You should populate it in init instead of main()– Matt Timmermans
Jan 4 at 19:00