de.topobyte.adt.graph

Class Graph<T>

  • Type Parameters:
    T - the type of node elements.
    Direct Known Subclasses:
    UndirectedGraph 

    public class Graph<T>
extends Object
    A class to represent an unweighted directed graph.

    • Constructor Summary

      Constructors

      Constructor and Description
      Graph()
       

    • Method Summary

      Modifier and Type Method and Description
      void addEdge(T a, T b)
      Add this edge to the graph.
      void addNode(T node)
      Add a node to the graph.
      void addNodes(Set<T> nodesToAdd)
      Add all these nodes to the graph.
      boolean containsEdge(T a, T b)
      Returns true if this graph contains the specified edge from a to b.
      boolean containsNode(T node)
      Returns true if this graph contains the specified node.
      int degreeIn(T node)
      Get the number of incoming edges.
      int degreeOut(T node)
      Get the number of outgoing edges.
      Set<T> getEdgesIn(T node)
      Get all incoming edges (the nodes that can be reached via these edges).
      Set<T> getEdgesOut(T node)
      Get all outgoing edges (the nodes that can be reached via these edges).
      Collection<T> getNodes()
      Return the nodes of this graph.
      Set<Set<T>> getPartition()
      Get a partition of the graph.
      Set<T> getReachable(T node)
      Find all nodes reachable in the graph starting from the specified node.
      void removeAllNodes(Collection<T> toRemove)
      Remove a collection of nodes from the graph.
      void removeEdge(T a, T b)
      Remove this edge from graph.
      void removeNode(T node)
      Remove a node from the graph.
      Graph<T> reversed()
      Create a graph with the same nodes as this one, just all edges reversed.

    • Constructor Detail

      • Graph

        public Graph()

    • Method Detail

      • addNode

        public void addNode(T node)
        Add a node to the graph.
        Parameters:
        node - the node to add.

      • containsNode

        public boolean containsNode(T node)
        Returns true if this graph contains the specified node.
        Parameters:
        node - node whose presence in this graph is to be tested.
        Returns:
        true if this graph contains the specified node.

      • removeNode

        public void removeNode(T node)
        Remove a node from the graph.
        Parameters:
        node - the node to remove.

      • removeAllNodes

        public void removeAllNodes(Collection<T> toRemove)
        Remove a collection of nodes from the graph.
        Parameters:
        toRemove - the nodes to remove.

      • addNodes

        public void addNodes(Set<T> nodesToAdd)
        Add all these nodes to the graph.
        Parameters:
        nodesToAdd - a set of nodes to add.

      • addEdge

        public void addEdge(T a,
                    T b)
        Add this edge to the graph.
        Parameters:
        a - a node.
        b - another node.

      • containsEdge

        public boolean containsEdge(T a,
                            T b)
        Returns true if this graph contains the specified edge from a to b.
        Parameters:
        a - a node.
        b - another node.
        Returns:
        true if this graph contains an edge from a to b.

      • removeEdge

        public void removeEdge(T a,
                       T b)
        Remove this edge from graph.
        Parameters:
        a - a node.
        b - another node.

      • getNodes

        public Collection<T> getNodes()
        Return the nodes of this graph.
        Returns:
        the set of nodes.

      • getEdgesOut

        public Set<T> getEdgesOut(T node)
        Get all outgoing edges (the nodes that can be reached via these edges).
        Parameters:
        node - the node whose edges to get.
        Returns:
        a set of reachable nodes.

      • getEdgesIn

        public Set<T> getEdgesIn(T node)
        Get all incoming edges (the nodes that can be reached via these edges).
        Parameters:
        node - the node whose incoming edges to get.
        Returns:
        a set of nodes that can reach this one.

      • degreeIn

        public int degreeIn(T node)
        Get the number of incoming edges.
        Parameters:
        node - the node.
        Returns:
        the number of incoming edges.

      • degreeOut

        public int degreeOut(T node)
        Get the number of outgoing edges.
        Parameters:
        node - the node.
        Returns:
        the number of outgoing edges.

      • getPartition

        public Set<Set<T>> getPartition()
        Get a partition of the graph. Each subset consist of a set of nodes that are connected. This currently expects the graph to be undirected.
        Returns:
        a partition of the graph.

      • getReachable

        public Set<T> getReachable(T node)
        Find all nodes reachable in the graph starting from the specified node.
        Parameters:
        node - the node to start the traversal of the graph from.
        Returns:
        a set containing all reachable nodes of the graph.

      • reversed

        public Graph<T> reversed()
        Create a graph with the same nodes as this one, just all edges reversed. Note that the returned graph uses the same internal data structures as the original graph so changes on the reversed graph will affect the original graph and vice versa.
        Returns:
        a graph with all edges reversed.