Package dev.roanh.gmark.util

Class UniqueGraph<V,E>

java.lang.Object
dev.roanh.gmark.util.UniqueGraph<V,E>
Type Parameters:
V - Type of the data stored at vertices.
E - Type of the data stored at edges.
Direct Known Subclasses:
ConfigGraph, EdgeGraph, SchemaGraph, SelectivityGraph
public class UniqueGraph<V,E> extends Object
Utility class to model a graph with directed edges. Both edges and nodes are assumed to be unique, that is, no two edges or nodes exist that cannot be distinguished. Both vertices and edges support storing some form of data. The data stored at nodes is assumed to uniquely identify a given node. This class does not perform a lot of integrity checks in order to stay performant.

  • Field Details

    • nodeMap

      private Map<V,UniqueGraph.GraphNode<V,E>> nodeMap
      Map for efficient graph node lookup from the data stored a specific node. Note that it is assumed that there are no nodes that store the same data.

    • nodes

      private List<UniqueGraph.GraphNode<V,E>> nodes
      List of all nodes in this graph.

    • edges

      private List<UniqueGraph.GraphEdge<V,E>> edges
      List of all edges in this graph.

    • nextNodeID

      private int nextNodeID
      The ID to assign to the next node added to the graph.

  • Constructor Details

    • UniqueGraph

      public UniqueGraph()

  • Method Details

    • removeNodeIf

      public List<UniqueGraph.GraphNode<V,E>> removeNodeIf(Predicate<UniqueGraph.GraphNode<V,E>> predicate)
      Removes all nodes from the graph that match the given predicate. The returned nodes still reference the remaining nodes in the graph but remaining graph nodes no longer reference the removed nodes.
      Parameters:
      predicate - The predicate nodes should match to be removed.
      Returns:
      A list of removed graph nodes.

    • getNodes

      public List<UniqueGraph.GraphNode<V,E>> getNodes()
      Gets a list of all nodes in this graph.
      Returns:
      All nodes in this graph.

    • getEdges

      public List<UniqueGraph.GraphEdge<V,E>> getEdges()
      Gets a list of all edges in this graph.
      Returns:
      All edges in this graph.

    • getNode

      public UniqueGraph.GraphNode<V,E> getNode(V data)
      Gets a single node from this graph by the data that is stored at the node to find. Note that nodes are assumed to store information that uniquely identifies them, meaning the given data uniquely identifies a single node.
      Parameters:
      data - The data stored at the node to find.
      Returns:
      The node that stores the given data or null if no such node exists.

    • addUniqueNode

      public UniqueGraph.GraphNode<V,E> addUniqueNode(V data)
      Adds a new unique node to this graph that is associated with the given data. The data given is assumed to uniquely identify a single node in the whole graph. If this graph already contains a node associated with the same data then a new node is not added to the graph and the existing node is returned instead.
      Parameters:
      data - The data to associated with the node.
      Returns:
      The (newly added) node that is associated with the given data.

    • getEdgeCount

      public int getEdgeCount()
      Gets the total number of edges in the graph.
      Returns:
      The total number of edges in the graph.

    • getNodeCount

      public int getNodeCount()
      Gets the total number of nodes in the graph.
      Returns:
      The total number of nodes in the graph.

    • getEdge

      public UniqueGraph.GraphEdge<V,E> getEdge(V source, V target)
      Gets the unlabelled edge connecting the node associated with the given source data and the node associated with the given target data.
      Parameters:
      source - The data to identify the source node.
      target - The data to identify the target node.
      Returns:
      The edge connecting the source and target node or null if no such node exists.

    • getEdge

      public UniqueGraph.GraphEdge<V,E> getEdge(V source, V target, E data)
      Gets the edge with the given label data connecting the node associated with the given source data and the node associated with the given target data.
      Parameters:
      source - The data to identify the source node.
      target - The data to identify the target node.
      data - The edge label data.
      Returns:
      The edge connecting the source and target node or null if no such node exists.

    • addUniqueEdge

      public void addUniqueEdge(V source, V target, E data)
      Adds a new unique edge with the given label data from the node associated with the given source data to the existing node associated with the given target data.
      Parameters:
      source - The data to identify the node to connect from with.
      target - The data to identify the node to connect to with.
      data - The edge label data.

    • addUniqueEdge

      public void addUniqueEdge(UniqueGraph.GraphNode<V,E> source, V target, E data)
      Adds a new unique edge with the given label data from the given source node to the existing node associated with the given target data.
      Parameters:
      source - The source node to add an edge from.
      target - The data to identify the node to connect to with.
      data - The edge label data.

    • addUniqueEdge

      public void addUniqueEdge(V source, UniqueGraph.GraphNode<V,E> target, E data)
      Adds a new unique edge with the given label data to the given target node from the existing node associated with the given source data.
      Parameters:
      source - The data to identify the node to connect from with.
      target - The target node to add an edge to.
      data - The edge label data.

    • addUniqueEdge

      public void addUniqueEdge(V source, V target)
      Adds a new unique edge without any label from the node associated with the given source data to the existing node associated with the given target data.
      Parameters:
      source - The data to identify the node to connect from with.
      target - The data to identify the node to connect to with.

    • addUniqueEdge

      public void addUniqueEdge(UniqueGraph.GraphNode<V,E> source, V target)
      Adds a new unique edge without any label from the given source node to the existing node associated with the given target data.
      Parameters:
      source - The source node to add an edge from.
      target - The data to identify the node to connect to with.

    • addUniqueEdge

      public void addUniqueEdge(V source, UniqueGraph.GraphNode<V,E> target)
      Adds a new unique edge without any label to this node from the existing node associated with the given source data.
      Parameters:
      source - The data to identify the node to connect from with.
      target - The target node to add an edge to.

    • addUniqueEdge

      public void addUniqueEdge(UniqueGraph.GraphNode<V,E> source, UniqueGraph.GraphNode<V,E> target)
      Adds a new unique edge without any label from the given source node to the given target node to connect to.
      Parameters:
      source - The source node to add an edge from.
      target - The target node to add an edge to.

    • addUniqueEdge

      public void addUniqueEdge(UniqueGraph.GraphNode<V,E> source, UniqueGraph.GraphNode<V,E> target, E data)
      Adds a new unique edge with the given label data from the given source node to the given target node to connect to.
      Parameters:
      source - The source node to add an edge from.
      target - The target node to add an edge to.
      data - The edge label data.

    • toAdjacencyList

      public int[][] toAdjacencyList()
      Computes the adjacency list representation of this graph. For this the unique ID of every graph node is used (see UniqueGraph.GraphNode.getID(). The adjacency list is returned as a 2-dimensional array, the first dimension has as many indices as there were nodes added to the graph. Each of these indices corresponds to the unique ID of one of the nodes in the graph. Indices for nodes no longer in the graph will have a value of null. All other indices have an array with the IDs of all the nodes the node has an edge to.
      Returns:
      The adjacency list representation of this graph.

    • copy

      public UniqueGraph<V,E> copy()
      Makes a deep copy of this graph.
      Returns:
      The copy of this graph.