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

   1 /*
   2  * Copyright 2008 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
  29     private List<Node> nodes;
  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      * @throws IllegalArgumentException
  46      *             In case the node already exists. Node equality is checked
  47      *             using <code>equals</code>.
  48      */
  49     public void addNode(Node aNode) {
  50         if (nodes.contains(aNode)) {
  51             throw new IllegalArgumentException("Node '" + aNode.getName()
  52                     + "' already exists");
  53         }
  54         nodes.add(aNode);
  55     }
  56
  57     /**
  58      * Finds a node with the given name.
  59      *
  60      * @param aName
  61      *            Node name.
  62      * @return Node or null if not found.
  63      */
  64     public Node findNode(String aName) {
  65         for (Node node : nodes) {
  66             if (node.getName().equals(aName)) {
  67                 return node;
  68             }
  69         }
  70         return null;
  71     }
  72
  73     /**
  74      * Removes a node.
  75      *
  76      * @param aNode
  77      *            Node to remove.
  78      * @return True iff the node was removed.
  79      * @throws IllegalArgumentException
  80      *             In case there are edges of which the node is a part.
  81      */
  82     public boolean removeNode(Node aNode) {
  83         if (!findOutgoing(aNode).isEmpty() || !findIncoming(aNode).isEmpty()) {
  84             throw new IllegalArgumentException("Cannot remove node '"
  85                     + aNode.getName()
  86                     + "' because it is connected to one or more edges");
  87         }
  88         return nodes.remove(aNode);
  89     }
  90
  91     /**
  92      * Adds a list of nodes.
  93      *
  94      * @param aNodes
  95      *            Nodes to add.
  96      *
  97      * @see #addNode(Node)
  98      */
  99     public void addNodes(List<Node> aNodes) {
 100         for (Node node : aNodes) {
 101             addNode(node);
 102         }
 103     }
 104
 105     /**
 106      * Adds an edge.
 107      *
 108      * @param aEdge
 109      *            Edge to add.
 110      * @throws IllegalArgumentException
 111      *             In case one of the nodes of the edges is not part of the
 112      *             graph or if the same edge (as determined by
 113      *             {@link #equals(Object)} is already a part of the graph.
 114      */
 115     public void addEdge(Edge aEdge) {
 116         if (edges.contains(aEdge)) {
 117             throw new IllegalArgumentException("Edge '" + aEdge
 118                     + "' already exists");
 119         }
 120         if (!nodes.contains(aEdge.getFrom())) {
 121             throw new IllegalArgumentException("From node '" + aEdge.getFrom()
 122                     + "' from edge '" + aEdge + "' is not part of the graph");
 123         }
 124         if (!nodes.contains(aEdge.getTo())) {
 125             throw new IllegalArgumentException("To node '" + aEdge.getTo()
 126                     + "' from edge '" + aEdge + "' is not part of the graph");
 127         }
 128         edges.add(aEdge);
 129     }
 130
 131     /**
 132      * Removes an edge.
 133      * @param aEdge Edge to remove.
 134      * @return True if the edge was removed.
 135      */
 136     public boolean removeEdge(Edge aEdge) {
 137         return edges.remove(aEdge);
 138     }
 139
 140     /**
 141      * Adds a number of edges.
 142      * @param aEdges Edges to add.
 143      */
 144     public void addEdges(List<Edge> aEdges) {
 145         for (Edge edge : aEdges) {
 146             addEdge(edge);
 147         }
 148     }
 149
 150     /**
 151      * Gets the nodes.
 152      * @return Copy of the list of nodes of the graph.
 153      */
 154     public List<Node> getNodes() {
 155         return new ArrayList<Node>(nodes);
 156     }
 157
 158     /**
 159      * Gets the edges.
 160      * @return Copy of the list of edges of the graph.
 161      */
 162     public List<Edge> getEdges() {
 163         return new ArrayList<Edge>(edges);
 164     }
 165
 166     /**
 167      * Extends the graph with edges using an edge factory. All combinations of
 168      * nodes are passed to the factory which creates additional edges.
 169      * @param aFactory Edge factory.
 170      */
 171     public void extend(EdgeFactory aFactory) {
 172         for (Node from : nodes) {
 173             for (Node to : nodes) {
 174                 edges.addAll(aFactory.create(from, to));
 175             }
 176         }
 177     }
 178
 179     /**
 180      * Applies a filter to the graph for removing elements.
 181      * @param aFilter Filter to apply.
 182      */
 183     public void applyFilter(EdgeFilter aFilter) {
 184         for (Iterator<Edge> edge = edges.iterator(); edge.hasNext(); ) {
 185             if (aFilter.isViolated(edge.next())) {
 186                 edge.remove();
 187             }
 188         }
 189     }
 190
 191     /**
 192      * Finds all outgoing edges of a node. More specifically, finds
 193      * all edges <code>e</code> for which <code>e.getFrom().getName() = aNode.getName()</code>.
 194      * @param aNode Node for which to find outgoing edges.
 195      * @return List of outgoing edges.
 196      */
 197     public List<Edge> findOutgoing(Node aNode) {
 198         List<Edge> result = new ArrayList<Edge>();
 199         for (Edge edge : edges) {
 200             if (edge.getFrom().getName().equals(aNode.getName())) {
 201                 result.add(edge);
 202             }
 203         }
 204         return result;
 205     }
 206
 207     /**
 208      * Finds all incoming edges of a node.
 209      * More specifically, finds
 210      * all edges <code>e</code> for which <code>e.getTo().getName() = aNode.getName()</code>.
 211      * @param aNode Node for which to find incoming edges.
 212      * @return List of incoming edges.
 213      */
 214     public List<Edge> findIncoming(Node aNode) {
 215         List<Edge> result = new ArrayList<Edge>();
 216         for (Edge edge : edges) {
 217             if (edge.getTo().getName().equals(aNode.getName())) {
 218                 result.add(edge);
 219             }
 220         }
 221         return result;
 222     }
 223
 224     /**
 225      * Implements a visitor design pattern.
 226      * This loops over all nodes and all edges and invokes the appropriate visit
 227      * methods on the visitor.
 228      * @param aVisitor Visitor.
 229      */
 230     public void accept(Visitor aVisitor) {
 231         List<Node> nodes = getNodes(); // copy to make sure the visitor can
 232         // modify the
 233         // list of nodes as part of the loop.
 234         List<Edge> edges = getEdges(); // copy ..... (see above).
 235
 236         for (Node node : nodes) {
 237             aVisitor.visitNode(node);
 238         }
 239         for (Edge edge : edges) {
 240             aVisitor.visitEdge(edge);
 241         }
 242     }
 243 }