2 * Copyright 2008 the original author or authors.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
16 package org.wamblee.system.graph;
18 import java.util.ArrayList;
19 import java.util.List;
22 * Represents a graph consisting of nodes and edges.
24 * @author Erik Brakkee
28 private List<Node> _nodes;
29 private List<Edge> _edges;
32 * Constructs the graph.
35 _nodes = new ArrayList<Node>();
36 _edges = new ArrayList<Edge>();
44 * @throws IllegalArgumentException
45 * In case the node already exists. Node equality is checked
46 * using <code>equals</code>.
48 public void addNode(Node aNode) {
49 if (_nodes.contains(aNode)) {
50 throw new IllegalArgumentException("Node '" + aNode.getName()
51 + "' already exists");
57 * Finds a node with the given name.
61 * @return Node or null if not found.
63 public Node findNode(String aName) {
64 for (Node node : _nodes) {
65 if (node.getName().equals(aName)) {
77 * @return True iff the node was removed.
78 * @throws IllegalArgumentException
79 * In case there are edges of which the node is a part.
81 public boolean removeNode(Node aNode) {
82 if (!findOutgoing(aNode).isEmpty() || !findIncoming(aNode).isEmpty()) {
83 throw new IllegalArgumentException("Cannot remove node '"
85 + "' because it is connected to one or more edges");
87 return _nodes.remove(aNode);
91 * Adds a list of nodes.
98 public void addNodes(List<Node> aNodes) {
99 for (Node node : aNodes) {
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.
114 public void addEdge(Edge aEdge) {
115 if (_edges.contains(aEdge)) {
116 throw new IllegalArgumentException("Edge '" + aEdge
117 + "' already exists");
119 if (!_nodes.contains(aEdge.getFrom())) {
120 throw new IllegalArgumentException("From node '" + aEdge.getFrom()
121 + "' from edge '" + aEdge + "' is not part of the graph");
123 if (!_nodes.contains(aEdge.getTo())) {
124 throw new IllegalArgumentException("To node '" + aEdge.getTo()
125 + "' from edge '" + aEdge + "' is not part of the graph");
132 * @param aEdge Edge to remove.
133 * @return True if the edge was removed.
135 public boolean removeEdge(Edge aEdge) {
136 return _edges.remove(aEdge);
140 * Adds a number of edges.
141 * @param aEdges Edges to add.
143 public void addEdges(List<Edge> aEdges) {
144 for (Edge edge : aEdges) {
151 * @return Copy of the list of nodes of the graph.
153 public List<Node> getNodes() {
154 return new ArrayList<Node>(_nodes);
159 * @return Copy of the list of edges of the graph.
161 public List<Edge> getEdges() {
162 return new ArrayList<Edge>(_edges);
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.
170 public void extend(EdgeFactory aFactory) {
171 for (Node from : _nodes) {
172 for (Node to : _nodes) {
173 _edges.addAll(aFactory.create(from, to));
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.
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())) {
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.
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())) {
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.
217 public void accept(Visitor aVisitor) {
218 List<Node> nodes = getNodes(); // copy to make sure the visitor can
220 // list of nodes as part of the loop.
221 List<Edge> edges = getEdges(); // copy ..... (see above).
223 for (Node node : nodes) {
224 aVisitor.visitNode(node);
226 for (Edge edge : edges) {
227 aVisitor.visitEdge(edge);