Skip to main content
aboutsummaryrefslogtreecommitdiffstats
blob: 02860e7b84a7c5f3e76796d85d3bf19ed123a276 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
// ========================================================================
// Copyright (c) Webtide LLC
// ------------------------------------------------------------------------
// All rights reserved. This program and the accompanying materials
// are made available under the terms of the Eclipse Public License v1.0
// and Apache License v2.0 which accompanies this distribution.
//
// The Eclipse Public License is available at 
// http://www.eclipse.org/legal/epl-v10.html
//
// The Apache License v2.0 is available at
// http://www.apache.org/licenses/LICENSE-2.0.txt
//
// You may elect to redistribute this code under either of these licenses. 
// ========================================================================
package org.eclipse.jetty.deploy.graph;

import java.util.HashSet;
import java.util.Set;
import java.util.concurrent.CopyOnWriteArrayList;

/**
 * Basic directed graph implementation
 */
public class Graph
{
    private Set<Node> _nodes = new HashSet<Node>();
    private Set<Edge> _edges = new HashSet<Edge>();

    public void addEdge(Edge edge)
    {
        Node fromNode = getNodeByName(edge.getFrom().getName());
        if (fromNode==null)
            addNode(fromNode=edge.getFrom());
        Node toNode = getNodeByName(edge.getTo().getName());
        if (toNode==null)
            addNode(toNode=edge.getTo());
        
        // replace edge with normalized edge
        if (edge.getFrom()!=fromNode || edge.getTo()!=toNode)
            edge=new Edge(fromNode,toNode);
        
        this._edges.add(edge);
    }

    public void addEdge(String from, String to)
    {
        Node fromNode = getNodeByName(from);
        if (fromNode==null)
        {
            fromNode = new Node(from);
            addNode(fromNode);
        }
            
        Node toNode = getNodeByName(to);
        if (toNode==null)
        {
            toNode = new Node(to);
            addNode(toNode);
        }

        addEdge(fromNode,toNode);
    }

    private void addEdge(Node fromNode, Node toNode)
    {
        Edge edge = new Edge(fromNode,toNode);
        addEdge(edge);
    }

    public void addNode(Node node)
    {
        this._nodes.add(node);
    }

    /**
     * Convenience method for {@link #insertNode(Edge, Node)}
     * 
     * @param edge
     *            the edge to split and insert a node into
     * @param nodeName
     *            the name of the node to insert along the edge
     */
    public void insertNode(Edge edge, String nodeName)
    {
        Node node = getNodeByName(nodeName);
        if (node==null)
        {
            node = new Node(nodeName);
        }

        insertNode(edge,node);
    }

    /**
     * Insert an arbitrary node on an existing edge.
     * 
     * @param edge
     *            the edge to split and insert a node into
     * @param node
     *            the node to insert along the edge
     */
    public void insertNode(Edge edge, Node node)
    {
        // Remove existing edge
        removeEdge(edge);
        // Ensure node is added
        addNode(node);
        // Add start edge
        addEdge(edge.getFrom(),node);
        // Add second edge
        addEdge(node,edge.getTo());
    }

    /**
     * Find all edges that are connected to the specific node, both as an outgoing {@link Edge#getFrom()} or incoming
     * {@link Edge#getTo()} end point.
     * 
     * @param node
     *            the node with potential end points
     * @return the set of edges connected to the node
     */
    public Set<Edge> findEdges(Node node)
    {
        Set<Edge> fromedges = new HashSet<Edge>();

        for (Edge edge : this._edges)
        {
            if ((edge.getFrom() == node) || (edge.getTo() == node))
            {
                fromedges.add(edge);
            }
        }

        return fromedges;
    }

    /**
     * Find all edges that are connected {@link Edge#getFrom()} the specific node.
     * 
     * @param from
     *            the node with potential edges from it
     * @return the set of edges from the node
     */
    public Set<Edge> findEdgesFrom(Node from)
    {
        Set<Edge> fromedges = new HashSet<Edge>();

        for (Edge edge : this._edges)
        {
            if (edge.getFrom() == from)
            {
                fromedges.add(edge);
            }
        }

        return fromedges;
    }

    /**
     * Convenience method for {@link #getPath(Node, Node)}
     * 
     * @param nodeNameOrigin
     *            the name of the node to the path origin.
     * @param nodeNameDest
     *            the name of the node to the path destination.
     * @return the path to take
     */
    public Path getPath(String nodeNameOrigin, String nodeNameDest)
    {
        if (nodeNameOrigin.equals(nodeNameDest))
        {
            return new Path();
        }

        Node from = getNodeByName(nodeNameOrigin);
        Node to = getNodeByName(nodeNameDest);
        return getPath(from,to);
    }

    /**
     * Using BFS (Breadth First Search) return the path from a any arbitrary node to any other.
     * 
     * @param from
     *            the node from
     * @param to
     *            the node to
     * @return the path to take or null if there is no path.
     */
    public Path getPath(Node from, Node to)
    {
        if (from == to)
        {
            return new Path();
        }

        // Perform a Breadth First Search (BFS) of the tree.
        Path path = breadthFirst(from,to,new CopyOnWriteArrayList<Path>(),new HashSet<Edge>());
        return path;
    }
    

    private Path breadthFirst(Node from, Node destination, CopyOnWriteArrayList<Path> paths, Set<Edge> seen)
    {
        // Add next unseen segments to paths.
        boolean edgesAdded = false;
        if (paths.size()==0)
            paths.add(new Path());

        for (Path path : paths)
        {
            Set<Edge> next = findEdgesFrom(path.nodes()==0?from:path.lastNode());
            if (next.size() == 0)
                continue; // no new edges

            // Split path for other edges
            int splits=0;
            for (Edge edge:next)
            {
                if (seen.contains(edge))
                    continue;
                seen.add(edge);
                Path nextPath = (++splits==next.size())?path:path.forkPath();
                // Add segment to split'd path
                nextPath.add(edge);
                
                // Are we there yet?
                if (destination.equals(edge.getTo()))
                    return nextPath;

                edgesAdded = true;
                
                // Add to extra paths
                if (nextPath!=path)
                    paths.add(nextPath);
            }
        }

        if (edgesAdded)
            return breadthFirst(from,destination,paths,seen);
        return null;
    }


    public Set<Edge> getEdges()
    {
        return _edges;
    }

    /**
     * Get the Node by Name.
     * 
     * @param name
     *            the name to lookup
     * @return the node if found or null if not found.
     */
    public Node getNodeByName(String name)
    {
        for (Node node : _nodes)
        {
            if (node.getName().equals(name))
            {
                return node;
            }
        }
        return null;
    }

    public Set<Node> getNodes()
    {
        return _nodes;
    }

    public void removeEdge(Edge edge)
    {
        this._edges.remove(edge);
    }

    public void removeEdge(String fromNodeName, String toNodeName)
    {
        Node fromNode = getNodeByName(fromNodeName);
        Node toNode = getNodeByName(toNodeName);
        Edge edge = new Edge(fromNode,toNode);
        removeEdge(edge);
    }

    public void removeNode(Node node)
    {
        this._nodes.remove(node);
    }

    public void setEdges(Set<Edge> edges)
    {
        this._edges = edges;
    }

    public void setNodes(Set<Node> nodes)
    {
        this._nodes = nodes;
    }
}

Back to the top