Package graphlib.paths

Class Walk<T>

java.lang.Object
graphlib.paths.Walk<T>
All Implemented Interfaces:
Iterable<Node<T>>
public class Walk<T> extends Object implements Iterable<Node<T>>
Represents a walk in a graph, consisting of a sequence of nodes in the order in which they are visited. Nodes can be visited multiple times.

  • Constructor Summary

    Constructors
    Constructor
    Description
    Walk()
    Creates an empty walk.
    Walk(Node<T>... nodes)
    Creates a walk containing the given nodes in the given order.
    Walk(Walk<T> walk)
    Create a walk by copying another walk.

  • Method Summary

    Modifier and Type
    Method
    Description
    final void
    add(int i, Node<T> node)
    Inserts the given node at the given position in the current walk.
    final void
    add(Node<T> node)
    Adds a node to the end of the walk.
    final void
    append(Walk<T> walk)
    Appends a given walk at the end of the current walk.
    final void
    insert(Node<T> node, Walk<T> walk)
    Inserts the given walk after the given node in the current walk.
    final Iterator<Node<T>>
    iterator()
    Retrieves an iterator of all nodes contained in the walk.
    final int
    length()
    Retrieves the length of the walk (number of edges).
    final int
    size()
    Retrieves the size of the walk (number of nodes).

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    Methods inherited from interface java.lang.Iterable

    forEach, spliterator

  • Constructor Details

    • Walk

      public Walk()
      Creates an empty walk.

    • Walk

      @SafeVarargs public Walk(Node<T>... nodes)
      Creates a walk containing the given nodes in the given order.
      Parameters:
      nodes - nodes contained in walk

    • Walk

      public Walk(Walk<T> walk)
      Create a walk by copying another walk. A deep copy is made.
      Parameters:
      walk - walk to copy

  • Method Details

    • length

      public final int length()
      Retrieves the length of the walk (number of edges). The length is defined as the number of edges followed from one node to another. Returns zero if less than two nodes have been added to the walk.
      Returns:
      length of walk

    • size

      public final int size()
      Retrieves the size of the walk (number of nodes). The size is defined as the number of nodes contained in the walk.
      Returns:
      size of the walk

    • add

      public final void add(Node<T> node)
      Adds a node to the end of the walk.
      Parameters:
      node - node added to the walk
      Throws:
      NullPointerException - if node is null

    • append

      public final void append(Walk<T> walk)
      Appends a given walk at the end of the current walk. For example, given a walk w = [a,b,c,d,e], calling w.append([x,y,z]) modifies the walk w to [a,b,c,d,e,x,y,z]. The given walk is copied, due to which this operation runs in linear time in the length of the appended walk.
      Parameters:
      walk - walk to append

    • add

      public final void add(int i, Node<T> node)
      Inserts the given node at the given position in the current walk. Useful for insertions at the beginnen of the walk, as this method takes linear time in the given index i (and is independent of the length of the list).
      Parameters:
      i - index at which node should be inserted
      node - node to insert

    • insert

      public final void insert(Node<T> node, Walk<T> walk)
      Inserts the given walk after the given node in the current walk. This method can be used to join walks. For example, given a walk w = [a,b,c,d,e], calling w.insert(b, [x,y,z]) modifies the walk w to [a,b,x,y,z,c,d,e]. The given walk is copied when inserting, due to which an insert runs in linear time in the length of the inserted walk.

      In case the given node occurs multiple times in the current walk, the given walk is inserted after an arbitrary occurrence of this node. For example, given a walk w = [a,b,c,b,e], calling w.insert(b, [x,y,z]) either modifies the walk w to [a,b,x,y,z,c,b,e] or to [a,b,c,b,x,y,z,e] (which one is unpredictable).

      Note that, given a walk w = [a,b,c,d,e], calling w.insert(e, [x,y,z]) is equivalent to calling w.append([x,y,z]) and modifies the walk w to [a,b,c,d,e,x,y,z].

      Parameters:
      node - node after which the walk is to be inserted
      walk - walk to insert
      Throws:
      IllegalArgumentException - if the given node does not occur in the walk

    • iterator

      public final Iterator<Node<T>> iterator()
      Retrieves an iterator of all nodes contained in the walk. Nodes are returned by this iterator in the order in which they are visited. Possibly, the same node can be visited multiple times.
      Specified by:
      iterator in interface Iterable<T>
      Returns:
      iterator of nodes in walk