177 lines
7.7 KiB
Java
177 lines
7.7 KiB
Java
|
package com.google.common.graph;
|
||
|
|
|
||
|
|
import com.google.common.base.Function;
|
||
|
|
import com.google.common.base.Preconditions;
|
||
|
|
import com.google.common.collect.ImmutableSet;
|
||
|
|
import com.google.common.collect.Iterators;
|
||
|
|
import com.google.common.collect.Sets;
|
||
|
|
import com.google.common.collect.UnmodifiableIterator;
|
||
|
|
import com.google.common.math.IntMath;
|
||
|
|
import com.google.common.primitives.Ints;
|
||
|
|
import java.util.AbstractSet;
|
||
|
|
import java.util.Set;
|
||
|
|
|
||
|
|
/* JADX INFO: Access modifiers changed from: package-private */
|
||
|
|
/* loaded from: classes2.dex */
|
||
|
|
public abstract class AbstractBaseGraph<N> implements BaseGraph<N> {
|
||
|
|
protected long edgeCount() {
|
||
|
|
long j = 0;
|
||
|
|
while (nodes().iterator().hasNext()) {
|
||
|
|
j += degree(r0.next());
|
||
|
|
}
|
||
|
|
Preconditions.checkState((1 & j) == 0);
|
||
|
|
return j >>> 1;
|
||
|
|
}
|
||
|
|
|
||
|
|
@Override // com.google.common.graph.BaseGraph
|
||
|
|
public Set<EndpointPair<N>> edges() {
|
||
|
|
return new AbstractSet<EndpointPair<N>>(this) { // from class: com.google.common.graph.AbstractBaseGraph.1
|
||
|
|
final AbstractBaseGraph this$0;
|
||
|
|
|
||
|
|
{
|
||
|
|
this.this$0 = this;
|
||
|
|
}
|
||
|
|
|
||
|
|
@Override // java.util.AbstractCollection, java.util.Collection, java.lang.Iterable, java.util.Set
|
||
|
|
public UnmodifiableIterator<EndpointPair<N>> iterator() {
|
||
|
|
return EndpointPairIterator.of(this.this$0);
|
||
|
|
}
|
||
|
|
|
||
|
|
@Override // java.util.AbstractCollection, java.util.Collection, java.util.Set
|
||
|
|
public int size() {
|
||
|
|
return Ints.saturatedCast(this.this$0.edgeCount());
|
||
|
|
}
|
||
|
|
|
||
|
|
@Override // java.util.AbstractCollection, java.util.Collection, java.util.Set
|
||
|
|
public boolean remove(Object obj) {
|
||
|
|
throw new UnsupportedOperationException();
|
||
|
|
}
|
||
|
|
|
||
|
|
/* JADX WARN: Multi-variable type inference failed */
|
||
|
|
@Override // java.util.AbstractCollection, java.util.Collection, java.util.Set
|
||
|
|
public boolean contains(Object obj) {
|
||
|
|
if (!(obj instanceof EndpointPair)) {
|
||
|
|
return false;
|
||
|
|
}
|
||
|
|
EndpointPair<?> endpointPair = (EndpointPair) obj;
|
||
|
|
return this.this$0.isOrderingCompatible(endpointPair) && this.this$0.nodes().contains(endpointPair.nodeU()) && this.this$0.successors((AbstractBaseGraph) endpointPair.nodeU()).contains(endpointPair.nodeV());
|
||
|
|
}
|
||
|
|
};
|
||
|
|
}
|
||
|
|
|
||
|
|
@Override // com.google.common.graph.BaseGraph
|
||
|
|
public ElementOrder<N> incidentEdgeOrder() {
|
||
|
|
return ElementOrder.unordered();
|
||
|
|
}
|
||
|
|
|
||
|
|
@Override // com.google.common.graph.BaseGraph
|
||
|
|
public Set<EndpointPair<N>> incidentEdges(N n) {
|
||
|
|
Preconditions.checkNotNull(n);
|
||
|
|
Preconditions.checkArgument(nodes().contains(n), "Node %s is not an element of this graph.", n);
|
||
|
|
return new IncidentEdgeSet<N>(this, this, n) { // from class: com.google.common.graph.AbstractBaseGraph.2
|
||
|
|
@Override // java.util.AbstractCollection, java.util.Collection, java.lang.Iterable, java.util.Set
|
||
|
|
public UnmodifiableIterator<EndpointPair<N>> iterator() {
|
||
|
|
if (this.graph.isDirected()) {
|
||
|
|
return Iterators.unmodifiableIterator(Iterators.concat(Iterators.transform(this.graph.predecessors((BaseGraph<N>) this.node).iterator(), new Function<N, EndpointPair<N>>(this) { // from class: com.google.common.graph.AbstractBaseGraph.2.1
|
||
|
|
final AnonymousClass2 this$1;
|
||
|
|
|
||
|
|
{
|
||
|
|
this.this$1 = this;
|
||
|
|
}
|
||
|
|
|
||
|
|
@Override // com.google.common.base.Function
|
||
|
|
public /* bridge */ /* synthetic */ Object apply(Object obj) {
|
||
|
|
return apply((AnonymousClass1) obj);
|
||
|
|
}
|
||
|
|
|
||
|
|
@Override // com.google.common.base.Function
|
||
|
|
public EndpointPair<N> apply(N n2) {
|
||
|
|
return EndpointPair.ordered(n2, this.this$1.node);
|
||
|
|
}
|
||
|
|
}), Iterators.transform(Sets.difference(this.graph.successors((BaseGraph<N>) this.node), ImmutableSet.of(this.node)).iterator(), new Function<N, EndpointPair<N>>(this) { // from class: com.google.common.graph.AbstractBaseGraph.2.2
|
||
|
|
final AnonymousClass2 this$1;
|
||
|
|
|
||
|
|
{
|
||
|
|
this.this$1 = this;
|
||
|
|
}
|
||
|
|
|
||
|
|
@Override // com.google.common.base.Function
|
||
|
|
public /* bridge */ /* synthetic */ Object apply(Object obj) {
|
||
|
|
return apply((C00372) obj);
|
||
|
|
}
|
||
|
|
|
||
|
|
@Override // com.google.common.base.Function
|
||
|
|
public EndpointPair<N> apply(N n2) {
|
||
|
|
return EndpointPair.ordered(this.this$1.node, n2);
|
||
|
|
}
|
||
|
|
})));
|
||
|
|
}
|
||
|
|
return Iterators.unmodifiableIterator(Iterators.transform(this.graph.adjacentNodes(this.node).iterator(), new Function<N, EndpointPair<N>>(this) { // from class: com.google.common.graph.AbstractBaseGraph.2.3
|
||
|
|
final AnonymousClass2 this$1;
|
||
|
|
|
||
|
|
{
|
||
|
|
this.this$1 = this;
|
||
|
|
}
|
||
|
|
|
||
|
|
@Override // com.google.common.base.Function
|
||
|
|
public /* bridge */ /* synthetic */ Object apply(Object obj) {
|
||
|
|
return apply((AnonymousClass3) obj);
|
||
|
|
}
|
||
|
|
|
||
|
|
@Override // com.google.common.base.Function
|
||
|
|
public EndpointPair<N> apply(N n2) {
|
||
|
|
return EndpointPair.unordered(this.this$1.node, n2);
|
||
|
|
}
|
||
|
|
}));
|
||
|
|
}
|
||
|
|
};
|
||
|
|
}
|
||
|
|
|
||
|
|
@Override // com.google.common.graph.BaseGraph
|
||
|
|
public int degree(N n) {
|
||
|
|
if (isDirected()) {
|
||
|
|
return IntMath.saturatedAdd(predecessors((AbstractBaseGraph<N>) n).size(), successors((AbstractBaseGraph<N>) n).size());
|
||
|
|
}
|
||
|
|
Set<N> adjacentNodes = adjacentNodes(n);
|
||
|
|
return IntMath.saturatedAdd(adjacentNodes.size(), (allowsSelfLoops() && adjacentNodes.contains(n)) ? 1 : 0);
|
||
|
|
}
|
||
|
|
|
||
|
|
@Override // com.google.common.graph.BaseGraph
|
||
|
|
public int inDegree(N n) {
|
||
|
|
return isDirected() ? predecessors((AbstractBaseGraph<N>) n).size() : degree(n);
|
||
|
|
}
|
||
|
|
|
||
|
|
@Override // com.google.common.graph.BaseGraph
|
||
|
|
public int outDegree(N n) {
|
||
|
|
return isDirected() ? successors((AbstractBaseGraph<N>) n).size() : degree(n);
|
||
|
|
}
|
||
|
|
|
||
|
|
@Override // com.google.common.graph.BaseGraph
|
||
|
|
public boolean hasEdgeConnecting(N n, N n2) {
|
||
|
|
Preconditions.checkNotNull(n);
|
||
|
|
Preconditions.checkNotNull(n2);
|
||
|
|
return nodes().contains(n) && successors((AbstractBaseGraph<N>) n).contains(n2);
|
||
|
|
}
|
||
|
|
|
||
|
|
@Override // com.google.common.graph.BaseGraph
|
||
|
|
public boolean hasEdgeConnecting(EndpointPair<N> endpointPair) {
|
||
|
|
Preconditions.checkNotNull(endpointPair);
|
||
|
|
if (!isOrderingCompatible(endpointPair)) {
|
||
|
|
return false;
|
||
|
|
}
|
||
|
|
N nodeU = endpointPair.nodeU();
|
||
|
|
return nodes().contains(nodeU) && successors((AbstractBaseGraph<N>) nodeU).contains(endpointPair.nodeV());
|
||
|
|
}
|
||
|
|
|
||
|
|
/* JADX INFO: Access modifiers changed from: protected */
|
||
|
|
public final void validateEndpoints(EndpointPair<?> endpointPair) {
|
||
|
|
Preconditions.checkNotNull(endpointPair);
|
||
|
|
Preconditions.checkArgument(isOrderingCompatible(endpointPair), "Mismatch: unordered endpoints cannot be used with directed graphs");
|
||
|
|
}
|
||
|
|
|
||
|
|
/* JADX INFO: Access modifiers changed from: protected */
|
||
|
|
public final boolean isOrderingCompatible(EndpointPair<?> endpointPair) {
|
||
|
|
return endpointPair.isOrdered() || !isDirected();
|
||
|
|
}
|
||
|
|
}
|