in commons/src/main/java/org/apache/causeway/commons/graph/GraphUtils.java [286:494]
public record Graph<T>(
GraphKernel kernel,
Can<T> nodes,
Map<Long, Object> edgeAttributeByPackedEdgeIndex) {
// -- TRAVERSAL
public void visitNeighbors(final int nodeIndex,
final @Nullable Consumer<T> nodeVisitor) {
kernel()
.streamNeighbors(nodeIndex)
.forEach(neighborIndex->
nodeVisitor.accept(nodes.getElseFail(neighborIndex)));
}
public void visitNeighbors(final int nodeIndex,
final @Nullable EdgeFilter edgeFilter,
final @Nullable Consumer<T> nodeVisitor) {
if(nodeVisitor==null) return;
var stream = kernel()
.streamNeighbors(nodeIndex);
stream = edgeFilter==null
? stream
: stream.filter(neighborIndex->
edgeFilter.test(nodeIndex, neighborIndex));
stream.forEach(neighborIndex->
nodeVisitor.accept(nodes.getElseFail(neighborIndex)));
}
public void visitEdges(final int nodeIndex,
final @Nullable EdgeFilter edgeFilter,
final @Nullable EdgeConsumer<T> edgeConsumer) {
if(edgeConsumer==null) return;
var fromNode = nodes.getElseFail(nodeIndex);
var stream = kernel()
.streamNeighbors(nodeIndex);
stream = edgeFilter==null
? stream
: stream.filter(neighborIndex->
edgeFilter.test(nodeIndex, neighborIndex));
stream.forEach(neighborIndex->
edgeConsumer.accept(
nodeIndex, fromNode,
neighborIndex, nodes.getElseFail(neighborIndex)));
}
public void visitNeighborsIndexed(final int nodeIndex,
final @Nullable IndexedConsumer<T> nodeVisitor) {
if(nodeVisitor==null) return;
kernel()
.streamNeighbors(nodeIndex)
.forEach(neighborIndex->
nodeVisitor.accept(neighborIndex, nodes.getElseFail(neighborIndex)));
}
// public Stream<T> streamNeighbors(final int nodeIndex) {
// return kernel()
// .streamNeighbors(nodeIndex)
// .mapToObj(neighborIndex->nodes.getElseFail(neighborIndex));
// }
//
// public record IndexedNode<T>(
// int index,
// T node){
// }
//
// public Stream<IndexedNode<T>> streamNeighborsIndexed(final int nodeIndex) {
// return kernel()
// .streamNeighbors(nodeIndex)
// .mapToObj(neighborIndex->new IndexedNode<>(neighborIndex, nodes.getElseFail(neighborIndex)));
// }
// -- TRANSFORMATION
/**
* Returns an isomorphic graph with this graph's nodes replaced by given mapping function.
*/
public <R> Graph<R> map(final Function<T, R> nodeMapper) {
var graph = new Graph<R>(kernel, nodes.map(nodeMapper), edgeAttributeByPackedEdgeIndex());
_Assert.assertEquals(kernel.nodeCount(), graph.nodes().size());
return graph;
}
/**
* Returns a sub-graph with any nodes removed from this graph, that do not pass the filter.
*/
public Graph<T> filter(final Predicate<T> filter) {
if(nodes.isEmpty()) return this;
var nodeType = _Casts.<Class<T>>uncheckedCast(nodes.getFirst().get().getClass());
var builder = new GraphBuilder<T>(nodeType, kernel().characteristics);
var isUndirected = kernel().isUndirected();
nodes.forEach(IndexedConsumer.zeroBased((nodeIndex, node)->{
if(filter.test(node)) {
builder.addNode(node);
Graph.this.visitNeighborsIndexed(nodeIndex, (neighborIndex, neighbor)->{
if(isUndirected
&& neighborIndex<nodeIndex) {
return;
}
if(filter.test(neighbor)) {
var edgeAttributes = edgeAttributeByPackedEdgeIndex()
.get(_Longs.pack(nodeIndex, neighborIndex));
if(edgeAttributes!=null) {
builder.addEdge(node, neighbor, edgeAttributes);
} else {
builder.addEdge(node, neighbor);
}
}
});
}
}));
return builder.build();
}
// -- EDGE ATTRIBUTE
/**
* For multi-graphs, edge attributes are shared.
*/
public Optional<Object> getEdgeAttribute(final int fromIndex, final int toIndex) {
final long packedEdgeIndex = kernel().isUndirected()
? _Longs.pack(Math.min(fromIndex, toIndex), Math.max(fromIndex, toIndex))
: _Longs.pack(fromIndex, toIndex);
return Optional.ofNullable(
edgeAttributeByPackedEdgeIndex.get(packedEdgeIndex));
}
// -- SORTING
/**
* Returns an isomorphic graph that has its node list sorted by given comparator.
* <p>
* Preserves graph characteristics and edge attributes.
*/
public Graph<T> sorted(final Comparator<T> nodeComparator) {
var sortedNodes = nodes.sorted(nodeComparator);
_Assert.assertEquals(nodes.size(), sortedNodes.size(),
()->"nodeComparator has reduced the number of nodes from the original node list");
var builder = new GraphBuilder<T>((Class<T>) null, kernel.characteristics);
sortedNodes.forEach(builder::addNode);
for(int nodeIndex = 0; nodeIndex < kernel.nodeCount(); ++nodeIndex) {
visitEdges(nodeIndex, EdgeFilter.includeAll(), (i, a, j, b)->{
builder.addEdge(a, b, getEdgeAttribute(i, j).orElse(null));
});
}
return builder.build();
}
// -- FORMAT
@Override
public String toString() {
return toString(null, null);
}
public String toString(
final @Nullable Function<T, String> nodeFormatter) {
return toString(NodeFormatter.of(nodeFormatter), null);
}
public String toString(
final @Nullable NodeFormatter<T> nodeFormatter,
final @Nullable Function<Object, String> edgeAttributeFormatter) {
var isDirected = !kernel().isUndirected();
var hasEdgeAttributes = !edgeAttributeByPackedEdgeIndex.isEmpty();
final NodeFormatter<T> nodeFormat = nodeFormatter != null
? nodeFormatter
: NodeFormatter.of(null);
final Function<Object, String> edgeAttributeFormat = edgeAttributeFormatter != null
? edgeAttributeFormatter
: edgeAttr->"(" + edgeAttr + ")";
final EdgeFormatter<T> edgeFormat = hasEdgeAttributes
? isDirected
? (i, a, j, b, nf) -> String.format("%s -> %s%s", nf.format(i, a), nf.format(j, b),
getEdgeAttribute(i, j).map(edgeAttributeFormat).map(s->" "+s).orElse(""))
: (i, a, j, b, nf) -> String.format("%s - %s%s", nf.format(i, a), nf.format(j, b),
getEdgeAttribute(i, j).map(edgeAttributeFormat).map(s->" "+s).orElse(""))
: isDirected
? (i, a, j, b, nf) -> String.format("%s -> %s", nf.format(i, a), nf.format(j, b))
: (i, a, j, b, nf) -> String.format("%s - %s", nf.format(i, a), nf.format(j, b));
var filter = isDirected
? EdgeFilter.includeAll()
: EdgeFilter.excludeToLessThanFrom();
var sb = new StringBuilder();
for(int nodeIndex = 0; nodeIndex < kernel.nodeCount(); ++nodeIndex) {
visitEdges(nodeIndex, filter, (i, a, j, b)->{
sb
.append(edgeFormat.format(i, a, j, b, nodeFormat))
.append("\n");
});
if(kernel().neighborCount(nodeIndex)==0) {
sb
.append(String.format("%s", nodeFormat.format(nodeIndex, nodes.getElseFail(nodeIndex))))
.append("\n");
}
}
return sb.toString();
}
}