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