1 | using System;
|
---|
2 | using System.Drawing;
|
---|
3 | using System.Collections;
|
---|
4 | using System.Collections.Generic;
|
---|
5 | using System.Collections.Specialized;
|
---|
6 | using System.Text;
|
---|
7 | using Netron.Diagramming.Core.Analysis;
|
---|
8 | namespace Netron.Diagramming.Core {
|
---|
9 | public partial class Model : IGraph, ITree {
|
---|
10 | #region Fields
|
---|
11 | private bool mIsDirected;
|
---|
12 | private ITree mSpanningTree;
|
---|
13 | #endregion
|
---|
14 |
|
---|
15 | /// <summary>
|
---|
16 | /// Get the in-degree of a node, the number of edges for which the node
|
---|
17 | /// is the target.
|
---|
18 | /// </summary>
|
---|
19 | /// <param name="node"></param>
|
---|
20 | /// <returns></returns>
|
---|
21 | int IGraph.InDegree(INode node) {
|
---|
22 | return (node as INode).InDegree;
|
---|
23 | }
|
---|
24 |
|
---|
25 | /// <summary>
|
---|
26 | /// Get the out-degree of a node, the number of edges for which the node
|
---|
27 | /// is the source.
|
---|
28 | /// </summary>
|
---|
29 | /// <param name="node"></param>
|
---|
30 | /// <returns></returns>
|
---|
31 | int IGraph.OutDegree(INode node) {
|
---|
32 | return (node as INode).OutDegree;
|
---|
33 | }
|
---|
34 |
|
---|
35 | /// <summary>
|
---|
36 | /// Get the degree of a node, the number of edges for which a node
|
---|
37 | /// is either the source or the target.
|
---|
38 | /// </summary>
|
---|
39 | /// <param name="node"></param>
|
---|
40 | /// <returns></returns>
|
---|
41 | int IGraph.Degree(INode node) {
|
---|
42 | return (node as INode).Degree;
|
---|
43 | }
|
---|
44 |
|
---|
45 | /// <summary>
|
---|
46 | /// Indicates if the edges of this graph are directed or undirected.
|
---|
47 | /// </summary>
|
---|
48 | /// <value></value>
|
---|
49 | bool IGraph.IsDirected {
|
---|
50 | get { return mIsDirected; }
|
---|
51 | }
|
---|
52 |
|
---|
53 | /// <summary>
|
---|
54 | /// Returns the nodes for the current page. This is the same as the <see cref="Model.Shapes"/> property except that the return type is
|
---|
55 | /// here <see cref="INode"/> rather than <see cref="IShape"/> type.
|
---|
56 | /// </summary>
|
---|
57 | /// <value></value>
|
---|
58 | CollectionBase<INode> IGraph.Nodes {
|
---|
59 | get {
|
---|
60 | CollectionBase<INode> nodes = new CollectionBase<INode>();
|
---|
61 | foreach (IShape shape in this.CurrentPage.Shapes) {
|
---|
62 | nodes.Add(shape as INode);
|
---|
63 | }
|
---|
64 | return nodes;
|
---|
65 | }
|
---|
66 | }
|
---|
67 |
|
---|
68 | /// <summary>
|
---|
69 | /// Gets the edges.
|
---|
70 | /// </summary>
|
---|
71 | /// <value>The edges.</value>
|
---|
72 | CollectionBase<IEdge> IGraph.Edges {
|
---|
73 | get {
|
---|
74 | CollectionBase<IEdge> edges = new CollectionBase<IEdge>();
|
---|
75 | foreach (IConnection cn in this.CurrentPage.Connections) {
|
---|
76 | edges.Add(cn as IEdge);
|
---|
77 | }
|
---|
78 | return edges;
|
---|
79 | }
|
---|
80 | }
|
---|
81 | /// <summary>
|
---|
82 | /// Get the source Node for the given Edge instance.
|
---|
83 | /// </summary>
|
---|
84 | /// <param name="edge"></param>
|
---|
85 | /// <returns></returns>
|
---|
86 | INode IGraph.FromNode(IEdge edge) {
|
---|
87 | return edge.SourceNode;
|
---|
88 | }
|
---|
89 |
|
---|
90 | INode IGraph.ToNode(IEdge edge) {
|
---|
91 | return edge.TargetNode;
|
---|
92 | }
|
---|
93 |
|
---|
94 | /// <summary>
|
---|
95 | /// Given an Edge and an incident Node, return the other Node
|
---|
96 | /// connected to the edge.
|
---|
97 | /// </summary>
|
---|
98 | /// <param name="edge"></param>
|
---|
99 | /// <param name="node"></param>
|
---|
100 | /// <returns></returns>
|
---|
101 | INode IGraph.AdjacentNode(IEdge edge, INode node) {
|
---|
102 | if (edge.SourceNode == node)
|
---|
103 | return edge.TargetNode;
|
---|
104 | else if (edge.TargetNode == node)
|
---|
105 | return edge.SourceNode;
|
---|
106 | else
|
---|
107 | throw new InconsistencyException("The node is not a target or source node of the given edge.");
|
---|
108 |
|
---|
109 | }
|
---|
110 |
|
---|
111 | /// <summary>
|
---|
112 | /// Gets the collection of all adjacent nodes connected to the given node by an
|
---|
113 | /// incoming edge (i.e., all nodes that "point" at this one).
|
---|
114 | /// </summary>
|
---|
115 | /// <param name="node"></param>
|
---|
116 | /// <returns></returns>
|
---|
117 | CollectionBase<INode> IGraph.InNeighbors(INode node) {
|
---|
118 | return node.InNeighbors;
|
---|
119 | }
|
---|
120 |
|
---|
121 | /// <summary>
|
---|
122 | /// Gets the collection of adjacent nodes connected to the given node by an
|
---|
123 | /// outgoing edge (i.e., all nodes "pointed" to by this one).
|
---|
124 | /// </summary>
|
---|
125 | /// <param name="node"></param>
|
---|
126 | /// <returns></returns>
|
---|
127 | CollectionBase<INode> IGraph.OutNeighbors(INode node) {
|
---|
128 | return node.OutNeighbors;
|
---|
129 | }
|
---|
130 |
|
---|
131 | /// <summary>
|
---|
132 | /// Get an iterator over all nodes connected to the given node.
|
---|
133 | /// </summary>
|
---|
134 | /// <param name="node"></param>
|
---|
135 | /// <returns></returns>
|
---|
136 | CollectionBase<INode> IGraph.Neighbors(INode node) {
|
---|
137 | return node.Neighbors;
|
---|
138 | }
|
---|
139 |
|
---|
140 | /// <summary>
|
---|
141 | /// Edgeses the specified node.
|
---|
142 | /// </summary>
|
---|
143 | /// <param name="node">The node.</param>
|
---|
144 | /// <returns></returns>
|
---|
145 | CollectionBase<IEdge> IGraph.EdgesOf(INode node) {
|
---|
146 | return node.Edges;
|
---|
147 | }
|
---|
148 |
|
---|
149 | /// <summary>
|
---|
150 | /// Ins the edges.
|
---|
151 | /// </summary>
|
---|
152 | /// <param name="node">The node.</param>
|
---|
153 | /// <returns></returns>
|
---|
154 | CollectionBase<IEdge> IGraph.InEdges(INode node) {
|
---|
155 | return node.InEdges;
|
---|
156 | }
|
---|
157 |
|
---|
158 | /// <summary>
|
---|
159 | /// Outs the edges.
|
---|
160 | /// </summary>
|
---|
161 | /// <param name="node">The node.</param>
|
---|
162 | /// <returns></returns>
|
---|
163 | CollectionBase<IEdge> IGraph.OutEdges(INode node) {
|
---|
164 | return node.OutEdges;
|
---|
165 | }
|
---|
166 |
|
---|
167 |
|
---|
168 | /// <summary>
|
---|
169 | /// Gets the spanning tree.
|
---|
170 | /// </summary>
|
---|
171 | /// <value>The spanning tree.</value>
|
---|
172 | ITree IGraph.SpanningTree {
|
---|
173 | get { return mSpanningTree; }
|
---|
174 | }
|
---|
175 |
|
---|
176 | /// <summary>
|
---|
177 | /// Makes the spanning tree.
|
---|
178 | /// </summary>
|
---|
179 | /// <param name="node">The node.</param>
|
---|
180 | /// <returns></returns>
|
---|
181 | void IGraph.MakeSpanningTree(INode node) {
|
---|
182 | // build unweighted spanning tree by BFS
|
---|
183 | LinkedList<INode> q = new LinkedList<INode>();
|
---|
184 | BitArray visit = new BitArray(this.CurrentPage.Shapes.Count);
|
---|
185 | q.AddFirst(node);
|
---|
186 | visit[this.CurrentPage.Shapes.IndexOf(node as IShape)] = true;
|
---|
187 | INode n;
|
---|
188 | while (q.Count > 0) {
|
---|
189 | INode p = q.First.Value;
|
---|
190 | q.RemoveFirst();
|
---|
191 | if (p.Children == null)
|
---|
192 | p.Children = new CollectionBase<INode>();
|
---|
193 | if (visit[this.CurrentPage.Shapes.IndexOf(p as IShape)])
|
---|
194 | p.Children.Clear();
|
---|
195 | foreach (IEdge edge in p.Edges) {
|
---|
196 | n = edge.AdjacentNode(p);
|
---|
197 | if (n == null) continue;
|
---|
198 | try {
|
---|
199 | if (!visit[this.CurrentPage.Shapes.IndexOf(n as IShape)]) {
|
---|
200 | q.AddLast(n);
|
---|
201 | visit[this.CurrentPage.Shapes.IndexOf(n as IShape)] = true;
|
---|
202 | n.ParentNode = p;
|
---|
203 | n.ParentEdge = edge;
|
---|
204 | p.Children.Add(n);
|
---|
205 | }
|
---|
206 | }
|
---|
207 | catch (ArgumentOutOfRangeException) { continue; }
|
---|
208 | }
|
---|
209 |
|
---|
210 | }
|
---|
211 | mSpanningTree = this as ITree;
|
---|
212 |
|
---|
213 | }
|
---|
214 |
|
---|
215 |
|
---|
216 | void ITree.ForEach<T>(Action<T> action, INode startNode) {
|
---|
217 | (action as Action<INode>).Invoke(startNode);
|
---|
218 | if (startNode.Children == null)
|
---|
219 | return;
|
---|
220 |
|
---|
221 | foreach (INode node in startNode.Children) {
|
---|
222 | //(action as Action<INode>).Invoke(node);
|
---|
223 | (this as ITree).ForEach<INode>((action as Action<INode>), node);
|
---|
224 | }
|
---|
225 |
|
---|
226 | }
|
---|
227 |
|
---|
228 |
|
---|
229 |
|
---|
230 |
|
---|
231 | /// <summary>
|
---|
232 | /// Clears the spanning tree.
|
---|
233 | /// </summary>
|
---|
234 | void IGraph.ClearSpanningTree() {
|
---|
235 | mSpanningTree = null;
|
---|
236 | }
|
---|
237 | IEdge ITree.ParentEdge(INode node) {
|
---|
238 | if (mSpanningTree == null)
|
---|
239 | return null;
|
---|
240 | return mSpanningTree.ParentEdge(node);
|
---|
241 | }
|
---|
242 |
|
---|
243 | /// <summary>
|
---|
244 | /// Indicates if the edges of this graph are directed or undirected.
|
---|
245 | /// </summary>
|
---|
246 | /// <value></value>
|
---|
247 | bool ITree.IsDirected {
|
---|
248 | get { return mIsDirected; }
|
---|
249 | set { mIsDirected = value; }
|
---|
250 | }
|
---|
251 |
|
---|
252 | INode ITree.Root {
|
---|
253 | get {
|
---|
254 | return mLayoutRoot as INode;
|
---|
255 | }
|
---|
256 | set {
|
---|
257 | mLayoutRoot = value as IShape;
|
---|
258 | }
|
---|
259 | }
|
---|
260 |
|
---|
261 | CollectionBase<INode> ITree.Children(INode node) {
|
---|
262 | if (mSpanningTree == null)
|
---|
263 | return null;
|
---|
264 | return mSpanningTree.Children(node);
|
---|
265 | }
|
---|
266 |
|
---|
267 | CollectionBase<IEdge> ITree.ChildEdges(INode node) {
|
---|
268 | if (mSpanningTree == null)
|
---|
269 | return null;
|
---|
270 | return mSpanningTree.ChildEdges(node);
|
---|
271 | }
|
---|
272 |
|
---|
273 | INode ITree.NextSibling(INode node) {
|
---|
274 | if (mSpanningTree == null)
|
---|
275 | return null;
|
---|
276 | return mSpanningTree.NextSibling(node);
|
---|
277 | }
|
---|
278 |
|
---|
279 | INode ITree.PreviousSibling(INode node) {
|
---|
280 | if (mSpanningTree == null)
|
---|
281 | return null;
|
---|
282 | return mSpanningTree.PreviousSibling(node);
|
---|
283 | }
|
---|
284 |
|
---|
285 | INode ITree.LastChild(INode node) {
|
---|
286 | if (mSpanningTree == null)
|
---|
287 | return null;
|
---|
288 | return mSpanningTree.LastChild(node);
|
---|
289 | }
|
---|
290 |
|
---|
291 | INode ITree.FirstChild(INode node) {
|
---|
292 | if (mSpanningTree == null)
|
---|
293 | return null;
|
---|
294 | return mSpanningTree.FirstChild(node);
|
---|
295 | }
|
---|
296 |
|
---|
297 | int ITree.ChildCount(INode node) {
|
---|
298 | if (mSpanningTree == null)
|
---|
299 | return 0;
|
---|
300 | return mSpanningTree.ChildCount(node);
|
---|
301 | }
|
---|
302 |
|
---|
303 | int ITree.Depth(INode node) {
|
---|
304 | if (mSpanningTree == null)
|
---|
305 | return 0;
|
---|
306 | return mSpanningTree.Depth(node);
|
---|
307 | }
|
---|
308 |
|
---|
309 |
|
---|
310 | }
|
---|
311 | }
|
---|