Package com.qfs.graph

Interface IDirectedGraph<K,V,E>

Type Parameters:
K - the type of the keys for the vertices
V - the type of the content for the vertices
E - the type of the edges

Edge convention: a null value for an edge between two nodes is interpreted as the absence of edges between these two nodes.

All Superinterfaces:
Map<K,V>
All Known Subinterfaces:
IConcurrentDirectedGraph<K,V,E>, IDirectedMultiGraph<K,V,E>, IQueryStoreTree, ITree<K,V,E>
All Known Implementing Classes:
ConcurrentDirectedGraph, DirectedGraph, DirectedMultiGraph, QueryStoreTree, Tree, UnmodifiableDirectedMultiGraph, UserStoreGraph
public interface IDirectedGraph<K,V,E> extends Map<K,V>
Represent a mutable directed graph.
Author:
ActiveViam

  • Method Details

    • addNode

      void addNode(K key, V value)
      Adds a node to the graph. If a node already exists with the same key it is overridden and all edges are now connected to the new node.
      Parameters:
      key - the key of the node to add
      value - the value of the node to add

    • setNode

      default V setNode(K key, V value)

    • removeNode

      default V removeNode(K key)
      Removes a node from the graph.
      Returns:
      the value associated with the node

    • getNodes

      default Collection<Map.Entry<K,V>> getNodes()

    • forEachNode

      default void forEachNode(BiConsumer<K,V> consumer)

    • setEdge

      E setEdge(K from, K to, E edge)
      Changes the edge between two nodes.
      Parameters:
      from - the node from which the edge should start
      to - the node to which this edge should go
      edge - the new value for the edge, a null value will be interpreted as a removal of the previous edge (if any)
      Returns:
      the previous edge between from and to

    • removeEdge

      void removeEdge(K from, K to)
      Removes the edge between two nodes.
      Parameters:
      from - the node from which this edge starts
      to - the node to which this edge goes

    • getEdge

      E getEdge(K from, K to)
      Retrieves the edge linking a node to another.
      Parameters:
      from - the node from which this edge starts
      to - the node to which this edge goes
      Returns:
      null if from and to are not linked by convention

    • getEdges

      Collection<E> getEdges()
      Retrieves the (unordered) list of all edges in the graph.
      Returns:
      a non null but possibly empty collection of edges

    • getTo

      K getTo(K from, E edge)
      Finds the node reachable from a given node and a given edge.

      If two Object.equals(Object) edges connect K to different nodes A and B, A or B will be returned non deterministically.

      Parameters:
      from - the node from which the edge starts
      edge - the edge to use
      Returns:
      the node to which from is connected via edge, or null if there is no such edge starting from from

    • getEdgesFrom

      Map<K,E> getEdgesFrom(K from)
      Retrieves all edges starting from a node and returns them along with the node they reach.

      If from is not contained in the graph, an empty map will be returned.

      Parameters:
      from - the node from which the edges start
      Returns:
      the edges (and the vertices' keys) that leave from

    • getEdgesTo

      Map<K,E> getEdgesTo(K to)
      A lot slower than getEdgesFrom(Object) since edges are indexed by their from node.
      Parameters:
      to - the node to which the edge go
      Returns:
      the vertices' keys and the edges that reach to

    • getReachers

      Set<K> getReachers(Set<K> included)
      Returns all the nodes that have at least one of their edges ending in a node included in the given set.
      Parameters:
      included - the nodes to be included
      Returns:
      the set containing all nodes that can reach one of the included nodes by following edges multiple times, it includes all the given nodes

    • getReached

      Set<K> getReached(Set<K> included)
      Returns all the nodes that can be reached from at least one of the included nodes.
      Parameters:
      included - the nodes to be included.
      Returns:
      the set containing all nodes that can be reached from one of the included nodes by following edges multiple times

    • hasEdge

      boolean hasEdge(K from, K to)
      Checks the existence of an edge between two nodes.

      Convention: an edge exist if getEdge(Object, Object) returns a non null value.

      Parameters:
      from - the node from which the edge should start
      to - the node to which this edge connects
      Returns:
      true if there is an edge between the 2 nodes, false otherwise

    • moveKey

      void moveKey(K from, K to)
      Replaces a key by another.

      Moves the value and all edges from and to the previous key to the new key.

      Parameters:
      from - the original value
      to - the destination value

    • filterEdges

      IDirectedGraph<K,V,E> filterEdges(Predicate<E> filter)
      Creates a directed graph with the same vertices but only the edges selected by a filter.
      Parameters:
      filter - tells for each edge if it should be copied in the new graph or not
      Returns:
      the new graph, it has less edges but the contained vertices and edges are the same objects than in the original graph

    • isAcyclic

      boolean isAcyclic()
      Checks whether or not this graph has cycles.
      Returns:
      true if the graph has no cycle (is acyclic), false otherwise