Class PatonCycleBase<V,​E>

  • Type Parameters:
    V - the vertex type.
    E - the edge type.
    All Implemented Interfaces:
    UndirectedCycleBase<V,​E>

    public class PatonCycleBase<V,​E>
    extends java.lang.Object
    implements UndirectedCycleBase<V,​E>
    Find a cycle base of an undirected graph using the Paton's algorithm.

    See:
    K. Paton, An algorithm for finding a fundamental set of cycles for an undirected linear graph, Comm. ACM 12 (1969), pp. 514-518.

    • Constructor Summary

      Constructors 
      Constructor Description
      PatonCycleBase()
      Create a cycle base finder with an unspecified graph.
      PatonCycleBase​(UndirectedGraph<V,​E> graph)
      Create a cycle base finder for the specified graph.
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      java.util.List<java.util.List<V>> findCycleBase()
      Finds a cycle base of the graph.
      Note that the full algorithm is executed on every call since the graph may have changed between calls.
      UndirectedGraph<V,​E> getGraph()
      Returns the graph on which the cycle base search algorithm is executed by this object.
      void setGraph​(UndirectedGraph<V,​E> graph)
      Sets the graph on which the cycle base search algorithm is executed by this object.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Constructor Detail

      • PatonCycleBase

        public PatonCycleBase()
        Create a cycle base finder with an unspecified graph.
      • PatonCycleBase

        public PatonCycleBase​(UndirectedGraph<V,​E> graph)
        Create a cycle base finder for the specified graph.
        Parameters:
        graph - - the DirectedGraph in which to find cycles.
        Throws:
        java.lang.IllegalArgumentException - if the graph argument is null.
    • Method Detail

      • setGraph

        public void setGraph​(UndirectedGraph<V,​E> graph)
        Sets the graph on which the cycle base search algorithm is executed by this object.
        Specified by:
        setGraph in interface UndirectedCycleBase<V,​E>
        Parameters:
        graph - the graph.
      • findCycleBase

        public java.util.List<java.util.List<V>> findCycleBase()
        Finds a cycle base of the graph.
        Note that the full algorithm is executed on every call since the graph may have changed between calls.
        Specified by:
        findCycleBase in interface UndirectedCycleBase<V,​E>
        Returns:
        A list of cycles constituting a cycle base for the graph. Possibly empty but never null.