Mam za zadanie znaleźć trasę z jednego punktu do drugiego. Każdą listę punktów mam liście np:
lista1 = {a,b,c,d,e,f};
lista2 = {g, e, h, i ,j };
lista3 = {k, l, i, n, m};
I przykładowo mam znaleźć trasę z "d" do "n" i nie mam zielonego pojęcia jak to zrealizować nie implementując grafu. I punktów wspólnych dla list może być więcej niż 1,więc tych tras może być też >1. Dodatkowo z góry nie wiem ile takich list będzie. Z góry dzięki za pomoc.
W jakim sensie trasę? Np. "trasa" z d do n: d -> n.
lion137 napisał(a):
W jakim sensie trasę? Np. "trasa" z
ddon:d -> n.
W takim, żeby w nowej liście były punkty od d do n czyli np
lista4 = {d, e, h, i ,n };
A czemu {d, e, h, i ,n }, a nie np., d, h, n?
lion137 napisał(a):
A czemu
{d, e, h, i ,n }, a nie np.,d, h, n?
Dlatego,żeby był uwzględniony każdy punkt po drodze
Btw. Nawet jak nie masz grafu... to masz graf. Co najwyżej kijowo zapisany ( w tych listach).
Nie wiem jak inni ale ja zupełnie nie rozumiem co przechowuja te twoje listy i dlaczego trasa o której piszesz ma przebiegać tak jak napisałeś. Możesz wyjaśnić? To są listy wierzchołków które są połączone? Spójne podgrafy? Ale wtedy d->n byłoby d->e->i->n a nie to co napisałeś.
Shalom napisał(a):
Nie wiem jak inni ale ja zupełnie nie rozumiem co przechowuja te twoje listy i dlaczego trasa o której piszesz ma przebiegać tak jak napisałeś. Możesz wyjaśnić? To są listy wierzchołków które są połączone? Spójne podgrafy? Ale wtedy
d->nbyłobyd->e->i->na nie to co napisałeś.
To są listy wierzchołków, które są połączone, dlatego wierzchołek, który występuje w 2 listach jest pkt przecięcia
Czyli graf wygląda tak jak na załączonym rysunku i ścieżka też?
yarel napisał(a):
Czyli graf wygląda tak jak na załączonym rysunku i ścieżka też?
Wygląda tak jak w moim załączniku ale to tylko przykład a docelowy graf, który będzie użyty do szukania może być (a raczej na pewno będzie) dowolny, ale bez pętli
EDIT: o wygląda dokładnie tak samo
Hmm, to teraz pytanie właściwe, dlaczego nie chcesz skorzystać z jakiegoś algorytmu grafowego? W końcu masz graf na wejściu, tylko w dziwnej postaci, więc możesz zaimplementować operacje typu: daj mi sąsiadów wierzchołka X (przeglądasz wszystkie listy i jak jest tam X, to bierzesz poprzednik i nastepnik o ile występują) i nie musisz budować grafu w innej postaci.
Ze znalezieniem tych punktów przecięcia nie mam problemu, bo sprawdzam każda listę ale jak je znajdę to niezbyt wiem jak zaimplementować to szukanie w przód i tył
W pythonie:
from collections import deque
graph = [
['a', 'b', 'c', 'd', 'e', 'f'],
['g', 'e', 'h', 'i', 'j'],
['k', 'l', 'i', 'n', 'm']
]
def graph_nodes(a_graph):
return list(set([node for _ in a_graph for node in _]))
def neighbours(a_graph, a_node):
node_neighbours = []
"""
Przegladamy kazda z list reprezentujacych graf i jesli napotkamy zadany wierzcholek, to zapamietujemy jego
poprzednika i nastepnika (o ile istnieja).
"""
for a_list in a_graph:
for i, element in enumerate(a_list):
if element == a_node and i + 1 < len(a_list):
node_neighbours.append(a_list[i + 1])
if element == a_node and i - 1 >= 0:
node_neighbours.append(a_list[i - 1])
return list(set(node_neighbours))
# Zwykle przechodzenie grafu
def find_path(a_graph, from_node, to_node):
nodes = graph_nodes(a_graph)
if from_node not in nodes or to_node not in nodes:
return None
visited = {n: False for n in nodes}
""" W kolejce pamietamy sciezke od zadanego wierzcholka"""
queue = deque([from_node])
while len(queue) > 0:
remembered_path = queue.pop()
current_node = remembered_path[-1] # Ostatni element sciezki to wierzcholek do dalszej analizy
visited[current_node] = True
if current_node == to_node:
return remembered_path
for node in neighbours(a_graph, current_node):
if not visited[node]:
visited[node] = True
new_path = [n for n in remembered_path]
new_path.append(node)
queue.append(new_path)
return None
print("Path={}".format(find_path(graph, 'd', 'n')))
print("Path={}".format(find_path(graph, 'a', 'm')))
print("Path={}".format(find_path(graph, 'k', 'j')))
print("Path={}".format(find_path(graph, 'FOO', 'BAR')))
print("Path={}".format(find_path(graph, 'a', 'BAR')))
Akurat muszę to zrobić w Javie ale dzięki :)
Przepisałem to do Javy ale nigdy nie pisałem w Pythonie i pewnie są błędy:
private Map<Integer, List<String>> linia; //tutaj znajdują się wszystkie listy wierzchołków
///// metody przepisane z Pytona w kodzie:
private List<String> setNeighbours(Map<Integer, List<String>> graph, String node) {
for (i = 0; i < graph.size(); i++) {
for (j = 0; j < graph.get(i).size(); j++) {
if (graph.get(i).get(j).contains(node) && j + 1 < graph.get(i).size())
neighbours.add(graph.get(i).get(j + 1));
if (graph.get(i).get(j).contains(node) && j - 1 >= 0)
neighbours.add(graph.get(i).get(j - 1));
}
}
return neighbours;
}
private List<String> allNodes(Map<Integer, List<String>> graph) {
for (i = 0; i < graph.size(); i++) {
for (j = 0; j < graph.get(i).size(); j++)
nodes.add(graph.get(i).get(j));
}
return nodes;
}
{
if (!allNodes(linia).contains(from.getName()) || !allNodes(linia).contains(to.getName())) {
System.out.println("Dla podanych przystanków nie ma rozwiązań.");
} else {
ArrayList<Boolean> visited = new ArrayList<>();
for (i = 0; i < allNodes(linia).size(); i++) {
visited.set(allNodes(linia).indexOf(i), false);
}
Queue<String> queue = new ArrayDeque<>();
queue.add(from.getName());
while(queue.size() > 0) {
path.add(queue.poll());
String currentNode = path.get(0);
visited.set(allNodes(linia).indexOf(currentNode), true);
if(currentNode == to.getName())
System.out.println(path);//musze dodać do trasa
for (String node : setNeighbours(linia, currentNode)) {
if(visited.get(allNodes(linia).indexOf(node)) == false) {
visited.set(allNodes(linia).indexOf(node), true);
ArrayList<String> new_path = new ArrayList<>();
new_path.addAll(path);
new_path.add(node);
queue.add(node);
}
}
}
}
}
yarel napisał(a):
A oto zgrabna implementacja tworzenia grafu:
def adjacency_list(graph):
s = {}
for path in graph:
for a, b in zip(path, path[1:]):
try:
s[a].add(b)
except KeyError:
s[a] = {b}
try:
s[b].add(a)
except KeyError:
s[b] = {a}
return [(k, list(v)) for k, v in s.items()] # ewentualnie po prostu `return s`