目次 ⇒ Javaアルゴリズムライブラリ-Artery-サンプル
#概要
本サンプルの内容
閉路判定(Q07_00)
始点・終点を求める(Q07_01)
非連結のグラフを分割する(Q07_02)
トポロジカルソートを行う(Q07_03)
指定駅間の経路を求める(Q07_04)
(参考)ロジックのソース-トポロジカルソート、指定駅間の経路
これから実装しようとしている大体の内容(⇒気長に待っててね)
経路探索で通過しない駅の指定 ⇒ ver201912実装
経路の幅優先探索
ArCreatorで得られる数値の最小値探索(例.駅数最小、距離最小、時間最小)
快速問題、複々線問題
(別サンプル)作業日程の作成
(別サンプル)作業日程の山崩し(最大能力に合わせる、最長日程に合わせる)
(別サンプル)作業のクリティカルパス、フロート、最早日程、最遅日程
(別サンプル)リソース(作業者など)を考慮した作業日程の作成
(別サンプル)リソース(作業者など)使用の平準化、リソースのスケジュール表作成
(別サンプル)作業日程の予定と実績
(別サンプル)作業遅延に対する別日程の作成
#サンプルデータの概要
解説サンプルとして鉄道路線を題材にする。JR山手線(内回り、外回り)、JR中央線(東京⇔高尾)、京王線(本線(新宿⇔八王子)、井の頭線(渋谷⇔吉祥寺)、相模原線(調布⇔橋本)、高尾線(北野⇔高尾山口)など)。近くの方は見なくても分かるけれども路線図を参照。
複線区間は往と復を別々にエッジをArGraphEdgeDir.ONE_WAYで定義している。単線区間は一つのエッジをArGraphEdgeDir.TWO_WAYで定義している。
東京⇔神田間は、中央線と山手線で二重定義しているので、きちんと処理できなければならない。
JR八王子と京王八王子は、すこし離れていて歩くが、八王子として登録してあり乗換駅とした。
#閉路判定(Q07_00)
・山手線⇒閉じている
・中央線(上り＋下り) ⇒ 閉じていない
・中央線(下り)＋京王相模原線(下り) ⇒ 閉じていない
Q07_00.java
package jp.avaj.lib.algo;
import java.util.ArrayList;
import java.util.List;
import jp.avaj.lib.test.L;
/** 鉄道路線をサンプルにしたグラフ処理-閉路判定 */
public class Q07_00 {
public static void main(String[] args) {
L.p("山手線 ⇒ 閉路");
{
// 山手線の経路情報を取得する
List<ArGraphEdge<String>> edges = new ArrayList<ArGraphEdge<String>>();
edges.addAll(ArRailways.yamanote);
edges = ArList.randomize(edges); // 念のためにランダマイズする
// 閉路判定をする
L.p(""+ArGraph.closed(edges));
}
L.p("中央線(上り＋下り) ⇒ 閉路ではない");
{
List<ArGraphEdge<String>> edges = new ArrayList<ArGraphEdge<String>>();
edges.addAll(ArRailways.chuuou);
edges = ArList.randomize(edges); // 念のためにランダマイズする
// 閉路判定をする
L.p(""+ArGraph.closed(edges));
}
L.p("中央線(下り)＋京王相模原線(下り) ⇒ 閉路ではない");
{
List<ArGraphEdge<String>> edges = new ArrayList<ArGraphEdge<String>>();
edges.addAll(ArRailways.chuuouKudari);
edges.addAll(ArRailways.keioSagamiKudari);
edges = ArList.randomize(edges); // 念のためにランダマイズする
// 閉路判定をする
L.p(""+ArGraph.closed(edges));
}
}
}
Q07_00.txt
山手線 ⇒ 閉路
true
中央線(上り＋下り) ⇒ 閉路ではない
false
中央線(下り)＋京王相模原線(下り) ⇒ 閉路ではない
false
#始点・終点を求める(Q07_01)
・山手線 ⇒ 始点終点なし
・中央線(上り＋下り)＋京王相模原線(上り＋下り) ⇒ 東京(始終点)、高尾(始終点)、調布(始終点)、橋本(始終点)
・京王線(下り) ⇒ 新宿(始点)、八王子(終点)
・京王線(下り)＋小田急線上り(下北沢⇒新宿) ⇒ 下北沢(始点)、八王子(終点)、注、新宿は通過駅
・京王線(上り)＋小田急線上り(下北沢⇒新宿) ⇒ 下北沢(始点)、八王子(始点)、新宿(終点)
Q07_01.java
package jp.avaj.lib.algo;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import jp.avaj.lib.def.ArGraphEdgeDir;
import jp.avaj.lib.test.L;
/** 鉄道路線をサンプルにしたグラフ処理-始点・終点を求める */
public class Q07_01 {
public static void main(String[] args) {
Map<String, ArGraphConnection<String>> points;
L.p("山手線 ⇒ 始点終点なし");
{
List<ArGraphEdge<String>> edges = new ArrayList<ArGraphEdge<String>>();
edges.addAll(ArRailways.yamanote);
edges = ArList.randomize(edges); // 念のためランダマイズ
points = ArGraph.getStartEndPoints(edges);
L.p("始点と終点="+points.keySet().toString());
points = ArGraph.getStartPoints(edges);
L.p("始点="+points.keySet().toString());
points = ArGraph.getEndPoints(edges);
L.p("終点="+points.keySet().toString());
}
L.p("中央線(上り＋下り)＋京王相模原線(上り＋下り) ⇒ 東京(始終点)、高尾(始終点)、調布(始終点)、橋本(始終点)");
{
List<ArGraphEdge<String>> edges = new ArrayList<ArGraphEdge<String>>();
edges.addAll(ArRailways.chuuou);
edges.addAll(ArRailways.keioSagami);
edges = ArList.randomize(edges); // 念のためランダマイズ
points = ArGraph.getStartEndPoints(edges);
L.p("始点と終点="+points.keySet().toString());
points = ArGraph.getStartPoints(edges);
L.p("始点="+points.keySet().toString());
points = ArGraph.getEndPoints(edges);
L.p("終点="+points.keySet().toString());
}
L.p("京王線(下り) ⇒ 新宿(始点)、八王子(終点)");
{
List<ArGraphEdge<String>> edges = new ArrayList<ArGraphEdge<String>>();
edges.addAll(ArRailways.keioMainKudari);
edges = ArList.randomize(edges); // 念のためランダマイズ
points = ArGraph.getStartEndPoints(edges);
L.p("始点と終点="+points.keySet().toString());
points = ArGraph.getStartPoints(edges);
L.p("始点="+points.keySet().toString());
points = ArGraph.getEndPoints(edges);
L.p("終点="+points.keySet().toString());
}
L.p("京王線(下り)＋小田急線上り(下北沢⇒新宿) ⇒ 下北沢(始点)、八王子(終点)、注、新宿は通過駅");
{
List<ArGraphEdge<String>> edges = new ArrayList<ArGraphEdge<String>>();
edges.addAll(ArRailways.keioMainKudari);
edges.add(new ArGraphEdge<String>("下北沢","新宿",ArGraphEdgeDir.ONE_WAY));
edges = ArList.randomize(edges); // 念のためランダマイズ
points = ArGraph.getStartEndPoints(edges);
L.p("始点と終点="+points.keySet().toString());
points = ArGraph.getStartPoints(edges);
L.p("始点="+points.keySet().toString());
points = ArGraph.getEndPoints(edges);
L.p("終点="+points.keySet().toString());
}
L.p("京王線(上り)＋小田急線上り(下北沢⇒新宿) ⇒ 下北沢(始点)、八王子(始点)、新宿(終点)");
{
List<ArGraphEdge<String>> edges = new ArrayList<ArGraphEdge<String>>();
edges.addAll(ArRailways.keioMainNobori);
edges.add(new ArGraphEdge<String>("下北沢","新宿",ArGraphEdgeDir.ONE_WAY));
edges = ArList.randomize(edges); // 念のためランダマイズ
points = ArGraph.getStartEndPoints(edges);
L.p("始点と終点="+points.keySet().toString());
points = ArGraph.getStartPoints(edges);
L.p("始点="+points.keySet().toString());
points = ArGraph.getEndPoints(edges);
L.p("終点="+points.keySet().toString());
}
}
}
Q07_01.txt
山手線 ⇒ 始点終点なし
始点と終点=[]
始点=[]
終点=[]
中央線(上り＋下り)＋京王相模原線(上り＋下り) ⇒ 東京(始終点)、高尾(始終点)、調布(始終点)、橋本(始終点)
始点と終点=[高尾, 調布, 東京, 橋本]
始点=[高尾, 調布, 東京, 橋本]
終点=[高尾, 調布, 東京, 橋本]
京王線(下り) ⇒ 新宿(始点)、八王子(終点)
始点と終点=[新宿, 八王子]
始点=[新宿]
終点=[八王子]
京王線(下り)＋小田急線上り(下北沢⇒新宿) ⇒ 下北沢(始点)、八王子(終点)、注、新宿は通過駅
始点と終点=[下北沢, 八王子]
始点=[下北沢]
終点=[八王子]
京王線(上り)＋小田急線上り(下北沢⇒新宿) ⇒ 下北沢(始点)、八王子(始点)、新宿(終点)
始点と終点=[新宿, 下北沢, 八王子]
始点=[下北沢, 八王子]
終点=[新宿]
#非連結のグラフを分割する(Q07_02)
・山手線(外回り＋内回り) ⇒ 分割できない、山手線が戻される
・中央線(上り＋下り)＋京王相模原線(上り＋下り) ⇒ 中央線と京王相模原線に分割される
Q07_02.java
package jp.avaj.lib.algo;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import jp.avaj.lib.test.L;
/** 鉄道路線をサンプルにしたグラフ処理-非連結のグラフを分割する */
public class Q07_02 {
public static void main(String[] args) {
List<Map<String,ArGraphConnection<String>>> pointList;
//
L.p("山手線(外回り＋内回り) ⇒ 分割できない、山手線が戻される");
{
List<ArGraphEdge<String>> edges = new ArrayList<ArGraphEdge<String>>();
edges.addAll(ArRailways.yamanote);
edges = ArList.randomize(edges); // 念のためにランダマイズ
pointList = ArGraph.divide(edges);
printPointList(pointList);
}
L.p("中央線(上り＋下り)＋京王相模原線(上り＋下り) ⇒ 中央線と京王相模原線に分割される");
{
List<ArGraphEdge<String>> edges = new ArrayList<ArGraphEdge<String>>();
edges.addAll(ArRailways.chuuou);
edges.addAll(ArRailways.keioSagami);
edges = ArList.randomize(edges); // 念のためにランダマイズ
pointList = ArGraph.divide(edges);
printPointList(pointList);
}
}
private static void printPointList(List<Map<String,ArGraphConnection<String>>> pointList) {
for(Map<String,ArGraphConnection<String>> point : pointList) {
L.p(point.keySet().toString());
}
}
}
Q07_02.txt
山手線(外回り＋内回り) ⇒ 分割できない、山手線が戻される
[渋谷, 新宿, 品川, 池袋, 東京, 神田, 上野]
中央線(上り＋下り)＋京王相模原線(上り＋下り) ⇒ 中央線と京王相模原線に分割される
[国分寺, 新宿, 吉祥寺, 高尾, 四谷, 東京, 三鷹, 中野, 立川, 神田, 八王子]
[永山, 調布, 橋本]
#トポロジカルソートを行う(Q07_03)
・山手線(外回り) ⇒ ループしているのでソートできない
・中央線(上り＋下り ⇒ 上下線なのでソートできない
・中央線(下り)＋京王線(下り)＋京王相模原線(下り) ⇒ (分岐・合流があるが)ソートできる
・中央線(下り)＋京王相模原線(下り) ⇒ (離れているが)ソートできる
Q07_03.java
package jp.avaj.lib.algo;
import java.util.ArrayList;
import java.util.List;
import jp.avaj.lib.test.L;
/** 鉄道路線をサンプルにしたグラフ処理-トポロジカルソートを行う */
public class Q07_03 {
public static void main(String[] args) {
List<String> sortedList;
L.p("山手線(外回り) ⇒ ループしているのでソートできない");
{
List<ArGraphEdge<String>> edges = new ArrayList<ArGraphEdge<String>>();
edges.addAll(ArRailways.yamanoteSoto);
edges = ArList.randomize(edges); // 念のためにランダマイズ
sortedList = ArGraph.topologicalSort(edges);
L.p("sortedList="+sortedList);
}
L.p("中央線(上り＋下り ⇒ 上下線なのでソートできない");
{
List<ArGraphEdge<String>> edges = new ArrayList<ArGraphEdge<String>>();
edges.addAll(ArRailways.chuuou);
edges = ArList.randomize(edges); // 念のためにランダマイズ
sortedList = ArGraph.topologicalSort(edges);
L.p("sortedList="+sortedList);
}
L.p("中央線(下り)＋京王線(下り)＋京王相模原線(下り) ⇒ (分岐・合流があるが)ソートできる");
{
List<ArGraphEdge<String>> edges = new ArrayList<ArGraphEdge<String>>();
edges.addAll(ArRailways.chuuouKudari);
edges.addAll(ArRailways.keioMainKudari);
edges.addAll(ArRailways.keioSagamiKudari);
edges = ArList.randomize(edges); // 念のためにランダマイズ
sortedList = ArGraph.topologicalSort(edges);
L.p("sortedList="+sortedList);
}
L.p("中央線(下り)＋京王相模原線(下り) ⇒ (離れているが)ソートできる");
{
List<ArGraphEdge<String>> edges = new ArrayList<ArGraphEdge<String>>();
edges.addAll(ArRailways.chuuouKudari);
edges.addAll(ArRailways.keioSagamiKudari);
edges = ArList.randomize(edges); // 念のためにランダマイズ
sortedList = ArGraph.topologicalSort(edges);
L.p("sortedList="+sortedList);
}
}
}
Q07_03.txt
山手線(外回り) ⇒ ループしているのでソートできない
sortedList=null
中央線(上り＋下り ⇒ 上下線なのでソートできない
sortedList=null
中央線(下り)＋京王線(下り)＋京王相模原線(下り) ⇒ (分岐・合流があるが)ソートできる
sortedList=[東京, 神田, 四谷, 新宿, 中野, 明大前, 吉祥寺, 調布, 三鷹, 東府中, 永山, 国分寺, 府中, 橋本, 立川, 聖蹟, 高幡, 北野, 八王子, 高尾]
中央線(下り)＋京王相模原線(下り) ⇒ (離れているが)ソートできる
sortedList=[調布, 東京, 永山, 神田, 橋本, 四谷, 新宿, 中野, 吉祥寺, 三鷹, 国分寺, 立川, 八王子, 高尾]
#指定駅間の経路を求める(Q07_04)
・ロジックは深さ優先探索、幅優先探索は未実装。
・途中駅も指定できる。
・通過しない駅も指定できる。
・(京王線下り)・(調布⇒高幡⇒八王子) ⇒ 一直線の経路のみ
・(京王線下り)・(調布⇒高幡⇒八王子)(聖蹟を通過せず) ⇒ ルートが存在しない
・(京王線下り＋中央線下り＋高尾線)・(高幡⇒高尾) ⇒ 中央線を回るルートも取得できること
・(京王線＋中央線＋高尾線)・(高幡⇒北野⇒高尾) ⇒ 新宿を回るルートも取得できること
・(中央線＋山手線＋京王全線)・(東京⇒神田) ⇒ 八王子や高尾などを回るルートも取得できること
・(中央線＋山手線＋京王全線)・(東京⇒神田)(品川を通過せず) ⇒ 東京⇒神田のルートのみ
・(中央線＋山手線＋京王全線)・(動物園⇒聖蹟) ⇒ 東京などを回るルートも取得できること
・(中央線＋京王相模原線)・(新宿⇒橋本) ⇒ ルートが存在しない
Q07_04.java
package jp.avaj.lib.algo;
import java.util.ArrayList;
import java.util.List;
import jp.avaj.lib.test.L;
/** 鉄道路線をサンプルにしたグラフ処理-指定駅間の経路を求める */
public class Q07_04 {
public static void main(String[] args) {
L.p("(京王線下り)・(調布⇒高幡⇒八王子)");
{
List<ArGraphEdge<String>> edges = new ArrayList<ArGraphEdge<String>>();
edges.addAll(ArRailways.keioMainKudari);
edges = ArList.randomize(edges); // 念のためランダマイズ
List<List<String>> routes = ArGraph.findRoute(edges,new String[]{"調布","高幡","八王子"},null);
printRoutes(routes);
L.p("(京王線下り)・(調布⇒高幡⇒八王子)(聖蹟を通過せず) ⇒ ルートが存在しない");
routes = ArGraph.findRoute(edges,new String[]{"調布","高幡","八王子"},new String[]{"聖蹟"});
printRoutes(routes);
}
L.p("(京王線下り＋中央線下り＋京王高尾線)・(高幡⇒高尾) ⇒ 中央線を回るルートも取得できること");
{
List<ArGraphEdge<String>> edges = new ArrayList<ArGraphEdge<String>>();
edges.addAll(ArRailways.keioMainKudari);
edges.addAll(ArRailways.chuuouKudari);
edges.addAll(ArRailways.keioTakao);
edges = ArList.randomize(edges); // 念のためランダマイズ
List<List<String>> routes = ArGraph.findRoute(edges,new String[]{"高幡","高尾"},null);
printRoutes(routes);
}
L.p("(京王線＋中央線＋高尾線)・(高幡⇒北野⇒高尾) ⇒ 新宿を回るルートも取得できること");
{
List<ArGraphEdge<String>> edges = new ArrayList<ArGraphEdge<String>>();
edges.addAll(ArRailways.keioMain);
edges.addAll(ArRailways.chuuou);
edges.addAll(ArRailways.keioTakao);
edges = ArList.randomize(edges); // 念のためランダマイズ
List<List<String>> routes = ArGraph.findRoute(edges,new String[]{"高幡","北野","高尾"},null);
printRoutes(routes);
}
L.p("(中央線＋山手線＋京王全線)・(東京⇒神田) ⇒ 八王子や高尾などを回るルートも取得できること");
{
List<ArGraphEdge<String>> edges = new ArrayList<ArGraphEdge<String>>();
edges.addAll(ArRailways.keioAll);
edges.addAll(ArRailways.chuuou);
edges.addAll(ArRailways.yamanote);
edges = ArList.randomize(edges); // 念のためランダマイズ
List<List<String>> routes = ArGraph.findRoute(edges,new String[]{"東京","神田"},null);
printRoutes(routes);
L.p("(中央線＋山手線＋京王全線)・(東京⇒神田)(品川を通過せず) ⇒ 東京⇒神田のルートのみ");
routes = ArGraph.findRoute(edges,new String[]{"東京","神田"},new String[]{"品川"});
printRoutes(routes);
}
L.p("(中央線＋山手線＋京王全線)・(動物園⇒聖蹟) ⇒ 東京などを回るルートも取得できること");
{
List<ArGraphEdge<String>> edges = new ArrayList<ArGraphEdge<String>>();
edges.addAll(ArRailways.keioAll);
edges.addAll(ArRailways.chuuou);
edges.addAll(ArRailways.yamanote);
edges = ArList.randomize(edges); // 念のためランダマイズ
List<List<String>> routes = ArGraph.findRoute(edges,new String[]{"動物園","聖蹟"},null);
printRoutes(routes);
}
L.p("(中央線＋京王相模原線)・(新宿⇒橋本) ⇒ ルートが存在しない");
{
List<ArGraphEdge<String>> edges = new ArrayList<ArGraphEdge<String>>();
edges.addAll(ArRailways.chuuou);
edges.addAll(ArRailways.keioSagami);
edges = ArList.randomize(edges); // 念のためランダマイズ
List<List<String>> routes = ArGraph.findRoute(edges,new String[]{"新宿","橋本"},null);
printRoutes(routes);
}
}
private static void printRoutes(List<List<String>> routes) {
for (List<String> route : routes) {
L.p(route.toString());
}
}
}
Q07_04.txt
(京王線下り)・(調布⇒高幡⇒八王子)
[調布, 東府中, 府中, 聖蹟, 高幡, 北野, 八王子]
(京王線下り)・(調布⇒高幡⇒八王子)(聖蹟を通過せず) ⇒ ルートが存在しない
(京王線下り＋中央線下り＋京王高尾線)・(高幡⇒高尾) ⇒ 中央線を回るルートも取得できること
[高幡, 北野, めじろ台, 高尾]
[高幡, 北野, 八王子, 高尾]
(京王線＋中央線＋高尾線)・(高幡⇒北野⇒高尾) ⇒ 新宿を回るルートも取得できること
[高幡, 北野, めじろ台, 高尾]
[高幡, 北野, 八王子, 高尾]
[高幡, 聖蹟, 府中, 東府中, 調布, 明大前, 新宿, 中野, 吉祥寺, 三鷹, 国分寺, 立川, 八王子, 北野, めじろ台, 高尾]
(中央線＋山手線＋京王全線)・(東京⇒神田) ⇒ 八王子や高尾などを回るルートも取得できること
[東京, 品川, 渋谷, 新宿, 四谷, 神田]
[東京, 品川, 渋谷, 新宿, 池袋, 上野, 神田]
[東京, 品川, 渋谷, 下北沢, 明大前, 新宿, 四谷, 神田]
[東京, 品川, 渋谷, 下北沢, 明大前, 新宿, 池袋, 上野, 神田]
[東京, 品川, 渋谷, 下北沢, 明大前, 調布, 東府中, 府中, 聖蹟, 高幡, 北野, 八王子, 立川, 国分寺, 三鷹, 吉祥寺, 中野, 新宿, 四谷, 神田]
[東京, 品川, 渋谷, 下北沢, 明大前, 調布, 東府中, 府中, 聖蹟, 高幡, 北野, 八王子, 立川, 国分寺, 三鷹, 吉祥寺, 中野, 新宿, 池袋, 上野, 神田]
[東京, 品川, 渋谷, 下北沢, 明大前, 調布, 東府中, 府中, 聖蹟, 高幡, 北野, めじろ台, 高尾, 八王子, 立川, 国分寺, 三鷹, 吉祥寺, 中野, 新宿, 四谷, 神田]
[東京, 品川, 渋谷, 下北沢, 明大前, 調布, 東府中, 府中, 聖蹟, 高幡, 北野, めじろ台, 高尾, 八王子, 立川, 国分寺, 三鷹, 吉祥寺, 中野, 新宿, 池袋, 上野, 神田]
[東京, 品川, 渋谷, 下北沢, 明大前, 吉祥寺, 中野, 新宿, 四谷, 神田]
[東京, 品川, 渋谷, 下北沢, 明大前, 吉祥寺, 中野, 新宿, 池袋, 上野, 神田]
[東京, 神田]
(中央線＋山手線＋京王全線)・(東京⇒神田)(品川を通過せず) ⇒ 東京⇒神田のルートのみ
[東京, 神田]
(中央線＋山手線＋京王全線)・(動物園⇒聖蹟) ⇒ 東京などを回るルートも取得できること
[動物園, 高幡, 聖蹟]
[動物園, 高幡, 北野, 八王子, 立川, 国分寺, 三鷹, 吉祥寺, 明大前, 調布, 東府中, 府中, 聖蹟]
[動物園, 高幡, 北野, 八王子, 立川, 国分寺, 三鷹, 吉祥寺, 中野, 新宿, 明大前, 調布, 東府中, 府中, 聖蹟]
[動物園, 高幡, 北野, 八王子, 立川, 国分寺, 三鷹, 吉祥寺, 中野, 新宿, 渋谷, 下北沢, 明大前, 調布, 東府中, 府中, 聖蹟]
[動物園, 高幡, 北野, 八王子, 立川, 国分寺, 三鷹, 吉祥寺, 中野, 新宿, 池袋, 上野, 神田, 東京, 品川, 渋谷, 下北沢, 明大前, 調布, 東府中, 府中, 聖蹟]
[動物園, 高幡, 北野, 八王子, 立川, 国分寺, 三鷹, 吉祥寺, 中野, 新宿, 四谷, 神田, 東京, 品川, 渋谷, 下北沢, 明大前, 調布, 東府中, 府中, 聖蹟]
[動物園, 高幡, 北野, めじろ台, 高尾, 八王子, 立川, 国分寺, 三鷹, 吉祥寺, 明大前, 調布, 東府中, 府中, 聖蹟]
[動物園, 高幡, 北野, めじろ台, 高尾, 八王子, 立川, 国分寺, 三鷹, 吉祥寺, 中野, 新宿, 明大前, 調布, 東府中, 府中, 聖蹟]
[動物園, 高幡, 北野, めじろ台, 高尾, 八王子, 立川, 国分寺, 三鷹, 吉祥寺, 中野, 新宿, 渋谷, 下北沢, 明大前, 調布, 東府中, 府中, 聖蹟]
[動物園, 高幡, 北野, めじろ台, 高尾, 八王子, 立川, 国分寺, 三鷹, 吉祥寺, 中野, 新宿, 池袋, 上野, 神田, 東京, 品川, 渋谷, 下北沢, 明大前, 調布, 東府中, 府中, 聖蹟]
[動物園, 高幡, 北野, めじろ台, 高尾, 八王子, 立川, 国分寺, 三鷹, 吉祥寺, 中野, 新宿, 四谷, 神田, 東京, 品川, 渋谷, 下北沢, 明大前, 調布, 東府中, 府中, 聖蹟]
(中央線＋京王相模原線)・(新宿⇒橋本) ⇒ ルートが存在しない
#(参考)ロジックのソース-トポロジカルソート、指定駅間の経路
###トポロジカルソート
ArGraph.java
/** トポロジカルソートを行う.ループしている場合はnullが戻される */
public static <$Point> List<$Point> topologicalSort(Collection<ArGraphEdge<$Point>> edges) {
Map<$Point,ArGraphConnection<$Point>> pointMap = getAllPoints(edges);
Map<$Point,ArGraphConnection<$Point>> startPoints = getStartPoints(edges);
Map<$Point,ArGraphConnection<$Point>> pointInfos = getAllPoints(edges);
Map<$Point,Integer> inputCount = new HashMap<$Point,Integer>();
if (startPoints.keySet().size() == 0) { return null; }
Set<$Point> pointKeys = pointInfos.keySet();
// 各ポイントに流入してくるポイントの数を求める
for ($Point point : pointKeys) {
inputCount.put(point,pointInfos.get(point).getConnectedFrom().size());
}
List<$Point> notChecked = new ArrayList<$Point>();
// まずスタートポイントからチェックを始める
pointKeys = startPoints.keySet();
for ($Point point : pointKeys) {
notChecked.add(point);
}
List<$Point> sorted = new ArrayList<$Point>();
for (;;) {
if (notChecked.size() == 0) { break; }
$Point point = notChecked.remove(0);
// ソート済みのポイントに含まれていたらエラー⇒(間接の)ループ構造になっている..
if (sorted.contains(point)) { return null; }
// 流入ポイント数を-1 ⇒ 0以上ならば他にまだ流入ポイントがあるので後回しにする
if (ArMap.calc(inputCount,point,ArCalc.SUB,1) > 0) { continue; }
// ポイントをソート済みに追加
sorted.add(point);
// 流出ポイントを未チェックリストに入れる
ArGraphConnection<$Point> conn = pointMap.get(point);
List<$Point> connectedTo = conn.getConnectedTo();
for ($Point to : connectedTo) {
// 流出ポイントが流入ポイントにあればエラー⇒(直接の)ループ構造になっている
if (conn.getConnectedFrom().contains(to)) { return null; }
notChecked.add(to);
}
}
return sorted;
}
###指定駅間の経路
ArGraph.java
/**
* 指定ポイント間の経路を求める.
* @param pontMap ポイント情報、事前にgetAllPointsで求めること.
* @param targetPoints 通過ポイント,[0]:出発地、[n-1]:目的地
* @param nonTargets 経由しないポイント,nullならば無指定.
*/
public static <$Point> List<List<$Point>> findRoute(Collection<ArGraphEdge<$Point>> edges,$Point[] targetPoints,$Point[] nonTargets) {
Map<$Point,ArGraphConnection<$Point>> pointMap = getAllPoints(edges);
return findRoute(pointMap,targetPoints,nonTargets);
}
/**
* 指定ポイント間の経路を求める.
* @param pontMap ポイント情報、事前にgetAllPointsで求めること.
* @param targetPoints 通過ポイント,[0]:出発地、[n-1]:目的地
* @param nonTagetes 経由しないポイント,nullならば無指定.
*/
public static <$Point> List<List<$Point>> findRoute(Map<$Point,ArGraphConnection<$Point>> pointMap,$Point[] targetPoints,$Point[] nonTargets) {
List<List<$Point>> resultList = new ArrayList<List<$Point>>();
List<$Point> currentList = new ArrayList<$Point>();
currentList.add(targetPoints[0]);
findRouteRecursive(pointMap,targetPoints,nonTargets,resultList,currentList,targetPoints[0],null,1);
return resultList;
}
/**
* findRouteの実質処理
* @param pointMap 各ポイントの情報
* @oaran targetPoints 出発点、(経由点)、目的地
* @param nonTargets 経由しないポイント,nullならば無指定.
* @param resultList 求めた経路が格納される
* @param currentPointList 未チェックのポイント
* @param currentPoint チェック対象のポイント
* @param priorPoint 前のポイント
* @param targetIndex targetPoinsのインデックス(次の経由地を示す)
*/
private static <$Point> void findRouteRecursive(Map<$Point,ArGraphConnection<$Point>> pointMap,
$Point[] targetPoints,
$Point[] nonTargets,
List<List<$Point>> resultList,
List<$Point> currentPointList,
$Point currentPoint,
$Point priorPoint,
int targetIndex) {
ArGraphConnection<$Point> conn = pointMap.get(currentPoint);
List<$Point> nextPoints = conn.getConnectedTo();
// チェック対象ポイントが接続しているポイントを一つずつチェックしていく
for ($Point nextPoint : nextPoints) {
if (nextPoint.equals(priorPoint)) { continue; }
if (currentPointList.contains(nextPoint)) { continue; }
if (nonTargets != null) {
if (ArArray.contains(nonTargets,nextPoint)) { continue; }
}
// 次のポイントが経由地に一致したら..
if (nextPoint.equals(targetPoints[targetIndex])) {
currentPointList.add(nextPoint);
targetIndex++;
// 最終目的地に到着？
if (targetIndex == targetPoints.length) {
resultList.add(ArList.clone(currentPointList));
}
else {
// 次のポイントをチェックする
findRouteRecursive(pointMap,targetPoints,nonTargets,resultList,ArList.clone(currentPointList),nextPoint,currentPoint,targetIndex);
}
// 別ルートを探索するために、直前に追加したポイントを削除
currentPointList.remove(currentPointList.size()-1);
targetIndex--;
continue;
}
if (! currentPointList.contains(nextPoint)) {
currentPointList.add(nextPoint);
// 次のポイントをチェックする
findRouteRecursive(pointMap,targetPoints,nonTargets,resultList,ArList.clone(currentPointList),nextPoint,currentPoint,targetIndex);
// 別ルートを探索するために、直前に追加したポイントを削除
currentPointList.remove(currentPointList.size()-1);
continue;
}
else {
// 次ポイントがすでにチェック対象ポイントにあれば、後でチェックする
}
}
}