経路探索

縁あって幅経路探索をPrologで。本当はエッジの重みを所要時間にしたり、乗り換えにもコストをつけたいんだけど、データを載せるのがめんど（ｒｙ

ginza_sen(shibuya, omote-sando).
ginza_sen(omote-sando, gaiemmae).
ginza_sen(gaiemmae, aoyama-itchome).
ginza_sen(aoyama-itchome, akasaka-mitsuke).
ginza_sen(akasaka-mitsuke, tameike-sanno).
ginza_sen(tameike-sanno, toranomon).
ginza_sen(toranomon, shimbashi).
ginza_sen(shimbashi, ginza).
ginza_sen(ginza, kyobashi).
ginza_sen(kyobashi, nihombashi).
ginza_sen(nihombashi, mitsukoshimae).
ginza_sen(mitsukoshimae, kanda).
ginza_sen(kanda, suehirocho).
ginza_sen(suehirocho, ueno-hirokoji).
ginza_sen(ueno-hirokoji, ueno).
ginza_sen(ueno, inaricho).
ginza_sen(inaricho, tawaramachi).
ginza_sen(tawaramachi, asakusa).

marunouchi_sen(ogikubo, minami-asagaya).
marunouchi_sen(minami-asagaya, shin-koenji).
marunouchi_sen(shin-koenji, higashi-koenji).
marunouchi_sen(higashi-koenji, shin-nakano).
marunouchi_sen(shin-nakano, nakano-sakaue).
marunouchi_sen(nakano-sakaue, nishi-shinjuku).
marunouchi_sen(nishi-shinjuku, shinjuku).
marunouchi_sen(shinjuku, shinjuku-sanchome).
marunouchi_sen(shinjuku-sanchome, shinjuku-gyoemmae).
marunouchi_sen(shinjuku-gyoemmae, yotsuya-sanchome).
marunouchi_sen(yotsuya-sanchome, yotsuya).
marunouchi_sen(yotsuya, akasaka-mitsuke).
marunouchi_sen(akasaka-mitsuke, kokkai-gijidomae).
marunouchi_sen(kokkai-gijidomae, kasumigaseki).
marunouchi_sen(kasumigaseki, ginza).
marunouchi_sen(ginza, tokyo).
marunouchi_sen(tokyo, otemachi).
marunouchi_sen(otemachi, awajicho).
marunouchi_sen(awajicho, ochanomizu).
marunouchi_sen(ochanomizu, hongo-sanchome).
marunouchi_sen(hongo-sanchome, korakuen).
marunouchi_sen(korakuen, myogadani).
marunouchi_sen(myogadani, shin-otsuka).
marunouchi_sen(shin-otsuka, ikebukuro).

marunouchi_sen(honancho, nakano-fujimicho).
marunouchi_sen(nakano-fujimicho, nakano-shimbashi).
marunouchi_sen(nakano-shimbashi, nakano-sakaue).

hibiya_sen(naka-meguro, ebisu).
hibiya_sen(ebisu, hiro-o).
hibiya_sen(hiro-o, roppongi).
hibiya_sen(roppongi, kamiyacho).
hibiya_sen(kamiyacho, kasumigaseki).
hibiya_sen(kasumigaseki, hibiya).
hibiya_sen(hibiya, ginza).
hibiya_sen(ginza, higashi-ginza).
hibiya_sen(higashi-ginza, tsukiji).
hibiya_sen(tsukiji, hatchobori).
hibiya_sen(hatchobori, kayabacho).
hibiya_sen(kayabacho, ningyocho).
hibiya_sen(ningyocho, kodemmacho).
hibiya_sen(kodemmacho, akihabara).
hibiya_sen(akihabara, naka-okachimachi).
hibiya_sen(naka-okachimachi, ueno).
hibiya_sen(ueno, iriya).
hibiya_sen(iriya, minowa).
hibiya_sen(minowa, minami-senju).
hibiya_sen(minami-senju, kita-senju).

touzai_sen(nakano, ochiai).
touzai_sen(ochiai, takadanobaba).
touzai_sen(takadanobaba, waseda).
touzai_sen(waseda, kagurazaka).
touzai_sen(kagurazaka, iidabashi).
touzai_sen(iidabashi, kudanshita).
touzai_sen(kudanshita, takebashi).
touzai_sen(takebashi, otemachi).
touzai_sen(otemachi, nihombashi).
touzai_sen(nihombashi, kayabacho).
touzai_sen(kayabacho, monzen-nakacho).
touzai_sen(monzen-nakacho, kiba).
touzai_sen(kiba, toyocho).
touzai_sen(toyocho, minami-sunamachi).
touzai_sen(minami-sunamachi, nishi-kasai).
touzai_sen(nishi-kasai, kasai).
touzai_sen(kasai, urayasu).
touzai_sen(urayasu, minami-gyotoku).
touzai_sen(minami-gyotoku, gyotoku).
touzai_sen(gyotoku, myoden).
touzai_sen(myoden, baraki-nakayama).
touzai_sen(baraki-nakayama, nishi-funabashi).

chiyoda_sen(yoyogi-uehara, yoyogi-koen).
chiyoda_sen(yoyogi-koen, meiji-jingumae).
chiyoda_sen(meiji-jingumae, omote-sando).
chiyoda_sen(omote-sando, nogizaka).
chiyoda_sen(nogizaka, akasaka).
chiyoda_sen(akasaka, kokkai-gijidomae).
chiyoda_sen(kokkai-gijidomae, kasumigaseki).
chiyoda_sen(kasumigaseki, hibiya).
chiyoda_sen(hibiya, nijubashimae).
chiyoda_sen(nijubashimae, otemachi).
chiyoda_sen(otemachi, shin-ochanomizu).
chiyoda_sen(shin-ochanomizu, yushima).
chiyoda_sen(yushima, nezu).
chiyoda_sen(nezu, sendagi).
chiyoda_sen(sendagi, nishi-nippori).
chiyoda_sen(nishi-nippori, machiya).
chiyoda_sen(machiya, kita-senju).
chiyoda_sen(kita-senju, ayase).
chiyoda_sen(ayase, kita-ayase).

yurakucho_sen(wakoshi, chikatetsu-narimasu).
yurakucho_sen(chikatetsu-narimasu, chikatetsu-akatsuka).
yurakucho_sen(chikatetsu-akatsuka, heiwadai).
yurakucho_sen(heiwadai, hikawadai).
yurakucho_sen(hikawadai, kotake-mukaihara).
yurakucho_sen(kotake-mukaihara, senkawa).
yurakucho_sen(senkawa, kanamecho).
yurakucho_sen(kanamecho, ikebukuro).
yurakucho_sen(ikebukuro, higashi-ikebukuro).
yurakucho_sen(higashi-ikebukuro, gokokuji).
yurakucho_sen(gokokuji, edogawabashi).
yurakucho_sen(edogawabashi, iidabashi).
yurakucho_sen(iidabashi, ichigaya).
yurakucho_sen(ichigaya, kojimachi).
yurakucho_sen(kojimachi, nagatacho).
yurakucho_sen(nagatacho, sakuradamon).
yurakucho_sen(sakuradamon, yurakucho).
yurakucho_sen(yurakucho, ginza-itchome).
yurakucho_sen(ginza-itchome, shintomicho).
yurakucho_sen(shintomicho, tsukishima).
yurakucho_sen(tsukishima, toyosu).
yurakucho_sen(toyosu, tatsumi).
yurakucho_sen(tatsumi, shin-kiba).

hanzoumon_sen(shibuya, omote-sando).
hanzoumon_sen(omote-sando, aoyama-itchome).
hanzoumon_sen(aoyama-itchome, nagatacho).
hanzoumon_sen(nagatacho, hanzomon).
hanzoumon_sen(hanzomon, kudanshita).
hanzoumon_sen(kudanshita, jimbocho).
hanzoumon_sen(jimbocho, otemachi).
hanzoumon_sen(otemachi, mitsukoshimae).
hanzoumon_sen(mitsukoshimae, suitengumae).
hanzoumon_sen(suitengumae, kiyosumi-shirakawa).
hanzoumon_sen(kiyosumi-shirakawa, sumiyoshi).
hanzoumon_sen(sumiyoshi, kinshicho).
hanzoumon_sen(kinshicho, oshiage).

nanboku_sen(meguro, shirokanedai).
nanboku_sen(shirokanedai, shirokane-takanawa).
nanboku_sen(shirokane-takanawa, azabu-juban).
nanboku_sen(azabu-juban, roppongi-itchome).
nanboku_sen(roppongi-itchome, tameike-sanno).
nanboku_sen(tameike-sanno, nagatacho).
nanboku_sen(nagatacho, yotsuya).
nanboku_sen(yotsuya, ichigaya).
nanboku_sen(ichigaya, iidabashi).
nanboku_sen(iidabashi, korakuen).
nanboku_sen(korakuen, todaimae).
nanboku_sen(todaimae, hon-komagome).
nanboku_sen(hon-komagome, komagome).
nanboku_sen(komagome, nishigahara).
nanboku_sen(nishigahara, oji).
nanboku_sen(oji, oji-kamiya).
nanboku_sen(oji-kamiya, shimo).
nanboku_sen(shimo, akabane-iwabuchi).

next(X, Y) :- ginza_sen(X, Y).
next(X, Y) :- ginza_sen(Y, X).
next(X, Y) :- marunouchi_sen(X, Y).
next(X, Y) :- marunouchi_sen(Y, X).
next(X, Y) :- hibiya_sen(X, Y).
next(X, Y) :- hibiya_sen(Y, X).
next(X, Y) :- touzai_sen(X, Y).
next(X, Y) :- touzai_sen(Y, X).
next(X, Y) :- chiyoda_sen(X, Y).
next(X, Y) :- chiyoda_sen(Y, X).
next(X, Y) :- yurakucho_sen(X, Y).
next(X, Y) :- yurakucho_sen(Y, X).
next(X, Y) :- hanzoumon_sen(X, Y).
next(X, Y) :- hanzoumon_sen(Y, X).
next(X, Y) :- nanboku_sen(X, Y).
next(X, Y) :- nanboku_sen(Y, X).

search_path(Start) :-
	retractall(path(Start, _, _)),
	assert(path(Start, Start, [Start])),
	search_path1(Start, 1).

search_path1(Start, N) :-
	select_current_node(Start, N).

search_path1(Start, N) :-
	path(Start, _, AnyPath),
	length(AnyPath, N),
	!,
	N1 is N + 1,
	search_path1(Start, N1).

select_current_node(Start, N) :-
	path(Start, CurrentNode, CurrentPath),
	length(CurrentPath, N),
	check_next_node(Start, CurrentNode, CurrentPath),
	fail.

check_next_node(Start, CurrentNode, CurrentPath) :-
	next(CurrentNode, NextNode),
	not(memberchk(NextNode, CurrentPath)),
	save_next_node_path(Start, CurrentPath, NextNode).

save_next_node_path(Start, CurrentPath, NextNode) :-
	not(path(Start, NextNode, _)),
	!,
	assert(path(Start, NextNode, [NextNode|CurrentPath])).

save_next_node_path(Start, CurrentPath, NextNode) :-
	path(Start, NextNode, OldNextNodePath),
	!,
	length(OldNextNodePath, OldNextNodePathLength),
	length(CurrentPath, CurrentPathLength),
	OldNextNodePathLength > CurrentPathLength + 1,
	retractall(path(Start, NextNode, _)),
	assert(path(Start, NextNode, [NextNode|CurrentPath])).