jgrapht · Jun 11, 2018 · Jun 13, 2018 · Jun 13, 2018 · Jun 13, 2018 · Jun 26, 2018
diff --git a/docs/Gemfile.lock b/docs/Gemfile.lock
@@ -26,7 +26,7 @@ GEM
     execjs (2.7.0)
     faraday (0.15.1)
       multipart-post (>= 1.2, < 3)
-    ffi (1.9.23)
+    ffi (1.13.1)
     forwardable-extended (2.6.0)
     gemoji (3.0.0)
     github-pages (185)
@@ -199,15 +199,15 @@ GEM
       rb-inotify (~> 0.9, >= 0.9.7)
       ruby_dep (~> 1.2)
     mercenary (0.3.6)
-    mini_portile2 (2.3.0)
+    mini_portile2 (2.4.0)
     minima (2.4.1)
       jekyll (~> 3.5)
       jekyll-feed (~> 0.9)
       jekyll-seo-tag (~> 2.1)
     minitest (5.11.3)
     multipart-post (2.0.0)
-    nokogiri (1.8.2)
-      mini_portile2 (~> 2.3.0)
+    nokogiri (1.10.10)
+      mini_portile2 (~> 2.4.0)
     octokit (4.9.0)
       sawyer (~> 0.8.0, >= 0.5.3)
     pathutil (0.16.1)
@@ -220,7 +220,7 @@ GEM
     ruby-enum (0.7.2)
       i18n
     ruby_dep (1.5.0)
-    rubyzip (1.2.1)
+    rubyzip (2.3.0)
     safe_yaml (1.0.4)
     sass (3.5.6)
       sass-listen (~> 4.0.0)

diff --git a/jgrapht-core/src/main/java/org/jgrapht/GraphTests.java b/jgrapht-core/src/main/java/org/jgrapht/GraphTests.java
@@ -17,8 +17,13 @@
  */
 package org.jgrapht;
 
-import org.jgrapht.alg.connectivity.*;
 import org.jgrapht.alg.cycle.*;
+import org.jgrapht.alg.connectivity.BiconnectivityInspector;
+import org.jgrapht.alg.connectivity.ConnectivityInspector;
+import org.jgrapht.alg.connectivity.KosarajuStrongConnectivityInspector;
+import org.jgrapht.alg.cycle.ChordalityInspector;
+import org.jgrapht.alg.cycle.HierholzerEulerianCycle;
+import org.jgrapht.alg.interval.*;
 
 import java.util.*;
 import java.util.stream.*;
@@ -29,6 +34,7 @@
  * @author Barak Naveh
  * @author Dimitrios Michail
  * @author Joris Kinable
+ * @author Ira Justus Fesefeldt
  */
 public abstract class GraphTests
 {
@@ -497,6 +503,24 @@ public static <V, E> boolean isChordal(Graph<V, E> graph)
         Objects.requireNonNull(graph, GRAPH_CANNOT_BE_NULL);
         return new ChordalityInspector<>(graph).isChordal();
     }
+
+    /**
+     * Tests whether a graph is an interval graph. <a href="https://en.wikipedia.org/wiki/Interval_graph">
+     * Interval graphs</a> are a familiy of graphs, which can be represented as intersections of intervals.
+     * The vertices are intervals on the number line and two vertices are connected if and only if the intervals of
+     * these vertices intersect each other.
+     * 
+     * @param graph the input graph
+     * @param <V> the graph vertex type
+     * @param <E> the graph edge type
+     * @return true if the graph is an interval graph, false otherwise
+     * @see IntervalGraphRecognizer#isIntervalGraph()
+     * 
+     */
+    public static <V, E> boolean isIntervalGraph(Graph<V, E> graph) {
+        Objects.requireNonNull(graph, GRAPH_CANNOT_BE_NULL);
+        return new IntervalGraphRecognizer<>(graph).isIntervalGraph();
+    }
 
     /**
      * Checks whether a graph is <a href="http://www.graphclasses.org/classes/gc_14.html">weakly

diff --git a/jgrapht-core/src/main/java/org/jgrapht/alg/interfaces/IntervalStructureInterface.java b/jgrapht-core/src/main/java/org/jgrapht/alg/interfaces/IntervalStructureInterface.java
@@ -0,0 +1,68 @@
+/*
+ * (C) Copyright 2003-2018, by Christoph Grüne and Contributors.
+ *
+ * JGraphT : a free Java graph-theory library
+ *
+ * This program and the accompanying materials are dual-licensed under
+ * either
+ *
+ * (a) the terms of the GNU Lesser General Public License version 2.1
+ * as published by the Free Software Foundation, or (at your option) any
+ * later version.
+ *
+ * or (per the licensee's choosing)
+ *
+ * (b) the terms of the Eclipse Public License v1.0 as published by
+ * the Eclipse Foundation.
+ */
+package org.jgrapht.alg.interfaces;
+
+import org.jgrapht.graph.interval.Interval;
+
+import java.util.List;
+
+/**
+ * Interface of IntervalStructure
+ * This interface is used for an implementation of an efficient data structure to maintain intervals.
+ *
+ * @param <T> the type of the interval
+ *
+ * @author Christoph Grüne (christophgruene)
+ * @since Apr 26, 2018
+ */
+public interface IntervalStructureInterface<T extends Comparable<T>> {
+
+    /**
+     * Returns all intervals that overlap with the given <code>interval</code>
+     *
+     * @param interval the interval
+     * @return all intervals that overlap with the given <code>interval</code>
+     */
+    List<Interval<T>> overlapsWith(Interval<T> interval);
+
+
+    /**
+     * Returns all intervals that overlap with the given <code>point</code>
+     * @param point the point
+     * @return all intervals that overlap with the given <code>point</code>
+     */
+    List<Interval<T>> overlapsWithPoint(T point);
+
+    /**
+     * adds an interval to the interval tree. It returns true iff the key has been added successfully.
+     *
+     * @param interval the interval
+     *
+     * @return true, if the key was not contained in the tree; false, otherwise
+     */
+    boolean add(Interval<T> interval);
+
+    /**
+     * removes an interval from the tree. It returns true iff the key has been removed successfully.
+     *
+     * @param interval the interval
+     *
+     * @return true, if the key was contained in the tree; false, otherwise
+     */
+    boolean remove(Interval<T> interval);
+}
diff --git a/jgrapht-core/src/main/java/org/jgrapht/alg/interfaces/IntervalTreeInterface.java b/jgrapht-core/src/main/java/org/jgrapht/alg/interfaces/IntervalTreeInterface.java
@@ -0,0 +1,59 @@
+/*
+ * (C) Copyright 2003-2018, by Christoph Grüne and Contributors.
+ *
+ * JGraphT : a free Java graph-theory library
+ *
+ * This program and the accompanying materials are dual-licensed under
+ * either
+ *
+ * (a) the terms of the GNU Lesser General Public License version 2.1
+ * as published by the Free Software Foundation, or (at your option) any
+ * later version.
+ *
+ * or (per the licensee's choosing)
+ *
+ * (b) the terms of the Eclipse Public License v1.0 as published by
+ * the Eclipse Foundation.
+ */
+package org.jgrapht.alg.interfaces;
+
+import org.jgrapht.graph.interval.Interval;
+import org.jgrapht.graph.interval.IntervalTreeNodeValue;
+import org.jgrapht.util.BinarySearchTree;
+
+import java.util.List;
+
+/**
+ * Interface of IntervalTree
+ * This is the interface to an interval tree. It maintains intervals in order to find intersecting intervals and
+ * included points in O(log n + k), where n is the number of intervals and k the output size,
+ * i.e. the number of output intervals.
+ *
+ * @param <T> The type of the interval
+ * @param <K> The key for the search tree
+ * @param <NodeValue> The node value type
+ *
+ * @author Christoph Grüne (christophgruene)
+ * @since Apr 26, 2018
+ */
+public interface IntervalTreeInterface
+        <K, NodeValue extends IntervalTreeNodeValue<Interval<T>, T>, T extends Comparable<T>>
+        extends BinarySearchTree<K, NodeValue> {
+
+    /**
+     * Returns all intervals of all vertices that intersect with the given <code>interval</code>
+     *
+     * @param interval the interval
+     * @return all intersecting intervals of vertices in the graph
+     */
+    List<Interval<T>> overlapsWith(Interval<T> interval);
+
+    /**
+     * Returns all intervals of all vertices that include the given <code>point</code>
+     *
+     * @param point the point
+     * @return all including intervals of vertices in the graph
+     */
+    List<Interval<T>> overlapsWith(T point);
+
+}