@Test public void subgraph() { Graph<Integer> graph = Graphs.newInstance(); addPath(graph, 1, 2, 3, 4, 5, 1); addPath(graph, 1, 3, 5, 2, 4, 1); Graph<Integer> sub = Graphs.subgraph(graph, object -> object != 5); Graph<Integer> expect = Graphs.newInstance(); addPath(expect, 1, 2, 3, 4, 1); addPath(expect, 1, 3); addPath(expect, 2, 4); assertThat(sub, is(expect)); }
public static <V> Graph<V> subgraph(Graph<? extends V> graph, Predicate<? super V> matcher) { if (graph == null) { throw new IllegalArgumentException("graph must not be null"); } if (matcher == null) { throw new IllegalArgumentException("matcher must not be null"); } Graph<V> subgraph = newInstance(); Map<V, Boolean> matchedSet = new HashMap<>(); for (V vertex : graph.getNodeSet()) { boolean matched = matcher.test(vertex); if (matched) { subgraph.addNode(vertex); } matchedSet.put(vertex, matched); } if (subgraph.isEmpty()) { return subgraph; } for (Graph.Vertex<? extends V> vertex : graph) { V from = vertex.getNode(); assert matchedSet.containsKey(from); if (Boolean.FALSE.equals(matchedSet.get(from))) { continue; } for (V to : vertex.getConnected()) { assert matchedSet.containsKey(to); if (Boolean.FALSE.equals(matchedSet.get(to))) { continue; } subgraph.addEdge(from, to); } } return subgraph; }
Graphs { public static <V> Graph<V> subgraph(Graph<? extends V> graph, Predicate<? super V> matcher) { if (graph == null) { throw new IllegalArgumentException("graph must not be null"); } if (matcher == null) { throw new IllegalArgumentException("matcher must not be null"); } Graph<V> subgraph = newInstance(); Map<V, Boolean> matchedSet = new HashMap<>(); for (V vertex : graph.getNodeSet()) { boolean matched = matcher.test(vertex); if (matched) { subgraph.addNode(vertex); } matchedSet.put(vertex, matched); } if (subgraph.isEmpty()) { return subgraph; } for (Graph.Vertex<? extends V> vertex : graph) { V from = vertex.getNode(); assert matchedSet.containsKey(from); if (Boolean.FALSE.equals(matchedSet.get(from))) { continue; } for (V to : vertex.getConnected()) { assert matchedSet.containsKey(to); if (Boolean.FALSE.equals(matchedSet.get(to))) { continue; } subgraph.addEdge(from, to); } } return subgraph; } }
Graphs { public static <V> Graph<V> subgraph(Graph<? extends V> graph, Predicate<? super V> matcher) { if (graph == null) { throw new IllegalArgumentException("graph must not be null"); } if (matcher == null) { throw new IllegalArgumentException("matcher must not be null"); } Graph<V> subgraph = newInstance(); Map<V, Boolean> matchedSet = new HashMap<>(); for (V vertex : graph.getNodeSet()) { boolean matched = matcher.test(vertex); if (matched) { subgraph.addNode(vertex); } matchedSet.put(vertex, matched); } if (subgraph.isEmpty()) { return subgraph; } for (Graph.Vertex<? extends V> vertex : graph) { V from = vertex.getNode(); assert matchedSet.containsKey(from); if (Boolean.FALSE.equals(matchedSet.get(from))) { continue; } for (V to : vertex.getConnected()) { assert matchedSet.containsKey(to); if (Boolean.FALSE.equals(matchedSet.get(to))) { continue; } subgraph.addEdge(from, to); } } return subgraph; } private  Graphs(); }
Graphs { public static <V> Graph<V> subgraph(Graph<? extends V> graph, Predicate<? super V> matcher) { if (graph == null) { throw new IllegalArgumentException("graph must not be null"); } if (matcher == null) { throw new IllegalArgumentException("matcher must not be null"); } Graph<V> subgraph = newInstance(); Map<V, Boolean> matchedSet = new HashMap<>(); for (V vertex : graph.getNodeSet()) { boolean matched = matcher.test(vertex); if (matched) { subgraph.addNode(vertex); } matchedSet.put(vertex, matched); } if (subgraph.isEmpty()) { return subgraph; } for (Graph.Vertex<? extends V> vertex : graph) { V from = vertex.getNode(); assert matchedSet.containsKey(from); if (Boolean.FALSE.equals(matchedSet.get(from))) { continue; } for (V to : vertex.getConnected()) { assert matchedSet.containsKey(to); if (Boolean.FALSE.equals(matchedSet.get(to))) { continue; } subgraph.addEdge(from, to); } } return subgraph; } private  Graphs(); static Graph<V> newInstance(); static Graph<V> copy(Graph<? extends V> graph); static Set<V> collectHeads(Graph<? extends V> graph); static Set<V> collectTails(Graph<? extends V> graph); static Set<V> collectAllConnected(Graph<? extends V> graph, Collection<? extends V> startNodes); static Set<V> findNearest(
            Graph<? extends V> graph,
            Collection<? extends V> startNodes,
            Predicate<? super V> matcher); static Set<V> collectNearest(
            Graph<? extends V> graph,
            Collection<? extends V> startNodes,
            Predicate<? super V> matcher); static Set<Set<V>> findCircuit(Graph<? extends V> graph); static Set<Set<V>> findStronglyConnectedComponents(Graph<? extends V> graph); static List<V> sortPostOrder(Graph<? extends V> graph); static Graph<V> transpose(Graph<V> graph); static Graph<V> subgraph(Graph<? extends V> graph, Predicate<? super V> matcher); }
Graphs { public static <V> Graph<V> subgraph(Graph<? extends V> graph, Predicate<? super V> matcher) { if (graph == null) { throw new IllegalArgumentException("graph must not be null"); } if (matcher == null) { throw new IllegalArgumentException("matcher must not be null"); } Graph<V> subgraph = newInstance(); Map<V, Boolean> matchedSet = new HashMap<>(); for (V vertex : graph.getNodeSet()) { boolean matched = matcher.test(vertex); if (matched) { subgraph.addNode(vertex); } matchedSet.put(vertex, matched); } if (subgraph.isEmpty()) { return subgraph; } for (Graph.Vertex<? extends V> vertex : graph) { V from = vertex.getNode(); assert matchedSet.containsKey(from); if (Boolean.FALSE.equals(matchedSet.get(from))) { continue; } for (V to : vertex.getConnected()) { assert matchedSet.containsKey(to); if (Boolean.FALSE.equals(matchedSet.get(to))) { continue; } subgraph.addEdge(from, to); } } return subgraph; } private  Graphs(); static Graph<V> newInstance(); static Graph<V> copy(Graph<? extends V> graph); static Set<V> collectHeads(Graph<? extends V> graph); static Set<V> collectTails(Graph<? extends V> graph); static Set<V> collectAllConnected(Graph<? extends V> graph, Collection<? extends V> startNodes); static Set<V> findNearest(
            Graph<? extends V> graph,
            Collection<? extends V> startNodes,
            Predicate<? super V> matcher); static Set<V> collectNearest(
            Graph<? extends V> graph,
            Collection<? extends V> startNodes,
            Predicate<? super V> matcher); static Set<Set<V>> findCircuit(Graph<? extends V> graph); static Set<Set<V>> findStronglyConnectedComponents(Graph<? extends V> graph); static List<V> sortPostOrder(Graph<? extends V> graph); static Graph<V> transpose(Graph<V> graph); static Graph<V> subgraph(Graph<? extends V> graph, Predicate<? super V> matcher);  }