Java Gold SE 11の学習にて、自分がわからなかったポイントです。 Comaprableによる比較とComparatorによる比較を、サンプルコードで見比べてみます。 Comparableによる比較 Comparableによる比較により自オブジェクトを比較することができます。 compareTo()メソッドは比較対象のオブジェクト自身が実装します。 並び順のルールは1つのみ設定することができます。 Nike.java import java.util.*; public class Nike implements Comparable<Nike> { private int id; private String maker; private String type; // コンストラクタ public Nike(int id, String maker, String type) { this.id = id; this.maker = maker; this.type = type; } /** * @return the id */ public int getId() { return this.id; } /** * @return the maker */ public String getMaker() { return this.maker; } /** * @return the type */ public String getType() { return this.type; } @Override public int compareTo(Nike nike) { // 1. idで並び替え // Integerクラスのcompare()メソッドを利用 return Integer.compare(this.id, nike.getId()); } public String toString() { return "id: " + this.getId() + ", " + "maker: " + this.getMaker() + ", " + "type: " + this.getType(); } public static void main(String[] args) { Nike nike1 = new Nike(2, "NIKE", "Air Force 1"); Nike nike2 = new Nike(3, "NIKE", "Zoom"); Nike nike3 = new Nike(1, "NIKE", "Air Max"); List<Nike> list = Arrays.asList(nike1, nike2, nike3); // a. System.out.println("a."); System.out.println(""); for (Nike nike : list) { System.out.println("ソート前： " + "id: " + nike.getId() + ", " + "maker: " + nike.getMaker() + ", " + "type: " + nike.getType()); } // Collectionsクラスのsort​(List<T> list)メソッドを利用 Collections.sort(list); System.out.println(""); for (Nike nike : list) { System.out.println("ソート後： " + "id: " + nike.getId() + ", " + "maker: " + nike.getMaker() + ", " + "type: " + nike.getType()); } } } a. ソート前： id: 2, maker: NIKE, type: Air Force 1 ソート前： id: 3, maker: NIKE, type: Zoom ソート前： id: 1, maker: NIKE, type: Air Max ソート後： id: 1, maker: NIKE, type: Air Max ソート後： id: 2, maker: NIKE, type: Air Force 1 ソート後： id: 3, maker: NIKE, type: Zoom 並び順について、idでの並べ替えは以下のコードでも同じ結果が得られます。 Nike.java @Override public int compareTo(Nike nike) { // 1. idで並び替え return this.id - nike.getId(); } また、並び順はid以外のフィールドを用いて定義することも可能です。 Nike.java @Override public int compareTo(Nike nike) { // 2. makerで並び替え // StringクラスのcompareTo()メソッドを利用 return this.maker.compareTo(nike.getMaker()); } @Override public int compareTo(Nike nike) { // 3. typeで並び替え // StringクラスのcompareTo()メソッドを利用 return this.type.compareTo(nike.getType()); } Comparatorによる比較 Comparatorによる比較により2つのオブジェクトを比較することができます。 並び順のルールはComparatorインターフェースを継承したクラスを作成して定義します。 並び順のルールは複数設定することができます。 Nike2.java import java.util.*; public class Nike2 { private int id; private String maker; private String type; public Nike2(int id, String maker, String type) { this.id = id; this.maker = maker; this.type = type; } /** * @return the id */ public int getId() { return this.id; } /** * @return the maker */ public String getMaker() { return this.maker; } /** * @return the type */ public String getType() { return this.type; } public String toString() { return "id: " + this.getId() + ", " + "maker: " + this.getMaker() + ", " + "type: " + this.getType(); } public static void main(String[] args) { Nike2 nike1 = new Nike2(2, "NIKE", "Air Force 1"); Nike2 nike2 = new Nike2(3, "NIKE", "Zoom"); Nike2 nike3 = new Nike2(1, "NIKE", "Air Max"); List<Nike2> list = Arrays.asList(nike1, nike2, nike3); // a. System.out.println("a."); System.out.println(""); for (Nike2 nike : list) { System.out.println("ソート前： " + "id: " + nike.getId() + ", " + "maker: " + nike.getMaker() + ", " + "type: " + nike.getType()); } // Listインターフェースのsort​(Comparator<? super E> c)メソッドを利用 list.sort(new IdComparator()); System.out.println(""); for (Nike2 nike : list) { System.out.println("ソート後： " + "id: " + nike.getId() + ", " + "maker: " + nike.getMaker() + ", " + "type: " + nike.getType()); } System.out.println(""); // b. TreeSetを使用 System.out.println("b."); System.out.println(""); Set<Nike2> set = new TreeSet<>(); set.add(new Nike2(2, "NIKE", "Air Force 1")); set.add(new Nike2(3, "NIKE", "Zoom")); set.add(new Nike2(1, "NIKE", "Air Max")); System.out.println("TreeSet: " + set); } } IdComparator.java import java.util.Comparator; public class IdComparator implements Comparator<Nike2> { // 昇順 @Override public int compare(Nike2 nike, Nike2 nike2) { if (nike.getId() > nike2.getId()) { return 1; } else if (nike.getId() < nike2.getId()) { return -1; } else { return 0; } } } a. ソート前： id: 2, maker: NIKE, type: Air Force 1 ソート前： id: 3, maker: NIKE, type: Zoom ソート前： id: 1, maker: NIKE, type: Air Max ソート後： id: 1, maker: NIKE, type: Air Max ソート後： id: 2, maker: NIKE, type: Air Force 1 ソート後： id: 3, maker: NIKE, type: Zoom b. TreeSet: [id: 1, maker: NIKE, type: Air Max, id: 2, maker: NIKE, type: Air Force 1, id: 3, maker: NIKE, type: Zoom] b. に記載したTreeSetを用いることで、自然順序で並び替えてくれます。 TreeSetの定義情報を参照すると以下のように記載されています。 TreeSet.java // more code... /** * Constructs a new, empty tree set, sorted according to the * natural ordering of its elements. // more code... */ // more code... TreeSetのTreeSet​(Comparator<? super E> comparator)コンストラクタを用いることで、Comparatorを継承して作成した並び順の定義どおりに並べ替えをすることができます。 例えば、idの降順に並べ替えたいときは以下のように記述します。 IdComaprator.java import java.util.Comparator; public class IdComparator implements Comparator<Nike2> { // 降順 @Override public int compare(Nike2 nike, Nike2 nike2) { if (nike.getId() > nike2.getId()) { return -1; } else if (nike.getId() < nike2.getId()) { return 1; } else { return 0; } } } a. ソート前： id: 2, maker: NIKE, type: Air Force 1 ソート前： id: 3, maker: NIKE, type: Zoom ソート前： id: 1, maker: NIKE, type: Air Max ソート後： id: 3, maker: NIKE, type: Zoom ソート後： id: 2, maker: NIKE, type: Air Force 1 ソート後： id: 1, maker: NIKE, type: Air Max b. TreeSet: [id: 3, maker: NIKE, type: Zoom, id: 2, maker: NIKE, type: Air Force 1, id: 1, maker: NIKE, type: Air Max] 以上となります。

SpringBoot環境構築 はじめに SpringBootでWebアプリケーションを作ってみたかったので公式リファレンスを見ながら環境構築をやっていきます。 自分の記録用なので環境構築をしたい方は公式リファレンスを見ながらやったほうがいいと思います。。 ちなみにJavaでフレームワークを使うのは初めて。サーブレットとJSPで簡単なものを作ったことあるぐらいのレベル。 開発環境 mac osx 10.15.7 java 16.0.1 maven 3.8.2 インストールの説明割愛。 Spring Boot CLIのインストール Homebrewを使用してるので以下でインストールしました。 $ brew tap spring-io/tap $ brew install spring-boot POMの作成 VScodeを開きディレクトリを作成、そこにpom.xmlを作成。 pom.xml <?xml version="1.0" encoding="UTF-8"?> <project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 https://maven.apache.org/xsd/maven-4.0.0.xsd"> <modelVersion>4.0.0</modelVersion> <groupId>com.example</groupId> <artifactId>myproject</artifactId> <version>0.0.1-SNAPSHOT</version> <parent> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-parent</artifactId> <version>2.4.5</version> </parent> <dependencies> <dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-web</artifactId> </dependency> </dependencies> <build> <plugins> <plugin> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-maven-plugin</artifactId> </plugin> </plugins> </build> <description/> <developers> <developer/> </developers> <licenses> <license/> </licenses> <scm> <url/> </scm> <url/> <!-- Additional lines to be added here... --> </project> pom.xmlはMavenコマンドを実行する際にプロジェクトを管理するビルドファイル。 (POMはProject Object Modelの略) コードの作成 Mavenはsrc/main/javaからソースをコンパイルを行う。 したがって以下のファイルをsrc/main/java/Example.javaに作成した。 Example.java import org.springframework.boot.*; import org.springframework.boot.autoconfigure.*; import org.springframework.web.bind.annotation.*; @RestController @EnableAutoConfiguration public class Example { @RequestMapping("/") String home() { return "Hello World!"; } public static void main(String[] args) { SpringApplication.run(Example.class, args); } } @EnableAutoConfigurationがよくわかりませんでした。 mainメソッドは、引数にExample.classとargs配列を渡して、SpringApplicationクラスのrunメソッドを呼び出してます。 これにより自動構成されたTomcatWebサーバが起動するそうです。 実行 以下を実行 $ mvn spring-boot:run http://localhost:8080/ にアクセスしてHello World!と表示されればOK よくわからんかった @EnableAutoConfiguration アノテーション jarの依存関係とか

概要 最近QuarkusというJavaフレームワークの存在を知りました。 Quarkus は、Java 仮想マシン (JVM) およびネイティブコンパイルのために作成されたフルスタックの Kubernetes ネイティブ Java フレームワークで、Java をコンテナに最適化し、サーバーレス、クラウド、Kubernetes の各環境で効果的なプラットフォームとして使用できるようにします。 https://www.redhat.com/ja/topics/cloud-native-apps/what-is-quarkus だそうです。 KubernetesネイティブなJavaフレームワークということで、マイクロサービスが流行りつつある今、個人的には将来性のあるフレームワークなのかな、と思っています。 特徴や詳しい使い方は他の方に任せます。（ こちらの記事では、Quarkusのサイトで紹介されているredis-clientを使ったサンプルアプリケーションの作り方をまとめました。 Redisと接続してCRUDを行うRESTful APIアプリケーションです。 ↓のページに記載されている内容を、私の方でいくつか加（減）筆したものになります。 https://quarkus.io/guides/redis 手順 Maven Projectを作る quickに新規でQuarkusプロジェクトを新規で作成するのであれば、以下のコマンドを実行するだけです。 -DprojectGroupIdや-DprojectArtifactIdはお好みで変更してください。 mvn io.quarkus:quarkus-maven-plugin:1.13.4.Final:create \ -DprojectGroupId=org.acme \ -DprojectArtifactId=redis-quickstart \ -Dextensions="redis-client,resteasy-jackson,resteasy-mutiny" \ -DnoExamples cd redis-quickstart ※Quarkusのバージョン1.13.4時点では、3.6.2以降のバージョンのmavenが必要です。 -Dextensionsで、Quarkus+Redisなアプリケーションを実装するのに必要なライブラリが指定されています。 redis-client: Redisのクライアントライブラリです。 resteasy-jackson, resteasy-mutiny: REST APIを作るのに必要なライブラリです。 既に作成されているMavenプロジェクトにライブラリを追加する場合は、以下のコマンドを実行するか、 ./mvnw quarkus:add-extension -Dextensions="redis-client" pom.xmlに以下を追記してください。 pom.xml <dependency> <groupId>io.quarkus</groupId> <artifactId>quarkus-redis-client</artifactId> </dependency> Redisサーバを用意する Redisサーバを用意されていない方は、DockerでRedisコンテナを用意しておきましょう。 docker run --ulimit memlock=-1:-1 -it --rm=true --memory-swappiness=0 --name redis_quarkus_test -p 6379:6379 redis:5.0.6 アプリケーションの作成 ここからソースコードを触っていきます。 事前に下記コマンドで必要なディレクトリを作成しておきます。 # redis-quickstart配下で mkdir -p src/{main,test}/java/org/acme/redis/ application.properties application.propertiesにRedisサーバのURLを記述します。 quarkus.redis.hosts=redis://localhost:6379 POJO ソースコードの解説は時間があるときにやります（やらないとは言っていない…言ってない！） src/main/java/org/acme/redis/Increment.java package org.acme.redis; public class Increment { public String key; public int value; public Increment(String key, int value) { this.key = key; this.value = value; } public Increment() { } } Service src/main/java/org/acme/redis/IncrementService.java package org.acme.redis; import io.quarkus.redis.client.RedisClient; import io.quarkus.redis.client.reactive.ReactiveRedisClient; import io.smallrye.mutiny.Uni; import io.vertx.mutiny.redis.client.Response; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import javax.inject.Inject; import javax.inject.Singleton; @Singleton class IncrementService { @Inject RedisClient redisClient; @Inject ReactiveRedisClient reactiveRedisClient; Uni<Void> del(String key) { return reactiveRedisClient.del(Arrays.asList(key)) .map(response -> null); } String get(String key) { return redisClient.get(key).toString(); } void set(String key, Integer value) { redisClient.set(Arrays.asList(key, value.toString())); } void increment(String key, Integer incrementBy) { redisClient.incrby(key, incrementBy.toString()); } Uni<List<String>> keys() { return reactiveRedisClient .keys("*") .map(response -> { List<String> result = new ArrayList<>(); for (Response r : response) { result.add(r.toString()); } return result; }); } } Resource src/main/java/org/acme/redis/IncrementResource.java package org.acme.redis; import javax.inject.Inject; import javax.ws.rs.GET; import javax.ws.rs.PathParam; import javax.ws.rs.PUT; import javax.ws.rs.Path; import javax.ws.rs.POST; import javax.ws.rs.DELETE; import java.util.List; import io.smallrye.mutiny.Uni; @Path("/increments") public class IncrementResource { @Inject IncrementService service; @GET public Uni<List<String>> keys() { return service.keys(); } @POST public Increment create(Increment increment) { service.set(increment.key, increment.value); return increment; } @GET @Path("/{key}") public Increment get(@PathParam("key") String key) { return new Increment(key, Integer.valueOf(service.get(key))); } @PUT @Path("/{key}") public void increment(@PathParam("key") String key, Integer value) { service.increment(key, value); } @DELETE @Path("/{key}") public Uni<Void> delete(@PathParam("key") String key) { return service.del(key); } } Test こちらはオプショナルです。 src/test/java/org/acme/redis/IncrementResourceTest.java package org.acme.redis; import static org.hamcrest.Matchers.is; import org.junit.jupiter.api.Test; import io.quarkus.test.junit.QuarkusTest; import static io.restassured.RestAssured.given; import io.restassured.http.ContentType; @QuarkusTest public class IncrementResourceTest { @Test public void testRedisOperations() { // verify that we have nothing given() .accept(ContentType.JSON) .when() .get("/increments") .then() .statusCode(200) .body("size()", is(0)); // create a first increment key with an initial value of 0 given() .contentType(ContentType.JSON) .accept(ContentType.JSON) .body("{\"key\":\"first-key\",\"value\":0}") .when() .post("/increments") .then() .statusCode(200) .body("key", is("first-key")) .body("value", is(0)); // create a second increment key with an initial value of 10 given() .contentType(ContentType.JSON) .accept(ContentType.JSON) .body("{\"key\":\"second-key\",\"value\":10}") .when() .post("/increments") .then() .statusCode(200) .body("key", is("second-key")) .body("value", is(10)); // increment first key by 1 given() .contentType(ContentType.JSON) .body("1") .when() .put("/increments/first-key") .then() .statusCode(204); // verify that key has been incremented given() .accept(ContentType.JSON) .when() .get("/increments/first-key") .then() .statusCode(200) .body("key", is("first-key")) .body("value", is(1)); // increment second key by 1000 given() .contentType(ContentType.JSON) .body("1000") .when() .put("/increments/second-key") .then() .statusCode(204); // verify that key has been incremented given() .accept(ContentType.JSON) .when() .get("/increments/second-key") .then() .statusCode(200) .body("key", is("second-key")) .body("value", is(1010)); // verify that we have two keys in registered given() .accept(ContentType.JSON) .when() .get("/increments") .then() .statusCode(200) .body("size()", is(2)); // delete first key given() .accept(ContentType.JSON) .when() .delete("/increments/first-key") .then() .statusCode(204); // verify that we have one key left after deletion given() .accept(ContentType.JSON) .when() .get("/increments") .then() .statusCode(200) .body("size()", is(1)); // delete second key given() .accept(ContentType.JSON) .when() .delete("/increments/second-key") .then() .statusCode(204); // verify that there is no key left given() .accept(ContentType.JSON) .when() .get("/increments") .then() .statusCode(200) .body("size()", is(0)); } } ※手順に従って進めていましたが、私の場合はio.hamcrestとio.restassuredのライブラリが見つからず、エラーとなりました。 エラーが発生した場合は、以下をpom.xmlに追加してください。 pom.xml <dependency> <groupId>org.hamcrest</groupId> <artifactId>hamcrest</artifactId> <version>2.1</version> <scope>test</scope> </dependency> <dependency> <groupId>io.rest-assured</groupId> <artifactId>rest-assured</artifactId> <version>3.0.0</version> <scope>test</scope> <dependency> ソースコードの編集は以上です。 アプリケーションを動かしてみる 下記コマンドでアプリケーションを動かしてみましょう。 ./mvnw quarkus:dev 起動すると、下記のようなログがコンソールに表示されます。（1.3秒くらいで起動できてますね。） 作成したアプリケーションを試してみる 起動が完了すると8080ポートをListenするので、curlコマンドで/incrementsにPOSTしてみましょう。 curl -X POST -H "Content-Type: application/json" -d '{"key":"first","value":10}' http://localhost:8080/increments # -> {"key":"first","value":10} /incrementsをGETすると、登録したキーのリストが返ってきます。 curl http://localhost:8080/increments # -> ["first"] キーを指定してGETをすれば、key-valueがJsonで返却されます。 curl http://localhost:8080/increments/first # -> {"key":"first","value":10} 念のため、Redisサーバにアクセスしてレコードを確認してみます。 docker exec -it redis_quarkus_test redis-cli 127.0.0.1:6379> keys * # -> 1) "first" 127.0.0.1:6379> get first # -> "10" ちゃんと登録されてますね。 PUTをすると、指定したキーの値を指定した分だけ増加させます。 curl -X PUT -H "Content-Type: application/json" -d '27' http://localhost:8080/increments/first curl http://localhost:8080/increments/first # -> {"key":"first","value":37} DELETEをすると、Redisからレコードを削除します。 curl -X DELETE http://localhost:8080/increments/first curl http://localhost:8080/increments # -> [] ※リクエストで指定されたキーがRedisサーバにないときのエラーハンドリングはしていないので、キー指定が間違っていると例外が発生します。 curl http://localhost:8080/increments/second # -> java.lang.NullPointerException: Cannot invoke "io.vertx.redis.client.Response.toString()" because the return value of "io.quarkus.redis.client.RedisClient.get(String)" is null mvnパッケージングと実行 JVMで動かす場合 # パッケージング ./mvnw package # 起動 java -jar target/quarkus-app/quarkus-run.jar Nativeで動かす場合 Quarkusを使う利点の１つである、ネイティブコンパイルを行い起動する方法です。 こちらの方法によるパッケージングには少々時間がかかります。（Intel Corei7-10710uで2分半程度。PCがめっちゃ熱くなりました。） # パッケージング ./mvnw package -Pnative # 起動 ./target/redis-quickstart-1.0.0-SNAPSHOT-runner その他の操作 こちらのページでは、上述の手順以外に下記のような手順が掲載されています。 コネクションのヘルスチェック 複数Redisクライアント コンフィグレーション 工事中

困ったこと MapperのSQLをXMLに記載するとき、不等号（大なり、小なり　など）を使用すると、 「要素のコンテンツは、整形式の文字データまたはマークアップから成るものでなければなりません。」 のエラーになってしまう。 解決方法 <![CDATA[と]]>で囲むと良い. 以下の2つがあるが、1がおすすめ。 1. 該当箇所を囲む <select id="methodName" parameterType="EntityClass" resultType="Integer"> SELECT id FROM test WHERE <![CDATA[ start_date <= NOW() and end_date > NOW() ]]> </select> 2. SQL文全体を囲む この方が可読性が良いが、動的SQLを記載しても反映されない。 <select id="methodName" parameterType="EntityClass" resultType="Integer"> <![CDATA[ SELECT id FROM test WHERE start_date <= NOW() and end_date > NOW()) ]]> </select>

Javaで配列とリスト配列で配列の要素を数える方法が違います。 配列の場合は public class Main{ public static void main(String[] args){ String[] data = {"test1","test2","test3"}; for(int i=0;i<data.length;i++){ System.out.println(data[i]); } } } に対し、リスト配列では import java.util.*; public class Main{ public static void main(String[] args){ ArrayList<String> data = new ArrayList<String>(); data.add("test1"); data.add("test2"); data.add("test3"); for (int i=0;i<data.size();i++){ System.out.println(data.get(i)); } } } になります。配列ではlengthメソッドに対し、リスト配列ではsize関数になります。

関数を評価した後の値が欲しい Apache POIでセルの値を取得する際、「セルに関数が含まれている場合は関数を評価した後の値が欲しい」とします。書き方はいろいろあるのですが、おおよそ以下のようにすればよいです。 // WorkBookオブジェクトからFormulaEvaluatorを生成する。 FormulaEvaluator formulaEvaluator = book.getCreationHelper().createFormulaEvaluator(); // CellのCellTypeを取得する。Cellが関数を含む場合は関数の評価後のCellTypeを取得する。 CellType cellType = (cell.getCellType() == CellType.FORMULA) ? formulaEvaluator.evaluateFormulaCell(cell) : cell.getCellType(); // CellTypeにあわせて値を取得する。ここではサンプルとして文字列型を取得している。 if (cellType == CellType.STRING) { String stringCellValue = cell.getStringCellValue(); doSomething(stringCellValue); } 関数を評価する前の値が欲しい / 関数そのものが欲しい 上とは違って、セルに含まれている関数そのものが欲しい場合は、Cell::getCellFormulaを利用します。 if (cell.getCellType() == CellType.FORMULA) { String cellFormula = cell.getCellFormula(); doSomething(cellFormula); } 動作確認環境 (pom.xmlより抜粋) <!-- https://mvnrepository.com/artifact/org.apache.poi/poi --> <dependency> <groupId>org.apache.poi</groupId> <artifactId>poi</artifactId> <version>5.0.0</version> </dependency> <!-- https://mvnrepository.com/artifact/org.apache.poi/poi-ooxml --> <dependency> <groupId>org.apache.poi</groupId> <artifactId>poi-ooxml</artifactId> <version>5.0.0</version> </dependency>

目次 I部 準備 spigotプラグインを作る (1) II部 絶賛執筆中!!

すごいお久しぶりです。beatbox4108です。 今回からは、spigotプラグインの作り方をやっていきたいと思います。 まずspigotって? spigotは、minecraftのサーバーです。 もともとは、bukkitというものが主流でしたが、現在はbukkitとの互換性があるspigotが主流です。 bukkitやspigotはプラグインというものを導入して、minecraftの機能を追加したり変更したりできます。 プラグインでできること/できないこと 機能 できるかどうか UIの追加 X ブロックの追加 X AIの変更 O UIの表示、機能追加 O Javaとの連携 O 上に挙げたのはほんの少しで、他にもいろいろな機能があります。 思いつかなかったなんて言えない 実際にやってみる 前提条件 IntelliJ IDEAがインストールされている。 JDKがインストールされている 筆者の環境 OS---linux mint 20.1 64bit Java---openjdk 11.0.9.1/OpenJDK Runtime Environment (build 11.0.9.1+1-Ubuntu-0ubuntu1.20.04)/OpenJDK 64-Bit Server VM (build 11.0.9.1+1-Ubuntu-0ubuntu1.20.04, mixed mode) IntelliJ IDEA のプラグインを導入 IntelliJの、Minecraftプラグインを導入します。もう入っているなら、適当に読み飛ばしてください IntelliJを起動したら、下の画像に示した四角の部分=プラグインをクリックしてください。 次に、赤の検索バーにminecraftと入力し、緑の部分がMinecraft Devとなっているのを確認したら、青のインストールを押してください。次に出てくるダイアログでは、同意しますを押してください インストールが完了したら、サイドバーのプロジェクト(赤で示した部分)を押して、新規プロジェクト(青で示した部分)を押してください。 赤枠で示したMinecraftを押し、青枠で示したSpigotPluginを押して、次へ進みます。 赤枠を自由に設定し、青枠をMavenからGradleに変更します。 画面が変わったら、今度は好きなように設定してください。 設定項目と、意味、内容を表に示しました。 項目 内容、意味 Plugin Name その名の通り、プラグインの名前です。半角英数字のみでお願いします。 Main Class Name メインクラスの名前を設定します。よくドメイン名を反対にした名前が用いられます。例:com.beatbox4108.tutorial MinecraftVersion 開発するバージョンを指定します。ここでは1.16.5で進めます。 Description 名前の通り説明です。 Authors 作成者です。複数人いる場合は、,で区切ります。 Website サイトのURLです。多分任意 Log Prefix ログに使う接頭辞です。空にすると、プラグイン名が使われるようです。 Load at プラグインが読み込まれるタイミングを設定します。Post Worldは、ワールド読み込み後、Startupは、サーバー起動後=ワールド読み込み前です。 Load Before プラグイン名を指定します。指定したプラグインより先に読み込むように設定できます。複数ある場合は,で区切ります。 Depend 依存するプラグインを指定します。ここで指定したプラグインはこのプラグインより先に読み込まれます。 Soft Depend 依存するプラグインを指定します。Dependとの違いは、指定したプラグインが導入されていなくても、エラーが発生しません。 赤枠で示したところを入力します。好きなように入れてください。青枠で示したところを押せば、保存場所を選択できます。 完了です! お疲れ様です。次回はいよいよコードを書いていきたいと思います。 目次 前回 今回 次回

最新バージョンのJDKをmacにインストールする流れでハマったので忘れないようにメモ 環境 Mac Os catalina 10.15.7 概要 ※調べるとcaskを使う記事が複数でてきましたが使わなくてよかったので以下で実施 % brew install java ==> Downloading https://ghcr.io/v2/homebrew/core/openjdk/manifests/15.0.2 ######################################################################## 100.0% ==> Downloading https://ghcr.io/v2/homebrew/core/openjdk/blobs/sha256:fca110fb6caad1228156b587a3ca9fa9ab5a ==> Downloading from https://pkg-containers.githubusercontent.com/ghcr1/blobs/sha256:fca110fb6caad1228156b ######################################################################## 100.0% ==> Pouring openjdk--15.0.2.catalina.bottle.tar.gz ==> Caveats For the system Java wrappers to find this JDK, symlink it with sudo ln -sfn /usr/local/opt/openjdk/libexec/openjdk.jdk /Library/Java/JavaVirtualMachines/openjdk.jdk openjdk is keg-only, which means it was not symlinked into /usr/local, because macOS provides similar software and installing this software in parallel can cause all kinds of trouble. If you need to have openjdk first in your PATH, run: echo 'export PATH="/usr/local/opt/openjdk/bin:$PATH"' >> ~/.zshrc For compilers to find openjdk you may need to set: export CPPFLAGS="-I/usr/local/opt/openjdk/include" ==> Summary ? /usr/local/Cellar/openjdk/15.0.2: 614 files, 324.9MB よく見ると上記の文章内に全部記載されているんですが、、、 インストールされたか確認してみると以下 % java --version No Java runtime present, requesting install. どないなっとんねんと思いましたが、シンボリックリンクを貼って解消（インストール時のログにも出てますね） % sudo ln -sfn $(brew --prefix)/opt/openjdk/libexec/openjdk.jdk /Library/Java/JavaVirtualMachines/openjdk.jdk 再度確認すると問題なくjavaのバージョンが確認できました。 % java --version openjdk 15.0.2 2021-01-19 OpenJDK Runtime Environment (build 15.0.2+7) OpenJDK 64-Bit Server VM (build 15.0.2+7, mixed mode, sharing)

SpringとMySQLを利用したREST API作成メモ API例 以下のようなユーザー情報の登録、取得、一覧取得用APIを作成する。 ユーザー登録API(POST /api/users) リクエスト POST /api/users HTTP/1.1 Host: localhost:8080 Content-Type: application/json Content-Length: 24 { "name":"test4" } レスポンス { "id": 4, "name": "test4" } ユーザー取得API(GET /api/users/{user_id}) リクエスト GET /api/users/4 HTTP/1.1 Host: localhost:8080 Content-Type: application/json レスポンス { "id": 4, "name": "test4" } ユーザー一覧取得API (GET /api/users) リクエスト GET /api/users HTTP/1.1 Host: localhost:8080 Content-Type: application/json レスポンス [ { "id": 1, "name": "test" }, { "id": 2, "name": "test2" }, { "id": 3, "name": "test3" }, { "id": 4, "name": "test4" } ] 接続用MySQL DB構築 こちらの手順でMySQLコンテナを立ち上げる。 以下のSQLusersテーブルを作成する。 CREATE TABLE `sample_db`.`users` ( `id` BIGINT NOT NULL AUTO_INCREMENT, `name` VARCHAR(45) NULL, PRIMARY KEY (`id`), UNIQUE INDEX `id_UNIQUE` (`id` ASC)); API 実装 Application層 Controller (UserController) リクエストを受け付け、ドメイン層UserRepositoryを呼び出す。 package com.example.restservice.controller; import java.util.List; import org.springframework.beans.factory.annotation.Autowired; import org.springframework.validation.annotation.Validated; import org.springframework.web.bind.annotation.GetMapping; import org.springframework.web.bind.annotation.PathVariable; import org.springframework.web.bind.annotation.PostMapping; import org.springframework.web.bind.annotation.RequestBody; import org.springframework.web.bind.annotation.RequestMapping; import org.springframework.web.bind.annotation.RestController; import com.example.restservice.exception.NotFoundException; import com.example.restservice.model.User; import com.example.restservice.repository.UserRepository; // Controller @RestController @RequestMapping("/api") public class UserController { @Autowired UserRepository UserRepository; @GetMapping("/users") public List<User> getAllUsers() { return UserRepository.findAll(); } @PostMapping("/users") public User createUser(@Validated @RequestBody User User) { return UserRepository.save(User); } @GetMapping("/users/{id}") public User getUserById(@PathVariable(value = "id") Integer UserId) { return UserRepository.findById(UserId) .orElseThrow(() -> new NotFoundException("User", "id", UserId)); } } Domain層 Respository Interface(UserRepository) データ操作を担う。 package com.example.restservice.repository; import java.util.List; import org.springframework.data.jpa.repository.JpaRepository; import org.springframework.stereotype.Repository; import com.example.restservice.model.User; // Repository Interface @Repository public interface UserRepository extends JpaRepository<User, Integer> { } Infrastructure層 Entity(User) package com.example.restservice.model; import javax.persistence.Column; import javax.persistence.Entity; import javax.persistence.GeneratedValue; import javax.persistence.GenerationType; import javax.persistence.Id; import javax.persistence.Table; import lombok.Data; @Entity @Data @Table(name = "users") public class User { @Id @Column(name = "id") @GeneratedValue(strategy=GenerationType.IDENTITY) private int id; @Column(name = "name") private String name; } 例外(NotFoundException) 取得API実行時にスローする例外 package com.example.restservice.exception; import org.springframework.http.HttpStatus; import org.springframework.web.bind.annotation.ResponseStatus; @ResponseStatus(value = HttpStatus.NOT_FOUND) public class NotFoundException extends RuntimeException { private String resourceName; private String fieldName; private Object fieldValue; public NotFoundException( String resourceName, String fieldName, Object fieldValue) { super(String.format("%s not found with %s : '%s'", resourceName, fieldName, fieldValue)); this.resourceName = resourceName; this.fieldName = fieldName; this.fieldValue = fieldValue; } public String getResourceName() { return resourceName; } public String getFieldName() { return fieldName; } public Object getFieldValue() { return fieldValue; } } DB接続設定 src/main/resources/application.propertiesに以下を記述する。 spring.datasource.url=jdbc:mysql://localhost:3306/sample_db spring.datasource.username=mysqluser spring.datasource.password=mysqlpass spring.datasource.driver-class-name=com.mysql.cj.jdbc.Driver 動作確認 上記のAPI例のリクエストを投げ、レスポンスを受信できることを確認する。 参考情報 Spring Bootで実装するWebAPIのアーキテクチャを考える callicoder/spring-boot-mysql-rest-api-tutorial

2021年3月から毎日問題が公開されている「競プロ典型90問」、皆さま解いていらっしゃいますでしょうか？ 一昨日、第40問として公開された「Get More Money」が解説を読み、その後いろいろな記事を見ても理解が難しかったので整理してみました。 当然のことながらこの問題の解法に触れますので、問題に挑戦したい方はこの記事は後からお読みいただくことをお勧めします。 AtCoder常設ジャッジ 問題画像 公式解説 何が理解できなかったのか 公式解説にもある通り、この問題はいわゆる「燃やす埋める問題」というタイプの問題です。公式解説は紙面の都合もあって要点を絞って書かれているので、ほとんど予備知識がなかった筆者の場合はあまり腹落ちしませんでした。そこで「燃やす埋める問題」というキーワードを元にググってみて記事を色々と読んだのですが、どうもこの問題を解くやり方はいくつかパターンがあるようで、書いてある記事によってパターンが違ってなかなか理解が追いつきませんでした。 最終的に、以下の記事にある3パターンあるようだったので、それぞれ今回の問題に当てはめてみるとどうなるかを整理して理解を深めてみました。 最小カットを使って「燃やす埋める」問題を解くスライドのフォロー(診断人氏ブログ) 筆者と同じように、ネット上の記事をいろいろ読んで混乱した方は本記事に一度目を通してから読み直すと、頭の中が整理しやすくなるのではないかと思っています。 燃やす埋める問題とは 燃やす埋める問題とは以下のような問題です。 $N$個の品物があり、それぞれの物を「燃やす」か「埋める」必要がある 品物$i$を燃やすのに$x_i(\ge 0)$円、埋めるのに$y_i(\ge 0)$円かかる また、以下の形式のルールが$M$個ある ・品物$a_j$を燃やして品物$b_j$を埋めると、罰金$c_j(\ge 0)$円かかる 最小で何円必要か 品物を処分するコストを最小化する問題のようです。 今回の典型90問の問題は以下のような問題でした。 $\ $AtCoder共和国には$N$軒の家があり、$1$から$N$までの番号が付けられています。 はじめ、家$i$の中には、現金$A_i$円と、$k_i$本の鍵（それぞれ家$c_{i,1},c_{i,2},…,c_{i,k_i}$の鍵）が置いてあり、家に入ることでこれらを回収できます。 ただし、任意の$j$ $(1\le j\le k_i)$に対して$c_{i,j}\gt i$ が保証されます。 また、家$i$に入るためには、以下の2つのことをする必要があります。 ・AtCoder共和国の中に家$i$の鍵があれば、それらをすべて回収した状態にする ・料金$W$円を支払う あなたはAtCoder共和国の家にある現金を集めることで、できるだけ多くの金額を得ようと考えています。家に入る手順をうまく決めたときに、最大で何円得するかを求めてください。 すなわち、家に入って回収した金額を$I$円、家に入るために支払った料金を$O$円として、$I−O$の最大値を求めてください。 ただし、家に入るための費用は必要ならいつでも支払えるものとします。 $\ $この問題は、予め各家から現金$A_i$円を回収しておいて、訪れないことにした家には$A_i$円返金する(支払う)と解釈することで、以下のように言い換えられます。 $N$件の家があり、それぞれの家を「訪れる」か「訪れない」必要がある 家$i$を訪れるのに$W(\ge 0)$円、訪れないのに$A_i(\ge 0)$円かかる また、以下の形式のルールが$\sum_{i} k_i$個ある ・家$c_{i,j}$を訪れて、家$i$を訪れないと、罰金$\infty$円かかる(鍵を持っていないので) 最小で何円必要か $\ $予め回収しておいた$\sum_{i} A_i$円から、この問題で求めた最小コストを引くと、元々の問題の答えになります。 これによって、今回の問題は「燃やす埋める問題」に帰着できました。 最小カット問題とは 解き方のパターンは最初にも触れたように3パターンあるのですが、いずれも問題の状況を有向グラフで表して「最小カット」問題に帰着させるという点では同じです。ということで、まずは「最小カット」問題を説明します。 「最小カット」というのは、自分流にイメージしやすいたとえで言えば、以下のような問題です。 sとtを含む有向グラフがある(自国sと敵国t、他の点は街と想定) 各辺は容量が決まっている(街の間の輸送のキャパシティと想定) 各街を自国と敵国に分けて、自国から敵国方向への輸送を遮断した時に、遮断される輸送量が最小になるようにする(自国に入ってくる方は遮断しない) 出ていく方だけ遮断し、それを最小にするということを覚えやすくするために、「自国」「敵国」という表現にしてみました。 なお、この問題の点や数値の設定はプログラミングコンテストチャレンジブック(通称「蟻本」)を参考にしました。 上記の場合、11が最小値になります。 証明は省略しますが、この問題は以下のような最大流の問題として解くことができます。 自国拠点sから敵国拠点tへの輸送量の最大値はいくらか この問題も確かに答えは11となっています。これを解くアルゴリズムは後述します。 最小カットへの帰着3パターン ここまでを整理すると、今回の問題は「燃やす埋める問題」に帰着でき、「燃やす埋める問題」は「最小カット問題」に帰着でき、「最小カット問題」は「最大流問題」に帰着できるので、最終的に今回の問題は最大流の問題として解くことができます。 ネット記事を見ていて混乱したのは、「燃やす埋める問題」を「最小カット問題」に帰着する際の考え方がちょっとずつ異なるものが3パターンあり、よくわからなくなったところでした。3パターンはいずれも冒頭に紹介した以下のサイトに掲載されています。 最小カットを使って「燃やす埋める」問題を解くスライドのフォロー(診断人氏ブログ) この3パターンを今回の問題に当てはめてみます。 3つのパターン全てに共通するのは、始点s、終点tと家1〜NのN+2点からなる有向グラフを作って最小カットを行うというところです。矢印や容量を何だと見立てるかがそれぞれ異なっています。 パターン1：公式解説方式 まずは今回の問題の出題者であるE869120氏による公式解説のパターンです。診断人氏ブログの[B]に該当します。 このパターンでは、訪れる家を赤(自国)、訪れない家を青(敵国)として塗り分ける問題だと見立てます。最小カットでは遮断する輸送量を最小化しますので、今回の場合はコストを輸送量と見立てます。 家1を訪れる(赤＝自国)とすると、家1とt(青＝敵国)を遮断する必要があるので、訪れた時に支払うコストである訪問料金は家1→tに割り当てます。また家1を訪れない(青＝敵国)とすると、s(赤＝自国)→家1を遮断する必要があるので、訪れない時に支払うコストである返金額を割り当てます。 鍵の条件については、家1に家2の鍵があるというのは、家1に訪れていない(青＝敵国)のに、家2に訪れる(赤＝自国)ということはできないという意味なので、このパターンになった時に遮断に無限のコストがかかるように家2→家1に∞のコストを割り当てます。 図示するとこんな感じです。 なお、問題設定は例題に記載されている以下を使用しています。 家は全部で5件 訪問料金は500円(W) 各家にはそれぞれ100円、300円、1200円、700円、1000円置いてある(A) 家1には家2と家5の鍵、家2には家5の鍵、家3には家4の鍵が置いてある(c) これを最小カットで解くと以下のようになります。(最小カットの解き方は後述) カットした辺の合計値2400が最小のコストになっており、最初に各家から回収した3300円との差額が最大獲得金額となります。 Javaのコードで書くと以下のような感じです。 Scanner sc = new Scanner(System.in); int N = Integer.parseInt(sc.next()); long W = Long.parseLong(sc.next()); DinicNetwork net = new DinicNetwork(N + 2); long sum = 0; for ( int i = 1 ; i <= N ; i++ ) { long A = Long.parseLong(sc.next()); net.addEdge(0, i, A); // sと家を接続 net.addEdge(i, N + 1, W); // 家とtを接続 sum += A; // 予めお金を回収 } for ( int i = 1 ; i <= N ; i++ ) { int k = Integer.parseInt(sc.next()); for ( int j = 0 ; j < k ; j++ ) { int c = Integer.parseInt(sc.next()); net.addEdge(c, i, DinicNetwork.INF); // 家同士を無限大で接続 } } sc.close(); System.out.println(sum - net.maxFlow(0, N + 1)); DinicNetworkというのが最小カット(=最大流)を解くためのアルゴリズムで、この実装は後述します。 パターン2：診断人氏方式 先ほどから紹介している診断人氏のブログでも紹介されていますが、氏自身による以下のSlideShareの方式です。診断人氏ブログの[A]に該当します。 最小カットを使って「燃やす埋める問題」を解く このパターンでは、各選択肢とその際のコストを辺に割り当てています。パターン1とよく似ていますが、パターン1では各頂点の塗り分けで選択肢を表していたのに対して、本パターンでは選択肢が辺で表現されているのがちょっと違います。 訪れる・訪れないをどの辺に割り当てるかは、元々の見立てである「燃やす」＝「訪れる」、「埋める」＝「訪れない」として、上記スライドのやり方と合わせています。その結果、パターン1とはちょっと違うグラフになっています。 ただし、左側を「訪れない」、右側を「訪れる」とすることにすれば、パターン1と全く同じグラフを解いていることになります。 解いた結果は以下の通りです。 当然のことながら、結果はパターン1と一致します。 これもJavaコードをつけておきます。(辺の割り当て方がちょっと違うだけです) Scanner sc = new Scanner(System.in); int N = Integer.parseInt(sc.next()); long W = Long.parseLong(sc.next()); DinicNetwork net = new DinicNetwork(N + 2); long sum = 0; for ( int i = 1 ; i <= N ; i++ ) { long A = Long.parseLong(sc.next()); net.addEdge(0, i, W); // sと家を接続 net.addEdge(i, N + 1, A); // 家とtを接続 sum += A; // 予めお金を回収 } for ( int i = 1 ; i <= N ; i++ ) { int k = Integer.parseInt(sc.next()); for ( int j = 0 ; j < k ; j++ ) { int c = Integer.parseInt(sc.next()); net.addEdge(i, c, DinicNetwork.INF); // 家同士を無限大で接続 } } sc.close(); System.out.println(sum - net.maxFlow(0, N + 1)); パターン3：Project Selection Problem これはtokoharu氏が推奨している定式化です。診断人氏ブログの[C]に該当します。以下の記事に説明があります。 『燃やす埋める』と『ProjectSelectionProblem』 続：『燃やす埋める』と『ProjectSelectionProblem』 より正確には、このパターンは元の問題を「燃やす埋める問題」に帰着するのではなく、元の問題を「Project Selection Problem」に帰着し、それを最小カットに帰着します。 では、「Project Selection Problem」とは何でしょうか？以下のように定式化されています。 $N$個の要素がある。最初どの頂点も集合$B$に属しているが、これを集合$A$に移すことで利益を最大化したい。要素$i$が$A$に属する時には利得$p_i$を得るという情報が与えられる。さらに 3 つ組の列$(x_j, y_j, z_j)$が与えられ、これは$x_j$が$A$に属し、かつ$y_j$が$B$に属していた時に$z_j (\ge 0)$だけ損失をすることを意味する。得られる利得の最大値を答えよ。 言っていることはわかるのですが、Project Selectionという言葉との関係が最初よくわかりませんでした。いろいろ考えた結果、以下のような意味合いなのだろうと推測しました。 $N$個のプロジェクトがある。最初どのプロジェクトも「実施しない($B$)」予定であるが、これを「実施する($A$)」ことにして利益を最大化したい。プロジェクト$i$を実施する時には利得$p_i$を得るという情報が与えられる。さらに3つ組の列$(x_j, y_j, z_j)$が与えられ、これはプロジェクト$x_j$を実施し、かつプロジェクト$y_j$が実施しなかった時に$z_j (\ge 0)$だけ損失をすることを意味する。得られる利得の最大値を答えよ。 こうすると、実施するプロジェクトを選ぶ問題ということで、名は体を表している感じがします。 $\ $今回の場合だと、「家を訪れること」をプロジェクトとみなし、それを実施した際の利得は$A_i-W$であり、家iに家jの鍵があるというのは、家jプロジェクトを実施し(訪れる)、かつ家iプロジェクトを実施しない(訪れない)というのは、鍵がなく不可能なので無限大の損失をする、とすれば良さそうです。注意事項としては、利得$A_i-W$は負の値である可能性があるというところです。 Project Selection Problemは最大流(=最小カット)への帰着の仕方も定式化されており、以下のようになっています。 この問題に対する解は、 $$\sum_{v\in V}\max(0,p_v) - {\rm maxflow}(s,t)$$ で求めることができる。ただし、${\rm maxflow}(s, t)$とは、 1. 要素に対応する点の他に、新しくs,tの頂点を導入した$N+2$頂点のグラフの上に 2. $p_v \gt 0$であればsから$v$に容量$p_v$の辺を張り、 3. $p_v \lt 0$であれば$v$からtに容量$−p_v$の辺を張り、 4. $x_j$から$y_j$に容量$z_j$の辺を張ったときの、 5. s-t 間の最大流の値である 今回の問題でグラフを描いてみると以下のようになります。 今までと違うのは、各家について訪れる・訪れないのそれぞれのコストを出すのではなく、訪れるとした場合の利得だけを考えているというところです。なので、各家はs,tのどちらかにしか線が接続されていません。 また先ほどの式の最初のΣの部分は、意味としては正の利得だけ足した、つまり正の利得分は最初に得ていることにした、ということになります。グラフでは正の利得はs側から接続していて、やらないとした場合は(切断した場合は)利得予定だった分を損するという考え方になっているので、辻褄があっています。一方、利得が負になっているものは最初には計上しておらず、何もしなければ(=訪れなければ)そのまま損得0で、訪れることにする(=カットする)と損失として計上されるので、これも辻褄があっています。 解いた結果は以下の通りです。 パターン1,2とはちょっと様子が違いますが、結局は同じことになっています。これもJavaコードを貼っておきます。 Scanner sc = new Scanner(System.in); int N = Integer.parseInt(sc.next()); long W = Long.parseLong(sc.next()); DinicNetwork net = new DinicNetwork(N + 2); long sum = 0; for ( int i = 1 ; i <= N ; i++ ) { long A = Long.parseLong(sc.next()); if ( A - W > 0 ) { net.addEdge(0, i, A - W); // sと家を接続 sum += A - W; // 正の利得だけ先に足しておく } else { net.addEdge(i, N + 1, W - A); // 家とtを接続 } } for ( int i = 1 ; i <= N ; i++ ) { int k = Integer.parseInt(sc.next()); for ( int j = 0 ; j < k ; j++ ) { int c = Integer.parseInt(sc.next()); net.addEdge(c, i, DinicNetwork.INF); // 家同士を無限大で接続 } } sc.close(); System.out.println(sum - net.maxFlow(0, N + 1)); パターンの比較 で、結局どのパターンで考えるのが良いのか、ということですが、そもそもこの方法をちゃんと学んだのが今日初めてなのでまだ使い分け方がよくわかっていないのが正直なところです。もう少しこの手の問題の経験を積んでから評価するのが良いと思いますが、初見では以下のような印象を持ちました。 パターン1は塗り分け問題として考えやすいが、コストをどこにマッピングするかが混乱しやすそう パターン2は辺＝選択肢というのが直感的だが、頂点間を結ぶ方向が混乱しやすそう パターン3は実行する・しないというイメージがつきやすいが、解き方含めてきちんと覚えておく必要がありそう 最大流を解くアルゴリズム(Dinic法) ここまでで最小カット＝最大流への帰着のさせ方がわかったので、最後に最大流を解くアルゴリズムを紹介しておきます。基本的には蟻本の受け売りです。 以下3つのステップを経て、高速なDinic法へ到達します。(実際にはより高速な解法もあるようです) Step1：貪欲法(嘘解法) この方法は嘘解法なので正しい解は導けないのですが、正しい解を求める際のベースになるのでまずはここから紹介します。基本的には以下のようなやり方です。 sからtに向けて、正の容量の辺だけを使ったDFSで経路を探索 その経路に目一杯流す(正確にはその経路上の容量の最小値の分だけその経路に流す) sからtへの容量が残った経路がなくなるまで繰り返す Step2：Ford-Fulkerson法 さて、Step1の貪欲法は嘘解法で、見つけた10という値は実は最大値ではありません。最初に見つけた経路でs→A→B→tを5流してしまいましたが、最終図をじっと眺めてみると、流すのを4に留めておけば、次のs→A→C→tで6流すことになり、その後さらにs→B→tに1流せる余地が残っていたはずです。 Step1の最後の状況と、上記のようにさらに1流した状況を比べると、A→Bに流れている5の分を1だけ押し戻すということを許容し、Step1の最後の状況に対してs→B→A→C→tに1流したことに相当します。このような押し戻しを加味して貪欲法で求めるのがFord-Fulkerson法です。 sからtに向けて、正の容量の辺だけを使ったDFSで経路を探索 その経路に目一杯流す(正確にはその経路上の容量の最小値の分だけその経路に流す) その際に、後で押し戻せるように逆向きに同じ容量のパスを追加する 追加したパスも含めて、sからtへの容量が残った経路がなくなるまで繰り返す $\ $証明は省略しますが、これは正しい解法になっています。このアルゴリズムは、最大流量を$F$、$|E|$を辺の数とすると、DFS部分が1回あたり$O(|E|)$、運悪く毎回1だけ流せるパスを見つけてしまった場合にDFSがおよそ$F$回実行されることになるので、最悪のケースで$O(F|E|)$で動作します。 Step3：Dinic法 Dinic法はFord-Fulkerson法のDFS部分にルールを作って無闇に実行しないようにすることで、実行オーダーを最大流量$F$ではなく、頂点数と辺の数に依存するようにしたものです(と筆者は解釈しました。適切でなければご指摘ください)。 細かい説明は省略しますが、以下のようなアルゴリズムになります。 sからBFSで各頂点にsからの距離(level)を付与 その結果、tにたどり着けなくなっていればそこまでで流した量が最大流量 sからtに向けて、正の容量の辺だけを使い、かつ距離が狭義単調増大するDFSで経路を探索 その経路に目一杯流す(正確にはその経路上の容量の最小値の分だけその経路に流す) その際に、後で押し戻せるように逆向きに同じ容量のパスを追加する 追加したパスも含めて、sからtへの容量が残った経路がなくなるまでDFSを繰り返す。その際に既に調べた経路はもう調べない DFSで経路が見つからなくなったら、BFSからやり直す 3つ目の図で、s→A→C→tも残っているように見えますが、C→tが両方level=2なので狭義単調増加になっておらず、DFSでの経路はなくなったので、BFSからやり直しになっています。 このアルゴリズムを実装したJavaコードを以下に貼っておきます(蟻本のJava移植版です) public class DinicNetwork { static final long INF = Long.MAX_VALUE; int[] level = null; int[] iter = null; ArrayList<Edge> edges[] = null; public class Edge { int to = 0; long cap = 0; int rev = 0; Edge( int to, long cap, int rev ) { this.to = to; this.cap = cap; this.rev = rev; } } public DinicNetwork(int N) { level = new int[N]; iter = new int[N]; edges = new ArrayList[N]; for ( int i = 0 ; i < N ; i++ ) { edges[i] = new ArrayList(); } } public void addEdge(int from, int to, long cap) { edges[from].add(new Edge(to, cap, edges[to].size())); edges[to].add(new Edge(from, 0, edges[from].size() - 1)); } private void bfs(int s) { Arrays.fill(level, -1); Deque<Integer> queue = new ArrayDeque<Integer>(); level[s] = 0; queue.add(s); while ( !queue.isEmpty() ) { int v = queue.poll(); for ( Edge e : edges[v] ) { if ( e.cap > 0 && level[e.to] < 0 ) { level[e.to]= level[v] + 1; queue.add(e.to); } } } } private long dfs(int v, int t, long f) { if ( v == t ) return f; while ( iter[v] < edges[v].size() ) { Edge e = edges[v].get(iter[v]); if ( e.cap > 0 && level[v] < level[e.to] ) { long d = dfs(e.to, t, Math.min(f, e.cap)); if ( d > 0 ) { e.cap = add(e.cap, -d); edges[e.to].get(e.rev).cap = add(edges[e.to].get(e.rev).cap, d); return d; } } iter[v]++; } return 0; } private long add(long a, long diff) { return a == INF ? INF : a + diff; } public long maxFlow(int s, int t) { long flow = 0; while ( true ) { bfs(s); if ( level[t] < 0 ) return flow; Arrays.fill(iter, 0); long f = 0; while ( (f = dfs(s, t, INF)) > 0 ) { flow += f; } } } } アルゴリズムの説明の中で、DFSについて「その際に既に調べた経路はもう調べない」と書きましたが、iterという配列で実行したindexの位置を記録している部分がそれにあたります。 $\ $このアルゴリズムの計算量は、頂点数$|V|$、辺の数$|E|$として、$O(|E||V|^2)$となっていますが、この計算量から見積もるよりもだいぶ高速に動くようです。 計算量の詳細については以下のサイトが詳しいのでご参照ください。 Dinic 法とその時間計算量