Package de.xima.fc.utils

Class XGraphUtils

  • Direct Known Subclasses:
    GraphAlgos
    public class XGraphUtils
extends Object
    Helper methods for Graph and ValueGraph data structures.
    Since:
    8.0.0
    Author:
    XIMA MEDIA GmbH

    • Constructor Summary

      Constructors 
      Constructor Description
      XGraphUtils()  

    • 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, Iterable<? extends N> startNodes)
      Returns the set of nodes from which the node can be reached.
      static <N> Set<N> arrivingNodes​(com.google.common.graph.Graph<N> graph, N startNode)
      Returns the set of nodes from which the node can be reached.
      static <N,​V>
      Set<N>      		 arrivingNodes​(com.google.common.graph.ValueGraph<N,​? extends V> graph, Iterable<? extends N> startNodes, IValueGraphEdgePredicate<? super N,​? super V> edgeFilter)
      Returns the set of nodes from which the node can be reached.
      static <N,​I,​R>
      com.google.common.graph.ImmutableGraph<R>      		 immutableFromTreeAccessor​(N startNode, ITreeAccessor<N,​I> treeAccessor, com.google.common.graph.GraphBuilder<Object> builder, BiFunction<N,​I,​R> mapper)
      Creates a directed graph from a given start node and its children, recursively.
      static <N> Set<N> reachableNodes​(com.google.common.graph.Graph<N> graph, Iterable<? extends N> startNodes)
      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> Set<N> reachableNodes​(com.google.common.graph.Graph<N> graph, N startNode)
      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,​V>
      Set<N>      		 reachableNodes​(com.google.common.graph.ValueGraph<N,​? extends V> graph, Iterable<? extends N> startNodes, IValueGraphEdgePredicate<? super N,​? super V> edgeFilter)
      Taken from Graphs.reachableNodes(Graph, Object), but for value graphs and 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

      • XGraphUtils

        public XGraphUtils()

    • Method Detail

      • arrivingNodes

        public static <N> Set<N> arrivingNodes​(com.google.common.graph.Graph<N> graph,
                                       Iterable<? extends N> startNodes)
        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 traverse.
        startNodes - Nodes where to start traversal.
        Returns:
        A mutable set with 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.
        Since:
        8.0.0

      • arrivingNodes

        public static <N> Set<N> arrivingNodes​(com.google.common.graph.Graph<N> graph,
                                       N startNode)
        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 traverse.
        startNode - Node where to start traversal.
        Returns:
        A mutable set with 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.

      • arrivingNodes

        public static <N,​V> Set<N> arrivingNodes​(com.google.common.graph.ValueGraph<N,​? extends V> graph,
                                               Iterable<? extends N> startNodes,
                                               IValueGraphEdgePredicate<? super N,​? super V> edgeFilter)
        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.
        V - Type of the values associated with the edges in he graph.
        Parameters:
        graph - Graph to traverse.
        startNodes - Nodes where to start traversal.
        edgeFilter - Filter for the edges to respect when computing the arriving nodes. Each edge for which this filter return false is excluded. In other words, this method behaves as if it would first construct a new graph with the same nodes of the original graph and those edge for which the filter returns true; and then compute the arriving nodes on that new graph.
        Returns:
        A mutable set with 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 nodes themselves, unless a 0+ cycle with the node exists in the graph.
        Since:
        8.0.0

      • immutableFromTreeAccessor

        public static <N,​I,​R> com.google.common.graph.ImmutableGraph<R> immutableFromTreeAccessor​(N startNode,
                                                                                                      ITreeAccessor<N,​I> treeAccessor,
                                                                                                      com.google.common.graph.GraphBuilder<Object> builder,
                                                                                                      BiFunction<N,​I,​R> mapper)
        Creates a directed graph from a given start node and its children, recursively.
        Type Parameters:
        N - Type of the input nodes.
        I - Type of the ID of each node.
        R - Type of the output nodes.
        Parameters:
        startNode - Start or root node
        treeAccessor - How to access the children of an input node.
        builder - Graph builder to use for creating a new graph.
        mapper - How to map an input node o an output node.
        Returns:
        A graph with one edge for each (parent, child)from the input.

      • reachableNodes

        public static <N> Set<N> reachableNodes​(com.google.common.graph.Graph<N> graph,
                                        Iterable<? extends N> startNodes)
        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 traverse.
        startNodes - Nodes where to start traversal.
        Returns:
        A mutable set with 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.
        Since:
        8.0.0

      • reachableNodes

        public static <N> Set<N> reachableNodes​(com.google.common.graph.Graph<N> graph,
                                        N startNode)
        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 traverse.
        startNode - Node where to start traversal.
        Returns:
        A mutable set with 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.

      • reachableNodes

        public static <N,​V> Set<N> reachableNodes​(com.google.common.graph.ValueGraph<N,​? extends V> graph,
                                                Iterable<? extends N> startNodes,
                                                IValueGraphEdgePredicate<? super N,​? super V> edgeFilter)
        Taken from Graphs.reachableNodes(Graph, Object), but for value graphs and 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.
        V - Type of the values associated with the edges in he graph.
        Parameters:
        graph - Graph to traverse.
        startNodes - Nodes where to start traversal.
        edgeFilter - Filter for the edges to respect when computing the reachable nodes. Each edge for which this filter return false is excluded. In other words, this method behaves as if it would first construct a new graph with the same nodes of the original graph and those edge for which the filter returns true; and then compute the reachable nodes on that new graph.
        Returns:
        A mutable set with all nodes that are reachable from the given start node by traversing the edges of the graph. This will not include the nodes themselves, unless a 0+ cycle with the node exists in the graph.
        Since:
        8.0.0

      • 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 traverse.
        Returns:
        The transitive closure of the given graph.