Mixing
Find shortest path recursively by taking parent node into consideration in a graph stored as dictionary
0
I have a graph as below:
I store it in the dictionary data structure.
Suppose I want to find path from D to M:
Then I want something like find shortest path from D to M :
D-H-K-M
and then take it's parent nodes where it finds path from A-M without D in it,
A-E-I-L-M
and B-M without D in it,
B-E-I-L-M
For now, I have been able to find just the shortest path from D-M.
class Graph(object):
def __init__(self, graph_dict=None):
""" initializes a graph object
If no dictionary or None is given,
an empty dictionary will be used
"""
if graph_dict == None:
graph_dict = {}
self.__graph_dict = graph_dict
def vertices(self):
""" returns the vertices of a graph """
return list(self.__graph_dict.keys())
def edges(self):
""" returns the edges of a graph """
return self.__generate_edges()
def add_vertex(self, vertex):
""" If the vertex "vertex" is not in
self.__graph_dict, a key "vertex" with an empty
list as a value is added to the dictionary.
Otherwise nothing has to be done.
"""
if vertex not in self.__graph_dict:
self.__graph_dict[vertex] =
def add_edge(self, edge):
""" assumes that edge is of type set, tuple or list;
between two vertices can be multiple edges!
"""
edge = set(edge)
(vertex1, vertex2) = tuple(edge)
if vertex1 in self.__graph_dict:
self.__graph_dict[vertex1].append(vertex2)
else:
self.__graph_dict[vertex1] = [vertex2]
def __generate_edges(self):
""" A static method generating the edges of the
graph "graph". Edges are represented as sets
with one (a loop back to the vertex) or two
vertices
"""
edges =
for vertex in self.__graph_dict:
for neighbour in self.__graph_dict[vertex]:
if {neighbour, vertex} not in edges:
edges.append({vertex, neighbour})
return edges
def __str__(self):
res = "vertices: "
for k in self.__graph_dict:
res += str(k) + " "
res += "nedges: "
for edge in self.__generate_edges():
res += str(edge) + " "
return res
def find_path(self, start_vertex, end_vertex, path=):
""" find all paths from start_vertex to
end_vertex in graph """
graph = self.__graph_dict
path = path + [start_vertex]
if start_vertex == end_vertex:
return [path]
if start_vertex not in graph:
return
paths =
for vertex in graph[start_vertex]:
if vertex not in path:
extended_paths = self.find_path(vertex,
end_vertex,
path)
for p in extended_paths:
paths.append(p)
return paths
graph_dict = { 'a' : ['d', 'e'],
'b' : ['d', 'e'],
'c' : ['h'],
'd' : ['a', 'b', 'h'],
'e' : ['a', 'b', 'i'],
'f' : ['i'],
'g' : ['k'],
'h' : ['c', 'd', 'k'],
'i' : ['e', 'f', 'l'],
'j' : ['l'],
'k' : ['g', 'h', 'm'],
'l' : ['i', 'j', 'm'],
'm' : ['k', 'l']
}
graph = Graph(graph_dict)
print('The path from vertex "d" to vertex "m":')
path = graph.find_path('d', 'm')
min = len(path[0])
for path_list in path:
if len(path_list)<min:
min = path_list
print(min)
Thank you!
python dictionary graph path-finding
asked Nov 19 '18 at 15:43
ms1941
133
add a comment |
0
I have a graph as below:
I store it in the dictionary data structure.
Suppose I want to find path from D to M:
Then I want something like find shortest path from D to M :
D-H-K-M
and then take it's parent nodes where it finds path from A-M without D in it,
A-E-I-L-M
and B-M without D in it,
B-E-I-L-M
For now, I have been able to find just the shortest path from D-M.
class Graph(object):
def __init__(self, graph_dict=None):
""" initializes a graph object
If no dictionary or None is given,
an empty dictionary will be used
"""
if graph_dict == None:
graph_dict = {}
self.__graph_dict = graph_dict
def vertices(self):
""" returns the vertices of a graph """
return list(self.__graph_dict.keys())
def edges(self):
""" returns the edges of a graph """
return self.__generate_edges()
def add_vertex(self, vertex):
""" If the vertex "vertex" is not in
self.__graph_dict, a key "vertex" with an empty
list as a value is added to the dictionary.
Otherwise nothing has to be done.
"""
if vertex not in self.__graph_dict:
self.__graph_dict[vertex] =
def add_edge(self, edge):
""" assumes that edge is of type set, tuple or list;
between two vertices can be multiple edges!
"""
edge = set(edge)
(vertex1, vertex2) = tuple(edge)
if vertex1 in self.__graph_dict:
self.__graph_dict[vertex1].append(vertex2)
else:
self.__graph_dict[vertex1] = [vertex2]
def __generate_edges(self):
""" A static method generating the edges of the
graph "graph". Edges are represented as sets
with one (a loop back to the vertex) or two
vertices
"""
edges =
for vertex in self.__graph_dict:
for neighbour in self.__graph_dict[vertex]:
if {neighbour, vertex} not in edges:
edges.append({vertex, neighbour})
return edges
def __str__(self):
res = "vertices: "
for k in self.__graph_dict:
res += str(k) + " "
res += "nedges: "
for edge in self.__generate_edges():
res += str(edge) + " "
return res
def find_path(self, start_vertex, end_vertex, path=):
""" find all paths from start_vertex to
end_vertex in graph """
graph = self.__graph_dict
path = path + [start_vertex]
if start_vertex == end_vertex:
return [path]
if start_vertex not in graph:
return
paths =
for vertex in graph[start_vertex]:
if vertex not in path:
extended_paths = self.find_path(vertex,
end_vertex,
path)
for p in extended_paths:
paths.append(p)
return paths
graph_dict = { 'a' : ['d', 'e'],
'b' : ['d', 'e'],
'c' : ['h'],
'd' : ['a', 'b', 'h'],
'e' : ['a', 'b', 'i'],
'f' : ['i'],
'g' : ['k'],
'h' : ['c', 'd', 'k'],
'i' : ['e', 'f', 'l'],
'j' : ['l'],
'k' : ['g', 'h', 'm'],
'l' : ['i', 'j', 'm'],
'm' : ['k', 'l']
}
graph = Graph(graph_dict)
print('The path from vertex "d" to vertex "m":')
path = graph.find_path('d', 'm')
min = len(path[0])
for path_list in path:
if len(path_list)<min:
min = path_list
print(min)
Thank you!
python dictionary graph path-finding
asked Nov 19 '18 at 15:43
ms1941
133
Can you explain what is wrong with your code? How does it's output differ from what you want?
– Yakov Dan
Nov 19 '18 at 16:01
@YakovDan I am not able to get the second part of it where I need to find the parent nodes and while finding the path from parent node to destination, (in example, A-M or B-M) it should not consider the source(D).
– ms1941
Nov 19 '18 at 16:11
add a comment |
0
0
0
I have a graph as below:
I store it in the dictionary data structure.
Suppose I want to find path from D to M:
Then I want something like find shortest path from D to M :
D-H-K-M
and then take it's parent nodes where it finds path from A-M without D in it,
A-E-I-L-M
and B-M without D in it,
B-E-I-L-M
For now, I have been able to find just the shortest path from D-M.
class Graph(object):
def __init__(self, graph_dict=None):
""" initializes a graph object
If no dictionary or None is given,
an empty dictionary will be used
"""
if graph_dict == None:
graph_dict = {}
self.__graph_dict = graph_dict
def vertices(self):
""" returns the vertices of a graph """
return list(self.__graph_dict.keys())
def edges(self):
""" returns the edges of a graph """
return self.__generate_edges()
def add_vertex(self, vertex):
""" If the vertex "vertex" is not in
self.__graph_dict, a key "vertex" with an empty
list as a value is added to the dictionary.
Otherwise nothing has to be done.
"""
if vertex not in self.__graph_dict:
self.__graph_dict[vertex] =
def add_edge(self, edge):
""" assumes that edge is of type set, tuple or list;
between two vertices can be multiple edges!
"""
edge = set(edge)
(vertex1, vertex2) = tuple(edge)
if vertex1 in self.__graph_dict:
self.__graph_dict[vertex1].append(vertex2)
else:
self.__graph_dict[vertex1] = [vertex2]
def __generate_edges(self):
""" A static method generating the edges of the
graph "graph". Edges are represented as sets
with one (a loop back to the vertex) or two
vertices
"""
edges =
for vertex in self.__graph_dict:
for neighbour in self.__graph_dict[vertex]:
if {neighbour, vertex} not in edges:
edges.append({vertex, neighbour})
return edges
def __str__(self):
res = "vertices: "
for k in self.__graph_dict:
res += str(k) + " "
res += "nedges: "
for edge in self.__generate_edges():
res += str(edge) + " "
return res
def find_path(self, start_vertex, end_vertex, path=):
""" find all paths from start_vertex to
end_vertex in graph """
graph = self.__graph_dict
path = path + [start_vertex]
if start_vertex == end_vertex:
return [path]
if start_vertex not in graph:
return
paths =
for vertex in graph[start_vertex]:
if vertex not in path:
extended_paths = self.find_path(vertex,
end_vertex,
path)
for p in extended_paths:
paths.append(p)
return paths
graph_dict = { 'a' : ['d', 'e'],
'b' : ['d', 'e'],
'c' : ['h'],
'd' : ['a', 'b', 'h'],
'e' : ['a', 'b', 'i'],
'f' : ['i'],
'g' : ['k'],
'h' : ['c', 'd', 'k'],
'i' : ['e', 'f', 'l'],
'j' : ['l'],
'k' : ['g', 'h', 'm'],
'l' : ['i', 'j', 'm'],
'm' : ['k', 'l']
}
graph = Graph(graph_dict)
print('The path from vertex "d" to vertex "m":')
path = graph.find_path('d', 'm')
min = len(path[0])
for path_list in path:
if len(path_list)<min:
min = path_list
print(min)
Thank you!
python dictionary graph path-finding
asked Nov 19 '18 at 15:43
ms1941
133
I have a graph as below:
I store it in the dictionary data structure.
Suppose I want to find path from D to M:
Then I want something like find shortest path from D to M :
D-H-K-M
and then take it's parent nodes where it finds path from A-M without D in it,
A-E-I-L-M
and B-M without D in it,
B-E-I-L-M
For now, I have been able to find just the shortest path from D-M.
class Graph(object):
def __init__(self, graph_dict=None):
""" initializes a graph object
If no dictionary or None is given,
an empty dictionary will be used
"""
if graph_dict == None:
graph_dict = {}
self.__graph_dict = graph_dict
def vertices(self):
""" returns the vertices of a graph """
return list(self.__graph_dict.keys())
def edges(self):
""" returns the edges of a graph """
return self.__generate_edges()
def add_vertex(self, vertex):
""" If the vertex "vertex" is not in
self.__graph_dict, a key "vertex" with an empty
list as a value is added to the dictionary.
Otherwise nothing has to be done.
"""
if vertex not in self.__graph_dict:
self.__graph_dict[vertex] =
def add_edge(self, edge):
""" assumes that edge is of type set, tuple or list;
between two vertices can be multiple edges!
"""
edge = set(edge)
(vertex1, vertex2) = tuple(edge)
if vertex1 in self.__graph_dict:
self.__graph_dict[vertex1].append(vertex2)
else:
self.__graph_dict[vertex1] = [vertex2]
def __generate_edges(self):
""" A static method generating the edges of the
graph "graph". Edges are represented as sets
with one (a loop back to the vertex) or two
vertices
"""
edges =
for vertex in self.__graph_dict:
for neighbour in self.__graph_dict[vertex]:
if {neighbour, vertex} not in edges:
edges.append({vertex, neighbour})
return edges
def __str__(self):
res = "vertices: "
for k in self.__graph_dict:
res += str(k) + " "
res += "nedges: "
for edge in self.__generate_edges():
res += str(edge) + " "
return res
def find_path(self, start_vertex, end_vertex, path=):
""" find all paths from start_vertex to
end_vertex in graph """
graph = self.__graph_dict
path = path + [start_vertex]
if start_vertex == end_vertex:
return [path]
if start_vertex not in graph:
return
paths =
for vertex in graph[start_vertex]:
if vertex not in path:
extended_paths = self.find_path(vertex,
end_vertex,
path)
for p in extended_paths:
paths.append(p)
return paths
graph_dict = { 'a' : ['d', 'e'],
'b' : ['d', 'e'],
'c' : ['h'],
'd' : ['a', 'b', 'h'],
'e' : ['a', 'b', 'i'],
'f' : ['i'],
'g' : ['k'],
'h' : ['c', 'd', 'k'],
'i' : ['e', 'f', 'l'],
'j' : ['l'],
'k' : ['g', 'h', 'm'],
'l' : ['i', 'j', 'm'],
'm' : ['k', 'l']
}
graph = Graph(graph_dict)
print('The path from vertex "d" to vertex "m":')
path = graph.find_path('d', 'm')
min = len(path[0])
for path_list in path:
if len(path_list)<min:
min = path_list
print(min)
Thank you!
python dictionary graph path-finding
python dictionary graph path-finding
asked Nov 19 '18 at 15:43
ms1941
133
asked Nov 19 '18 at 15:43
ms1941
133
asked Nov 19 '18 at 15:43
ms1941
133
asked Nov 19 '18 at 15:43
ms1941
133
asked Nov 19 '18 at 15:43
ms1941
133
133
Can you explain what is wrong with your code? How does it's output differ from what you want?
– Yakov Dan
Nov 19 '18 at 16:01
@YakovDan I am not able to get the second part of it where I need to find the parent nodes and while finding the path from parent node to destination, (in example, A-M or B-M) it should not consider the source(D).
– ms1941
Nov 19 '18 at 16:11
add a comment |
Can you explain what is wrong with your code? How does it's output differ from what you want?
– Yakov Dan
Nov 19 '18 at 16:01
@YakovDan I am not able to get the second part of it where I need to find the parent nodes and while finding the path from parent node to destination, (in example, A-M or B-M) it should not consider the source(D).
– ms1941
Nov 19 '18 at 16:11
Can you explain what is wrong with your code? How does it's output differ from what you want?
– Yakov Dan
Nov 19 '18 at 16:01
Can you explain what is wrong with your code? How does it's output differ from what you want?
– Yakov Dan
Nov 19 '18 at 16:01
@YakovDan I am not able to get the second part of it where I need to find the parent nodes and while finding the path from parent node to destination, (in example, A-M or B-M) it should not consider the source(D).
– ms1941
Nov 19 '18 at 16:11
@YakovDan I am not able to get the second part of it where I need to find the parent nodes and while finding the path from parent node to destination, (in example, A-M or B-M) it should not consider the source(D).
– ms1941
Nov 19 '18 at 16:11
add a comment |
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
});
}
});
draft saved
draft discarded
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%2f53378145%2ffind-shortest-path-recursively-by-taking-parent-node-into-consideration-in-a-gra%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
draft saved
draft discarded
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.
draft saved
draft discarded
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%2f53378145%2ffind-shortest-path-recursively-by-taking-parent-node-into-consideration-in-a-gra%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 what is wrong with your code? How does it's output differ from what you want?
– Yakov Dan
Nov 19 '18 at 16:01
@YakovDan I am not able to get the second part of it where I need to find the parent nodes and while finding the path from parent node to destination, (in example, A-M or B-M) it should not consider the source(D).
– ms1941
Nov 19 '18 at 16:11