How to find a list of unique shortest paths in a list of paths?
up vote
2
down vote
favorite
Imagine I have a tree graph as shown below, where a node can have multiple children, and so on.. (a node can have only 1 parent). If I have a list of paths along that graph, how can I find a subset of those paths that are unique and shortest?
Example Input (List of paths):
[1, 2, 3]
[1, 2]
[1, 7]
[1, 8, 9, 10]
Expected Output:
[1, 2]
[1, 7]
[1, 8, 9, 10]
The [1, 2, 3] path is ignored because it is longer than [1, 2], while the [1, 8, 9, 10] path is kept because it is unique.
algorithm tree graph-theory shortest-path
edited Nov 7 at 16:05
Dominique Fortin
1,606816
asked Nov 7 at 10:15
RandomName
284
|
show 3 more comments
up vote
2
down vote
favorite
Imagine I have a tree graph as shown below, where a node can have multiple children, and so on.. (a node can have only 1 parent). If I have a list of paths along that graph, how can I find a subset of those paths that are unique and shortest?
Example Input (List of paths):
[1, 2, 3]
[1, 2]
[1, 7]
[1, 8, 9, 10]
Expected Output:
[1, 2]
[1, 7]
[1, 8, 9, 10]
The [1, 2, 3] path is ignored because it is longer than [1, 2], while the [1, 8, 9, 10] path is kept because it is unique.
algorithm tree graph-theory shortest-path
edited Nov 7 at 16:05
Dominique Fortin
1,606816
asked Nov 7 at 10:15
RandomName
284
What is the expected output for[1, 2, 3] [1, 2, 4]?
– Cid
Nov 7 at 10:26
@Cid if [1] or [1,2] don't exist, both should appear in the output since they are unique.
– RandomName
Nov 7 at 10:43
So basically if a prefix exists, then you remove that element?
– Willem Van Onsem
Nov 7 at 11:18
1
@WillemVanOnsem it looks like. The problem become really simpler, the terms graph and tree can be ignored since the whole "roads" are send as input. There is no need to parse the tree, this is just array processing. shortest path is here, in my opinion, badly used
– Cid
Nov 7 at 12:18
@Cid: well we can make a prefix-tree here we update for each item,but indeed, it is simpler in terms of graph and tree.
– Willem Van Onsem
Nov 7 at 12:20
|
show 3 more comments
up vote
2
down vote
favorite
up vote
2
down vote
favorite
Imagine I have a tree graph as shown below, where a node can have multiple children, and so on.. (a node can have only 1 parent). If I have a list of paths along that graph, how can I find a subset of those paths that are unique and shortest?
Example Input (List of paths):
[1, 2, 3]
[1, 2]
[1, 7]
[1, 8, 9, 10]
Expected Output:
[1, 2]
[1, 7]
[1, 8, 9, 10]
The [1, 2, 3] path is ignored because it is longer than [1, 2], while the [1, 8, 9, 10] path is kept because it is unique.
algorithm tree graph-theory shortest-path
edited Nov 7 at 16:05
Dominique Fortin
1,606816
asked Nov 7 at 10:15
RandomName
284
Imagine I have a tree graph as shown below, where a node can have multiple children, and so on.. (a node can have only 1 parent). If I have a list of paths along that graph, how can I find a subset of those paths that are unique and shortest?
Example Input (List of paths):
[1, 2, 3]
[1, 2]
[1, 7]
[1, 8, 9, 10]
Expected Output:
[1, 2]
[1, 7]
[1, 8, 9, 10]
The [1, 2, 3] path is ignored because it is longer than [1, 2], while the [1, 8, 9, 10] path is kept because it is unique.
algorithm tree graph-theory shortest-path
algorithm tree graph-theory shortest-path
edited Nov 7 at 16:05
Dominique Fortin
1,606816
asked Nov 7 at 10:15
RandomName
284
edited Nov 7 at 16:05
Dominique Fortin
1,606816
asked Nov 7 at 10:15
RandomName
284
edited Nov 7 at 16:05
Dominique Fortin
1,606816
edited Nov 7 at 16:05
Dominique Fortin
1,606816
edited Nov 7 at 16:05
Dominique Fortin
1,606816
1,606816
asked Nov 7 at 10:15
RandomName
284
asked Nov 7 at 10:15
RandomName
284
asked Nov 7 at 10:15
RandomName
284
284
What is the expected output for[1, 2, 3] [1, 2, 4]?
– Cid
Nov 7 at 10:26
@Cid if [1] or [1,2] don't exist, both should appear in the output since they are unique.
– RandomName
Nov 7 at 10:43
So basically if a prefix exists, then you remove that element?
– Willem Van Onsem
Nov 7 at 11:18
1
@WillemVanOnsem it looks like. The problem become really simpler, the terms graph and tree can be ignored since the whole "roads" are send as input. There is no need to parse the tree, this is just array processing. shortest path is here, in my opinion, badly used
– Cid
Nov 7 at 12:18
@Cid: well we can make a prefix-tree here we update for each item,but indeed, it is simpler in terms of graph and tree.
– Willem Van Onsem
Nov 7 at 12:20
|
show 3 more comments
What is the expected output for[1, 2, 3] [1, 2, 4]?
– Cid
Nov 7 at 10:26
@Cid if [1] or [1,2] don't exist, both should appear in the output since they are unique.
– RandomName
Nov 7 at 10:43
So basically if a prefix exists, then you remove that element?
– Willem Van Onsem
Nov 7 at 11:18
1
@WillemVanOnsem it looks like. The problem become really simpler, the terms graph and tree can be ignored since the whole "roads" are send as input. There is no need to parse the tree, this is just array processing. shortest path is here, in my opinion, badly used
– Cid
Nov 7 at 12:18
@Cid: well we can make a prefix-tree here we update for each item,but indeed, it is simpler in terms of graph and tree.
– Willem Van Onsem
Nov 7 at 12:20
What is the expected output for
[1, 2, 3] [1, 2, 4] ?– Cid
Nov 7 at 10:26
What is the expected output for
[1, 2, 3] [1, 2, 4] ?– Cid
Nov 7 at 10:26
@Cid if [1] or [1,2] don't exist, both should appear in the output since they are unique.
– RandomName
Nov 7 at 10:43
@Cid if [1] or [1,2] don't exist, both should appear in the output since they are unique.
– RandomName
Nov 7 at 10:43
So basically if a prefix exists, then you remove that element?
– Willem Van Onsem
Nov 7 at 11:18
So basically if a prefix exists, then you remove that element?
– Willem Van Onsem
Nov 7 at 11:18
1
1
@WillemVanOnsem it looks like. The problem become really simpler, the terms graph and tree can be ignored since the whole "roads" are send as input. There is no need to parse the tree, this is just array processing. shortest path is here, in my opinion, badly used
– Cid
Nov 7 at 12:18
@WillemVanOnsem it looks like. The problem become really simpler, the terms graph and tree can be ignored since the whole "roads" are send as input. There is no need to parse the tree, this is just array processing. shortest path is here, in my opinion, badly used
– Cid
Nov 7 at 12:18
@Cid: well we can make a prefix-tree here we update for each item,but indeed, it is simpler in terms of graph and tree.
– Willem Van Onsem
Nov 7 at 12:20
@Cid: well we can make a prefix-tree here we update for each item,but indeed, it is simpler in terms of graph and tree.
– Willem Van Onsem
Nov 7 at 12:20
|
show 3 more comments
2 Answers
2
active
oldest
votes
up vote
2
down vote
First, sort the input paths by length. Maintain a set of leaf nodes. This will contain the last node of each valid path. After adding a leaf node, we'll forbid any path which includes that leaf node. When you add a path, check each of its members against the set of leaf nodes. If you get a match then the path is invalid, otherwise it's valid and you should add it's final element to the set of leaf nodes.
This is O(n log n) in the number of lists and linear in the number of elements across all lists.
answered Nov 7 at 13:06
Dave
2,4691225
Assuming the longest path's lengthsand the number of pathsn, the complexity would be actuallyO(n*log n*s).
– Emadpres
Nov 7 at 13:12
@Emadpres Say n is the number of paths and m is the number of elements. Then this is O(n log n) + O(m). I don't see why you think n*s comes into it.
– Dave
Nov 7 at 14:41
@Dave i think @Emadpres is right. Try your algorithm for these paths:[1,2,3],[1,4,5],[1,6,7],[1,8,9]
– nightfury1204
Nov 7 at 15:04
@nightfury1204 Well, in the case where all the paths are the same length then m = s*n so I agree for this case, but it isn't generally true. Maybe it's unclear what I meant by m? I mean the sum of the lengths of the paths, not the number of unique elements.
– Dave
Nov 7 at 16:54
add a comment |
up vote
1
down vote
Try to build a tree using these path. For each path, try to traverse from first node of the path to the last node of the path by setting edge to consecutive node.Mark last node of the path as leaf node after traversing each path. If you find any node marked as a leaf when traversing a path, you will stop traversing. Also remove the child of the node that marked as a leaf node. Every path from root node to leaf node in the final tree will be you answer. See figure below for more clarification:
Complexity will be sum of all path's length.
answered Nov 7 at 14:59
nightfury1204
80326
What do you mean by "Also remove the child of the node that marked as a leaf node"?
– Emadpres
Nov 8 at 8:26
1
@Emadpres see in the figure. InAfter path 3node2has child3and4.After path 4[1,2] remove child of node 2.
– nightfury1204
Nov 8 at 8:38
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
First, sort the input paths by length. Maintain a set of leaf nodes. This will contain the last node of each valid path. After adding a leaf node, we'll forbid any path which includes that leaf node. When you add a path, check each of its members against the set of leaf nodes. If you get a match then the path is invalid, otherwise it's valid and you should add it's final element to the set of leaf nodes.
This is O(n log n) in the number of lists and linear in the number of elements across all lists.
answered Nov 7 at 13:06
Dave
2,4691225
Assuming the longest path's lengthsand the number of pathsn, the complexity would be actuallyO(n*log n*s).
– Emadpres
Nov 7 at 13:12
@Emadpres Say n is the number of paths and m is the number of elements. Then this is O(n log n) + O(m). I don't see why you think n*s comes into it.
– Dave
Nov 7 at 14:41
@Dave i think @Emadpres is right. Try your algorithm for these paths:[1,2,3],[1,4,5],[1,6,7],[1,8,9]
– nightfury1204
Nov 7 at 15:04
@nightfury1204 Well, in the case where all the paths are the same length then m = s*n so I agree for this case, but it isn't generally true. Maybe it's unclear what I meant by m? I mean the sum of the lengths of the paths, not the number of unique elements.
– Dave
Nov 7 at 16:54
add a comment |
up vote
2
down vote
First, sort the input paths by length. Maintain a set of leaf nodes. This will contain the last node of each valid path. After adding a leaf node, we'll forbid any path which includes that leaf node. When you add a path, check each of its members against the set of leaf nodes. If you get a match then the path is invalid, otherwise it's valid and you should add it's final element to the set of leaf nodes.
This is O(n log n) in the number of lists and linear in the number of elements across all lists.
answered Nov 7 at 13:06
Dave
2,4691225
Assuming the longest path's lengthsand the number of pathsn, the complexity would be actuallyO(n*log n*s).
– Emadpres
Nov 7 at 13:12
@Emadpres Say n is the number of paths and m is the number of elements. Then this is O(n log n) + O(m). I don't see why you think n*s comes into it.
– Dave
Nov 7 at 14:41
@Dave i think @Emadpres is right. Try your algorithm for these paths:[1,2,3],[1,4,5],[1,6,7],[1,8,9]
– nightfury1204
Nov 7 at 15:04
@nightfury1204 Well, in the case where all the paths are the same length then m = s*n so I agree for this case, but it isn't generally true. Maybe it's unclear what I meant by m? I mean the sum of the lengths of the paths, not the number of unique elements.
– Dave
Nov 7 at 16:54
add a comment |
up vote
2
down vote
up vote
2
down vote
First, sort the input paths by length. Maintain a set of leaf nodes. This will contain the last node of each valid path. After adding a leaf node, we'll forbid any path which includes that leaf node. When you add a path, check each of its members against the set of leaf nodes. If you get a match then the path is invalid, otherwise it's valid and you should add it's final element to the set of leaf nodes.
This is O(n log n) in the number of lists and linear in the number of elements across all lists.
answered Nov 7 at 13:06
Dave
2,4691225
First, sort the input paths by length. Maintain a set of leaf nodes. This will contain the last node of each valid path. After adding a leaf node, we'll forbid any path which includes that leaf node. When you add a path, check each of its members against the set of leaf nodes. If you get a match then the path is invalid, otherwise it's valid and you should add it's final element to the set of leaf nodes.
This is O(n log n) in the number of lists and linear in the number of elements across all lists.
answered Nov 7 at 13:06
Dave
2,4691225
answered Nov 7 at 13:06
Dave
2,4691225
answered Nov 7 at 13:06
Dave
2,4691225
answered Nov 7 at 13:06
Dave
2,4691225
2,4691225
Assuming the longest path's lengthsand the number of pathsn, the complexity would be actuallyO(n*log n*s).
– Emadpres
Nov 7 at 13:12
@Emadpres Say n is the number of paths and m is the number of elements. Then this is O(n log n) + O(m). I don't see why you think n*s comes into it.
– Dave
Nov 7 at 14:41
@Dave i think @Emadpres is right. Try your algorithm for these paths:[1,2,3],[1,4,5],[1,6,7],[1,8,9]
– nightfury1204
Nov 7 at 15:04
@nightfury1204 Well, in the case where all the paths are the same length then m = s*n so I agree for this case, but it isn't generally true. Maybe it's unclear what I meant by m? I mean the sum of the lengths of the paths, not the number of unique elements.
– Dave
Nov 7 at 16:54
add a comment |
Assuming the longest path's lengthsand the number of pathsn, the complexity would be actuallyO(n*log n*s).
– Emadpres
Nov 7 at 13:12
@Emadpres Say n is the number of paths and m is the number of elements. Then this is O(n log n) + O(m). I don't see why you think n*s comes into it.
– Dave
Nov 7 at 14:41
@Dave i think @Emadpres is right. Try your algorithm for these paths:[1,2,3],[1,4,5],[1,6,7],[1,8,9]
– nightfury1204
Nov 7 at 15:04
@nightfury1204 Well, in the case where all the paths are the same length then m = s*n so I agree for this case, but it isn't generally true. Maybe it's unclear what I meant by m? I mean the sum of the lengths of the paths, not the number of unique elements.
– Dave
Nov 7 at 16:54
Assuming the longest path's length
s and the number of paths n, the complexity would be actually O(n*log n*s).– Emadpres
Nov 7 at 13:12
Assuming the longest path's length
s and the number of paths n, the complexity would be actually O(n*log n*s).– Emadpres
Nov 7 at 13:12
@Emadpres Say n is the number of paths and m is the number of elements. Then this is O(n log n) + O(m). I don't see why you think n*s comes into it.
– Dave
Nov 7 at 14:41
@Emadpres Say n is the number of paths and m is the number of elements. Then this is O(n log n) + O(m). I don't see why you think n*s comes into it.
– Dave
Nov 7 at 14:41
@Dave i think @Emadpres is right. Try your algorithm for these paths:
[1,2,3],[1,4,5],[1,6,7],[1,8,9]– nightfury1204
Nov 7 at 15:04
@Dave i think @Emadpres is right. Try your algorithm for these paths:
[1,2,3],[1,4,5],[1,6,7],[1,8,9]– nightfury1204
Nov 7 at 15:04
@nightfury1204 Well, in the case where all the paths are the same length then m = s*n so I agree for this case, but it isn't generally true. Maybe it's unclear what I meant by m? I mean the sum of the lengths of the paths, not the number of unique elements.
– Dave
Nov 7 at 16:54
@nightfury1204 Well, in the case where all the paths are the same length then m = s*n so I agree for this case, but it isn't generally true. Maybe it's unclear what I meant by m? I mean the sum of the lengths of the paths, not the number of unique elements.
– Dave
Nov 7 at 16:54
add a comment |
up vote
1
down vote
Try to build a tree using these path. For each path, try to traverse from first node of the path to the last node of the path by setting edge to consecutive node.Mark last node of the path as leaf node after traversing each path. If you find any node marked as a leaf when traversing a path, you will stop traversing. Also remove the child of the node that marked as a leaf node. Every path from root node to leaf node in the final tree will be you answer. See figure below for more clarification:
Complexity will be sum of all path's length.
answered Nov 7 at 14:59
nightfury1204
80326
What do you mean by "Also remove the child of the node that marked as a leaf node"?
– Emadpres
Nov 8 at 8:26
1
@Emadpres see in the figure. InAfter path 3node2has child3and4.After path 4[1,2] remove child of node 2.
– nightfury1204
Nov 8 at 8:38
add a comment |
up vote
1
down vote
Try to build a tree using these path. For each path, try to traverse from first node of the path to the last node of the path by setting edge to consecutive node.Mark last node of the path as leaf node after traversing each path. If you find any node marked as a leaf when traversing a path, you will stop traversing. Also remove the child of the node that marked as a leaf node. Every path from root node to leaf node in the final tree will be you answer. See figure below for more clarification:
Complexity will be sum of all path's length.
answered Nov 7 at 14:59
nightfury1204
80326
What do you mean by "Also remove the child of the node that marked as a leaf node"?
– Emadpres
Nov 8 at 8:26
1
@Emadpres see in the figure. InAfter path 3node2has child3and4.After path 4[1,2] remove child of node 2.
– nightfury1204
Nov 8 at 8:38
add a comment |
up vote
1
down vote
up vote
1
down vote
Try to build a tree using these path. For each path, try to traverse from first node of the path to the last node of the path by setting edge to consecutive node.Mark last node of the path as leaf node after traversing each path. If you find any node marked as a leaf when traversing a path, you will stop traversing. Also remove the child of the node that marked as a leaf node. Every path from root node to leaf node in the final tree will be you answer. See figure below for more clarification:
Complexity will be sum of all path's length.
answered Nov 7 at 14:59
nightfury1204
80326
Try to build a tree using these path. For each path, try to traverse from first node of the path to the last node of the path by setting edge to consecutive node.Mark last node of the path as leaf node after traversing each path. If you find any node marked as a leaf when traversing a path, you will stop traversing. Also remove the child of the node that marked as a leaf node. Every path from root node to leaf node in the final tree will be you answer. See figure below for more clarification:
Complexity will be sum of all path's length.
answered Nov 7 at 14:59
nightfury1204
80326
answered Nov 7 at 14:59
nightfury1204
80326
answered Nov 7 at 14:59
nightfury1204
80326
answered Nov 7 at 14:59
nightfury1204
80326
80326
What do you mean by "Also remove the child of the node that marked as a leaf node"?
– Emadpres
Nov 8 at 8:26
1
@Emadpres see in the figure. InAfter path 3node2has child3and4.After path 4[1,2] remove child of node 2.
– nightfury1204
Nov 8 at 8:38
add a comment |
What do you mean by "Also remove the child of the node that marked as a leaf node"?
– Emadpres
Nov 8 at 8:26
1
@Emadpres see in the figure. InAfter path 3node2has child3and4.After path 4[1,2] remove child of node 2.
– nightfury1204
Nov 8 at 8:38
What do you mean by "Also remove the child of the node that marked as a leaf node"?
– Emadpres
Nov 8 at 8:26
What do you mean by "Also remove the child of the node that marked as a leaf node"?
– Emadpres
Nov 8 at 8:26
1
1
@Emadpres see in the figure. In
After path 3 node 2 has child 3 and 4. After path 4 [1,2] remove child of node 2.– nightfury1204
Nov 8 at 8:38
@Emadpres see in the figure. In
After path 3 node 2 has child 3 and 4. After path 4 [1,2] remove child of node 2.– nightfury1204
Nov 8 at 8:38
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%2f53187409%2fhow-to-find-a-list-of-unique-shortest-paths-in-a-list-of-paths%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
What is the expected output for
[1, 2, 3] [1, 2, 4]?– Cid
Nov 7 at 10:26
@Cid if [1] or [1,2] don't exist, both should appear in the output since they are unique.
– RandomName
Nov 7 at 10:43
So basically if a prefix exists, then you remove that element?
– Willem Van Onsem
Nov 7 at 11:18
1
@WillemVanOnsem it looks like. The problem become really simpler, the terms graph and tree can be ignored since the whole "roads" are send as input. There is no need to parse the tree, this is just array processing. shortest path is here, in my opinion, badly used
– Cid
Nov 7 at 12:18
@Cid: well we can make a prefix-tree here we update for each item,but indeed, it is simpler in terms of graph and tree.
– Willem Van Onsem
Nov 7 at 12:20