From 8ba1a8f46c005f14d0e678a1234e6c40e48871cc Mon Sep 17 00:00:00 2001 From: erik Date: Fri, 16 May 2008 09:45:25 +0000 Subject: [PATCH] Added basic graph functionality as a first step towards simplifying the container implementation. --- .../org/wamblee/system/graph/DefaultEdge.java | 38 +++++ .../org/wamblee/system/graph/DefaultNode.java | 44 ++++++ .../java/org/wamblee/system/graph/Edge.java | 22 +++ .../org/wamblee/system/graph/EdgeFactory.java | 22 +++ .../java/org/wamblee/system/graph/Graph.java | 138 +++++++++++++++++ .../java/org/wamblee/system/graph/Node.java | 22 +++ .../org/wamblee/system/graph/Visitor.java | 23 +++ .../org/wamblee/system/graph/GraphTest.java | 141 ++++++++++++++++++ .../wamblee/system/graph/MyEdgeFactory.java | 41 +++++ .../java/org/wamblee/system/graph/MyNode.java | 30 ++++ 10 files changed, 521 insertions(+) create mode 100644 system/general/src/main/java/org/wamblee/system/graph/DefaultEdge.java create mode 100644 system/general/src/main/java/org/wamblee/system/graph/DefaultNode.java create mode 100644 system/general/src/main/java/org/wamblee/system/graph/Edge.java create mode 100644 system/general/src/main/java/org/wamblee/system/graph/EdgeFactory.java create mode 100644 system/general/src/main/java/org/wamblee/system/graph/Graph.java create mode 100644 system/general/src/main/java/org/wamblee/system/graph/Node.java create mode 100644 system/general/src/main/java/org/wamblee/system/graph/Visitor.java create mode 100644 system/general/src/test/java/org/wamblee/system/graph/GraphTest.java create mode 100644 system/general/src/test/java/org/wamblee/system/graph/MyEdgeFactory.java create mode 100644 system/general/src/test/java/org/wamblee/system/graph/MyNode.java diff --git a/system/general/src/main/java/org/wamblee/system/graph/DefaultEdge.java b/system/general/src/main/java/org/wamblee/system/graph/DefaultEdge.java new file mode 100644 index 00000000..886186fd --- /dev/null +++ b/system/general/src/main/java/org/wamblee/system/graph/DefaultEdge.java @@ -0,0 +1,38 @@ +/* + * Copyright 2008 the original author or authors. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.wamblee.system.graph; + +public class DefaultEdge implements Edge { + + private Node _from; + private Node _to; + + public DefaultEdge(Node aFrom, Node aTo) { + _from = aFrom; + _to = aTo; + } + + @Override + public Node getFrom() { + return _from; + } + + @Override + public Node getTo() { + return _to; + } + +} diff --git a/system/general/src/main/java/org/wamblee/system/graph/DefaultNode.java b/system/general/src/main/java/org/wamblee/system/graph/DefaultNode.java new file mode 100644 index 00000000..7a7ff3c5 --- /dev/null +++ b/system/general/src/main/java/org/wamblee/system/graph/DefaultNode.java @@ -0,0 +1,44 @@ +/* + * Copyright 2008 the original author or authors. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.wamblee.system.graph; + +public class DefaultNode implements Node { + + private String _name; + + public DefaultNode(String aName) { + _name = aName; + } + + @Override + public String getName() { + return _name; + } + + @Override + public boolean equals(Object aObj) { + if ( !(aObj instanceof Node)) { + return false; + } + Node node = (Node)aObj; + return _name.equals(node.getName()); + } + + @Override + public int hashCode() { + return _name.hashCode(); + } +} diff --git a/system/general/src/main/java/org/wamblee/system/graph/Edge.java b/system/general/src/main/java/org/wamblee/system/graph/Edge.java new file mode 100644 index 00000000..3aa0d846 --- /dev/null +++ b/system/general/src/main/java/org/wamblee/system/graph/Edge.java @@ -0,0 +1,22 @@ +/* + * Copyright 2008 the original author or authors. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.wamblee.system.graph; + +public interface Edge { + + Node getFrom(); + Node getTo(); +} diff --git a/system/general/src/main/java/org/wamblee/system/graph/EdgeFactory.java b/system/general/src/main/java/org/wamblee/system/graph/EdgeFactory.java new file mode 100644 index 00000000..32601e7f --- /dev/null +++ b/system/general/src/main/java/org/wamblee/system/graph/EdgeFactory.java @@ -0,0 +1,22 @@ +/* + * Copyright 2008 the original author or authors. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.wamblee.system.graph; + +import java.util.List; + +public interface EdgeFactory { + List create(NodeType aFrom, NodeType aTo); +} diff --git a/system/general/src/main/java/org/wamblee/system/graph/Graph.java b/system/general/src/main/java/org/wamblee/system/graph/Graph.java new file mode 100644 index 00000000..5d6e6ccd --- /dev/null +++ b/system/general/src/main/java/org/wamblee/system/graph/Graph.java @@ -0,0 +1,138 @@ +/* + * Copyright 2008 the original author or authors. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.wamblee.system.graph; + +import java.util.ArrayList; +import java.util.List; + +public class Graph { + + private List _nodes; + private List _edges; + + public Graph() { + _nodes = new ArrayList(); + _edges = new ArrayList(); + } + + public void addNode(Node aNode) { + if (_nodes.contains(aNode)) { + throw new IllegalArgumentException("Node '" + aNode.getName() + + "' already exists"); + } + _nodes.add(aNode); + } + + public Node findNode(String aName) { + for (Node node: _nodes) { + if ( node.getName().equals(aName)) { + return node; + } + } + return null; + } + + public boolean removeNode(Node aNode) { + if (!findOutgoing(aNode).isEmpty() || !findIncoming(aNode).isEmpty()) { + throw new IllegalArgumentException("Cannot remove node '" + + aNode.getName() + + "' because it is connected to one or more edges"); + } + return _nodes.remove(aNode); + } + + public void addNodes(List aNodes) { + for (Node node : aNodes) { + addNode(node); + } + } + + public void addEdge(Edge aEdge) { + if (_edges.contains(aEdge)) { + throw new IllegalArgumentException("Edge '" + aEdge + + "' already exists"); + } + if (!_nodes.contains(aEdge.getFrom())) { + throw new IllegalArgumentException("From node '" + aEdge.getFrom() + + "' from edge '" + aEdge + "' is not part of the graph"); + } + if (!_nodes.contains(aEdge.getTo())) { + throw new IllegalArgumentException("To node '" + aEdge.getTo() + + "' from edge '" + aEdge + "' is not part of the graph"); + } + _edges.add(aEdge); + } + + public boolean removeEdge(Edge aEdge) { + return _edges.remove(aEdge); + } + + public void addEdges(List aEdges) { + for (Edge edge : aEdges) { + addEdge(edge); + } + } + + public List getNodes() { + return new ArrayList(_nodes); + } + + public List getEdges() { + return new ArrayList(_edges); + } + + public void extend(EdgeFactory aFactory) { + for (Node from : _nodes) { + for (Node to : _nodes) { + _edges.addAll(aFactory.create(from, to)); + } + } + } + + public List findOutgoing(Node aNode) { + List result = new ArrayList(); + for (Edge edge : _edges) { + if (edge.getFrom().getName().equals(aNode.getName())) { + result.add(edge); + } + } + return result; + } + + public List findIncoming(Node aNode) { + List result = new ArrayList(); + for (Edge edge : _edges) { + if (edge.getTo().getName().equals(aNode.getName())) { + result.add(edge); + } + } + return result; + } + + public void accept(Visitor aVisitor) { + List nodes = getNodes(); // copy to make sure the visitor can + // modify the + // list of nodes as part of the loop. + List edges = getEdges(); // copy ..... (see above). + + for (Node node : nodes) { + aVisitor.visitNode(node); + } + for (Edge edge : edges) { + aVisitor.visitEdge(edge); + } + } +} diff --git a/system/general/src/main/java/org/wamblee/system/graph/Node.java b/system/general/src/main/java/org/wamblee/system/graph/Node.java new file mode 100644 index 00000000..0becfda6 --- /dev/null +++ b/system/general/src/main/java/org/wamblee/system/graph/Node.java @@ -0,0 +1,22 @@ +/* + * Copyright 2008 the original author or authors. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.wamblee.system.graph; + +public interface Node { + + String getName(); + +} diff --git a/system/general/src/main/java/org/wamblee/system/graph/Visitor.java b/system/general/src/main/java/org/wamblee/system/graph/Visitor.java new file mode 100644 index 00000000..9c3240e0 --- /dev/null +++ b/system/general/src/main/java/org/wamblee/system/graph/Visitor.java @@ -0,0 +1,23 @@ +/* + * Copyright 2008 the original author or authors. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.wamblee.system.graph; + +public interface Visitor { + + void visitNode(Node aNode); + + void visitEdge(Edge aEdge); +} diff --git a/system/general/src/test/java/org/wamblee/system/graph/GraphTest.java b/system/general/src/test/java/org/wamblee/system/graph/GraphTest.java new file mode 100644 index 00000000..305765f9 --- /dev/null +++ b/system/general/src/test/java/org/wamblee/system/graph/GraphTest.java @@ -0,0 +1,141 @@ +/* + * Copyright 2008 the original author or authors. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.wamblee.system.graph; + +import java.util.Arrays; +import java.util.List; + +import org.easymock.classextension.EasyMock; +import org.wamblee.test.AssertionUtils; + +import junit.framework.TestCase; + +public class GraphTest extends TestCase { + + public void testNodeMgt() { + final Graph graph = new Graph(); + assertTrue(graph.getNodes().isEmpty()); + assertTrue(graph.getEdges().isEmpty()); + + final Node x = new DefaultNode("x"); + graph.addNode(x); + assertEquals(Arrays.asList(new Node[] { x }), graph.getNodes()); + assertSame(x, graph.findNode("x")); + assertNull(graph.findNode("y")); + + assertTrue(graph.removeNode(x)); + assertTrue(graph.getNodes().isEmpty()); + + // Empty node set. + assertFalse(graph.removeNode(x)); + + Node y = new DefaultNode("y"); + graph.addNodes(Arrays.asList(new Node[] { x, y} )); + assertEquals(2, graph.getNodes().size()); + + // duplicate node + AssertionUtils.assertException(new AssertionUtils.ErroneousCode() { + @Override + public void run() throws Exception { + graph.addNode(new DefaultNode("x")); + } + }, IllegalArgumentException.class); + } + + public void testEdgeMgt() { + final Graph graph = new Graph(); + final Node x = new DefaultNode("x"); + final Node y = new DefaultNode("y"); + graph.addNode(x); + graph.addNode(y); + final Edge e = new DefaultEdge(x, y); + graph.addEdge(e); + assertEquals(Arrays.asList(new Edge[] { e }), graph.getEdges()); + + // duplicate edge. + AssertionUtils.assertException(new AssertionUtils.ErroneousCode() { + @Override + public void run() throws Exception { + graph.addEdge(e); + } + }, IllegalArgumentException.class); + + // Remove node when edge is still present + AssertionUtils.assertException(new AssertionUtils.ErroneousCode() { + @Override + public void run() throws Exception { + graph.removeNode(x); + } + }, IllegalArgumentException.class); + + + Node a = new DefaultNode("a"); + graph.addNode(a); + graph.addEdges(Arrays.asList(new Edge[] { new DefaultEdge(x, a), new DefaultEdge(y, a) })); + assertEquals(3, graph.getEdges().size()); + } + + public void testExtend() { + Graph graph = new Graph(); + graph.addNode(new MyNode("x", new String[] { "a", "b"})); + graph.addNode(new MyNode("y", new String[] { "b", "c"})); + graph.addNode(new MyNode("z", new String[] { "a", "c"})); + graph.extend(new MyEdgeFactory()); + + List edges = graph.getEdges(); + assertEquals(12, edges.size()); // 2 outgoing and 2 incoming nodes. + } + + public void testFindIncomingOutgoing() { + Graph graph = new Graph(); + Node x = new DefaultNode("x"); + Node y = new DefaultNode("y"); + graph.addNode(x); + graph.addNode(y); + Edge e = new DefaultEdge(x,y); + graph.addEdge(e); + + List incoming = graph.findIncoming(x); + assertTrue(incoming.isEmpty()); + List outgoing = graph.findOutgoing(x); + assertEquals(1, outgoing.size()); + assertSame(e, outgoing.get(0)); + + incoming = graph.findIncoming(y); + assertEquals(1, incoming.size()); + assertSame(e, incoming.get(0)); + + outgoing = graph.findOutgoing(y); + assertTrue(outgoing.isEmpty()); + } + + public void testAccept() { + Graph graph = new Graph(); + Node x = new DefaultNode("x"); + Node y = new DefaultNode("y"); + Edge e = new DefaultEdge(x, y); + graph.addNode(x); + graph.addNode(y); + graph.addEdge(e); + Visitor visitor = EasyMock.createMock(Visitor.class); + visitor.visitNode(x); + visitor.visitNode(y); + visitor.visitEdge(e); + EasyMock.replay(visitor); + graph.accept(visitor); + EasyMock.verify(visitor); + } +} diff --git a/system/general/src/test/java/org/wamblee/system/graph/MyEdgeFactory.java b/system/general/src/test/java/org/wamblee/system/graph/MyEdgeFactory.java new file mode 100644 index 00000000..daddccd6 --- /dev/null +++ b/system/general/src/test/java/org/wamblee/system/graph/MyEdgeFactory.java @@ -0,0 +1,41 @@ +/* + * Copyright 2008 the original author or authors. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.wamblee.system.graph; + +import java.util.ArrayList; +import java.util.List; + +public class MyEdgeFactory implements EdgeFactory { + + public MyEdgeFactory() { + // Empty. + } + + @Override + public List create(MyNode aFrom, MyNode aTo) { + List result = new ArrayList(); + for (String fromPort: aFrom.getPorts()) { + for (String toPort: aTo.getPorts()) { + if ( fromPort.equals(toPort)) { + result.add(new DefaultEdge(aFrom, aTo)); + } + } + } + + return result; + } + +} diff --git a/system/general/src/test/java/org/wamblee/system/graph/MyNode.java b/system/general/src/test/java/org/wamblee/system/graph/MyNode.java new file mode 100644 index 00000000..0090c3f9 --- /dev/null +++ b/system/general/src/test/java/org/wamblee/system/graph/MyNode.java @@ -0,0 +1,30 @@ +/* + * Copyright 2008 the original author or authors. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.wamblee.system.graph; + +public class MyNode extends DefaultNode { + + private String[] _ports; + + public MyNode(String aName, String[] aPorts) { + super(aName); + _ports = aPorts; + } + + public String[] getPorts() { + return _ports; + } +} -- 2.31.1