Package it.unimi.di.prog2.h24.digraph

Interface DiGraph<T>

Type Parameters:
T - the type of the graph nodes.
All Known Implementing Classes:
AdjacencyMapDiGraph, AdjacencyMatrixDiGraph, ArcListDiGraph, ImplicitDiGraph
public interface DiGraph<T>
An interface representing an directed graph where nodes are of generic type T.

A directed graph \( G = (N, A) \) is a pair where \( N \) is a finite set of nodes (of type T) and \(A = \{(x, y) : x, y \in N \} \) is the set of arcs that are ordered pairs of elements of \( N \); the first element of and arc is called source, and the second one is called destination. Given a node \( x \in N \), the set of outgoing nodes of \( x \) is the set \(\{y : (x, y) \in A \} \).

Classes implementing this interface can represent both immutable and mutable directed graphs, default implementations of mutation methods addNode(Object) and addArc(Object, Object) rise UnsupportedOperationException (while the default implementation of addArc(Arc) relies on addArc(Object, Object)).

Every implementation must at least override nodes(); moreover, since arcs() has a default implementation in terms of such method and outgoing(Object), and conversely outgoing(Object) has a default implementation in terms of arcs(), at least one of these two methods must be overridden. All other methods have default implementations based on outgoing(Object) and/or arcs(). Whenever possible, implementations should provide a copy constructor.

  • Method Summary

    Modifier and Type
    Method
    Description
    default void
    addArc(Arc<? extends T> arc)
    Adds an arc to this graph.
    default void
    addArc(T source, T destination)
    Adds an arc to this graph.
    default void
    addNode(T node)
    Adds a node to this graph.
    default Set<Arc<T>>
    arcs()
    Returns this graph arcs.
    static <T> void
    fill(DiGraph<? extends T> source, DiGraph<T> destination)
    Fills the given graph with the nodes and arcs of the given source graph.
    default boolean
    hasArc(Arc<? extends T> arc)
    Tells whether an arc belongs to this graph, or not.
    default boolean
    hasArc(T source, T destination)
    Tells whether an arc belongs to this graph, or not.
    default boolean
    hasNode(T node)
    Tells whether a node belongs to this graph, or not.
    Set<T>
    nodes()
    Returns the graph nodes.
    default Set<T>
    outgoing(T source)
    Returns the set of outgoing nodes of a given node.
    default void
    visit(T start, Consumer<? super T> visit, Supplier<? extends Queue<T>> supplier)
    Performs a visit on the graph.

  • Method Details

    • nodes

      Set<T> nodes()
      Returns the graph nodes.
      Returns:
      the graph nodes.

    • outgoing

      default Set<T> outgoing(T source)
      Returns the set of outgoing nodes of a given node.
      Parameters:
      source - the source node.
      Returns:
      the nodes that have an arc with the given source in this graph (the collection is empty if the source does not belong to this graph).
      Throws:
      NullPointerException - if source is null.

    • addNode

      default void addNode(T node)
      Adds a node to this graph.
      Parameters:
      node - the node to be added.
      Throws:
      UnsupportedOperationException - if this graph is immutable.
      NullPointerException - if node is null.

    • addArc

      default void addArc(T source, T destination)
      Adds an arc to this graph.

      It the source, or destination, node are not present in the graph, they are also added.

      Parameters:
      source - the source of the arc to be added.
      destination - the destination of the arc to be added.
      Throws:
      UnsupportedOperationException - if this graph is immutable.
      NullPointerException - if source or destination are null.

    • addArc

      default void addArc(Arc<? extends T> arc)
      Adds an arc to this graph.

      It the source, or destination, node are not present in the graph, they are also added.

      Parameters:
      arc - the arc to be added.
      Throws:
      UnsupportedOperationException - if this graph is immutable.
      NullPointerException - if arc is null.

    • hasArc

      default boolean hasArc(T source, T destination)
      Tells whether an arc belongs to this graph, or not.
      Parameters:
      source - the source of the arc to be queried.
      destination - the destination of the arc to be queried.
      Returns:
      whether the arc belongs to the graph, or not.
      Throws:
      NullPointerException - if source or destination are null.

    • hasArc

      default boolean hasArc(Arc<? extends T> arc)
      Tells whether an arc belongs to this graph, or not.
      Parameters:
      arc - the arc to be queried.
      Returns:
      whether the arc belongs to the graph, or not.
      Throws:
      NullPointerException - if arc is null.

    • hasNode

      default boolean hasNode(T node)
      Tells whether a node belongs to this graph, or not.
      Parameters:
      node - the node to be queried.
      Returns:
      whether the node belongs to the graph, or not.
      Throws:
      NullPointerException - if node is null.

    • arcs

      default Set<Arc<T>> arcs()
      Returns this graph arcs.
      Returns:
      the arcs belonging to this graph.

    • visit

      default void visit(T start, Consumer<? super T> visit, Supplier<? extends Queue<T>> supplier)
      Performs a visit on the graph.
      Parameters:
      start - the not where the visit must start.
      visit - a Consumer that will be called to visit every encountered node.
      supplier - a Supplier providing the Queue to be used to perform the visit.
      Throws:
      NullPointerException - if start, visit, or supplier are null.

    • fill

      static <T> void fill(DiGraph<? extends T> source, DiGraph<T> destination)
      Fills the given graph with the nodes and arcs of the given source graph.
      Type Parameters:
      T - the type of the destination graph nodes.
      Parameters:
      source - the source graph.
      destination - the destination graph.
      Throws:
      NullPointerException - if source or destination are null.