gt:         for (Vertex<E> v : vertices)
context: /* Copyright (C) 2022, Specify Collections Consortium
   * 
   * Specify Collections Consortium, Biodiversity Institute, University of Kansas,
   * 1345 Jayhawk Boulevard, Lawrence, Kansas, 66045, USA, support@specifysoftware.org
   * 
   * This program is free software; you can redistribute it and/or
   * modify it under the terms of the GNU General Public License
   * as published by the Free Software Foundation; either version 2
   * of the License, or (at your option) any later version.
   * 
   * This program is distributed in the hope that it will be useful,
   * but WITHOUT ANY WARRANTY; without even the implied warranty of
   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   * GNU General Public License for more details.
   * 
   * You should have received a copy of the GNU General Public License
   * along with this program; if not, write to the Free Software
   * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
  */
  package edu.ku.brc.specify.tasks.subpane.wb.graph;
  
  import java.util.HashSet;
  import java.util.LinkedList;
  import java.util.List;
  import java.util.Set;
  import java.util.SortedSet;
  import java.util.TreeSet;
  import java.util.Vector;
  
  import org.apache.log4j.Logger;
  
  /**
   * @author timo
   * 
   */
  public class DirectedGraph<E, F>
  {
      protected Set<Vertex<E>>    vertices;
      protected Set<Edge<E, F>>   edges;
      private static final Logger log = Logger.getLogger(DirectedGraph.class);
  
      public DirectedGraph()
      {
          vertices = new HashSet<Vertex<E>>();
          edges = new HashSet<Edge<E, F>>();
      }
  
      /**
       * @return a copy of the the object with an 'opposite' edge added for each edge.
       * I.E. for an edge from v1 to v2, an additional edge from v2 to v1 will be added to the copy.
       * The copy is shallow: new objects are not created for vertex or edge data.
       * 
       * @throws DirectedGraphException
       */
      protected DirectedGraph<E, F> makeUndirectedCopy() throws DirectedGraphException
      {
          DirectedGraph<E, F> result = new DirectedGraph<E, F>();
          for (Vertex<E> v : vertices)
          {
              result.addVertex(new Vertex<E>(v.getLabel(), v.getData()));
          }
          for (Edge<E, F> e : edges)
          {
              result.addEdge(e.getPointA().getLabel(), e.getPointB().getLabel());
              result.addEdge(e.getPointB().getLabel(), e.getPointA().getLabel());
          }
          return result;
      }
  
      /**
       * @return a listing of all edges in the graph.
       */
      public Vector<String> listEdges()
      {
          SortedSet<String> lines = new TreeSet<String>();
          for (Edge<E, F> e : edges)
          {
              lines.add(e.getPointA().getLabel() + " --> " + e.getPointB().getLabel());
          }
          return new Vector<String>(lines);
      }
  
      /**
       * @param v
       * 
       * adds v to the graph.
       * 
       * @throws DirectedGraphException if a vertex with same label as v is already in the graph.
       */
      public void addVertex(Vertex<E> v) throws DirectedGraphException
      {
          if (getVertexByLabel(v.getLabel()) != null) { throw new DirectedGraphException(
                  "vertex is already in graph"); }
          vertices.add(v);
      }
  
      /**
       * @param a
       * @param b
       * 
       * adds vertices a and b and adds an edge with null data from a to b.
       * 
       * @throws DirectedGraphException if a or b are already in the graph.
       */
      public void addEdge(Vertex<E> a, Vertex<E> b) throws DirectedGraphException
      {
          addEdge(a, b, null);
      }
  
      /**
       * @param a
       * @param b
       * @param data
       * 
       * adds vertices a and b and adds an edge with supplied data from a to b.
       * @throws DirectedGraphException if a or b are already in the graph.
       */
      public void addEdge(Vertex<E> a, Vertex<E> b, F data) throws DirectedGraphException
      {
          try
          {
              addVertex(a);
              addVertex(b);
              edges.add(new Edge<E, F>(a, b, data));
          }
          catch (DirectedGraphException e)
          {
              throw e;
          }
      }
  
      /**
       * @param aLabel
       * @param bLabel
       * @throws DirectedGraphException
       * 
       * adds an edge with null data between vertices with given labels. Throws exception if either vertex
       * is not in graph. Multiple edges between same vertices are possible.
       */
      public void addEdge(String aLabel, String bLabel) throws DirectedGraphException
      {
          addEdge(aLabel, bLabel, null);
      }
  
      /**
       * @param aLabel
       * @param bLabel
       * @param data
       * @throws DirectedGraphException
       * 
       * adds an edge with supplied data between vertices with given labels. Throws exception if either vertex
       * is not in graph. Multiple edges between same vertices are possible.
       */
      public void addEdge(String aLabel, String bLabel, F data) throws DirectedGraphException
      {
          Vertex<E> v1 = getVertexByLabel(aLabel);
          Vertex<E> v2 = getVertexByLabel(bLabel);
          if (v1 != null && v2 != null)
          {
              edges.add(new Edge<E, F>(v1, v2, data));
          }
          else
          {
              throw new DirectedGraphException("vertex does not exist in graph");
          }
      }
  
      /**
       * @param v1
       * @param v2
       * @return edge from v1 to v2 if it exists, or null.
       */
      private Edge<E, F> getEdge(Vertex<E> v1, Vertex<E> v2)
      {
          for (Edge<E, F> e : edges)
          {
              if (e.getPointA().equals(v1) && e.getPointB().equals(v2)) { return e; }
          }
          return null;
      }
  
      /**
       * @param v1
       * @param v2
       * @return edges from v1 to v2 if it exists.
       */
      private Vector<Edge<E, F>> getEdges(Vertex<E> v1, Vertex<E> v2)
      {
          Vector<Edge<E,F>> result = new Vector<Edge<E,F>>();
          for (Edge<E, F> e : edges)
          {
              if (e.getPointA().equals(v1) && e.getPointB().equals(v2)) 
              { 
                  result.add(e); 
              }
          }
          return result;
      }
  
      /**
       * @param v1
       * @param v2
       * @return edge data for edge from v2 to v2. null if no edge exists from v2 to v2.
       */
      public F getEdgeData(Vertex<E> v1, Vertex<E> v2)
      {
          Edge<E, F> e = getEdge(v1, v2);
          if (e != null) { return e.getData(); }
          return null;
      }
  
      /**
       * @param v1
       * @param v2
       * @return edge data for all edges from v2 to v2. 
       */
      public Vector<F> getAllEdgeData(Vertex<E> v1, Vertex<E> v2)
      {
          Vector<Edge<E, F>> es = getEdges(v1, v2);
          Vector<F> result = new Vector<F>();
          for (Edge<E,F> e : es)
          {
              result.add(e.getData());
          }
          return result;
      }
  
      /**
       * @param vData1
       * @param vData2
       * @return edge data for edge from vertex with vData1 to vertex with vData2, or null if there is no such edge in graph.
       * @throws DirectedGraphException if vertices with given data are not in graph.
       */
      public F getEdgeData(E vData1, E vData2) throws DirectedGraphException
      {
          Vertex<E> v1 = getVertexByData(vData1);
          Vertex<E> v2 = getVertexByData(vData2);
          if (v1 == null || v2 == null) { throw new DirectedGraphException(
                  "vertex does not exist in graph"); }
          return getEdgeData(v1, v2);
      }
  
      /**
       * @param vData1
       * @param vData2
       * @return edge data for all edgee from vertex with vData1 to vertex with vData2, or null if there is no such edge in graph.
       * @throws DirectedGraphException if vertices with given data are not in graph.
       */
      public Vector<F> getAllEdgeData(E vData1, E vData2) throws DirectedGraphException
      {
          Vertex<E> v1 = getVertexByData(vData1);
          Vertex<E> v2 = getVertexByData(vData2);
          if (v1 == null || v2 == null) { throw new DirectedGraphException(
                  "vertex does not exist in graph"); }
          return getAllEdgeData(v1, v2);
      }
  
      /**
       * @return true if graph is strongly connected.
       * @throws DirectedGraphException
       */
      public boolean isStronglyConnected() throws DirectedGraphException
      {
          for (Vertex<E> v : vertices)
          {
              Set<Vertex<E>> g = from(v);
              g.addAll(to(v));
              g.add(v);
              if (!g.equals(vertices)) { return false; }
          }
          return true;
      }
  
      /**
       * @return true if graph is connected.
       * @throws DirectedGraphException
       */
      public boolean isConnected() throws DirectedGraphException
      {
          DirectedGraph<E, F> undirected = makeUndirectedCopy();
          if (undirected == null) { return false; }
          return undirected.isStronglyConnected();
      }
  
      /**
       * @param v
       * @return vector of vertices that are endpoints of the edges leaving v.
       */
      public Vector<Vertex<E>> getAdjacentVertices(final Vertex<E> v)
      {
          Vector<Vertex<E>> result = new Vector<Vertex<E>>();
          for (Edge<E, F> e : edges)
          {
              if (e.getPointA().equals(v))
              {
                  result.add(e.getPointB());
              }
          }
          return result;
      }
  
      /**
       * @param v the vertex to remove.
       * 
       * Removes v and all edges that leave or enter v.
       */
      public void removeVertex(final Vertex<E> v)
      {
          List<Edge<E, F>> toRemove = new LinkedList<Edge<E, F>>();
          for (Edge<E, F> e : edges)
          {
               if (e.getPointA().equals(v) || e.getPointB().equals(v))
              {
                  toRemove.add(e);
              }
          }
          for (Edge<E,F> e : toRemove)
          {
              edges.remove(e);
          }
          vertices.remove(v);
      }
      /**
       * @param v
       * @param visited
       * 
       * performs a topological sort from v. The resulting sort is stored in visited.
       */
      protected void topoSort(final Vertex<E> v, Vector<Vertex<E>> visited)
      {
          for (Vertex<E> a : getAdjacentVertices(v))
          {
              if (!visited.contains(a))
              {
                  topoSort(a, visited);
              }
          }
          visited.insertElementAt(v, 0);
      }
  
      /**
       * @param v
       * @return a topological sort of the graph from v.
       */
      public Vector<Vertex<E>> topoSort(final Vertex<E> v)
      {
          Vector<Vertex<E>> result = new Vector<Vertex<E>>();
          topoSort(v, result);
          return result;
      }
  
      /**
       * @param vLabel
       * @return topological sort from vertex labeled vLabel.
       * @throws DirectedGraphException if no vertex labeled vLabel exists in graph.
       * 
       * Finds vertex with supplied label and returns the topologicial sort from v. 
       */
      public Vector<Vertex<E>> topoSort(final String vLabel) throws DirectedGraphException
      {
          Vertex<E> v = getVertexByLabel(vLabel);
          if (v == null) { throw new DirectedGraphException("vertex does not exist in graph"); }
          return topoSort(v);
      }
  
      /**
       * @param vLabel
       * @return vertex with given label.
       */
      public Vertex<E> getVertexByLabel(final String vLabel)
      {
  