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,​V>
      Optional<V>      		 edgeValue​(com.google.common.graph.ValueGraph<N,​V> graph, com.google.common.graph.EndpointPair<N> endpoints)
      Similar to ValueGraph.edgeValueOrDefault(EndpointPair, Object), but does not throw when the nodes do not exist in the graph and returns the an empty optional instead.
      static <N,​V>
      Optional<V>      		 edgeValue​(com.google.common.graph.ValueGraph<N,​V> graph, N nodeU, N nodeV)
      Similar to ValueGraph.edgeValue(EndpointPair), but does not throw when the nodes do not exist in the graph and returns an empty optional instead.
      static <N,​V>
      V      		 edgeValueOrDefault​(com.google.common.graph.ValueGraph<N,​V> graph, com.google.common.graph.EndpointPair<N> endpoints, V defaultValue)
      Similar to ValueGraph.edgeValueOrDefault(EndpointPair, Object), but does not throw when the nodes do not exist in the graph and returns the default value instead.
      static <N,​V>
      V      		 edgeValueOrDefault​(com.google.common.graph.ValueGraph<N,​V> graph, N nodeU, N nodeV, V defaultValue)
      Similar to ValueGraph.edgeValueOrDefault(EndpointPair, Object), but does not throw when the nodes do not exist in the graph and returns the default value instead.
      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> Iterable<N> leafNodes​(com.google.common.graph.Graph<N> graph)
      Finds all nodes in the graph that are leaf nodes, i.e.
      static <N> Iterable<N> leafNodes​(com.google.common.graph.ValueGraph<N,​?> graph)
      Finds all nodes in the graph that are leaf nodes, i.e.
      static <N> Set<N> leafNodeSet​(com.google.common.graph.Graph<N> graph)
      Finds all nodes in the graph that are leaf nodes, i.e.
      static <N> Set<N> leafNodeSet​(com.google.common.graph.ValueGraph<N,​?> graph)
      Finds all nodes in the graph that are leaf nodes, i.e.
      static <N> Set<N> predecessors​(com.google.common.graph.Graph<N> graph, N node)
      Same as Graph.predecessors(Object), but instead of throwing when the graph does not contain the node, returns an empty set.
      static <N,​V>
      Set<N>      		 predecessors​(com.google.common.graph.ValueGraph<N,​V> graph, N node)
      Same as ValueGraph.predecessors(Object), but instead of throwing when the graph does not contain the node, returns an empty set.
      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> Iterable<N> rootNodes​(com.google.common.graph.Graph<N> graph)
      Finds all nodes in the graph that are root nodes, i.e.
      static <N> Iterable<N> rootNodes​(com.google.common.graph.ValueGraph<N,​?> graph)
      Finds all nodes in the graph that are root nodes, i.e.
      static <N> Set<N> rootNodeSet​(com.google.common.graph.Graph<N> graph)
      Finds all nodes in the graph that are root nodes, i.e.
      static <N> Set<N> rootNodeSet​(com.google.common.graph.ValueGraph<N,​?> graph)
      Finds all nodes in the graph that are root nodes, i.e.
      static <N> Set<N> successors​(com.google.common.graph.Graph<N> graph, N node)
      Same as Graph.successors(Object), but instead of throwing when the graph does not contain the node, returns an empty set.
      static <N,​V>
      Set<N>      		 successors​(com.google.common.graph.ValueGraph<N,​V> graph, N node)
      Same as ValueGraph.successors(Object), but instead of throwing when the graph does not contain the node, returns an empty set.
      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.
      static <N> N treeRoot​(com.google.common.graph.Graph<N> graph)
      Finds the root node of the given tree, i.e.
      static <N> N treeRoot​(com.google.common.graph.ValueGraph<N,​?> graph)
      Finds the root node of the given tree, i.e.

    • 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

      • edgeValue

        public static <N,​V> Optional<V> edgeValue​(com.google.common.graph.ValueGraph<N,​V> graph,
                                                com.google.common.graph.EndpointPair<N> endpoints)
        Similar to ValueGraph.edgeValueOrDefault(EndpointPair, Object), but does not throw when the nodes do not exist in the graph and returns the an empty optional instead.
        Type Parameters:
        N - Type of the nodes in the graph.
        V - Type of the values of each node.
        Parameters:
        graph - Graph to process.
        endpoints - End points of the edge.
        Returns:
        The value for the edge, or empty when not found.

      • edgeValue

        public static <N,​V> Optional<V> edgeValue​(com.google.common.graph.ValueGraph<N,​V> graph,
                                                N nodeU,
                                                N nodeV)
        Similar to ValueGraph.edgeValue(EndpointPair), but does not throw when the nodes do not exist in the graph and returns an empty optional instead.
        Type Parameters:
        N - Type of the nodes in the graph.
        V - Type of the values of each node.
        Parameters:
        graph - Graph to process.
        nodeU - Start point of the edge.
        nodeV - End point of the edge.
        Returns:
        The value for the edge, or empty when not found.

      • edgeValueOrDefault

        public static <N,​V> V edgeValueOrDefault​(com.google.common.graph.ValueGraph<N,​V> graph,
                                               com.google.common.graph.EndpointPair<N> endpoints,
                                               V defaultValue)
        Similar to ValueGraph.edgeValueOrDefault(EndpointPair, Object), but does not throw when the nodes do not exist in the graph and returns the default value instead.
        Type Parameters:
        N - Type of the nodes in the graph.
        V - Type of the values of each node.
        Parameters:
        graph - Graph to process.
        endpoints - End points of the edge.
        defaultValue - Default value to return when no data is found.
        Returns:
        The value for the edge, or the default value when not found.

      • edgeValueOrDefault

        public static <N,​V> V edgeValueOrDefault​(com.google.common.graph.ValueGraph<N,​V> graph,
                                               N nodeU,
                                               N nodeV,
                                               V defaultValue)
        Similar to ValueGraph.edgeValueOrDefault(EndpointPair, Object), but does not throw when the nodes do not exist in the graph and returns the default value instead.
        Type Parameters:
        N - Type of the nodes in the graph.
        V - Type of the values of each node.
        Parameters:
        graph - Graph to process.
        nodeU - Start point of the edge.
        nodeV - End point of the edge.
        defaultValue - Default value to return when no data is found.
        Returns:
        The value for the edge, or the default value when not found.

      • 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.

      • leafNodes

        public static <N> Iterable<N> leafNodes​(com.google.common.graph.Graph<N> graph)
        Finds all nodes in the graph that are leaf nodes, i.e. that do not have outgoing edges.
        Type Parameters:
        N - Type of the nodes.
        Parameters:
        graph - Graph to process.
        Returns:
        All leaf nodes in the given graph.
        Since:
        8.1.0

      • leafNodes

        public static <N> Iterable<N> leafNodes​(com.google.common.graph.ValueGraph<N,​?> graph)
        Finds all nodes in the graph that are leaf nodes, i.e. that do not have outgoing edges.
        Type Parameters:
        N - Type of the nodes.
        Parameters:
        graph - Graph to process.
        Returns:
        All leaf nodes in the given graph.
        Since:
        8.1.0

      • leafNodeSet

        public static <N> Set<N> leafNodeSet​(com.google.common.graph.Graph<N> graph)
        Finds all nodes in the graph that are leaf nodes, i.e. that do not have outgoing edges.
        Type Parameters:
        N - Type of the nodes.
        Parameters:
        graph - Graph to process.
        Returns:
        All leaf nodes in the given graph.
        Since:
        8.1.0

      • leafNodeSet

        public static <N> Set<N> leafNodeSet​(com.google.common.graph.ValueGraph<N,​?> graph)
        Finds all nodes in the graph that are leaf nodes, i.e. that do not have outgoing edges.
        Type Parameters:
        N - Type of the nodes.
        Parameters:
        graph - Graph to process.
        Returns:
        All leaf nodes in the given graph.
        Since:
        8.1.0

      • predecessors

        public static <N> Set<N> predecessors​(com.google.common.graph.Graph<N> graph,
                                      N node)
        Same as Graph.predecessors(Object), but instead of throwing when the graph does not contain the node, returns an empty set.
        Type Parameters:
        N - Type of the nodes in the graph.
        Parameters:
        graph - Graph to process.
        node - A node of the graph.
        Returns:
        The set of predecessors of the node, empty when the graph does not contain the node.

      • predecessors

        public static <N,​V> Set<N> predecessors​(com.google.common.graph.ValueGraph<N,​V> graph,
                                              N node)
        Same as ValueGraph.predecessors(Object), but instead of throwing when the graph does not contain the node, returns an empty set.
        Type Parameters:
        N - Type of the nodes in the graph.
        Parameters:
        graph - Graph to process.
        node - A node of the graph.
        Returns:
        The set of predecessors of the node, empty when the graph does not contain the node.

      • 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

      • rootNodes

        public static <N> Iterable<N> rootNodes​(com.google.common.graph.Graph<N> graph)
        Finds all nodes in the graph that are root nodes, i.e. that do not have incoming edges.
        Type Parameters:
        N - Type of the nodes.
        Parameters:
        graph - Graph to process.
        Returns:
        All root nodes in the given graph.
        Since:
        8.1.0

      • rootNodes

        public static <N> Iterable<N> rootNodes​(com.google.common.graph.ValueGraph<N,​?> graph)
        Finds all nodes in the graph that are root nodes, i.e. that do not have incoming edges.
        Type Parameters:
        N - Type of the nodes.
        Parameters:
        graph - Graph to process.
        Returns:
        All root nodes in the given graph.
        Since:
        8.1.0

      • rootNodeSet

        public static <N> Set<N> rootNodeSet​(com.google.common.graph.Graph<N> graph)
        Finds all nodes in the graph that are root nodes, i.e. that do not have incoming edges.
        Type Parameters:
        N - Type of the nodes.
        Parameters:
        graph - Graph to process.
        Returns:
        All root nodes in the given graph.
        Since:
        8.1.0

      • rootNodeSet

        public static <N> Set<N> rootNodeSet​(com.google.common.graph.ValueGraph<N,​?> graph)
        Finds all nodes in the graph that are root nodes, i.e. that do not have incoming edges.
        Type Parameters:
        N - Type of the nodes.
        Parameters:
        graph - Graph to process.
        Returns:
        All root nodes in the given graph.
        Since:
        8.1.0

      • successors

        public static <N> Set<N> successors​(com.google.common.graph.Graph<N> graph,
                                    N node)
        Same as Graph.successors(Object), but instead of throwing when the graph does not contain the node, returns an empty set.
        Type Parameters:
        N - Type of the nodes in the graph.
        Parameters:
        graph - Graph to process.
        node - A node of the graph.
        Returns:
        The set of successors of the node, empty when the graph does not contain the node.

      • successors

        public static <N,​V> Set<N> successors​(com.google.common.graph.ValueGraph<N,​V> graph,
                                            N node)
        Same as ValueGraph.successors(Object), but instead of throwing when the graph does not contain the node, returns an empty set.
        Type Parameters:
        N - Type of the nodes in the graph.
        Parameters:
        graph - Graph to process.
        node - A node of the graph.
        Returns:
        The set of successors of the node, empty when the graph does not contain the node.

      • 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.

      • treeRoot

        public static <N> N treeRoot​(com.google.common.graph.Graph<N> graph)
        Finds the root node of the given tree, i.e. the first of all rootNodes(Graph). Use this method only when you are certain your graph is a tree!
        Type Parameters:
        N - Type of the nodes.
        Parameters:
        graph - Tree to process.
        Returns:
        The root node in the given graph, may be null when the graph is not a tree.
        Since:
        8.1.0

      • treeRoot

        public static <N> N treeRoot​(com.google.common.graph.ValueGraph<N,​?> graph)
        Finds the root node of the given tree, i.e. the first of all rootNodes(Graph). Use this method only when you are certain your graph is a tree!
        Type Parameters:
        N - Type of the nodes.
        Parameters:
        graph - Tree to process.
        Returns:
        The root node in the given graph, may be null when the graph is not a tree.
        Since:
        8.1.0