Class LoopDetector

java.lang.Object
neqsim.process.equipment.network.LoopDetector
All Implemented Interfaces:
Serializable
public class LoopDetector extends Object implements Serializable
Detects independent loops in a pipeline network using graph theory algorithms.

Uses Depth-First Search (DFS) to build a spanning tree of the network graph. Non-tree edges (chords) each define exactly one independent loop. The number of independent loops equals: E - V + 1 (for a connected graph) where E is the number of edges (pipelines) and V is the number of vertices (nodes).

Algorithm

  1. Build a graph representation from node/edge data
  2. Run DFS to create a spanning tree
  3. Identify chord edges (edges not in the spanning tree)
  4. For each chord, trace the fundamental cycle (loop)

References

  • Cormen, T.H. et al. "Introduction to Algorithms" - Graph algorithms
  • Cross, H. (1936). "Analysis of Flow in Networks of Conduits or Conductors."
Version:
1.0
Author:
Even Solbraa
See Also:

  • Field Details

    • serialVersionUID

      private static final long serialVersionUID
      See Also:

    • adjacencyList

      private final Map<String, List<LoopDetector.Edge>> adjacencyList
      Adjacency list representation of the network graph.

    • allEdges

      private final List<LoopDetector.Edge> allEdges
      All edges in the graph (forward direction only).

    • nodes

      private final Set<String> nodes
      Set of node names.

    • parent

      private final Map<String,String> parent
      Parent pointers from DFS spanning tree.

    • parentEdge

      private final Map<String, LoopDetector.Edge> parentEdge
      Edge used to reach each node in spanning tree.

    • depth

      private final Map<String,Integer> depth
      Depth of each node in the spanning tree.

    • spanningTreePipes

      private final Set<String> spanningTreePipes
      Set of pipe names that are in the spanning tree.

    • independentLoops

      private List<NetworkLoop> independentLoops
      Detected independent loops.

    • loopIdCounter

      private int loopIdCounter
      Counter for generating loop IDs.

  • Constructor Details

    • LoopDetector

      public LoopDetector()
      Create a new loop detector.

  • Method Details

    • addEdge

      public void addEdge(String fromNode, String toNode, String pipeName)
      Add an edge (pipe) to the graph.
      Parameters:
      fromNode - source node name
      toNode - target node name
      pipeName - pipe name

    • clear

      public void clear()
      Clear all data and prepare for new analysis.

    • findLoops

      public List<NetworkLoop> findLoops()
      Detect all independent loops in the network.
      Returns:
      list of independent loops

    • buildSpanningTree

      private void buildSpanningTree()
      Build a spanning tree using DFS.

    • findChordLoops

      private void findChordLoops()
      Find chord edges and construct the fundamental cycle for each.

    • traceFundamentalCycle

      private NetworkLoop traceFundamentalCycle(LoopDetector.Edge chord)
      Trace the fundamental cycle created by a chord edge.

      The fundamental cycle consists of the chord edge plus the unique path in the spanning tree between the chord's endpoints.

      Parameters:
      chord - the chord edge
      Returns:
      the network loop, or null if no valid loop

    • pathToRoot

      private List<String> pathToRoot(String node)
      Find the path from a node to the root of its spanning tree.
      Parameters:
      node - starting node
      Returns:
      list of nodes from node to root (inclusive)

    • findEdgeBetween

      private LoopDetector.Edge findEdgeBetween(String from, String to)
      Find an edge between two adjacent nodes.
      Parameters:
      from - source node
      to - target node
      Returns:
      the edge, or null if not found

    • getLoopCount

      public int getLoopCount()
      Get the number of independent loops.
      Returns:
      number of independent loops

    • getLoops

      public List<NetworkLoop> getLoops()
      Get the detected independent loops.
      Returns:
      unmodifiable list of loops

    • hasLoops

      public boolean hasLoops()
      Check if the network contains any loops.
      Returns:
      true if the network has loops (is not a tree)

    • getNodeCount

      public int getNodeCount()
      Get the number of nodes in the graph.
      Returns:
      number of nodes

    • getEdgeCount

      public int getEdgeCount()
      Get the number of edges in the graph.
      Returns:
      number of edges