I want to implement Tabu Search in Python to solve a problem related to a Graph (finding trees, coloring problem and that kind of stuff). I have written basic codes in Python and that's the first time I am writing something like that. I know how the algorithm works (in theory) and I am having some trouble to implement it.
What's the best way to generate the random solution so I can start the algorithm? I want to generate a random tree from an initial graph:
graph = { "a" : ["c"],
"b" : ["c", "e"],
"c" : ["a", "b", "d", "e"],
"d" : ["c"],
"e" : ["c", "b"],
"f" : []
}
I'm using these functions to see the edges and isolated nodes:
def generate_edges(graph):
edges = []
for node in graph:
for neighbour in graph[node]:
edges.append((node, neighbour))
return edges
print(generate_edges(graph))
def find_isolated_nodes(graph):
""" returns a list of isolated nodes. """
isolated = []
for node in graph:
if not graph[node]:
isolated += node
return isolated
print(find_isolated_nodes(graph))
And this one to find the paths:
def find_all_paths(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_all_paths(vertex,
end_vertex,
path)
for p in extended_paths:
paths.append(p)
return paths
What I need is to find a tree as a random solution so I can change it until is the biggest possible one in the graph I have.
What could be the best way to do that? Thank you.
