Package org.drip.service.common

Class GraphUtil

java.lang.Object
org.drip.service.common.GraphUtil
public class GraphUtil
extends java.lang.Object
GraphUtil implements Graph Utility Functions. It implements the following Functions:
  • Check if the Graph is Bipartite
  • Decode all possible Combinations of the Number
  • Establish the Separate Components connecting the Items
  • Given an undirected graph, find out all the vertices when removed will make the graph disconnected. Initially the graph is connected
  • There are N cities numbered from 1 to N
    • You are given connections, where each connections[i] = [city1, city2, cost] represents the cost to connect city1 and city2 together. (A connection is bidirectional: connecting city1 and city2 is the same as connecting city2 and city1)
    • Return the minimum cost so that for every pair of cities, there exists a path of connections (possibly of length 1) that connects those two cities together. The cost is the sum of the connection costs used. If the task is impossible, return -1

Module Computational Core Module
Library Computation Support
Project Environment, Product/Definition Containers, and Scenario/State Manipulation APIs
Package Assorted Data Structures Support Utilities
Author:
Lakshmi Krishnamurthy

  • Constructor Summary

    Constructors
    Constructor Description
    GraphUtil()  

  • Method Summary

    Modifier and Type Method Description
    static java.util.ArrayList<java.lang.Integer> CriticalNodes​(int[][] edgeArray)
    Given an undirected graph, find out all the vertices when removed will make the graph disconnected.
    static java.util.Set<java.lang.String> DecodeCombinations​(java.lang.String number)
    Decode all possible Combinations of the Number
    static boolean IsGraphBipartite​(int[][] graph)
    Check if the Graph is Bipartite
    static java.util.ArrayList<java.util.HashSet<java.lang.String>> LargestGroup​(java.util.List<java.util.List<java.lang.String>> itemListSequence)
    Establish the Separate Components connecting the Items
    static int MSPCost​(int[][] weightedEdgeArray)
    There are N cities numbered from 1 to N.

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • GraphUtil

      public GraphUtil()

  • Method Details

    • IsGraphBipartite

      public static final boolean IsGraphBipartite​(int[][] graph)
      Check if the Graph is Bipartite
      Parameters:
      graph - Graph as an Adjacency List
      Returns:
      TRUE - The Graph is Bipartite

    • DecodeCombinations

      public static final java.util.Set<java.lang.String> DecodeCombinations​(java.lang.String number)
      Decode all possible Combinations of the Number
      Parameters:
      number - The Input Number
      Returns:
      All possible Combinations of the Number

    • LargestGroup

      public static final java.util.ArrayList<java.util.HashSet<java.lang.String>> LargestGroup​(java.util.List<java.util.List<java.lang.String>> itemListSequence)
      Establish the Separate Components connecting the Items
      Parameters:
      itemListSequence - Sequence of Items Lists
      Returns:
      The Connected Components

    • CriticalNodes

      public static final java.util.ArrayList<java.lang.Integer> CriticalNodes​(int[][] edgeArray)
      Given an undirected graph, find out all the vertices when removed will make the graph disconnected. Initially the graph is connected.
      Parameters:
      edgeArray - Array of the Edges
      Returns:
      List of Critical Nodes

    • MSPCost

      public static final int MSPCost​(int[][] weightedEdgeArray)
      There are N cities numbered from 1 to N. You are given connections, where each connections[i] = [city1, city2, cost] represents the cost to connect city1 and city2 together. (A connection is bidirectional: connecting city1 and city2 is the same as connecting city2 and city1) Return the minimum cost so that for every pair of cities, there exists a path of connections (possibly of length 1) that connects those two cities together. The cost is the sum of the connection costs used. If the task is impossible, return -1.
      Parameters:
      weightedEdgeArray - Array of Weighted Edges
      Returns:
      The MSP Cost