Mam duży zestaw wierzchołków / węzłów reprezentujących zestaw wykresów. Zauważ, że w tym kompletnym zestawie może być wiele niezależnych wykresów. Celem jest znalezienie Min Liczba wierzchołków na wszystkich tych wykresach, które odpowiadają największą całkowitą sumę ciężarów na wszystkich krawędzi przechwyconych przez wybrane wierzchołki. Mam macierz przyrody w Pandy i używam NetworkX.

Poniżej znajduje się przykładowa dataframe z trzema kolumnami, w których liczba_ftrips jest waga. Mogę zapewnić wagę węzła = 10 * wycieczki, aby połączyć dwie metryki razem. To znaczy. Maksymalizacja # wycieczek - 10 * Numberofnodes

    Number_Of_Trips dropoff_gh7 pickup_gh7
0   304 9tbqhsx 9tbqj4g
1   271 9tbqj4f 9tbqhsx
2   263 9tbqt4s 9tbqhsx
3   258 9tbqdye 9tbqdsr
4   256 9tbqhgh 9tbqjfv
5   236 9tbqhsw 9tbqj4g
6   233 9tbqt4g 9tbqv03
7   229 9tbqhsx 9tbqj4c
8   218 9tbqy3f 9tbqt4s
9   213 9tbq5v4 9tbqh41
10  210 9tbqhgh 9tbqhsw
11  192 9tbqhgh 9tbqje4
12  186 9tbqy3f 9tbqt4g
13  184 9tbqhgh 9tbqj4z
14  183 9tbqe3d 9tbqe9e
15  170 9tbq3xn 9tbq39w
16  167 9tbq5bw 9tbqht6
17  163 9tbqhsx 9tbqh0x
18  162 9tbqdk1 9tbq7p2
19  160 9tbqsch 9tbqt4s

x = nx.from_pandas_dataframe(df,"dropoff_gh7","pickup_gh7","Number_Of_Trips")
graphs = list(nx.connected_component_subgraphs(x))
0
SriK 18 październik 2017, 21:27

2 odpowiedzi

Najlepsza odpowiedź

Zauważ, że jeden zastrzeżenie do pytania jest to, że możesz mieć wiele niezależnych subgraphów na wykresie, który może być rozwiązaniem. Najważniejszym intuicją do tego rozwiązania jest to, że najprawdopodobniej kandydaci do subgraphów są wierzchołkami, które dzielą się ze sobą wiele krawędzi. Okazuje się, że jest to dokładnie co ocenia się, gdy patrząc na Cliques na wykresie. W związku z tym rozwiązanie to po prostu wyciąga wszystkie przyciski, a następnie zdobywa one łączną liczbę ciężarów reprezentowanych przez wierzchołki w klików - liczba wierzchołków * koszt wierzchołka. Można to szybko prototypowi za pomocą Networkx.

G = nx.from_pandas_dataframe(df, "dropoff_gh7", "pickup_gh7", ['num_of_trips'])
# Find all the cliques in the graph (not only maximal but all sub cliques as well. Note that clique finding is NP complete so this may take a long time if your graph is > 100k of edges or more. For <100k edges, this took within 5 mins on a 16GB macbook pro 3GHz machine.
cliques = nx.find_cliques(G)
clique_trips = [np.array([c,G.subgraph(c).size(weight="num_of_trips")]) for c in cliques]
df_cliques = pd.DataFrame(clique_trips,columns=["vertices","num_of_trips"])
df_cliques["num_vertices"] = df_cliques.apply(lambda x:len(x[0]), axis=1)
df_cliques["weighted_trips"] = df_cliques.apply(lambda row: 
    row["num_of_trips"] - row["num_vertices"]*COST_PER_NODE, axis=1)
df_cliques = df_cliques.sort_values("weighted_trips")[::-1]
df_cliques.head()
# The top N cliques can then be aggregated into a set to identify the precise vertices that are most valuable.
0
SriK 31 październik 2017, 17:28

Oto zarys logiki.

Utwórz klaster strukturę. Klaster ma węzły członkowskie, wartość wewnętrzna (całkowite wycieczki wewnętrzne) i krawędzie do innych klastrów.

Zacznij od każdego węzła w indywidualnym klastrze. Umieść wszystkie te klastry w liście "nie zrobione". Teraz zamierzasz iterować tę listę, łącząc klastry, w których można znaleźć zalety. Wybierz pierwszy klaster na liście.

Itera : Dla każdej krawędzi tego klastra sprawdź wartość netto łączenia klastra na drugim końcu tej krawędzi: wycieczki wewnętrzne + wycieczki krawędziowe - 10 * populacja klastrów (ilość węzłów).

Serge : Conatenienate listy węzłów członków dwóch klastrów. Dodaj ich wewnętrzne wartości i wartość krawędzi między nimi. Dostosuj się do populacji węzła (jeśli nie robisz jeszcze tego rachunkowości w innym miejscu). Scal listę krawędzi do innych klastrów. Usuń skupiany klaster z listy "Not Done".

Kontynuuj ten proces "Kleene Zamknięcie", aż nie masz więcej węzłów, aby dodać zjeralnie. Przenieś ten wynikowy klaster do listy "Gotowe". Wybierz następny węzeł w liście "Nie" i powtórz pętlę Itera i scalania, dopóki lista "Gotowa" jest pusta.

Teraz przesuń całą listę "Done" z powrotem do listy "Nie wykonane" i powtórz proces, aż ukończysz przełęcz z nr dalej łączy.


Czy jest to wystarczająco szczegółowe, abyś mógł kodować proces?

1
Prune 20 październik 2017, 21:13