Class SimilarItemsGraph

java.lang.Object
org.troy.capstone.data_structures.SimilarItemsGraph
public class SimilarItemsGraph extends Object
Graph data structure to represent similar items. Uses an adjacency list representation.

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    static class 
    SimilarItemsGraph.Edge
    Inner class to represent an edge in the graph.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    protected List<SimilarItemsGraph.Edge>[]
    adjacencyList
    Adjacency list to represent edges between items.
    private final ItemRepo
    itemRepo
    Repository to store items.
    private static final float
    MIN_SIMILARITY_SCORE
    Minimum similarity score required for two items to be considered similar and have an edge between them in the graph.
    private static final int
    NUM_SIMILAR_ITEMS_TO_DISPLAY
    The number of similar items to display for selected items.
    protected int
    numItems
    Number of items in the graph.
    private final Table
    table
    The original table containing the items, used for retrieving items by index.

  • Constructor Summary

    Constructors
    Constructor
    Description
    SimilarItemsGraph()
    Default constructor.
    SimilarItemsGraph(ItemRepo itemRepo, Table table, Boolean buildGraph)
    Constructor for SimilarItemsGraph.

  • Method Summary

    Modifier and Type
    Method
    Description
    private void
    addEdge(int sourceItemIndex, int destItemIndex, float weight)
    Adds an undirected edge between two items in the graph with the given weight.
    private boolean
    canBuild(Boolean buildGraph)
    Determines whether the graph can be built based on the provided buildGraph value or the configuration.
    private List<SimilarItemsGraph.Edge>
    dijkstra(int startIndex)
    Basic algorithm taken from [2].
    private void
    fillGraph()
    Fills the graph with edges based on the similarity scores between items in the ItemRepo.
    List<VBox>
    findSimilarItems(String itemId)
    Finds similar items for the given item ID.

    Methods inherited from class Object

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

  • Field Details

    • MIN_SIMILARITY_SCORE

      private static final float MIN_SIMILARITY_SCORE
      Minimum similarity score required for two items to be considered similar and have an edge between them in the graph. Set to the 95th percentile of all similarity scores.
      See Also:

    • NUM_SIMILAR_ITEMS_TO_DISPLAY

      private static final int NUM_SIMILAR_ITEMS_TO_DISPLAY
      The number of similar items to display for selected items.
      See Also:

    • numItems

      protected int numItems
      Number of items in the graph.

    • itemRepo

      private final ItemRepo itemRepo
      Repository to store items. Iterated over when filling the graph.

    • table

      private final Table table
      The original table containing the items, used for retrieving items by index.

    • adjacencyList

      protected List<SimilarItemsGraph.Edge>[] adjacencyList
      Adjacency list to represent edges between items.

  • Constructor Details

    • SimilarItemsGraph

      public SimilarItemsGraph()
      Default constructor. Only used to allow for subclassing in the SimilarItemsGraphTest class. All fields are initialized to null.

    • SimilarItemsGraph

      public SimilarItemsGraph(ItemRepo itemRepo, Table table, Boolean buildGraph)
      Constructor for SimilarItemsGraph. Initializes the graph with the given ItemRepo.
      Parameters:
      itemRepo - The ItemRepo containing the items to be added to the graph.
      table - The original Table containing the items, used for retrieving items by index when filling the graph.
      buildGraph - A Boolean value indicating whether to build the graph. If null, the value from the configuration will be used.

  • Method Details

    • findSimilarItems

      public List<VBox> findSimilarItems(String itemId)
      Finds similar items for the given item ID.
      Parameters:
      itemId - The ID of the item for which to find similar items.
      Returns:
      A list of VBox panels representing the similar items.
      Throws:
      RuntimeException - if the item is not found in the hash map.

    • canBuild

      @Generated private boolean canBuild(Boolean buildGraph)
      Determines whether the graph can be built based on the provided buildGraph value or the configuration.
      Parameters:
      buildGraph - The buildGraph value to check. If null, the configuration value is used.
      Returns:
      true if the graph can be built, false otherwise.

    • addEdge

      private void addEdge(int sourceItemIndex, int destItemIndex, float weight)
      Adds an undirected edge between two items in the graph with the given weight.
      Parameters:
      sourceItemIndex - The index of the source item.
      destItemIndex - The index of the destination item.
      weight - The weight of the edge, representing the similarity score between the two items.
      Preconditions:
      sourceItemIndex and destItemIndex should be valid item indices corresponding to items in the graph. weight should be a non-negative float representing the similarity score between the two items.
      Postconditions:
      An undirected edge is added between the source and destination items in the graph with the specified weight. The adjacency list is updated to reflect the new edge. Nothing is done if the weight is below the minimum similarity score threshold.

    • fillGraph

      private void fillGraph()
      Fills the graph with edges based on the similarity scores between items in the ItemRepo.
      Preconditions:
      itemRepo should be properly initialized and contain valid items with a defined similarity method to calculate similarity scores between items. The number of items in the itemRepo should match the expected number of items in the graph.
      Postconditions:
      The graph is filled with undirected edges between items based on their similarity scores

    • dijkstra

      private List<SimilarItemsGraph.Edge> dijkstra(int startIndex)
      Basic algorithm taken from [2]. Computes the shortest paths from the start index to all other items in the graph.
      Parameters:
      startIndex - The index of the starting item from which to compute the shortest paths to all other items in the graph.
      Returns:
      A list of Edge objects, where each object contains the index of a similar item and its corresponding similarity score. The list is sorted in descending order of similarity scores and limited to the number of similar items to display.
      Preconditions:
      startIndex should be a valid item index corresponding to an item in the graph. The graph should be properly initialized with edges representing the similarity scores between items.
      Postconditions:
      The method returns a list of Edge objects, where each object contains the index of a similar item and its corresponding similarity score. The list is sorted in descending order of similarity scores and limited to the number of similar items to display. Items that are not reachable from the start index (i.e., have a distance of Float.MAX_VALUE) are excluded from the returned list.