[
https://issues.apache.org/jira/browse/BEAM-3891?focusedWorklogId=82784&page=com.atlassian.jira.plugin.system.issuetabpanels:worklog-tabpanel#worklog-82784
]
ASF GitHub Bot logged work on BEAM-3891:
----------------------------------------
Author: ASF GitHub Bot
Created on: 21/Mar/18 15:46
Start Date: 21/Mar/18 15:46
Worklog Time Spent: 10m
Work Description: tgroh closed pull request #4907: [BEAM-3891] Add a
suborder parameter to Networks#topologicalOrder
URL: https://github.com/apache/beam/pull/4907
This is a PR merged from a forked repository.
As GitHub hides the original diff on merge, it is displayed below for
the sake of provenance:
As this is a foreign pull request (from a fork), the diff is supplied
below (as it won't show otherwise due to GitHub magic):
diff --git
a/runners/core-construction-java/src/main/java/org/apache/beam/runners/core/construction/graph/Networks.java
b/runners/core-construction-java/src/main/java/org/apache/beam/runners/core/construction/graph/Networks.java
index 9f901f47836..508483395c2 100644
---
a/runners/core-construction-java/src/main/java/org/apache/beam/runners/core/construction/graph/Networks.java
+++
b/runners/core-construction-java/src/main/java/org/apache/beam/runners/core/construction/graph/Networks.java
@@ -23,11 +23,14 @@
import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Maps;
+import com.google.common.graph.ElementOrder;
import com.google.common.graph.EndpointPair;
import com.google.common.graph.MutableNetwork;
import com.google.common.graph.Network;
+import com.google.common.graph.NetworkBuilder;
import java.util.ArrayDeque;
import java.util.ArrayList;
+import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashSet;
@@ -143,8 +146,46 @@ public final NodeT apply(NodeT input) {
return visitedNodes;
}
- /** Returns a set of nodes sorted in topological order. */
- public static <NodeT, EdgeT> Iterable<NodeT> topologicalOrder(Network<NodeT,
EdgeT> network) {
+ /**
+ * Return a set of nodes in sorted topological order.
+ *
+ * <p>Nodes will be considered in the order specified by the {@link Network
Network's} {@link
+ * Network#nodeOrder()}.
+ */
+ public static <NodeT> Iterable<NodeT> topologicalOrder(Network<NodeT, ?>
network) {
+ return computeTopologicalOrder(network);
+ }
+
+ /**
+ * Return a set of nodes in sorted topological order.
+ *
+ * <p>Nodes will be considered in the order specified by the {@link
+ * ElementOrder#sorted(Comparator) sorted ElementOrder} created with the
provided comparator.
+ */
+ public static <NodeT, EdgeT> Iterable<NodeT> topologicalOrder(
+ Network<NodeT, EdgeT> network, Comparator<NodeT> nodeOrder) {
+ // Copy the characteristics of the network to ensure that the result
network can represent the
+ // original network, just with the provided suborder
+ MutableNetwork<NodeT, EdgeT> orderedNetwork =
+
NetworkBuilder.from(network).nodeOrder(ElementOrder.sorted(nodeOrder)).build();
+ for (NodeT node : network.nodes()) {
+ orderedNetwork.addNode(node);
+ }
+ for (EdgeT edge : network.edges()) {
+ EndpointPair<NodeT> incident = network.incidentNodes(edge);
+ orderedNetwork.addEdge(incident.source(), incident.target(), edge);
+ }
+ return computeTopologicalOrder(orderedNetwork);
+ }
+
+ /**
+ * Compute the topological order for a {@link Network}.
+ *
+ * <p>Nodes must be considered in the order specified by the {@link Network
Network's} {@link
+ * Network#nodeOrder()}. This ensures that any two Networks with the same
nodes and node orders
+ * produce the same result.
+ */
+ private static <NodeT> Iterable<NodeT>
computeTopologicalOrder(Network<NodeT, ?> network) {
// TODO: (github/guava/2641) Upgrade Guava and remove this method if
topological sorting becomes
// supported externally or remove this comment if its not going to be
supported externally.
diff --git
a/runners/core-construction-java/src/test/java/org/apache/beam/runners/core/construction/graph/NetworksTest.java
b/runners/core-construction-java/src/test/java/org/apache/beam/runners/core/construction/graph/NetworksTest.java
index 947a005b04f..2dd8834585f 100644
---
a/runners/core-construction-java/src/test/java/org/apache/beam/runners/core/construction/graph/NetworksTest.java
+++
b/runners/core-construction-java/src/test/java/org/apache/beam/runners/core/construction/graph/NetworksTest.java
@@ -21,6 +21,7 @@
import static com.google.common.base.Preconditions.checkArgument;
import static org.hamcrest.Matchers.containsInAnyOrder;
import static org.hamcrest.Matchers.emptyIterable;
+import static org.hamcrest.Matchers.equalTo;
import static org.hamcrest.Matchers.greaterThan;
import static org.hamcrest.collection.IsEmptyCollection.empty;
import static org.junit.Assert.assertEquals;
@@ -29,10 +30,14 @@
import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Iterables;
+import com.google.common.collect.Ordering;
import com.google.common.collect.Sets;
+import com.google.common.graph.ElementOrder;
+import com.google.common.graph.EndpointPair;
import com.google.common.graph.MutableNetwork;
import com.google.common.graph.NetworkBuilder;
import java.util.Collections;
+import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
@@ -78,6 +83,55 @@ public void testTopologicalSort() {
}
}
+ @Test
+ public void testTopologicalSortWithSuborder() {
+ // This cast is required to narrow the type accepted by the comparator
+ Comparator<String> subOrder = (Comparator<String>) (Comparator)
Ordering.arbitrary();
+ MutableNetwork<String, String> network = createNetwork();
+
+ Iterable<String> sortedNodes = Networks.topologicalOrder(network,
subOrder);
+
+ MutableNetwork<String, String> naturalOrderedNetwork =
+ NetworkBuilder.from(network)
+ .nodeOrder(ElementOrder.<String>natural())
+ .edgeOrder(ElementOrder.<String>natural())
+ .build();
+ MutableNetwork<String, String> arbitraryOrderNetwork =
+ NetworkBuilder.from(network)
+ .nodeOrder(ElementOrder.unordered())
+ .edgeOrder(ElementOrder.unordered())
+ .build();
+ MutableNetwork<String, String> reverseNaturalOrderNetwork =
+ NetworkBuilder.from(network)
+ .nodeOrder(ElementOrder.sorted(Ordering.natural().reverse()))
+ .edgeOrder(ElementOrder.sorted(Ordering.natural().reverse()))
+ .build();
+
+ for (String node : network.nodes()) {
+ naturalOrderedNetwork.addNode(node);
+ arbitraryOrderNetwork.addNode(node);
+ reverseNaturalOrderNetwork.addNode(node);
+ }
+
+ for (String edge : network.edges()) {
+ EndpointPair<String> incident = network.incidentNodes(edge);
+ naturalOrderedNetwork.addEdge(incident.source(), incident.target(),
edge);
+ arbitraryOrderNetwork.addEdge(incident.source(), incident.target(),
edge);
+ reverseNaturalOrderNetwork.addEdge(incident.source(), incident.target(),
edge);
+ }
+
+ Iterable<String> naturalSortedNodes =
+ Networks.topologicalOrder(naturalOrderedNetwork, subOrder);
+ Iterable<String> arbitrarySortedNodes =
+ Networks.topologicalOrder(arbitraryOrderNetwork, subOrder);
+ Iterable<String> reverseNaturalSortedNodes =
+ Networks.topologicalOrder(reverseNaturalOrderNetwork, subOrder);
+
+ assertThat(sortedNodes, equalTo(naturalSortedNodes));
+ assertThat(sortedNodes, equalTo(arbitrarySortedNodes));
+ assertThat(sortedNodes, equalTo(reverseNaturalSortedNodes));
+ }
+
@Test
public void testReachableNodesWithEmptyNetwork() {
assertThat(
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
[email protected]
Issue Time Tracking
-------------------
Worklog Id: (was: 82784)
Time Spent: 1h 20m (was: 1h 10m)
> There should be some way to perform a Topological Sort with a stable output
> ---------------------------------------------------------------------------
>
> Key: BEAM-3891
> URL: https://issues.apache.org/jira/browse/BEAM-3891
> Project: Beam
> Issue Type: Bug
> Components: runner-core
> Reporter: Thomas Groh
> Assignee: Thomas Groh
> Priority: Major
> Time Spent: 1h 20m
> Remaining Estimate: 0h
>
> This really means that there is some way to produce the same iterable, order
> included, based on some property of the nodes. This can be done via
> performing a sort before the elements are added to the collection of nodes
> under consideration.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
