Package org.vanted.indexednodes

Class IndexedNodeSet

java.lang.Object
org.vanted.indexednodes.IndexedNodeSet
All Implemented Interfaces:
Iterable<Integer>
public class IndexedNodeSet
extends Object
implements Iterable<Integer>
A node collection that supports indexed access and fast index finding as well as speedy set operations.

It consists of a 'base set' of nodes (the universe) and a bit vector representing a subset of that base set.

For example, the base set is the set of all nodes in the current selection, such bit vectors could then represent e.g. connected components in the subgraph induced by the selection.

The set operations are very fast if copies or subsets of one superset are compared, however set operations on sets not sharing a superset will require linear time in the basis collection.

Nodes outside the base set cannot be added.

Iteration is guaranteed to be in index order.

Since:
2.8
Author:
Benjamin Moser

  • Method Details

    • setOfAllIn

      public static IndexedNodeSet setOfAllIn​(Collection<Node> allNodes)
      Constructs an set with the given node collection as basic collection, containing all nodes from the basis collection.
      Parameters:
      allNodes -

    • emptySetOf

      public static IndexedNodeSet emptySetOf​(Collection<Node> allNodes)
      Constructs an empty set with the given node collection as basic collection.
      Parameters:
      allNodes -

    • emptySubset

      public IndexedNodeSet emptySubset()
      Constructs an empty subset of this set of nodes. The sets share the same index space. Union, intersection and other methods can be executed very fast between this set and the subset.

    • singletonSubset

      public IndexedNodeSet singletonSubset​(int containedNode)

    • copy

      public IndexedNodeSet copy()
      Creates a subset of this set containing the same nodes with the same basis collection and index space.

    • first

      public int first()
      Returns the index of the contained node with the smallest index. If the set is empty, this method throws an exception.
      Returns:
      the smallest index of a contained node

    • get

      public Node get​(int index)

    • getInducedNeighboursOf

      public IndexedNodeSet getInducedNeighboursOf​(Node of)
      Returns a org.vanted.addons.indexednodes.IndexedNodeSet containing all neighbors of the node specified node that are also contained in this set.
      Parameters:
      of -

    • getInducedNeighboursOf

      public IndexedNodeSet getInducedNeighboursOf​(int ofIndex)
      Returns a org.vanted.addons.indexednodes.IndexedNodeSet containing all neighbors of the node at the specified index that *are also contained in this set*. This is useful for instance when doing a search in an induced subgraph.
      Parameters:
      ofIndex -

    • size

      public int size()

    • isEmpty

      public boolean isEmpty()

    • add

      public void add​(Node node)
      Adds a node from the basis collection passed on construction to this set.
      Parameters:
      node - the node to add.
      Throws:
      RuntimeException - if the node wasn't contained in the basis collection.

    • add

      public void add​(int index)
      Adds the node at index to this set.
      Parameters:
      index -
      Throws:
      IndexOutOfBoundsException

    • remove

      public void remove​(Node node)
      Removes a node from the basis collection passed on construction from this set. If the nodes was not previously contained, the set is left unchanged.
      Parameters:
      node - the node to add.
      Throws:
      RuntimeException - if the node isn't contained in the basis collection.

    • remove

      public void remove​(int index)
      Removed the node at index from this set. If the index was not previously contained, the set is left unchanged.
      Parameters:
      index -
      Throws:
      IndexOutOfBoundsException

    • isContainedBasisCollectionAndSet

      public boolean isContainedBasisCollectionAndSet​(Node node)
      Returns true if node is contained in this sets basis collection as well as in this set itself.
      Parameters:
      node - The node to check
      Returns:
      True if the node is contained in the basis collection and in this set, false otherwise.

    • contains

      public boolean contains​(Node node)
      Adds a node from the super set passed on construction to this set.
      Parameters:
      node - the node to add.
      Throws:
      RuntimeException - if the node wasn't contained in the super set.

    • contains

      public boolean contains​(int index)
      Adds the node at index to this set.
      Parameters:
      index -
      Throws:
      IndexOutOfBoundsException

    • union

      public void union​(IndexedNodeSet other)
      Performs the union operation with the given other org.vanted.addons.indexednodes.IndexedNodeSet. The node sets needs to have identical super node sets. After this operation, this node set will contain all nodes contained in this set before the operation or in the other set (or in both).
      Parameters:
      other -

    • intersection

      public void intersection​(IndexedNodeSet other)
      Performs the intersection operation with the given other org.vanted.addons.indexednodes.IndexedNodeSet. The node sets needs to have identical base sets. After this operation, this node set will contain all nodes contained in this set before the operation and in the other set.
      Parameters:
      other -

    • setMinus

      public void setMinus​(IndexedNodeSet other)

    • complement

      public void complement()
      Performs the complement operation on this set. After the operation this set will contain exactly those nodes from the super set, that were not contained in this set before the operation.

    • setOfContainedNodesWithOwnIndices

      public IndexedNodeSet setOfContainedNodesWithOwnIndices()

    • iterator

      public Iterator<Integer> iterator()
      Returns an iterator for this set, that iterates in index order.
      Specified by:
      iterator in interface Iterable<Integer>

    • getIndex

      public int getIndex​(Node node)
      Returns the index in this set, based on the indexing of the based collection. If the node is not part of the base collection a NotIndexedException is thrown. No checks are made whether the node actually belongs to the referenced set.