Package de.xima.fc.workflow

Class GraphAlgos

  • public class GraphAlgos
extends Object
    Helper methods for graph data structures.
    Since:
    7.0.0
    Author:
    XIMA MEDIA GmbH

    • Constructor Summary

      Constructors 
      Constructor Description
      GraphAlgos()  

    • Method Summary

      All Methods Static Methods Concrete Methods 
      Modifier and Type Method Description
      static <N> Set<N> arrivingNodes​(com.google.common.graph.Graph<N> graph, N node)
      Returns the set of nodes from which the node can be reached.
      static <N> Set<N> reachableNodes​(com.google.common.graph.Graph<N> graph, N node)
      Taken from Graphs.reachableNodes(Graph, Object), but fixed so that a node is only reachable from itself when there exists has a 0+ loop cycle with the loop.
      static <N> com.google.common.graph.Graph<N> transitiveClosure​(com.google.common.graph.Graph<N> graph)
      Taken from Graphs.transitiveClosure(Graph), but fixed so it does not add self-loops.

    • Constructor Detail

      • GraphAlgos

        public GraphAlgos()

    • Method Detail

      • arrivingNodes

        public static <N> Set<N> arrivingNodes​(com.google.common.graph.Graph<N> graph,
                                       N node)
        Returns the set of nodes from which the node can be reached. Node B is defined as reachable from node A if there exists a path (a sequence of adjacent outgoing edges) starting at node A and ending at node B. Note that a node is only reachable from itself when there exists a 0+ cycle with node in the graph.

        This is a "snapshot" based on the current topology of graph, rather than a live view of the set of nodes reachable from node. In other words, the returned Set will not be updated after modifications to graph.

        Type Parameters:
        N - Type of the nodes in the graph.
        Parameters:
        graph - Graph to process.
        node - Node to process.
        Returns:
        All nodes that are from which the given start node can be reached by traversing the edges of the graph. This will not include the node itself, unless a 0+ cycle with the node exists in the graph.

      • reachableNodes

        public static <N> Set<N> reachableNodes​(com.google.common.graph.Graph<N> graph,
                                        N node)
        Taken from Graphs.reachableNodes(Graph, Object), but fixed so that a node is only reachable from itself when there exists has a 0+ loop cycle with the loop. Also does not throw an illegal argument exception when the node is not contained in the graph.

        Returns the set of nodes that are reachable from node. Node B is defined as reachable from node A if there exists a path (a sequence of adjacent outgoing edges) starting at node A and ending at node B. Note that a node is only reachable from itself when there exists a 0+ cycle with node in the graph.

        This is a "snapshot" based on the current topology of graph, rather than a live view of the set of nodes reachable from node. In other words, the returned Set will not be updated after modifications to graph.

        Type Parameters:
        N - Type of the nodes in the graph.
        Parameters:
        graph - Graph to process.
        node - Node to process.
        Returns:
        All nodes that are reachable from the given start node by traversing the edges of the graph. This will not include the node itself, unless a 0+ cycle with the node exists in the graph.

      • transitiveClosure

        public static <N> com.google.common.graph.Graph<N> transitiveClosure​(com.google.common.graph.Graph<N> graph)
        Taken from Graphs.transitiveClosure(Graph), but fixed so it does not add self-loops. Can be replaced with Graphs.transitiveClosure(Graph) when https://github.com/google/guava/issues/2778 is resolved.

        Returns the transitive closure of graph. The transitive closure of a graph is another graph with an edge connecting node A to node B if node B is reachable from node A.

        This is a "snapshot" based on the current topology of graph, rather than a live view of the transitive closure of graph. In other words, the returned Graph will not be updated after modifications to graph.

        Type Parameters:
        N - Type of the nodes in the graph.
        Parameters:
        graph - Graph to process.
        Returns:
        The transitive closure of the given graph.