wamblee.org Git - utils/blob - system/general/src/main/java/org/wamblee/system/graph/Graph.java

   1 /*
   2  * Copyright 2005-2010 the original author or authors.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *      http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16 package org.wamblee.system.graph;
  17
  18 import java.util.ArrayList;
  19 import java.util.Iterator;
  20 import java.util.List;
  21
  22 /**
  23  * Represents a graph consisting of nodes and edges.
  24  *
  25  * @author Erik Brakkee
  26  */
  27 public class Graph {
  28     private List<Node> nodes;
  29
  30     private List<Edge> edges;
  31
  32     /**
  33      * Constructs the graph.
  34      */
  35     public Graph() {
  36         nodes = new ArrayList<Node>();
  37         edges = new ArrayList<Edge>();
  38     }
  39
  40     /**
  41      * Adds a node.
  42      *
  43      * @param aNode
  44      *            Node to add.
  45      *
  46      * @throws IllegalArgumentException
  47      *             In case the node already exists. Node equality is checked
  48      *             using <code>equals</code>.
  49      */
  50     public void addNode(Node aNode) {
  51         if (nodes.contains(aNode)) {
  52             throw new IllegalArgumentException("Node '" + aNode.getName() +
  53                 "' already exists");
  54         }
  55
  56         nodes.add(aNode);
  57     }
  58
  59     /**
  60      * Finds a node with the given name.
  61      *
  62      * @param aName
  63      *            Node name.
  64      *
  65      * @return Node or null if not found.
  66      */
  67     public Node findNode(String aName) {
  68         for (Node node : nodes) {
  69             if (node.getName().equals(aName)) {
  70                 return node;
  71             }
  72         }
  73
  74         return null;
  75     }
  76
  77     /**
  78      * Removes a node.
  79      *
  80      * @param aNode
  81      *            Node to remove.
  82      *
  83      * @return True iff the node was removed.
  84      *
  85      * @throws IllegalArgumentException
  86      *             In case there are edges of which the node is a part.
  87      */
  88     public boolean removeNode(Node aNode) {
  89         if (!findOutgoing(aNode).isEmpty() || !findIncoming(aNode).isEmpty()) {
  90             throw new IllegalArgumentException("Cannot remove node '" +
  91                 aNode.getName() +
  92                 "' because it is connected to one or more edges");
  93         }
  94
  95         return nodes.remove(aNode);
  96     }
  97
  98     /**
  99      * Adds a list of nodes.
 100      *
 101      * @param aNodes
 102      *            Nodes to add.
 103      *
 104      * @see #addNode(Node)
 105      */
 106     public void addNodes(List<Node> aNodes) {
 107         for (Node node : aNodes) {
 108             addNode(node);
 109         }
 110     }
 111
 112     /**
 113      * Adds an edge.
 114      *
 115      * @param aEdge
 116      *            Edge to add.
 117      *
 118      * @throws IllegalArgumentException
 119      *             In case one of the nodes of the edges is not part of the
 120      *             graph or if the same edge (as determined by
 121      *             {@link #equals(Object)} is already a part of the graph.
 122      */
 123     public void addEdge(Edge aEdge) {
 124         if (edges.contains(aEdge)) {
 125             throw new IllegalArgumentException("Edge '" + aEdge +
 126                 "' already exists");
 127         }
 128
 129         if (!nodes.contains(aEdge.getFrom())) {
 130             throw new IllegalArgumentException("From node '" + aEdge.getFrom() +
 131                 "' from edge '" + aEdge + "' is not part of the graph");
 132         }
 133
 134         if (!nodes.contains(aEdge.getTo())) {
 135             throw new IllegalArgumentException("To node '" + aEdge.getTo() +
 136                 "' from edge '" + aEdge + "' is not part of the graph");
 137         }
 138
 139         edges.add(aEdge);
 140     }
 141
 142     /**
 143      * Removes an edge.
 144      *
 145      * @param aEdge
 146      *            Edge to remove.
 147      *
 148      * @return True if the edge was removed.
 149      */
 150     public boolean removeEdge(Edge aEdge) {
 151         return edges.remove(aEdge);
 152     }
 153
 154     /**
 155      * Adds a number of edges.
 156      *
 157      * @param aEdges
 158      *            Edges to add.
 159      */
 160     public void addEdges(List<Edge> aEdges) {
 161         for (Edge edge : aEdges) {
 162             addEdge(edge);
 163         }
 164     }
 165
 166     /**
 167      * Gets the nodes.
 168      *
 169      * @return Copy of the list of nodes of the graph.
 170      */
 171     public List<Node> getNodes() {
 172         return new ArrayList<Node>(nodes);
 173     }
 174
 175     /**
 176      * Gets the edges.
 177      *
 178      * @return Copy of the list of edges of the graph.
 179      */
 180     public List<Edge> getEdges() {
 181         return new ArrayList<Edge>(edges);
 182     }
 183
 184     /**
 185      * Extends the graph with edges using an edge factory. All combinations of
 186      * nodes are passed to the factory which creates additional edges.
 187      *
 188      * @param aFactory
 189      *            Edge factory.
 190      */
 191     public void extend(EdgeFactory aFactory) {
 192         for (Node from : nodes) {
 193             for (Node to : nodes) {
 194                 edges.addAll(aFactory.create(from, to));
 195             }
 196         }
 197     }
 198
 199     /**
 200      * Applies a filter to the graph for removing elements.
 201      *
 202      * @param aFilter
 203      *            Filter to apply.
 204      */
 205     public void applyFilter(EdgeFilter aFilter) {
 206         for (Iterator<Edge> edge = edges.iterator(); edge.hasNext();) {
 207             if (aFilter.isViolated(edge.next())) {
 208                 edge.remove();
 209             }
 210         }
 211     }
 212
 213     /**
 214      * Finds all outgoing edges of a node. More specifically, finds all edges
 215      * <code>e</code> for which <code>e.getFrom().getName() =
 216      * aNode.getName()</code>.
 217      *
 218      * @param aNode
 219      *            Node for which to find outgoing edges.
 220      *
 221      * @return List of outgoing edges.
 222      */
 223     public List<Edge> findOutgoing(Node aNode) {
 224         List<Edge> result = new ArrayList<Edge>();
 225
 226         for (Edge edge : edges) {
 227             if (edge.getFrom().getName().equals(aNode.getName())) {
 228                 result.add(edge);
 229             }
 230         }
 231
 232         return result;
 233     }
 234
 235     /**
 236      * Finds all incoming edges of a node. More specifically, finds all edges
 237      * <code>e</code> for which <code>e.getTo().getName() =
 238      * aNode.getName()</code>.
 239      *
 240      * @param aNode
 241      *            Node for which to find incoming edges.
 242      *
 243      * @return List of incoming edges.
 244      */
 245     public List<Edge> findIncoming(Node aNode) {
 246         List<Edge> result = new ArrayList<Edge>();
 247
 248         for (Edge edge : edges) {
 249             if (edge.getTo().getName().equals(aNode.getName())) {
 250                 result.add(edge);
 251             }
 252         }
 253
 254         return result;
 255     }
 256
 257     /**
 258      * Implements a visitor design pattern. This loops over all nodes and all
 259      * edges and invokes the appropriate visit methods on the visitor.
 260      *
 261      * @param aVisitor
 262      *            Visitor.
 263      */
 264     public void accept(Visitor aVisitor) {
 265         List<Node> allNodes = getNodes(); // copy to make sure the visitor can
 266         // modify the
 267         // list of nodes as part of the loop.
 268
 269         List<Edge> allEdges = getEdges(); // copy ..... (see above).
 270
 271         for (Node node : allNodes) {
 272             aVisitor.visitNode(node);
 273         }
 274
 275         for (Edge edge : allEdges) {
 276             aVisitor.visitEdge(edge);
 277         }
 278     }
 279 }