blob: ccdbd4a2af135bc59deadc7dcbbd5cb5fcf8f559 (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
|
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<T> implements Comparable<Node<T>> {
private final T content;
private final List<Node<T>> 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<Node<T>> getNeighbourhood() {
return neighbours;
}
/**
* @return the neighbours with the Node itself
*/
public List<Node<T>> getInclusiveNeighbourhood() {
List<Node<T>> nb = new ArrayList<>();
nb.add(this);
nb.addAll(neighbours);
return nb;
}
/**
* @return the neighbours of the neighbours, without this Node itself
*/
public List<Node<T>> getSecondNeighbourhood() {
List<Node<T>> nb = new ArrayList<>();
for (Node<T> n : getNeighbourhood())
for (Node<T> 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<T> b) {
for (Node<T> 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<T> 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<Node<T>> neighbourhoodIntersection(Node<T> 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<T> b) {
return Integer.compare(neighbours.size(), b.neighbours.size());
}
}
|
