package nl.camilstaps.cs.graphs; import java.util.ArrayList; import java.util.List; import java.util.stream.Collectors; /** * A Node is a simple point in a graph, with references to its neighbours. It holds an integer 'content' which can act * as an identifier. * * @author Camil Staps */ public class Node implements Comparable> { private final T content; private final List> neighbours = new ArrayList<>(); public Node(T content) { this.content = content; } /** * @return the number of neighbours */ public int getDegree() { return neighbours.size(); } /** * @return the neighbours */ public List> getNeighbourhood() { return neighbours; } /** * @return the neighbours with the Node itself */ public List> getInclusiveNeighbourhood() { List> nb = new ArrayList<>(); nb.add(this); nb.addAll(neighbours); return nb; } /** * @return the neighbours of the neighbours, without this Node itself */ public List> getSecondNeighbourhood() { List> nb = new ArrayList<>(); for (Node n : getNeighbourhood()) for (Node n2 : n.getNeighbourhood()) if (!nb.contains(n2)) nb.add(n2); nb.remove(this); return nb; } /** * Node a dominates a Node b if the inclusive neighbourhood of a is a subset of the inclusive neighbourhood of b. * @param b the Node to compare to * @return true iff this Node dominates Node b */ public boolean dominates(Node b) { for (Node nb : getInclusiveNeighbourhood()) if (!b.getInclusiveNeighbourhood().contains(nb)) return false; return true; } /** * @param b the Node to compare to * @return true iff the neighbourhood of this Node is disjoint with the neighbourhood of Node b */ public boolean neighbourhoodsDisjoint(Node b) { return neighbourhoodIntersection(b).isEmpty(); } /** * @param b another Node * @return the intersection of the neighbourhood of this Node and the neighbourhood of Node b */ public List> neighbourhoodIntersection(Node b) { return neighbours.stream().filter(n -> b.getNeighbourhood().contains(n)).collect(Collectors.toList()); } /** * @return a String representation of the Node */ public String toString() { return "<" + content + ">"; } /** * Nodes are equal if their identifiers are equal * @param b the Node to compare to * @return true iff this Node is equivalent to Node b */ public boolean equals(Object b) { return !(b == null || b.getClass() != this.getClass()) && content == (((Node) b).content); } /** * This method allows sorting of Nodes by their degrees. * @param b the Node to compare to * @return 1 if d(this) > d(b), -1 if d(this) < d(b), 0 otherwise */ @Override @SuppressWarnings("NullableProblems") public int compareTo(Node b) { return Integer.compare(neighbours.size(), b.neighbours.size()); } }