Class DirectedAcyclicGraph<V,E>

java.lang.Object
io.lacuna.bifurcan.DirectedAcyclicGraph<V,E>
All Implemented Interfaces:
ICollection<IGraph<V,E>,V>, IGraph<V,E>, Iterable<V>
public class DirectedAcyclicGraph<V,E> extends Object implements IGraph<V,E>
A directed graph which will throw a DirectedAcyclicGraph.CycleException if any new edge creates a cycle.

  • Constructor Details

    • DirectedAcyclicGraph

      public DirectedAcyclicGraph()

    • DirectedAcyclicGraph

      public DirectedAcyclicGraph(ToLongFunction<V> hashFn, BiPredicate<V,V> equalsFn)

  • Method Details

    • from

      public static <V, E> DirectedAcyclicGraph<V,E> from(DirectedGraph<V,E> graph)
      Returns:
      a directed acyclic graph equivalent to graph
      Throws:
      DirectedAcyclicGraph.CycleException - if graph contains a cycle

    • top

      public Set<V> top()

    • bottom

      public Set<V> bottom()

    • directedGraph

      public DirectedGraph<V,E> directedGraph()

    • add

      public DirectedAcyclicGraph<V,E> add(IEdge<V,E> edge)
      Specified by:
      add in interface IGraph<V,E>

    • remove

      public DirectedAcyclicGraph<V,E> remove(IEdge<V,E> edge)
      Specified by:
      remove in interface IGraph<V,E>

    • link

      public DirectedAcyclicGraph<V,E> link(V from, V to, E edge)
      Specified by:
      link in interface IGraph<V,E>

    • link

      public DirectedAcyclicGraph<V,E> link(V from, V to)
      Specified by:
      link in interface IGraph<V,E>

    • vertices

      public Set<V> vertices()
      Specified by:
      vertices in interface IGraph<V,E>
      Returns:
      the set of all vertices in the graph

    • edges

      public Iterable<IEdge<V,E>> edges()
      Specified by:
      edges in interface IGraph<V,E>
      Returns:
      an iterator over every edge in the graph

    • edge

      public E edge(V src, V dst)
      Specified by:
      edge in interface IGraph<V,E>
      Returns:
      the value of the edge between from and to

    • edge

      public E edge(V src, V dst, E notFound)
      Specified by:
      edge in interface IGraph<V,E>
      Parameters:
      src - A vertex
      dst - Another vertex
      Returns:
      The value of the edge from from and to, or notFound if no such edge exists.

    • in

      public Set<V> in(V vertex)
      Description copied from interface: IGraph
      In an undirected graph, this is equivalent to IGraph.out(Object).
      Specified by:
      in in interface IGraph<V,E>
      Returns:
      the set of all incoming edges to vertex

    • out

      public Set<V> out(V vertex)
      Description copied from interface: IGraph
      In an undirected graph, this is equivalent to IGraph.in(Object).
      Specified by:
      out in interface IGraph<V,E>
      Returns:
      the set of all outgoing edges from vertex

    • link

      public DirectedAcyclicGraph<V,E> link(V from, V to, E edge, BinaryOperator<E> merge)
      Specified by:
      link in interface IGraph<V,E>
      Parameters:
      from - the source of the edge
      to - the destination of the edge
      edge - the value of the edge
      merge - the merge function for the edge values, if an edge already exists
      Returns:
      a graph containing the new edge
      Throws:
      DirectedAcyclicGraph.CycleException - if the new edge creates a cycle

    • unlink

      public DirectedAcyclicGraph<V,E> unlink(V from, V to)
      Specified by:
      unlink in interface IGraph<V,E>
      Returns:
      a graph without any edge between from and to

    • merge

      public DirectedAcyclicGraph<V,E> merge(IGraph<V,E> graph, BinaryOperator<E> merge)
      Specified by:
      merge in interface IGraph<V,E>

    • select

      public DirectedAcyclicGraph<V,E> select(ISet<V> vertices)
      Specified by:
      select in interface IGraph<V,E>
      Returns:
      a graph containing only the specified vertices and the edges between them

    • add

      public DirectedAcyclicGraph<V,E> add(V vertex)
      Specified by:
      add in interface IGraph<V,E>
      Returns:
      a graph with vertex added

    • remove

      public DirectedAcyclicGraph<V,E> remove(V vertex)
      Specified by:
      remove in interface IGraph<V,E>
      Returns:
      a graph with vertex removed, as well as all incoming and outgoing edges

    • forked

      public DirectedAcyclicGraph<V,E> forked()
      Description copied from interface: ICollection
      This returns a data structure which is forked, which is equivalent to Clojure's persistent data structures, also sometimes called functional or immutable. This is called "forked" because it means that multiple functions can make divergent changes to the data structure without affecting each other.

      If only a single function or scope uses the data structure, it can be left as a linear data structure, which can have significant performance benefits.

      If the data structure is already forked, it will simply return itself.

      Specified by:
      forked in interface ICollection<V,E>
      Returns:
      a forked form of the data structure

    • linear

      public DirectedAcyclicGraph<V,E> linear()
      Description copied from interface: ICollection
      This returns a data structure which is linear, or temporarily mutable. The term "linear", as used here, does not completely align with the formal definition of linear types as used in type theory. It is meant to describe the linear dataflow of the method calls, and as a converse to "forked" data structures.

      If ICollection.forked() is called on a linear collection, all references to that linear collection should be discarded.

      If the data structure is already linear, it will simply return itself.

      Specified by:
      linear in interface ICollection<V,E>
      Returns:
      a linear form of this data structure

    • isLinear

      public boolean isLinear()
      Specified by:
      isLinear in interface ICollection<V,E>
      Returns:
      true, if the collection is linear

    • isDirected

      public boolean isDirected()
      Specified by:
      isDirected in interface IGraph<V,E>
      Returns:
      whether the graph is directed

    • mapEdges

      public <U> DirectedAcyclicGraph<V,U> mapEdges(Function<IEdge<V,E>,U> f)
      Specified by:
      mapEdges in interface IGraph<V,E>

    • transpose

      public DirectedAcyclicGraph<V,E> transpose()
      Specified by:
      transpose in interface IGraph<V,E>
      Returns:
      a transposed version of the graph

    • vertexHash

      public ToLongFunction<V> vertexHash()
      Specified by:
      vertexHash in interface IGraph<V,E>
      Returns:
      the hash function for vertices

    • vertexEquality

      public BiPredicate<V,V> vertexEquality()
      Specified by:
      vertexEquality in interface IGraph<V,E>
      Returns:
      the equality check for vertices

    • hashCode

      public int hashCode()
      Overrides:
      hashCode in class Object

    • equals

      public boolean equals(Object obj)
      Overrides:
      equals in class Object

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • clone

      public DirectedAcyclicGraph<V,E> clone()
      Specified by:
      clone in interface ICollection<V,E>
      Overrides:
      clone in class Object
      Returns:
      a cloned copy of the collection