1 /*
2 * Grapht, an open source dependency injector.
3 * Copyright 2014-2015 various contributors (see CONTRIBUTORS.txt)
4 * Copyright 2010-2014 Regents of the University of Minnesota
5 *
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU Lesser General Public License as
8 * published by the Free Software Foundation; either version 2.1 of the
9 * License, or (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
13 * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
14 * details.
15 *
16 * You should have received a copy of the GNU General Public License along with
17 * this program; if not, write to the Free Software Foundation, Inc., 51
18 * Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
19 */
20 package org.grouplens.grapht.graph;
21
22 import com.google.common.base.Functions;
23 import com.google.common.collect.FluentIterable;
24 import com.google.common.collect.Maps;
25 import com.google.common.collect.Sets;
26 import org.apache.commons.lang3.tuple.Pair;
27 import org.slf4j.Logger;
28 import org.slf4j.LoggerFactory;
29
30 import java.util.List;
31 import java.util.Map;
32 import java.util.Set;
33
34 /**
35 * Merges graphs to remove redundant nodes. This takes graphs and merges them, pruning redundant
36 * nodes within the graphs and between graphs previously merged. It remembers graphs it has
37 * previously seen to allow nodes to be reused across multiple graphs.
38 *
39 * @param <V> The vertex type of graphs to merge.
40 * @param <E> The edge type of graphs to merge.
41 * @since 0.7
42 * @author <a href="http://grouplens.org">GroupLens Research</a>
43 */
44 public class MergePool<V,E> {
45 // TODO Allow arbitrary equivalence relations over graph nodes so this class is less specialized.
46 private static final Logger logger = LoggerFactory.getLogger(MergePool.class);
47
48 private final Set<DAGNode<V,E>> pool;
49
50 private MergePool() {
51 pool = Sets.newLinkedHashSet();
52 }
53
54 /**
55 * Create a merge pool that checks node labels for equality.
56 *
57 * @param <V> The node label type.
58 * @param <E> The edge label type.
59 * @return A new merge pool.
60 */
61 public static <V,E> MergePool<V,E> create() {
62 return new MergePool<V, E>();
63 }
64
65 /**
66 * Merge and simplify a graph. This will coalesce redundant nodes (equivalent labels and
67 * outgoing edge destinations), and will prefer to use nodes from graphs seen previously.
68 * This allows deduplication across multiple graphs.
69 *
70 * <p><strong>Noteo:</strong> edge labels are ignored for the purpose of merging.</p>
71 *
72 * @param graph The graph to simplify.
73 * @return The new simplified, merged graph.
74 */
75 public DAGNode<V,E> merge(DAGNode<V, E> graph) {
76 List<DAGNode<V, E>> sorted = graph.getSortedNodes();
77
78 Map<Pair<V,Set<DAGNode<V,E>>>, DAGNode<V,E>> nodeTable = Maps.newHashMap();
79 for (DAGNode<V, E> node: pool) {
80 Pair<V, Set<DAGNode<V, E>>> key =
81 Pair.of(node.getLabel(), node.getAdjacentNodes());
82 assert !nodeTable.containsKey(key);
83 nodeTable.put(key, node);
84 }
85
86 // We want to map nodes to their previous merged versions
87 Map<DAGNode<V,E>, DAGNode<V,E>> mergedMap = Maps.newHashMap();
88 // Now start processing nodes
89 for (DAGNode<V, E> toMerge: sorted) {
90 V sat = toMerge.getLabel();
91 // Resolve the merged neighbors of this node. They have already been
92 // merged, since we are going in topological order.
93 Set<DAGNode<V, E>> neighbors =
94 FluentIterable.from(toMerge.getOutgoingEdges())
95 .transform(DAGEdge.<V,E>extractTail())
96 .transform(Functions.forMap(mergedMap))
97 .toSet();
98
99 // See if we have already created an equivalent to this node
100 DAGNode<V, E> newNode = nodeTable.get(Pair.of(sat, neighbors));
101 if (newNode == null) {
102 // No, let's start building one
103 DAGNodeBuilder<V,E> bld = DAGNode.newBuilder();
104
105 boolean changed = false;
106 bld.setLabel(sat);
107 logger.debug("Adding new node to merged graph for satisfaction: {}", sat);
108
109 for (DAGEdge<V, E> edge: toMerge.getOutgoingEdges()) {
110 // create a new edge with the merged tail and same label
111 DAGNode<V, E> filtered = mergedMap.get(edge.getTail());
112 bld.addEdge(filtered, edge.getLabel());
113 // have we made a change to this node?
114 changed |= !filtered.equals(edge.getTail());
115 }
116
117 if (changed) {
118 // one of the node's neighbors has been replaced with merged version
119 // so use the new node
120 newNode = bld.build();
121 } else {
122 // no edges were changed, leave the node unmodified
123 newNode = toMerge;
124 }
125 nodeTable.put(Pair.of(sat, neighbors), newNode);
126 } else {
127 logger.debug("Node already in merged graph for satisfaction: {}", toMerge.getLabel());
128 }
129
130 // update merge map so future equivalent nodes get replaced with this one
131 mergedMap.put(toMerge, newNode);
132 }
133
134 // now let's find our return value - what did we merge the graph root to?
135 DAGNode<V, E> newRoot = mergedMap.get(graph);
136 // remember all its nodes for future merge operations
137 pool.addAll(newRoot.getReachableNodes());
138 // and we're done
139 return newRoot;
140 }
141 }