Graph


1   /*
2    * JBoss, Home of Professional Open Source
3    * Copyright 2005, JBoss Inc., and individual contributors as indicated
4    * by the @authors tag. See the copyright.txt in the distribution for a
5    * full listing of individual contributors.
6    *
7    * This is free software; you can redistribute it and/or modify it
8    * under the terms of the GNU Lesser General Public License as
9    * published by the Free Software Foundation; either version 2.1 of
10   * the License, or (at your option) any later version.
11   *
12   * This software is distributed in the hope that it will be useful,
13   * but WITHOUT ANY WARRANTY; without even the implied warranty of
14   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15   * Lesser General Public License for more details.
16   *
17   * You should have received a copy of the GNU Lesser General Public
18   * License along with this software; if not, write to the Free
19   * Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
20   * 02110-1301 USA, or see the FSF site: http://www.fsf.org.
21   */
22  package org.jboss.util.graph;
23  
24  import java.util.LinkedList  ;
25  import java.util.ArrayList  ;
26  
27  /**
28   * A directed graph data structure.
29   * 
30   * TODO: this needs to be moved into the common project.
31   * 
32   * @author Scott.Stark@jboss.org
33   * @version $Revision$
34   */
35  public class Graph<T>
36  {
37     /** Color used to mark unvisited nodes */
38     public static final int VISIT_COLOR_WHITE = 1;
39     /** Color used to mark nodes as they are first visited in DFS order */
40     public static final int VISIT_COLOR_GREY = 2;
41     /** Color used to mark nodes after descendants are completely visited */
42     public static final int VISIT_COLOR_BLACK = 3;
43     /** Vector<Vertex> of graph verticies */
44     private ArrayList  <Vertex<T>> verticies;
45     /** Vector<Edge> of edges in the graph */
46     private ArrayList  <Edge<T>> edges;
47  
48     // Construct a new graph
49     public Graph()
50     {
51        verticies = new ArrayList  <Vertex<T>>();
52        edges = new ArrayList  <Edge<T>>();
53     }
54  
55     /**
56      * Are there any verticies in the graph
57      * @return true if there are no verticies in the graph
58      */ 
59     public boolean isEmpty()
60     {
61        return verticies.size() == 0;
62     }
63  
64     /**
65      * Add a vertex to the graph
66      * @param v the Vertex to add
67      * @return true if the vertex was added, false if it was already in the graph.
68      */ 
69     public boolean addVertex(Vertex<T> v)
70     {
71        return verticies.add(v);
72     }
73  
74     /**
75      * Get the vertex count.
76      * @return the number of verticies in the graph.
77      */ 
78     public int size()
79     {
80        return verticies.size();
81     }
82  
83     /**
84      * Get the given Vertex.
85      * @param n the index [0, size()-1] of the Vertex to access
86      * @return the nth Vertex
87      */ 
88     public Vertex<T> getVertex(int n)
89     {
90        Vertex<T> v = verticies.get(n);
91        return v;
92     }
93  
94     /**
95      * Insert a directed, weighted Edge<T> into the graph
96      * @param from - the Edge<T> starting vertex
97      * @param to - the Edge<T> ending vertex
98      * @param cost - the Edge<T> weight/cost
99      * @return true if the Edge<T> was added, false if from already has this Edge<T>
100     */ 
101    public boolean addEdge(Vertex<T> from, Vertex<T> to, int cost)
102    {
103       Edge<T> e = new Edge<T>(from, to, cost);
104       if (from.findEdge(to) != null)
105          return false;
106       else
107       {
108          from.addEdge(e);
109          to.addEdge(e);
110          edges.add(e);
111          return true;
112       }
113    }
114 
115    /**
116     * Insert a bidirectional Edge<T> in the graph
117     * @param from - the Edge<T> starting vertex
118     * @param to - the Edge<T> ending vertex
119     * @param cost - the Edge<T> weight/cost
120     * @return true if edges between both nodes were added, false otherwise
121     */ 
122    public boolean insertBiEdge(Vertex<T> from, Vertex<T> to, int cost)
123    {
124       return addEdge(from, to, cost) && addEdge(to, from, cost);
125    }
126 
127    /**
128     * Remove a vertex from the graph
129     * @param from the Vertex to remove
130     * @return true if the Vertex was removed
131     */ 
132    public boolean removeVertex(Vertex<T> from)
133    {
134       if (!verticies.contains(from))
135          return false;
136 
137       verticies.remove(from);
138       for(int n = 0; n < from.getOutgoingEdgeCount(); n ++)
139       {
140          Edge<T> e = from.getOutgoingEdge(n);
141          from.remove(e);
142          Vertex<T> to = e.getTo();
143          to.remove(e);
144          edges.remove(e);
145       }
146       for(int n = 0; n < from.getIncomingEdgeCount(); n ++)
147       {
148          Edge<T> e = from.getIncomingEdge(n);
149          from.remove(e);
150          Vertex<T> predecessor = e.getFrom();
151          predecessor.remove(e);
152       }
153       return true;
154    }
155 
156    /**
157     * Remove an Edge<T> from the graph
158     * @param from - the Edge<T> starting vertex
159     * @param to - the Edge<T> ending vertex
160     * @return true if the Edge<T> exists, false otherwise
161     */ 
162    public boolean removeEdge(Vertex<T> from, Vertex<T> to)
163    {
164       Edge<T> e = from.findEdge(to);
165       if (e == null)
166          return false;
167       else
168       {
169          from.remove(e);
170          to.remove(e);
171          edges.remove(e);
172          return true;
173       }
174    }
175 
176    /**
177     * Clear the mark state of all verticies in the graph by calling
178     * clearMark() on all verticies.
179     * @see Vertex#clearMark()
180     */ 
181    public void clearMark()
182    {
183       for (int i = 0; i < verticies.size(); i++)
184       {
185          Vertex<T> w = verticies.get(i);
186          w.clearMark();
187       }
188    }
189 
190    /**
191     * Clear the mark state of all edges in the graph by calling
192     * clearMark() on all edges.
193     * @see Edge<T>#clearMark()
194     */ 
195    public void clearEdges()
196    {
197       for (int i = 0; i < edges.size(); i++)
198       {
199          Edge<T> e = (Edge<T>) edges.get(i);
200          e.clearMark();
201       }
202    }
203 
204    /**
205     * Perform a depth first serach using recursion.
206     * @param v - the Vertex to start the search from
207     * @param visitor - the vistor to inform prior to 
208     * @see Visitor#visit(Graph, Vertex) 
209     */ 
210    public void depthFirstSearch(Vertex<T> v, final Visitor<T> visitor)
211    {
212       VisitorEX<T, RuntimeException  > wrapper = new VisitorEX<T, RuntimeException  >()
213       {
214          public void visit(Graph<T> g, Vertex<T> v) throws RuntimeException  
215          {
216             visitor.visit(g, v);
217          }
218       };
219       this.depthFirstSearch(v, wrapper);
220    }
221    public <E extends Exception  > void depthFirstSearch(Vertex<T> v, VisitorEX<T, E> visitor)
222       throws E
223    {
224       if( visitor != null )
225          visitor.visit(this, v);      
226       v.visit();
227       for (int i = 0; i < v.getOutgoingEdgeCount(); i++)
228       {
229          Edge<T> e = v.getOutgoingEdge(i);
230          if (!e.getTo().visited())
231          {
232             depthFirstSearch(e.getTo(), visitor);
233          }
234       }
235    }
236 
237    // Breadth First Search
238    public void breadthFirstSearch(Vertex<T> v, final Visitor<T> visitor)
239    {
240       VisitorEX<T, RuntimeException  > wrapper = new VisitorEX<T, RuntimeException  >()
241       {
242          public void visit(Graph<T> g, Vertex<T> v) throws RuntimeException  
243          {
244             visitor.visit(g, v);
245          }
246       };
247       this.breadthFirstSearch(v, wrapper);
248    }
249    public <E extends Exception  > void breadthFirstSearch(Vertex<T> v, VisitorEX<T, E> visitor)
250       throws E
251    {
252       LinkedList  <Vertex<T>> q = new LinkedList  <Vertex<T>>();
253 
254       q.add(v);
255       if( visitor != null )
256          visitor.visit(this, v);
257       v.visit();
258       while (q.isEmpty() == false)
259       {
260          v = q.removeFirst();
261          for (int i = 0; i < v.getOutgoingEdgeCount(); i++)
262          {
263             Edge<T> e = v.getOutgoingEdge(i);
264             if (!e.getTo().visited())
265             {
266                q.add(e.getTo());
267                if( visitor != null )
268                   visitor.visit(this, e.getTo());
269                e.getTo().visit();
270             }
271          }
272       }
273    }
274 
275    // Find Spanning Tree
276    public void dfsSpanningTree(Vertex<T> v, DFSVisitor<T> visitor)
277    {
278       v.visit();
279       if( visitor != null )
280          visitor.visit(this, v);
281 
282       for (int i = 0; i < v.getOutgoingEdgeCount(); i++)
283       {
284          Edge<T> e = v.getOutgoingEdge(i);
285          if (!e.getTo().visited())
286          {
287             if( visitor != null )
288                visitor.visit(this, v, e);
289             e.mark();
290             dfsSpanningTree(e.getTo(), visitor);
291          }
292       }
293    }
294 
295 
296    /*
297    In order to detect cycles, we use a modified depth first search called a
298    colored DFS. All nodes are initially marked white. When a node is
299    encountered, it is marked grey, and when its descendants are completely
300    visited, it is marked black. If a grey node is ever encountered, then there
301    is a cycle. 
302    */
303    public Edge<T>[] findCycles()
304    {
305       ArrayList  <Edge<T>> cycleEdges = new ArrayList  <Edge<T>>();
306       // Mark all verticies as white
307       for(int n = 0; n < verticies.size(); n ++)
308       {
309          Vertex<T> v = getVertex(n);
310          v.setMarkState(VISIT_COLOR_WHITE);
311       }
312       for(int n = 0; n < verticies.size(); n ++)
313       {
314          Vertex<T> v = getVertex(n);
315          visit(v, cycleEdges);
316       }
317       Edge<T>[] cycles = new Edge[cycleEdges.size()];
318       cycleEdges.toArray(cycles);
319       return cycles;
320    }
321 
322    private void visit(Vertex<T> v, ArrayList  <Edge<T>> cycleEdges)
323    {
324       v.setMarkState(VISIT_COLOR_GREY);
325       int count = v.getOutgoingEdgeCount();
326       for(int n = 0; n < count; n ++)
327       {
328          Edge<T> e = v.getOutgoingEdge(n);
329          Vertex<T> u = e.getTo();
330          if( u.getMarkState() == VISIT_COLOR_GREY )
331          {
332             // A cycle Edge<T>
333             cycleEdges.add(e);
334          }
335          else if( u.getMarkState() == VISIT_COLOR_WHITE )
336          {
337             visit(u, cycleEdges);
338          }
339       }
340       v.setMarkState(VISIT_COLOR_BLACK);
341    }
342 
343    public String   toString()
344    {
345       StringBuffer   tmp = new StringBuffer  ("Graph[");
346       for (int i = 0; i < verticies.size(); i++)
347       {
348          Vertex<T> v = verticies.get(i);
349          tmp.append(v);
350       }
351       tmp.append(']');
352       return tmp.toString();
353    }
354    
355 }
356
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags