This is an automated email from the ASF dual-hosted git repository.
ahuber pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/causeway.git
The following commit(s) were added to refs/heads/master by this push:
new d89cad7bb8 CAUSEWAY-3404: adds subgraph algorithm and IntList picking
d89cad7bb8 is described below
commit d89cad7bb82904afed442274cbf64a0925dde0bc
Author: Andi Huber <[email protected]>
AuthorDate: Sat Jan 20 09:42:59 2024 +0100
CAUSEWAY-3404: adds subgraph algorithm and IntList picking
---
.../services/metamodel/objgraph/ObjectGraph.java | 8 +-
.../apache/causeway/commons/graph/GraphUtils.java | 22 +++++
.../collections/_PrimitiveCollections.java | 105 +++++++++++++++++++--
.../causeway/commons/graph/GraphUtilsTest.java | 45 +++++++++
.../collections/_PrimitiveCollectionsTest.java | 29 ++++++
5 files changed, 196 insertions(+), 13 deletions(-)
diff --git
a/api/applib/src/main/java/org/apache/causeway/applib/services/metamodel/objgraph/ObjectGraph.java
b/api/applib/src/main/java/org/apache/causeway/applib/services/metamodel/objgraph/ObjectGraph.java
index 4fe2b1c422..3e36c7c418 100644
---
a/api/applib/src/main/java/org/apache/causeway/applib/services/metamodel/objgraph/ObjectGraph.java
+++
b/api/applib/src/main/java/org/apache/causeway/applib/services/metamodel/objgraph/ObjectGraph.java
@@ -25,6 +25,7 @@ import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Optional;
+import java.util.function.Predicate;
import java.util.function.UnaryOperator;
import java.util.stream.Collectors;
@@ -257,9 +258,10 @@ public class ObjectGraph {
g.objects().clear();
subSet.forEach(g.objects()::add);
var objectIds = g.objectById().keySet();
- g.relations().removeIf(rel->
- !(objectIds.contains(rel.fromId())
- || objectIds.contains(rel.fromId())));
+ var isInSubgraph = (Predicate<ObjectGraph.Relation>) rel->
+ objectIds.contains(rel.fromId())
+ && objectIds.contains(rel.toId());
+ g.relations().removeIf(isInSubgraph.negate());
return g;
});
return subGraph;
diff --git
a/commons/src/main/java/org/apache/causeway/commons/graph/GraphUtils.java
b/commons/src/main/java/org/apache/causeway/commons/graph/GraphUtils.java
index ea22753173..486ccd5509 100644
--- a/commons/src/main/java/org/apache/causeway/commons/graph/GraphUtils.java
+++ b/commons/src/main/java/org/apache/causeway/commons/graph/GraphUtils.java
@@ -24,6 +24,8 @@ import java.util.function.BiPredicate;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
+import org.springframework.lang.Nullable;
+
import org.apache.causeway.commons.collections.Can;
import org.apache.causeway.commons.collections.ImmutableEnumSet;
import
org.apache.causeway.commons.graph.GraphUtils.GraphKernel.GraphCharacteristic;
@@ -92,6 +94,9 @@ public class GraphUtils {
public boolean isUndirected() {
return characteristics.contains(GraphCharacteristic.UNDIRECTED);
}
+ public int edgeCount() {
+ return adjacencyList.stream().mapToInt(IntList::size).sum();
+ }
public void addEdge(final int u, final int v) {
boundsCheck(u);
boundsCheck(v);
@@ -123,6 +128,23 @@ public class GraphUtils {
}
return copy;
}
+ /**
+ * Returns a sub-graph comprised only of nodes as picked per (zero
based) indexes {@code int[]}.
+ * @apiNote assumes nodeIndexes are unique and valid
+ */
+ public GraphKernel subGraph(final @Nullable int[] nodeIndexes) {
+ var pickedSubset = new IntList(nodeIndexes);
+ final int subsize = pickedSubset.size();
+ var sub = new GraphKernel(subsize, characteristics);
+ for (int i = 0; i < subsize; i++) {
+ final int fromIndex = i;
+ for (int v : adjacencyList.get(nodeIndexes[i])) {
+ pickedSubset.indexOf(v)
+ .ifPresent(toIndex->sub.addEdge(fromIndex, toIndex));
+ }
+ }
+ return sub;
+ }
/**
* Returns a list of {@code int[]},
* where each list entry contains the zero based indexes of weakly
connected graph nodes.
diff --git
a/commons/src/main/java/org/apache/causeway/commons/internal/collections/_PrimitiveCollections.java
b/commons/src/main/java/org/apache/causeway/commons/internal/collections/_PrimitiveCollections.java
index c39a4a22be..4e8f8a761f 100644
---
a/commons/src/main/java/org/apache/causeway/commons/internal/collections/_PrimitiveCollections.java
+++
b/commons/src/main/java/org/apache/causeway/commons/internal/collections/_PrimitiveCollections.java
@@ -18,16 +18,23 @@
*/
package org.apache.causeway.commons.internal.collections;
+import java.util.Arrays;
import java.util.Iterator;
import java.util.OptionalInt;
import java.util.PrimitiveIterator;
import java.util.stream.IntStream;
+import org.springframework.lang.Nullable;
+
+import org.apache.causeway.commons.internal.base._NullSafe;
+
+import lombok.NoArgsConstructor;
+import lombok.val;
import lombok.experimental.UtilityClass;
/**
* <h1>- internal use only -</h1>
- * Primitive int list implementation.
+ * Utility class providing some primitive collections.
* <p>
* <b>WARNING</b>: Do <b>NOT</b> use any of the classes provided by this
package! <br/>
* These may be changed or removed without notice!
@@ -39,16 +46,39 @@ public class _PrimitiveCollections {
/**
* Primitive int list implementation. Can also operate as a set,
- * if {@link IntList#addUnique(int)} is used over {@link IntList#add(int)}.
+ * if {@link IntList#addUnique(int)} (and variants) are used instead of
{@link IntList#add(int)}.
* @implNote not thread-safe
*/
+ @NoArgsConstructor
public static class IntList implements Iterable<Integer> {
-
private static final int DEFAULT_INITIAL_CAPACITY = 8;
+ // -- CONSTRUCTION
+
private int[] buf;
private int size = 0;
+ public IntList(final int initialCapacity) {
+ if(initialCapacity<0) {
+ throw new IndexOutOfBoundsException(initialCapacity);
+ }
+ this.buf = initialCapacity == 0
+ ? null // otherwise cannot use buffer doubling algorithm
below, when adding
+ : new int[initialCapacity];
+ }
+
+ public IntList(final @Nullable int[] array) {
+ this.size = _NullSafe.size(array);
+ if(size == 0) {
+ // don't init buf to 0 size, otherwise cannot use buffer
doubling algorithm below, when adding
+ return;
+ }
+ this.buf = new int[size];
+ System.arraycopy(array, 0, buf, 0, size);
+ }
+
+ // -- SIZE
+
public int size() {
return size;
}
@@ -60,10 +90,7 @@ public class _PrimitiveCollections {
return size!=0;
}
- public IntList addUnique(final int v) {
- if(!contains(v)) return add(v);
- return this;
- }
+ // -- ADDING
public IntList add(final int v) {
if(buf==null) {
@@ -77,6 +104,36 @@ public class _PrimitiveCollections {
return this;
}
+ //TODO should perhaps return some feedback, as to whether v was added
or not
+ public IntList addUnique(final int v) {
+ if(!contains(v)) return add(v);
+ return this;
+ }
+
+ public IntList addAll(final @Nullable int[] array) {
+ final int n = _NullSafe.size(array);
+ if(n!=0) {
+ var old = buf;
+ this.buf = new int[size + n];
+ System.arraycopy(old, 0, buf, 0, size);
+ System.arraycopy(array, 0, buf, size, n);
+ this.size += n;
+ }
+ return this;
+ }
+
+ public IntList addAllUnique(final @Nullable int[] array) {
+ final int n = _NullSafe.size(array);
+ if(n!=0) {
+ for (int v : array) {
+ addUnique(v);
+ }
+ }
+ return this;
+ }
+
+ // -- QUERIES
+
public int get(final int index) {
if(index<0
|| index>=size) {
@@ -101,12 +158,34 @@ public class _PrimitiveCollections {
return false;
}
- public IntStream stream() {
- return IntStream.of(toArray());
+ // -- PICKING
+
+ /**
+ * Ignores out of bounds picks.
+ */
+ public int[] toArrayPickByIndex(final @Nullable int... indexes) {
+ final int n = _NullSafe.size(indexes);
+ if(n==0) return new int[0];
+
+ val newElements = new int[n];
+ final int maxIndex = size()-1;
+ int elementCount = 0;
+ for(int index : indexes) {
+ if(index>=0
+ && index<=maxIndex) {
+ newElements[elementCount++] = buf[index];
+ }
+ }
+ return elementCount == n
+ ? newElements
+ : Arrays.copyOf(newElements, elementCount); // trim to
actual size
}
+ // -- CONVERSION
+
/**
- * @return a new array containing all the int(s) of this list
+ * Returns a new array containing all the int(s) of this list.
+ * @return non-null
*/
public int[] toArray() {
var result = new int[size];
@@ -116,6 +195,12 @@ public class _PrimitiveCollections {
return result;
}
+ // -- TRAVERSAL
+
+ public IntStream stream() {
+ return IntStream.of(toArray());
+ }
+
@Override
public Iterator<Integer> iterator() {
var defensiveCopy = toArray();
diff --git
a/commons/src/test/java/org/apache/causeway/commons/graph/GraphUtilsTest.java
b/commons/src/test/java/org/apache/causeway/commons/graph/GraphUtilsTest.java
new file mode 100644
index 0000000000..7baa30e8ad
--- /dev/null
+++
b/commons/src/test/java/org/apache/causeway/commons/graph/GraphUtilsTest.java
@@ -0,0 +1,45 @@
+package org.apache.causeway.commons.graph;
+
+import org.junit.jupiter.api.Test;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertFalse;
+
+import org.apache.causeway.commons.collections.ImmutableEnumSet;
+import org.apache.causeway.commons.graph.GraphUtils.GraphKernel;
+import
org.apache.causeway.commons.graph.GraphUtils.GraphKernel.GraphCharacteristic;
+
+class GraphUtilsTest {
+
+ @Test
+ void subgraph() {
+ var graph = new GraphKernel(4,
ImmutableEnumSet.noneOf(GraphCharacteristic.class));
+ graph.addEdge(0, 1);
+ graph.addEdge(1, 2);
+ graph.addEdge(2, 3);
+
+ assertFalse(graph.isUndirected());
+ assertEquals(4, graph.nodeCount());
+ assertEquals(3, graph.edgeCount());
+
+ // identity
+ var subgraphId = graph.subGraph(new int[] {0, 1, 2, 3});
+ assertFalse(subgraphId.isUndirected());
+ assertEquals(4, subgraphId.nodeCount());
+ assertEquals(3, subgraphId.edgeCount());
+
+ // disjoint
+ var subgraphDisjointNoEdges = graph.subGraph(new int[] {0, 3});
+ assertFalse(subgraphDisjointNoEdges.isUndirected());
+ assertEquals(2, subgraphDisjointNoEdges.nodeCount());
+ assertEquals(0, subgraphDisjointNoEdges.edgeCount());
+
+ // subgraph w/ 3 nodes, reordered
+ var subgraph3 = graph.subGraph(new int[] {3, 1, 2});
+ assertFalse(subgraph3.isUndirected());
+ assertEquals(3, subgraph3.nodeCount());
+ assertEquals(2, subgraph3.edgeCount());
+
+ }
+
+}
diff --git
a/commons/src/test/java/org/apache/causeway/commons/internal/collections/_PrimitiveCollectionsTest.java
b/commons/src/test/java/org/apache/causeway/commons/internal/collections/_PrimitiveCollectionsTest.java
index 8d0e26dbfa..ec6f84e00b 100644
---
a/commons/src/test/java/org/apache/causeway/commons/internal/collections/_PrimitiveCollectionsTest.java
+++
b/commons/src/test/java/org/apache/causeway/commons/internal/collections/_PrimitiveCollectionsTest.java
@@ -22,6 +22,7 @@ import java.util.stream.IntStream;
import org.junit.jupiter.api.Test;
+import static org.junit.jupiter.api.Assertions.assertArrayEquals;
import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertFalse;
import static org.junit.jupiter.api.Assertions.assertNotNull;
@@ -101,5 +102,33 @@ class _PrimitiveCollectionsTest {
assertEquals(2, intList.indexOf(7).orElse(-1));
}
+ @Test
+ void wrapping() {
+ var array = new int[]{
+ 1, 3, 2, 5,
+ 1, 3, 2, 5,
+ 1, 3, 2, 5,
+ 1, 3, 2, 5};
+ var intList = new IntList(array);
+ assertEquals(4*4, intList.size());
+ assertFalse(intList.isEmpty());
+ assertEquals(44, intList.stream().sum());
+ }
+
+ @Test
+ void addAll() {
+ var array = new int[]{1, 3, 2, 5, 1, 3, 2, 5};
+ var intList = new IntList(array).addAll(array);
+ assertEquals(4*4, intList.size());
+ assertFalse(intList.isEmpty());
+ assertEquals(44, intList.stream().sum());
+ }
+
+ @Test
+ void pickByIndex() {
+ var array = new int[]{1, 3, 2, 5};
+ var intList = new IntList(array);
+ assertArrayEquals(new int[]{1, 1, 5}, intList.toArrayPickByIndex(0, 0,
9, -1, 3));
+ }
}
