Class Node


  • public final class Node
    extends java.lang.Object
    A node (vertex) in the network.
    Version:
    4.8
    • Constructor Summary

      Constructors 
      Constructor Description
      Node​(java.lang.String name, int balance)  
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      (package private) void computePotentials()
      Recomputes the potential & depth values in the subtree rooted at this node.
      Node lca​(Node that)
      Finds the root of the smallest subtree that contains both this node and that node.
      void markTree​(boolean setMark)
      Sets or clears a mark on a subtree rooted at this node
      Node predecessorOnThread()
      Finds the predecessor of this node on the thread.
      Node rightMostLeaf()
      Finds the last node on the thread that has a larger depth than this node.
      java.lang.String toString()  
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
    • Field Detail

      • initialBalance

        public final int initialBalance
        for debug only
      • name

        public final java.lang.String name
        a label, great for debugging
      • potential

        public int potential
        the potential (or dual variable) of the network simplex
      • balance

        public int balance
        balance of the last feasible flow
      • deltaBalance

        public int deltaBalance
        change in balance for the next flow computation
      • artificial

        public Arc artificial
        connects this node to the root
      • toParent

        public Arc toParent
      • parent

        public Node parent
      • thread

        public Node thread
      • depth

        public int depth
      • marked

        boolean marked
        marks the cut (S,T) for dual pivot
      • degree

        public int degree
        number of connected arcs
      • adjacencyList

        public Arc[] adjacencyList
        adjacency list (recorded when degree reaches 2)
    • Constructor Detail

      • Node

        public Node​(java.lang.String name,
                    int balance)
    • Method Detail

      • lca

        public Node lca​(Node that)
        Finds the root of the smallest subtree that contains both this node and that node.
        Parameters:
        that - another node
        Returns:
        the least common ancestor of this & that
      • rightMostLeaf

        public Node rightMostLeaf()
        Finds the last node on the thread that has a larger depth than this node. Note that if this node is a leaf node then 'this' is returned.
        Returns:
        the last node on the thread that is in the subtree of this node
      • predecessorOnThread

        public Node predecessorOnThread()
        Finds the predecessor of this node on the thread. It uses the parent node as starting point of the search. (Hence, this method cannot be invoked on the root)
        Returns:
        the node i with i.thread == this
      • markTree

        public void markTree​(boolean setMark)
        Sets or clears a mark on a subtree rooted at this node
        Parameters:
        setMark - whether to set or clear the mark
      • computePotentials

        void computePotentials()
        Recomputes the potential & depth values in the subtree rooted at this node.
      • toString

        public java.lang.String toString()
        Overrides:
        toString in class java.lang.Object