KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > objectweb > perseus > dependency > lib > BasicDependencyGraph


1 /**
2  * Copyright (C) 2003 France Telecom R&D
3  *
4  * This library is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU Lesser General Public
6  * License as published by the Free Software Foundation; either
7  * version 2 of the License, or (at your option) any later version.
8  *
9  * This library is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12  * Lesser General Public License for more details.
13  *
14  * You should have received a copy of the GNU Lesser General Public
15  * License along with this library; if not, write to the Free Software
16  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17  */
18 package org.objectweb.perseus.dependency.lib;
19
20 import org.objectweb.fractal.api.control.BindingController;
21 import org.objectweb.perseus.dependency.api.DependencyGraph;
22 import org.objectweb.util.monolog.api.Logger;
23
24 import java.util.*;
25
26
27 /**
28  *
29  * @author S.Chassande-Barrioz
30  */
31 public final class BasicDependencyGraph
32         implements DependencyGraph, BindingController{
33
34     // associates to each node the set of its successors in the graph
35 public Map successors;
36
37     // list of nodes to be visited
38 private List toBeVisited;
39
40     // list of nodes already visited
41 private List visited;
42
43     protected Logger logger = null;
44
45     public BasicDependencyGraph () {
46         successors = new HashMap();
47         toBeVisited = new ArrayList();
48         visited = new ArrayList();
49     }
50
51     //IMPLEMENTATION OF THE UserBindingControler INTERFACE //
52 //------------------------------------------------------//
53
54     public String JavaDoc[] listFc() {
55         return new String JavaDoc[] {};
56     }
57
58     public Object JavaDoc lookupFc(String JavaDoc s) {
59         return null;
60     }
61
62     public void bindFc(String JavaDoc s, Object JavaDoc o) {
63         if ("logger".equals(s)) {
64             logger = (Logger) o;
65         }
66     }
67
68     public void unbindFc(String JavaDoc s) {
69     }
70
71
72     //IMPLEMENTATION OF THE DependencyGraph INTERFACE //
73 //------------------------------------------------//
74
75     /**
76      * Adds a vertex in the graph, or returns false is this would create a
77      * cycle.
78      */
79     public synchronized boolean addVertex (Object JavaDoc src, Object JavaDoc dst) {
80         Set s = (Set)successors.get(src);
81         if (s == null) {
82             s = new HashSet();
83             successors.put(src, s);
84         }
85         if (src.equals(dst) || s.contains(dst)) {
86             return true;
87         }
88
89         toBeVisited.clear();
90         visited.clear();
91
92         // finds the nodes accessible from dst
93 toBeVisited.add(dst);
94         while (!toBeVisited.isEmpty()) {
95             Object JavaDoc node = toBeVisited.remove(toBeVisited.size() - 1);
96             if (node.equals(src)) {
97                 // src is accessible from dst
98 // adding a vertex [src -> dst] would create a cycle
99 return false;
100             }
101             visited.add(node);
102
103             // adds the successors of 'node' in toBeVisited
104 Set t = (Set)successors.get(node);
105             if (t != null) {
106                 Iterator i = t.iterator();
107                 while (i.hasNext()) {
108                     Object JavaDoc successor = i.next();
109                     if (!visited.contains(successor)) {
110                         toBeVisited.add(successor);
111                     }
112                 }
113             }
114         }
115
116         s.add(dst);
117         return true;
118     }
119
120     /**
121      * Removes a vertex in the graph.
122      */
123     public synchronized void removeVertex (Object JavaDoc src, Object JavaDoc dst) {
124         Set s = (Set)successors.get(src);
125         if (s != null) {
126             s.remove(dst);
127             if (s.isEmpty()) {
128                 successors.remove(src);
129             }
130         }
131     }
132
133     void print(Object JavaDoc src, Object JavaDoc dst) {
134         StringBuffer JavaDoc sb = new StringBuffer JavaDoc();
135         sb.append("src=");
136         sb.append(src);
137         sb.append("\ndst=");
138         sb.append(dst);
139         sb.append("\n");
140         sb.append("dependency Graph: ");
141         if (successors.size() > 0) {
142             List waiters = new ArrayList(successors.keySet());
143             Set s = new HashSet(waiters.size() * 2);
144             s.addAll(successors.keySet());
145             s.addAll(successors.values());
146             for (int i = 0; i < waiters.size(); i++) {
147                 sb.append("\n");
148                 sb.append(waiters.get(i));
149                 sb.append(" = > ");
150                 sb.append(((Set)successors.get(waiters.get(i))).size());
151                 sb.append(": ");
152                 sb.append(successors.get(waiters.get(i)));
153             }
154         }
155         System.out.println(sb.toString());
156     }
157
158 }
159
Popular Tags