001/*-----------------------------------------------------------------------+ 002 | org.conqat.engine.index.incubator 003 | | 004 $Id$ 005 | | 006 | Copyright (c) 2009-2013 CQSE GmbH | 007 +-----------------------------------------------------------------------*/ 008package org.conqat.lib.commons.graph; 009 010import static org.conqat.lib.commons.collections.CollectionUtils.map; 011import static org.conqat.lib.commons.string.StringUtils.concat; 012 013import java.util.ArrayDeque; 014import java.util.Collection; 015import java.util.Collections; 016import java.util.Deque; 017import java.util.HashSet; 018import java.util.Optional; 019import java.util.Set; 020 021import org.conqat.lib.commons.collections.IIdProvider; 022import org.conqat.lib.commons.collections.IdManager; 023import org.conqat.lib.commons.visitor.IMeshWalker; 024 025/** 026 * Useful methods for debugging arbitrary graphs. 027 */ 028public class GraphDebuggingUtils { 029 030 /** 031 * Returns a string representation of the graph. The individual nodes are 032 * represented using their toString() method. This is useful for debugging. 033 * 034 * @param root 035 * the root node of the graph to visualize. 036 * @param optionalIdProvider 037 * an optional IdProvider that provides integer IDs for all Nodes. If 038 * {@code null}, we will use an IdManager. The IDs are assumed to be 039 * stable (the same on each query of the same node). 040 * @param walkers 041 * the mesh walkers used to traverse the graph. 042 */ 043 @SafeVarargs 044 public static <NodeT, X extends Exception> String getString(NodeT root, 045 IIdProvider<Integer, NodeT> optionalIdProvider, IMeshWalker<NodeT, X>... walkers) throws X { 046 return getString(root, optionalIdProvider, true, walkers); 047 } 048 049 /** 050 * Returns a human-readable string representation of the graph. The individual 051 * nodes are only represented as integers. This is useful for debugging. 052 * 053 * @param root 054 * the root node of the graph to visualize. 055 * @param optionalIdProvider 056 * an optional IdProvider that provides integer IDs for all Nodes. If 057 * {@code null}, we will use an IdManager. The IDs are assumed to be 058 * stable (the same on each query of the same node). 059 * @param walkers 060 * the mesh walkers used to traverse the graph. 061 */ 062 @SafeVarargs 063 public static <NodeT, X extends Exception> String getShortString(NodeT root, 064 IIdProvider<Integer, NodeT> optionalIdProvider, IMeshWalker<NodeT, X>... walkers) throws X { 065 return getString(root, optionalIdProvider, false, walkers); 066 } 067 068 /** 069 * Returns a string representation of the graph. 070 * 071 * @param root 072 * the root node of the graph to visualize. 073 * @param optionalIdProvider 074 * an optional IdProvider that provides integer IDs for all Nodes. If 075 * {@code null}, we will use an IdManager. The IDs are assumed to be 076 * stable (the same on each query of the same node). 077 * @param detailed 078 * if <code>true</code>, each node's toString() representation is 079 * included in the output. 080 * @param walkers 081 * the mesh walkers used to traverse different classes of edges found 082 * in the graph. 083 */ 084 @SafeVarargs 085 private static <NodeT, X extends Exception> String getString(NodeT root, 086 IIdProvider<Integer, NodeT> optionalIdProvider, boolean detailed, IMeshWalker<NodeT, X>... walkers) 087 throws X { 088 IIdProvider<Integer, NodeT> idProvider = getIdProvider(optionalIdProvider); 089 090 INodeRenderer<NodeT> nodeRenderer = (node) -> { 091 StringBuilder rendering = new StringBuilder(); 092 rendering.append(idProvider.obtainId(node)); 093 if (detailed) { 094 rendering.append(": { "); 095 rendering.append(node); 096 rendering.append(" }"); 097 } 098 return rendering.toString(); 099 }; 100 IEdgeRenderer<NodeT> edgeRenderer = (node, edgeClass, adjacentNodes) -> " --> " 101 + concat(map(adjacentNodes, idProvider::obtainId), ", ") + "\n"; 102 103 return renderGraph(root, nodeRenderer, edgeRenderer, walkers); 104 } 105 106 /** 107 * Returns a string representation of the graph in Dot format suitable for 108 * rendering with Graphviz. 109 * 110 * @param root 111 * the root node of the graph to visualize. 112 * @param optionalIdProvider 113 * an optional IdProvider that provides integer IDs for all Nodes. If 114 * {@code null}, we will use an IdManager. The IDs are assumed to be 115 * stable (the same on each query of the same node). 116 * @param walkers 117 * the mesh walkers used to traverse different classes of edges found 118 * in the graph. 119 * 120 * @see <a href="https://graphviz.gitlab.io/_pages/doc/info/lang.html">The DOT 121 * Language</a> 122 */ 123 @SafeVarargs 124 public static <NodeT, X extends Exception> String getDotString(NodeT root, 125 IIdProvider<Integer, NodeT> optionalIdProvider, IMeshWalker<NodeT, X>... walkers) throws X { 126 IIdProvider<Integer, NodeT> idProvider = getIdProvider(optionalIdProvider); 127 128 INodeRenderer<NodeT> nodeRenderer = (node) -> idProvider.obtainId(node) + // 129 " [label = " + toQuotedString(node.toString()) + "];\n"; 130 IEdgeRenderer<NodeT> edgeRenderer = (node, edgeClass, adjacentNodes) -> idProvider.obtainId(node) + " -> " + // 131 "{ " + concat(map(adjacentNodes, idProvider::obtainId), " ") + " }" + " [color=\"" 132 + EDGE_COLORS[edgeClass] + "\"];\n"; 133 134 return "digraph {\n" + renderGraph(root, nodeRenderer, edgeRenderer, walkers) + "}\n"; 135 } 136 137 /** Colors for different classes of edges */ 138 private static final String[] EDGE_COLORS = { "black", "blue", "red", "green" }; 139 140 private static <NodeT> IIdProvider<Integer, NodeT> getIdProvider(IIdProvider<Integer, NodeT> optionalIdProvider) { 141 return Optional.ofNullable(optionalIdProvider).orElseGet(IdManager::new); 142 } 143 144 @SafeVarargs 145 private static <NodeT, X extends Exception> String renderGraph(NodeT root, INodeRenderer<NodeT> nodeRenderer, 146 IEdgeRenderer<NodeT> edgeRenderer, IMeshWalker<NodeT, X>... walkers) throws X { 147 StringBuilder graph = new StringBuilder(); 148 149 Deque<NodeT> todo = new ArrayDeque<>(Collections.singleton(root)); 150 Set<NodeT> addedNodes = new HashSet<>(); 151 while (!todo.isEmpty()) { 152 NodeT nodeToAdd = todo.poll(); 153 if (!addedNodes.contains(nodeToAdd)) { 154 graph.append(nodeRenderer.render(nodeToAdd)); 155 156 for (int walkerIndex = 0; walkerIndex < walkers.length; walkerIndex++) { 157 IMeshWalker<NodeT, X> walker = walkers[walkerIndex]; 158 Collection<NodeT> adjacentElements = walker.getAdjacentElements(nodeToAdd); 159 graph.append(edgeRenderer.render(nodeToAdd, walkerIndex, adjacentElements)); 160 todo.addAll(adjacentElements); 161 } 162 163 addedNodes.add(nodeToAdd); 164 } 165 } 166 167 return graph.toString(); 168 } 169 170 /** 171 * Produces a double-quoted string as defined by the 172 * <a href="https://graphviz.gitlab.io/_pages/doc/info/lang.html">DOT 173 * language</a>. 174 */ 175 private static String toQuotedString(String string) { 176 return '"' + string.replace("\"", "\\\"") + '"'; 177 } 178 179 @FunctionalInterface 180 private interface INodeRenderer<NodeT> { 181 182 /** Renders the given node. */ 183 String render(NodeT node); 184 } 185 186 @FunctionalInterface 187 private interface IEdgeRenderer<NodeT> { 188 189 /** 190 * Renders the edges (of the given class) from the node to any adjacent nodes. 191 */ 192 String render(NodeT node, int edgeClass, Collection<NodeT> adjacentNodes); 193 } 194}