1
|
/*
|
2
|
Copyright (c) 2003-2006 Niels Kokholm and Peter Sestoft
|
3
|
Permission is hereby granted, free of charge, to any person obtaining a copy
|
4
|
of this software and associated documentation files (the "Software"), to deal
|
5
|
in the Software without restriction, including without limitation the rights
|
6
|
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
|
7
|
copies of the Software, and to permit persons to whom the Software is
|
8
|
furnished to do so, subject to the following conditions:
|
9
|
|
10
|
The above copyright notice and this permission notice shall be included in
|
11
|
all copies or substantial portions of the Software.
|
12
|
|
13
|
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
|
14
|
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
|
15
|
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
|
16
|
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
|
17
|
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
|
18
|
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
|
19
|
SOFTWARE.
|
20
|
*/
|
21
|
|
22
|
// C5 example: Graph representation with basic algorithms using C5
|
23
|
|
24
|
|
25
|
// Compile with
|
26
|
// csc /r:C5.dll Graph.cs
|
27
|
|
28
|
|
29
|
// The code is structured as a rudimentary Graph library, with an interface
|
30
|
// for (edge)weighted graphs and a single implementation based on an
|
31
|
// adjacency list representation using hash dictionaries.
|
32
|
|
33
|
|
34
|
// The algorithms implemented include:
|
35
|
//
|
36
|
// Breadth-First-Search and Depth-First-Search, with an interface based on actions
|
37
|
// to be taken as edges are traversed. Applications are checking for connectedness,
|
38
|
// counting components
|
39
|
//
|
40
|
// Priority-First-Search, where edges are traversed according to either weight or
|
41
|
// accumulated weight from the start of the search.
|
42
|
// An application of the non-accumulating version is the construction of a minimal
|
43
|
// spanning tree and therefore the following approximation algorithm.
|
44
|
// Applications of the accumulating version are the construction of a shortest path
|
45
|
// and the computation of the distance from one vertex to another one.
|
46
|
//
|
47
|
// An approximation algorithm for Travelling Salesman Problems,
|
48
|
// where the weights satisfies the triangle inequality.
|
49
|
|
50
|
|
51
|
// Pervasive generic parameters:
|
52
|
// V: The type of a vertex in a graph. Vertices are identified
|
53
|
// by the Equals method inherited from object (or overridden).
|
54
|
// E: The type of additional data associated with edges in a graph.
|
55
|
// W: The type of values of weights on edges in a weighted graph,
|
56
|
// in practise usually int or double. Must be comparable and
|
57
|
// there must be given a compatible way to add values.
|
58
|
|
59
|
// Interfaces:
|
60
|
// IGraph<V,E,W>: The interface for a graph implementation with
|
61
|
// vertex type V, edge dat type E and weight values of type W.
|
62
|
// IWeight<E,W>: The interface of a weight function
|
63
|
|
64
|
// Classes:
|
65
|
// HashGraph<V,E,W>: An implementation of IWeightedGraph<V,E,W> based on
|
66
|
// adjacency lists represented as hash dictionaries.
|
67
|
// HashGraph<V,E,W>.EdgesValue: A helper class for the Edges() method
|
68
|
// CountWeight<E>: A
|
69
|
// IntWeight:
|
70
|
// DoubleWeight:
|
71
|
|
72
|
// Value Types:
|
73
|
// Edge<V,E>:
|
74
|
// EdgeAction<V,E,U>:
|
75
|
|
76
|
// Some notes:
|
77
|
// The code only supports "natural" equality of vertices.
|
78
|
|
79
|
using C5;
|
80
|
using System;
|
81
|
using SCG = System.Collections.Generic;
|
82
|
|
83
|
namespace Graph
|
84
|
{
|
85
|
/// <summary>
|
86
|
/// (Duer ikke)
|
87
|
/// </summary>
|
88
|
/// <typeparam name="V"></typeparam>
|
89
|
/// <typeparam name="E"></typeparam>
|
90
|
interface IGraphVertex<V, E,W> where W : IComparable<W>
|
91
|
{
|
92
|
V Value { get;}
|
93
|
IGraph<V, E, W> Graph { get;}
|
94
|
ICollectionValue<KeyValuePair<V, E>> Adjacent { get;}
|
95
|
|
96
|
}
|
97
|
|
98
|
class Vertex<V>
|
99
|
{
|
100
|
//V v;
|
101
|
}
|
102
|
/// <summary>
|
103
|
///
|
104
|
/// </summary>
|
105
|
/// <typeparam name="V"></typeparam>
|
106
|
/// <typeparam name="E"></typeparam>
|
107
|
/// <typeparam name="W"></typeparam>
|
108
|
interface IGraph<V, E, W> where W : IComparable<W>
|
109
|
{
|
110
|
/// <summary>
|
111
|
///
|
112
|
/// </summary>
|
113
|
/// <value>The weight object for this graph</value>
|
114
|
IWeight<E, W> Weight { get;}
|
115
|
|
116
|
/// <summary>
|
117
|
///
|
118
|
/// </summary>
|
119
|
/// <value>The number of vertices in this graph</value>
|
120
|
int VertexCount { get;}
|
121
|
|
122
|
/// <summary>
|
123
|
///
|
124
|
/// </summary>
|
125
|
/// <value>The number of edges in this graph</value>
|
126
|
int EdgeCount { get;}
|
127
|
|
128
|
/// <summary>
|
129
|
/// The collection of vertices of this graph.
|
130
|
/// The return value is a snapshot, not a live view onto the graph.
|
131
|
/// </summary>
|
132
|
/// <returns></returns>
|
133
|
ICollectionValue<V> Vertices();
|
134
|
|
135
|
/// <summary>
|
136
|
/// The collection of edges incident to a particular vertex.
|
137
|
/// The return value is a snapshot og (endvertex, edgedata) pairs.
|
138
|
/// </summary>
|
139
|
/// <param name="vertex"></param>
|
140
|
/// <returns></returns>
|
141
|
ICollectionValue<KeyValuePair<V, E>> Adjacent(V vertex);
|
142
|
|
143
|
/// <summary>
|
144
|
/// The collection of all edges in the graph. The return value is a snapshot
|
145
|
/// of Edge values. Each edge is present once for an undefined direction.
|
146
|
/// </summary>
|
147
|
/// <returns></returns>
|
148
|
ICollectionValue<Edge<V, E>> Edges();
|
149
|
|
150
|
/// <summary>
|
151
|
/// Add a(n isolated) vertex to the graph Ignore if vertex is already in the graph.
|
152
|
/// </summary>
|
153
|
/// <param name="vertex"></param>
|
154
|
/// <returns>True if the vertex was added.</returns>
|
155
|
bool AddVertex(V vertex);
|
156
|
|
157
|
/// <summary>
|
158
|
/// Add an edge to the graph. If the edge is already in the graph, update the
|
159
|
/// edge data. Add vertices as needed.
|
160
|
/// </summary>
|
161
|
/// <param name="start"></param>
|
162
|
/// <param name="end"></param>
|
163
|
/// <param name="edgedata"></param>
|
164
|
/// <returns>True if the edge was added</returns>
|
165
|
bool AddEdge(V start, V end, E edgedata);
|
166
|
|
167
|
/// <summary>
|
168
|
/// Remove a vertex and all its incident edges from the graph.
|
169
|
/// </summary>
|
170
|
/// <returns>True if the vertex was already in the graph and hence was removed</returns>
|
171
|
bool RemoveVertex(V vertex);
|
172
|
|
173
|
/// <summary>
|
174
|
/// Remove an edge from the graph. Do not remove the vertices if they become isolated.
|
175
|
/// </summary>
|
176
|
/// <param name="start"></param>
|
177
|
/// <param name="end"></param>
|
178
|
/// <param name="edgedata">On output, the edge data associated with the removed edge.</param>
|
179
|
/// <returns>True if </returns>
|
180
|
bool RemoveEdge(V start, V end, out E edgedata);
|
181
|
|
182
|
/// <summary>
|
183
|
/// Is there an edge from start to end in this graph, and if so, what is
|
184
|
/// the data on that edge.
|
185
|
/// </summary>
|
186
|
/// <param name="start"></param>
|
187
|
/// <param name="end"></param>
|
188
|
/// <param name="edge"></param>
|
189
|
/// <returns></returns>
|
190
|
bool FindEdge(V start, V end, out E edge);
|
191
|
|
192
|
/// <summary>
|
193
|
/// Construct the subgraph corresponding to a set of vertices.
|
194
|
/// </summary>
|
195
|
/// <param name="vs"></param>
|
196
|
/// <returns></returns>
|
197
|
IGraph<V, E, W> SubGraph(ICollectionValue<V> vs);
|
198
|
|
199
|
/// <summary>
|
200
|
///
|
201
|
/// </summary>
|
202
|
/// <value>True if graph is connected</value>
|
203
|
bool IsConnected { get; }
|
204
|
|
205
|
/// <summary>
|
206
|
///
|
207
|
/// </summary>
|
208
|
/// <value>The number of connected components of this graph</value>
|
209
|
int ComponentCount { get;}
|
210
|
|
211
|
/// <summary>
|
212
|
/// Compute the connnected components of this graph.
|
213
|
/// </summary>
|
214
|
/// <returns>A collection of (vertex,component) pairs, where the first part of the
|
215
|
/// pair is some vertex in the component.</returns>
|
216
|
ICollectionValue<KeyValuePair<V, IGraph<V, E, W>>> Components();
|
217
|
|
218
|
/// <summary>
|
219
|
/// Traverse the connected component containing the <code>start</code> vertex,
|
220
|
/// in either BFS or DFS order, beginning at <code>start</code> and performing the action
|
221
|
/// <code>act</code> on each edge part of the constructed tree.
|
222
|
/// </summary>
|
223
|
/// <param name="bfs">True if BFS, false if DFS</param>
|
224
|
/// <param name="start">The vertex to start at</param>
|
225
|
/// <param name="act">The action to perform at each node</param>
|
226
|
void TraverseVertices(bool bfs, V start, Action<Edge<V, E>> act);
|
227
|
|
228
|
/// <summary>
|
229
|
/// Traverse an undirected graph in either BFS or DFS order, performing the action
|
230
|
/// <code>act</code> on each vertex.
|
231
|
/// The start vertex of each component of the graph is undefinded.
|
232
|
/// </summary>
|
233
|
/// <param name="bfs">True if BFS, false if DFS</param>
|
234
|
/// <param name="act"></param>
|
235
|
void TraverseVertices(bool bfs, Action<V> act);
|
236
|
|
237
|
/// <summary>
|
238
|
/// Traverse an undirected graph in either BFS or DFS order, performing the action
|
239
|
/// <code>act</code> on each edge in the traversal and beforecomponent/aftercomponent
|
240
|
/// at the start and end of each component (with argument: the start vertex of the component).
|
241
|
/// </summary>
|
242
|
/// <param name="bfs">True if BFS, false if DFS</param>
|
243
|
/// <param name="act"></param>
|
244
|
/// <param name="beforecomponent"></param>
|
245
|
/// <param name="aftercomponent"></param>
|
246
|
void TraverseVertices(bool bfs, Action<Edge<V, E>> act, Action<V> beforecomponent, Action<V> aftercomponent);
|
247
|
|
248
|
/// <summary>
|
249
|
/// A more advanced Depth First Search traversal.
|
250
|
/// </summary>
|
251
|
/// <param name="start">The vertex to start the search at</param>
|
252
|
/// <param name="beforevertex">Action to perform when a vertex is first encountered.</param>
|
253
|
/// <param name="aftervertex">Action to perform when all edges out of a vertex has been handles.</param>
|
254
|
/// <param name="onfollow">Action to perform as an edge is traversed.</param>
|
255
|
/// <param name="onfollowed">Action to perform when an edge is travesed back.</param>
|
256
|
/// <param name="onnotfollowed">Action to perform when an edge (a backedge)is seen, but not followed.</param>
|
257
|
void DepthFirstSearch(V start, Action<V> beforevertex, Action<V> aftervertex,
|
258
|
Action<Edge<V, E>> onfollow, Action<Edge<V, E>> onfollowed, Action<Edge<V, E>> onnotfollowed);
|
259
|
|
260
|
//TODO: perhaps we should avoid exporting this?
|
261
|
/// <summary>
|
262
|
/// Traverse the part of the graph reachable from start in order of least distance
|
263
|
/// from start according to the weight function. Perform act on the edges of the
|
264
|
/// traversal as they are recognised.
|
265
|
/// </summary>
|
266
|
/// <typeparam name="W"></typeparam>
|
267
|
/// <param name="weight"></param>
|
268
|
/// <param name="start"></param>
|
269
|
/// <param name="act"></param>
|
270
|
void PriorityFirstTraverse(bool accumulating, V start, EdgeAction<V, E, W> act);
|
271
|
|
272
|
/// <summary>
|
273
|
/// Compute the (a) shortest path from start to end. THrow an exception if end cannot be reached rom start.
|
274
|
/// </summary>
|
275
|
/// <param name="weight"></param>
|
276
|
/// <param name="start"></param>
|
277
|
/// <param name="end"></param>
|
278
|
/// <returns></returns>
|
279
|
ICollectionValue<Edge<V, E>> ShortestPath(V start, V end);
|
280
|
|
281
|
/// <summary>
|
282
|
/// Compute the Distance from start to end, i.e. the total weight of a shortest path from start to end.
|
283
|
/// Throw an exception if end cannot be reached rom start.
|
284
|
/// </summary>
|
285
|
/// <param name="start"></param>
|
286
|
/// <param name="end"></param>
|
287
|
/// <returns></returns>
|
288
|
W Distance(V start, V end);
|
289
|
|
290
|
/// <summary>
|
291
|
/// Compute a minimum spanning tree for the graph.
|
292
|
/// Throw an exception if this graph is not connected.
|
293
|
/// </summary>
|
294
|
/// <param name="root">(The starting point of the PFS, to be removed)</param>
|
295
|
/// <returns></returns>
|
296
|
IGraph<V, E, W> MinimumSpanningTree(out V root);
|
297
|
|
298
|
/// <summary>
|
299
|
/// Compute a factor 2 approximation to a Minimum Weight
|
300
|
/// Perfect Matching in a graph using NNs
|
301
|
/// </summary>
|
302
|
/// <returns></returns>
|
303
|
ICollectionValue<Edge<V, E>> ApproximateMWPM();
|
304
|
|
305
|
/// <summary>
|
306
|
/// Construct a closed Euler tour of this graph if one exists, i.e. if
|
307
|
/// the graph is connected and all vertices have even degrees. Throw an
|
308
|
/// ArgumentException if no closed Euler tour exists.
|
309
|
/// </summary>
|
310
|
/// <returns>A list of vertices in an Euler tour of this graph.</returns>
|
311
|
IList<V> EulerTour();
|
312
|
|
313
|
/// <summary>
|
314
|
/// This is intended for implementations of the very simple factor 2 approximation
|
315
|
/// algorithms for the travelling salesman problem for Euclidic weight/distance
|
316
|
/// functions, i.e. distances that satisfy the triangle inequality. (We do not do 3/2)
|
317
|
/// </summary>
|
318
|
/// <returns></returns>
|
319
|
IDirectedCollectionValue<V> ApproximateTSP();
|
320
|
|
321
|
/// <summary>
|
322
|
/// Pretty-print the graph to the console (for debugging purposes).
|
323
|
/// </summary>
|
324
|
void Print(System.IO.TextWriter output);
|
325
|
}
|
326
|
|
327
|
/// <summary>
|
328
|
/// The type of an edge in a graph. An edge is identified by its pair of
|
329
|
/// vertices. The pair is considered ordered, and so an Edge really describes
|
330
|
/// an edge of the graph in a particular traversal direction.
|
331
|
/// </summary>
|
332
|
/// <typeparam name="V">The type of a vertex.</typeparam>
|
333
|
/// <typeparam name="E">The type of data asociated with edges.</typeparam>
|
334
|
struct Edge<V, E>
|
335
|
{
|
336
|
static SCG.IEqualityComparer<V> vequalityComparer = EqualityComparer<V>.Default;
|
337
|
public readonly V start, end;
|
338
|
public readonly E edgedata;
|
339
|
public Edge(V start, V end, E edgedata)
|
340
|
{
|
341
|
if (vequalityComparer.Equals(start, end))
|
342
|
throw new ArgumentException("Illegal: start and end are equal");
|
343
|
this.start = start; this.end = end; this.edgedata = edgedata;
|
344
|
}
|
345
|
|
346
|
public Edge<V, E> Reverse()
|
347
|
{
|
348
|
return new Edge<V, E>(end, start, edgedata);
|
349
|
}
|
350
|
|
351
|
public override string ToString()
|
352
|
{
|
353
|
return String.Format("(start='{0}', end='{1}', edgedata='{2}')", start, end, edgedata); ;
|
354
|
}
|
355
|
|
356
|
public override bool Equals(object obj)
|
357
|
{
|
358
|
if (obj is Edge<V, E>)
|
359
|
{
|
360
|
Edge<V, E> other = (Edge<V, E>)obj;
|
361
|
return vequalityComparer.Equals(start, other.start) && vequalityComparer.Equals(end, other.end);
|
362
|
}
|
363
|
return false;
|
364
|
}
|
365
|
|
366
|
/// <summary>
|
367
|
///
|
368
|
/// </summary>
|
369
|
/// <returns></returns>
|
370
|
public override int GetHashCode()
|
371
|
{
|
372
|
//TODO: should we use xor? Or a random factor?
|
373
|
return start.GetHashCode() + 148712671 * end.GetHashCode();
|
374
|
}
|
375
|
|
376
|
/// <summary>
|
377
|
/// The unordered equalityComparer compares edges independent of the order of the vertices.
|
378
|
/// </summary>
|
379
|
public class UnorderedEqualityComparer : SCG.IEqualityComparer<Edge<V, E>>
|
380
|
{
|
381
|
/// <summary>
|
382
|
/// Check if two edges have the same vertices irrespective of order.
|
383
|
/// </summary>
|
384
|
/// <param name="i1"></param>
|
385
|
/// <param name="i2"></param>
|
386
|
/// <returns></returns>
|
387
|
public bool Equals(Edge<V, E> i1, Edge<V, E> i2)
|
388
|
{
|
389
|
return (vequalityComparer.Equals(i1.start, i2.start) && vequalityComparer.Equals(i1.end, i2.end)) ||
|
390
|
(vequalityComparer.Equals(i1.end, i2.start) && vequalityComparer.Equals(i1.start, i2.end));
|
391
|
}
|
392
|
|
393
|
/// <summary>
|
394
|
/// Return a hash code compatible with the unordered equals.
|
395
|
/// </summary>
|
396
|
/// <param name="item"></param>
|
397
|
/// <returns></returns>
|
398
|
public int GetHashCode(Edge<V, E> item)
|
399
|
{
|
400
|
return item.start.GetHashCode() ^ item.end.GetHashCode();
|
401
|
}
|
402
|
}
|
403
|
}
|
404
|
|
405
|
/// <summary>
|
406
|
/// The type of the weight object of a graph. This consists of a function mapping
|
407
|
/// edge data values to weight values, and an operation to add two weight values.
|
408
|
/// It is required that weight values are comparable.
|
409
|
///
|
410
|
/// The user must assure that the add operation is commutative and fulfills
|
411
|
/// Add(w1,w2) ≤ w1 for all w1 and w2 that can appear as weights or sums of
|
412
|
/// weights. In practise, W will be int or double, all weight values will be
|
413
|
/// non-negative and the addition will be the natural addition on W.
|
414
|
/// </summary>
|
415
|
/// <typeparam name="E"></typeparam>
|
416
|
/// <typeparam name="W"></typeparam>
|
417
|
interface IWeight<E, W> where W : IComparable<W>
|
418
|
{
|
419
|
/// <summary>
|
420
|
/// Compute the weight value corresponding to specific edge data.
|
421
|
/// </summary>
|
422
|
/// <param name="edgedata"></param>
|
423
|
/// <returns></returns>
|
424
|
W Weight(E edgedata);
|
425
|
|
426
|
/// <summary>
|
427
|
/// Add two weight values.
|
428
|
/// </summary>
|
429
|
/// <param name="w1"></param>
|
430
|
/// <param name="w2"></param>
|
431
|
/// <returns></returns>
|
432
|
W Add(W w1, W w2);
|
433
|
}
|
434
|
|
435
|
/// <summary>
|
436
|
/// An action to perform when an edge is encountered during a traversal of the graph.
|
437
|
/// The "extra" parameter is for additional information supplied by the traversal
|
438
|
/// algorithm.
|
439
|
/// The intention of the bool return value is that returning false is a signal to the
|
440
|
/// traversal algorithm to abandon the traversl because the user has already found
|
441
|
/// what he was looking for.
|
442
|
/// </summary>
|
443
|
/// <typeparam name="V"></typeparam>
|
444
|
/// <typeparam name="E"></typeparam>
|
445
|
/// <typeparam name="U"></typeparam>
|
446
|
/// <param name="edge"></param>
|
447
|
/// <param name="extra"></param>
|
448
|
/// <returns></returns>
|
449
|
delegate bool EdgeAction<V, E, U>(Edge<V, E> edge, U extra);
|
450
|
|
451
|
|
452
|
/*
|
453
|
For a dense graph, we would use data fields:
|
454
|
|
455
|
E'[,] or E'[][] for the matrix. Possibly E'[][] for a triangular one!
|
456
|
Here E' = struct{E edgedata, bool present} or class{E edgedata}, or if E is a class just E.
|
457
|
Thus E' is E! for value types. Or we could have two matrices: E[][] and bool[][].
|
458
|
|
459
|
HashDictionary<V,int> to map vertex ids to indices.
|
460
|
ArrayList<V> for the map the other way.
|
461
|
Or simply a HashedArrayList<V> to get both?
|
462
|
|
463
|
PresentList<int>, FreeList<int> or similar, if we do not want to compact the indices in the matrix on each delete.
|
464
|
If we compact, we always do a delete on the vertex<->index map by a replace and a removelast:
|
465
|
vimap[ind]=vimap[vimap.Count]; vimap.RemoveLast(); //also reorder matrix!
|
466
|
|
467
|
|
468
|
*/
|
469
|
|
470
|
/// <summary>
|
471
|
/// An implementation of IGraph≤V,E,W≥ based on an adjacency list representation using hash dictionaries.
|
472
|
/// As a consequence, this will be most efficient for sparse graphs.
|
473
|
/// </summary>
|
474
|
/// <typeparam name="V"></typeparam>
|
475
|
/// <typeparam name="E"></typeparam>
|
476
|
/// <typeparam name="W"></typeparam>
|
477
|
class HashGraph<V, E, W> : IGraph<V, E, W> where W : IComparable<W>
|
478
|
{
|
479
|
int edgecount;
|
480
|
|
481
|
HashDictionary<V, HashDictionary<V, E>> graph;
|
482
|
|
483
|
IWeight<E, W> weight;
|
484
|
|
485
|
public IWeight<E, W> Weight { get { return weight; } }
|
486
|
|
487
|
|
488
|
/// <summary>
|
489
|
/// Create an initially empty graph.
|
490
|
/// </summary>
|
491
|
/// <param name="weight"></param>
|
492
|
[UsedBy("testTSP")]
|
493
|
public HashGraph(IWeight<E, W> weight)
|
494
|
{
|
495
|
this.weight = weight;
|
496
|
edgecount = 0;
|
497
|
graph = new HashDictionary<V, HashDictionary<V, E>>();
|
498
|
}
|
499
|
|
500
|
/// <summary>
|
501
|
/// Constructing a graph with no isolated vertices given a collection of edges.
|
502
|
/// </summary>
|
503
|
/// <param name="edges"></param>
|
504
|
[UsedBy()]
|
505
|
public HashGraph(IWeight<E, W> weight, SCG.IEnumerable<Edge<V, E>> edges) : this(weight)
|
506
|
{
|
507
|
foreach (Edge<V, E> edge in edges)
|
508
|
{
|
509
|
if (edge.start.Equals(edge.end))
|
510
|
throw new ApplicationException("Edge has equal start and end");
|
511
|
{
|
512
|
HashDictionary<V, E> edgeset;
|
513
|
//TODO: utilize upcoming FindOrAddSome operation
|
514
|
if (!graph.Find(edge.start, out edgeset))
|
515
|
graph.Add(edge.start, edgeset = new HashDictionary<V, E>());
|
516
|
if (!edgeset.UpdateOrAdd(edge.end, edge.edgedata))
|
517
|
edgecount++;
|
518
|
if (!graph.Find(edge.end, out edgeset))
|
519
|
graph.Add(edge.end, edgeset = new HashDictionary<V, E>());
|
520
|
edgeset.UpdateOrAdd(edge.start, edge.edgedata);
|
521
|
}
|
522
|
}
|
523
|
}
|
524
|
|
525
|
/// <summary>
|
526
|
/// This constructs a graph with a given set of vertices.
|
527
|
/// Will only allow these vertices.
|
528
|
/// Duplicate edges are allowed.
|
529
|
/// </summary>
|
530
|
/// <param name="vertices"></param>
|
531
|
/// <param name="edges"></param>
|
532
|
public HashGraph(IWeight<E, W> weight, SCG.IEnumerable<V> vertices, SCG.IEnumerable<Edge<V, E>> edges) : this(weight)
|
533
|
{
|
534
|
foreach (V v in vertices)
|
535
|
graph.Add(v, new HashDictionary<V, E>());
|
536
|
foreach (Edge<V, E> edge in edges)
|
537
|
{
|
538
|
HashDictionary<V, E> edgeset;
|
539
|
if (edge.start.Equals(edge.end))
|
540
|
throw new ApplicationException("Edge has equal start and end");
|
541
|
if (!graph.Find(edge.start, out edgeset))
|
542
|
throw new ApplicationException("Edge has unknown start");
|
543
|
if (!edgeset.UpdateOrAdd(edge.end, edge.edgedata))
|
544
|
edgecount++;
|
545
|
if (!graph.Find(edge.end, out edgeset))
|
546
|
throw new ApplicationException("Edge has unknown end");
|
547
|
edgeset.UpdateOrAdd(edge.start, edge.edgedata);
|
548
|
}
|
549
|
}
|
550
|
|
551
|
[UsedBy("testCOMP")]
|
552
|
public int VertexCount { get { return graph.Count; } }
|
553
|
|
554
|
[UsedBy("testCOMP")]
|
555
|
public int EdgeCount { get { return edgecount; } }
|
556
|
|
557
|
public ICollectionValue<V> Vertices()
|
558
|
{
|
559
|
return new GuardedCollectionValue<V>(graph.Keys);
|
560
|
}
|
561
|
|
562
|
public ICollectionValue<KeyValuePair<V, E>> Adjacent(V vertex)
|
563
|
{
|
564
|
return new GuardedCollectionValue<KeyValuePair<V, E>>(graph[vertex]);
|
565
|
}
|
566
|
|
567
|
class EdgesValue : CollectionValueBase<Edge<V, E>>
|
568
|
{
|
569
|
HashGraph<V, E, W> graph;
|
570
|
internal EdgesValue(HashGraph<V, E, W> g) { graph = g; }
|
571
|
|
572
|
public override bool IsEmpty { get { return graph.edgecount == 0; } }
|
573
|
|
574
|
public override int Count { get { return graph.edgecount; } }
|
575
|
|
576
|
public override Speed CountSpeed { get { return Speed.Constant; } }
|
577
|
|
578
|
|
579
|
public override Edge<V, E> Choose()
|
580
|
{
|
581
|
KeyValuePair<V, HashDictionary<V, E>> adjacent = graph.graph.Choose();
|
582
|
KeyValuePair<V, E> otherend = graph.graph[adjacent.Key].Choose();
|
583
|
return new Edge<V, E>(adjacent.Key, otherend.Key, otherend.Value);
|
584
|
}
|
585
|
|
586
|
public override SCG.IEnumerator<Edge<V, E>> GetEnumerator()
|
587
|
{
|
588
|
HashSet<Edge<V, E>> seen = new HashSet<Edge<V, E>>(new Edge<V, E>.UnorderedEqualityComparer());
|
589
|
foreach (V v in graph.graph.Keys)
|
590
|
foreach (KeyValuePair<V, E> p in graph.graph[v])
|
591
|
{
|
592
|
Edge<V, E> edge = new Edge<V, E>(v, p.Key, p.Value);
|
593
|
if (!seen.FindOrAdd(ref edge))
|
594
|
yield return edge;
|
595
|
}
|
596
|
}
|
597
|
}
|
598
|
|
599
|
public ICollectionValue<Edge<V, E>> Edges()
|
600
|
{
|
601
|
return new EdgesValue(this);
|
602
|
}
|
603
|
|
604
|
public bool AddVertex(V v)
|
605
|
{
|
606
|
if (graph.Contains(v))
|
607
|
return false;
|
608
|
graph.Add(v, new HashDictionary<V, E>());
|
609
|
return true;
|
610
|
}
|
611
|
|
612
|
//Note: no warning on update of edgedata!
|
613
|
//TODO: Shouldn?t Update or Add return the old value?
|
614
|
//Then it would be easy to check for updates
|
615
|
public bool AddEdge(V start, V end, E edgedata)
|
616
|
{
|
617
|
bool retval = false;
|
618
|
HashDictionary<V, E> edgeset;
|
619
|
if (graph.Find(start, out edgeset))
|
620
|
retval = !edgeset.UpdateOrAdd(end, edgedata);
|
621
|
else
|
622
|
{
|
623
|
graph[start] = edgeset = new HashDictionary<V, E>();
|
624
|
edgeset[end] = edgedata;
|
625
|
retval = true;
|
626
|
}
|
627
|
if (graph.Find(end, out edgeset))
|
628
|
edgeset.UpdateOrAdd(start, edgedata);
|
629
|
else
|
630
|
{
|
631
|
graph[end] = edgeset = new HashDictionary<V, E>();
|
632
|
edgeset[start] = edgedata;
|
633
|
}
|
634
|
if (retval)
|
635
|
edgecount++;
|
636
|
return retval;
|
637
|
}
|
638
|
|
639
|
public bool RemoveVertex(V vertex)
|
640
|
{
|
641
|
HashDictionary<V, E> edgeset;
|
642
|
if (!graph.Find(vertex, out edgeset))
|
643
|
return false;
|
644
|
foreach (V othervertex in edgeset.Keys)
|
645
|
graph[othervertex].Remove(vertex); //Assert retval==true
|
646
|
edgecount -= edgeset.Count;
|
647
|
graph.Remove(vertex);
|
648
|
return true;
|
649
|
}
|
650
|
|
651
|
public bool RemoveEdge(V start, V end, out E edgedata)
|
652
|
{
|
653
|
HashDictionary<V, E> edgeset;
|
654
|
if (!graph.Find(start, out edgeset))
|
655
|
{
|
656
|
edgedata = default(E);
|
657
|
return false;
|
658
|
}
|
659
|
if (!edgeset.Remove(end, out edgedata))
|
660
|
return false;
|
661
|
graph[end].Remove(start);
|
662
|
edgecount--;
|
663
|
return true;
|
664
|
}
|
665
|
|
666
|
public bool FindEdge(V start, V end, out E edgedata)
|
667
|
{
|
668
|
HashDictionary<V, E> edges;
|
669
|
if (!graph.Find(start, out edges))
|
670
|
{
|
671
|
edgedata = default(E);
|
672
|
return false;
|
673
|
}
|
674
|
return edges.Find(end, out edgedata);
|
675
|
}
|
676
|
|
677
|
public IGraph<V, E, W> SubGraph(ICollectionValue<V> vs)
|
678
|
{
|
679
|
HashSet<V> vertexset = vs as HashSet<V>;
|
680
|
if (vertexset == null)
|
681
|
{
|
682
|
vertexset = new HashSet<V>();
|
683
|
vertexset.AddAll(vs);
|
684
|
}
|
685
|
|
686
|
return new HashGraph<V, E, W>(weight,
|
687
|
vs,
|
688
|
Edges().Filter(delegate(Edge<V, E> e) { return vertexset.Contains(e.start) && vertexset.Contains(e.end); }));
|
689
|
}
|
690
|
|
691
|
public bool IsConnected
|
692
|
{
|
693
|
//TODO: optimize: needs to change Action<Edge<V,E>> to EdgeAction to be able to break out
|
694
|
get { return ComponentCount <= 1; }
|
695
|
}
|
696
|
|
697
|
public int ComponentCount
|
698
|
{
|
699
|
get
|
700
|
{
|
701
|
int components = 0;
|
702
|
TraverseVertices(false, null, delegate(V v) { components++; }, null);
|
703
|
return components;
|
704
|
}
|
705
|
}
|
706
|
|
707
|
public ICollectionValue<KeyValuePair<V, IGraph<V, E, W>>> Components()
|
708
|
{
|
709
|
ArrayList<KeyValuePair<V, IGraph<V, E, W>>> retval = new ArrayList<KeyValuePair<V, IGraph<V, E, W>>>();
|
710
|
HashGraph<V, E, W> component;
|
711
|
ArrayList<V> vertices = null;
|
712
|
Action<Edge<V, E>> edgeaction = delegate(Edge<V, E> e)
|
713
|
{
|
714
|
vertices.Add(e.end);
|
715
|
};
|
716
|
Action<V> beforecomponent = delegate(V v)
|
717
|
{
|
718
|
vertices = new ArrayList<V>();
|
719
|
vertices.Add(v);
|
720
|
};
|
721
|
Action<V> aftercomponent = delegate(V v)
|
722
|
{
|
723
|
//component = SubGraph(vertices);
|
724
|
component = new HashGraph<V, E, W>(weight);
|
725
|
foreach (V start in vertices)
|
726
|
{
|
727
|
//component.graph[start] = graph[start].Clone();
|
728
|
HashDictionary<V, E> edgeset = component.graph[start] = new HashDictionary<V, E>();
|
729
|
foreach (KeyValuePair<V, E> adjacent in graph[start])
|
730
|
edgeset[adjacent.Key] = adjacent.Value;
|
731
|
}
|
732
|
retval.Add(new KeyValuePair<V, IGraph<V, E, W>>(v, component));
|
733
|
};
|
734
|
TraverseVertices(false, edgeaction, beforecomponent, aftercomponent);
|
735
|
return retval;
|
736
|
}
|
737
|
|
738
|
[UsedBy("test1")]
|
739
|
public void TraverseVertices(bool bfs, V start, Action<Edge<V, E>> act)
|
740
|
{
|
741
|
if (!graph.Contains(start))
|
742
|
throw new ArgumentException("start Vertex not in graph");
|
743
|
IList<Edge<V, E>> todo = new LinkedList<Edge<V, E>>();
|
744
|
todo.FIFO = bfs;
|
745
|
HashSet<V> seen = new HashSet<V>();
|
746
|
V v;
|
747
|
while (!todo.IsEmpty || seen.Count == 0)
|
748
|
{
|
749
|
if (seen.Count > 1)
|
750
|
{
|
751
|
Edge<V, E> e = todo.Remove();
|
752
|
if (act != null)
|
753
|
act(e);
|
754
|
v = e.end;
|
755
|
}
|
756
|
else
|
757
|
{
|
758
|
seen.Add(start);
|
759
|
v = start;
|
760
|
}
|
761
|
|
762
|
HashDictionary<V, E> adjacent;
|
763
|
if (graph.Find(v, out adjacent))
|
764
|
{
|
765
|
foreach (KeyValuePair<V, E> p in adjacent)
|
766
|
{
|
767
|
V end = p.Key;
|
768
|
if (!seen.FindOrAdd(ref end))
|
769
|
todo.Add(new Edge<V, E>(v, end, p.Value));
|
770
|
}
|
771
|
}
|
772
|
}
|
773
|
}
|
774
|
|
775
|
public void TraverseVertices(bool bfs, Action<V> act)
|
776
|
{
|
777
|
TraverseVertices(bfs, delegate(Edge<V, E> e) { act(e.end); }, act, null);
|
778
|
}
|
779
|
|
780
|
//TODO: merge the hash set here with the intra omponent one?
|
781
|
public void TraverseVertices(bool bfs, Action<Edge<V, E>> act, Action<V> beforecomponent, Action<V> aftercomponent)
|
782
|
{
|
783
|
HashSet<V> missing = new HashSet<V>();
|
784
|
missing.AddAll(Vertices());
|
785
|
Action<Edge<V, E>> myact = act + delegate(Edge<V, E> e) { missing.Remove(e.end); };
|
786
|
Action<V> mybeforecomponent = beforecomponent + delegate(V v) { missing.Remove(v); };
|
787
|
while (!missing.IsEmpty)
|
788
|
{
|
789
|
V start = default(V);
|
790
|
foreach (V v in missing)
|
791
|
{ start = v; break; }
|
792
|
mybeforecomponent(start);
|
793
|
TraverseVertices(bfs, start, myact);
|
794
|
if (aftercomponent != null)
|
795
|
aftercomponent(start);
|
796
|
}
|
797
|
}
|
798
|
|
799
|
delegate void Visitor(V v, V parent, bool atRoot);
|
800
|
|
801
|
//TODO: allow actions to be null
|
802
|
[UsedBy("testDFS")]
|
803
|
public void DepthFirstSearch(V start, Action<V> before, Action<V> after,
|
804
|
Action<Edge<V, E>> onfollow, Action<Edge<V, E>> onfollowed, Action<Edge<V, E>> onnotfollowed)
|
805
|
{
|
806
|
HashSet<V> seen = new HashSet<V>();
|
807
|
seen.Add(start);
|
808
|
//If we do not first set visit = null, the compiler will complain at visit(end)
|
809
|
//that visit is uninitialized
|
810
|
Visitor visit = null;
|
811
|
visit = delegate(V v, V parent, bool atRoot)
|
812
|
{
|
813
|
before(v);
|
814
|
HashDictionary<V, E> adjacent;
|
815
|
if (graph.Find(v, out adjacent))
|
816
|
foreach (KeyValuePair<V, E> p in adjacent)
|
817
|
{
|
818
|
V end = p.Key;
|
819
|
Edge<V, E> e = new Edge<V, E>(v, end, p.Value);
|
820
|
if (!seen.FindOrAdd(ref end))
|
821
|
{
|
822
|
onfollow(e);
|
823
|
visit(end, v, false);
|
824
|
onfollowed(e);
|
825
|
}
|
826
|
else
|
827
|
{
|
828
|
if (!atRoot && !parent.Equals(end))
|
829
|
onnotfollowed(e);
|
830
|
}
|
831
|
}
|
832
|
after(v);
|
833
|
};
|
834
|
visit(start, default(V), true);
|
835
|
}
|
836
|
|
837
|
public void PriorityFirstTraverse(bool accumulated, V start, EdgeAction<V, E, W> act)
|
838
|
{
|
839
|
if (!graph.Contains(start))
|
840
|
throw new ArgumentException("Graph does not contain start");
|
841
|
IPriorityQueue<W> fringe = new IntervalHeap<W>();
|
842
|
HashDictionary<V, IPriorityQueueHandle<W>> seen = new HashDictionary<V, IPriorityQueueHandle<W>>();
|
843
|
HashDictionary<IPriorityQueueHandle<W>, Edge<V, E>> bestedge = new HashDictionary<IPriorityQueueHandle<W>, Edge<V, E>>();
|
844
|
|
845
|
IPriorityQueueHandle<W> h = null;
|
846
|
V current;
|
847
|
W currentdist;
|
848
|
while (!fringe.IsEmpty || seen.Count == 0)
|
849
|
{
|
850
|
if (seen.Count == 0)
|
851
|
{
|
852
|
seen.Add(start, h);
|
853
|
current = start;
|
854
|
currentdist = default(W);
|
855
|
}
|
856
|
else
|
857
|
{
|
858
|
currentdist = fringe.DeleteMin(out h);
|
859
|
Edge<V, E> e = bestedge[h];
|
860
|
if (!act(e, currentdist))
|
861
|
break;
|
862
|
bestedge.Remove(h);
|
863
|
current = e.end;
|
864
|
}
|
865
|
HashDictionary<V, E> adjacentnodes;
|
866
|
if (graph.Find(current, out adjacentnodes))
|
867
|
foreach (KeyValuePair<V, E> adjacent in adjacentnodes)
|
868
|
{
|
869
|
V end = adjacent.Key;
|
870
|
E edgedata = adjacent.Value;
|
871
|
W dist = weight.Weight(edgedata), olddist;
|
872
|
if (accumulated && !current.Equals(start)) dist = weight.Add(currentdist, weight.Weight(edgedata));
|
873
|
if (!seen.Find(end, out h))
|
874
|
{
|
875
|
h = null;
|
876
|
fringe.Add(ref h, dist);
|
877
|
seen[end] = h;
|
878
|
bestedge[h] = new Edge<V, E>(current, end, edgedata);
|
879
|
}
|
880
|
else if (fringe.Find(h, out olddist) && dist.CompareTo(olddist) < 0)
|
881
|
{
|
882
|
fringe[h] = dist;
|
883
|
bestedge[h] = new Edge<V, E>(current, end, edgedata);
|
884
|
}
|
885
|
}
|
886
|
}
|
887
|
}
|
888
|
|
889
|
public W Distance(V start, V end)
|
890
|
{
|
891
|
W dist = default(W);
|
892
|
bool found = false;
|
893
|
PriorityFirstTraverse(true, start, delegate(Edge<V, E> e, W w)
|
894
|
{
|
895
|
if (end.Equals(e.end)) { dist = w; found = true; return false; }
|
896
|
else return true;
|
897
|
});
|
898
|
if (found)
|
899
|
return dist;
|
900
|
throw new ArgumentException(String.Format("No path from {0} to {1}", start, end));
|
901
|
}
|
902
|
|
903
|
|
904
|
public ICollectionValue<Edge<V, E>> ShortestPath(V start, V end)
|
905
|
{
|
906
|
HashDictionary<V, Edge<V, E>> backtrack = new HashDictionary<V, Edge<V, E>>();
|
907
|
PriorityFirstTraverse(true, start, delegate(Edge<V, E> e, W w) { backtrack[e.end] = e; return !end.Equals(e.end); });
|
908
|
ArrayList<Edge<V, E>> path = new ArrayList<Edge<V, E>>();
|
909
|
Edge<V, E> edge;
|
910
|
V v = end;
|
911
|
while (backtrack.Find(v, out edge))
|
912
|
{
|
913
|
path.Add(edge);
|
914
|
v = edge.start;
|
915
|
}
|
916
|
if (path.IsEmpty)
|
917
|
throw new ArgumentException(String.Format("No path from {0} to {1}", start, end));
|
918
|
path.Reverse();
|
919
|
return path;
|
920
|
}
|
921
|
|
922
|
/// <summary>
|
923
|
/// NB: assume connected, throw exception if not
|
924
|
/// </summary>
|
925
|
/// <typeparam name="W"></typeparam>
|
926
|
/// <param name="edgeWeight"></param>
|
927
|
/// <returns></returns>
|
928
|
public IGraph<V, E, W> MinimumSpanningTree(out V start)
|
929
|
{
|
930
|
ArrayList<Edge<V, E>> edges = new ArrayList<Edge<V, E>>();
|
931
|
start = default(V);
|
932
|
foreach (V v in graph.Keys)
|
933
|
{ start = v; break; }
|
934
|
PriorityFirstTraverse(false, start, delegate(Edge<V, E> e, W w) { edges.Add(e); return true; });
|
935
|
if (edges.Count != graph.Count - 1)
|
936
|
throw new ArgumentException("Graph not connected");
|
937
|
return new HashGraph<V, E, W>(weight, edges);
|
938
|
}
|
939
|
|
940
|
public ICollectionValue<Edge<V, E>> ApproximateMWPM()
|
941
|
{
|
942
|
//Assume graph complete and even number of vertices
|
943
|
HashGraph<V, E, W> clone = new HashGraph<V, E, W>(weight, Edges());
|
944
|
ArrayList<Edge<V, E>> evenpath = new ArrayList<Edge<V, E>>();
|
945
|
ArrayList<Edge<V, E>> oddpath = new ArrayList<Edge<V, E>>();
|
946
|
V start = default(V);
|
947
|
foreach (V v in clone.Vertices()) { start = v; break; }
|
948
|
V current = start;
|
949
|
W evenweight, oddweight;
|
950
|
evenweight = oddweight = default(W);
|
951
|
bool even = true;
|
952
|
while (clone.VertexCount > 0)
|
953
|
{
|
954
|
V bestvertex = default(V);
|
955
|
E bestedge = default(E);
|
956
|
W bestweight = default(W);
|
957
|
if (clone.VertexCount == 1)
|
958
|
{
|
959
|
bestvertex = start;
|
960
|
bestedge = graph[current][start];
|
961
|
bestweight = weight.Weight(bestedge);
|
962
|
}
|
963
|
else
|
964
|
{
|
965
|
bool first = true;
|
966
|
foreach (KeyValuePair<V, E> p in clone.graph[current])
|
967
|
{
|
968
|
W thisweight = weight.Weight(p.Value);
|
969
|
if (first || bestweight.CompareTo(thisweight) > 0)
|
970
|
{
|
971
|
bestvertex = p.Key;
|
972
|
bestweight = thisweight;
|
973
|
bestedge = p.Value;
|
974
|
}
|
975
|
first = false;
|
976
|
}
|
977
|
}
|
978
|
clone.RemoveVertex(current);
|
979
|
//Console.WriteLine("-* {0} / {1} / {2}", bestvertex, bestweight, tour.Count);
|
980
|
if (even)
|
981
|
{
|
982
|
evenweight = evenpath.Count < 1 ? bestweight : weight.Add(evenweight, bestweight);
|
983
|
evenpath.Add(new Edge<V, E>(current, bestvertex, bestedge));
|
984
|
}
|
985
|
else
|
986
|
{
|
987
|
oddweight = oddpath.Count < 1 ? bestweight : weight.Add(oddweight, bestweight);
|
988
|
oddpath.Add(new Edge<V, E>(current, bestvertex, bestedge));
|
989
|
}
|
990
|
current = bestvertex;
|
991
|
even = !even;
|
992
|
}
|
993
|
//Console.WriteLine("Totalweights: even: {0} and odd: {1}", evenweight, oddweight);
|
994
|
return evenweight.CompareTo(oddweight) < 0 ? evenpath : oddpath;
|
995
|
}
|
996
|
|
997
|
/// <summary>
|
998
|
/// The construction is performed as follows:
|
999
|
/// Start at some vertex. Greedily construct a path starting there by
|
1000
|
/// following edges at random until no more unused edges are available
|
1001
|
/// from the current node, which must be the start node. Then follow
|
1002
|
/// the path constructed so far and whenever we meet a vertex with
|
1003
|
/// unused edges, construct a path from there greedily as above,
|
1004
|
/// inserting into the path in front of us.
|
1005
|
///
|
1006
|
/// The algorithm will use constant time for each vertex added
|
1007
|
/// to the path and
|
1008
|
///
|
1009
|
/// Illustrates use of views as a safe version of listnode pointers
|
1010
|
/// and hashed linked lists for choosing some item in constant time combined
|
1011
|
/// with (expected) constant time remove.
|
1012
|
/// </summary>
|
1013
|
/// <returns></returns>
|
1014
|
public IList<V> EulerTour()
|
1015
|
{
|
1016
|
bool debug = false;
|
1017
|
//Assert connected and all degrees even. (Connected is checked at the end)
|
1018
|
string fmt = "Graph does not have a closed Euler tour: vertex {0} has odd degree {1}";
|
1019
|
foreach (KeyValuePair<V, HashDictionary<V, E>> adj in graph)
|
1020
|
if (adj.Value.Count % 2 != 0)
|
1021
|
throw new ArgumentException(String.Format(fmt, adj.Key, adj.Value.Count));
|
1022
|
|
1023
|
LinkedList<V> path = new LinkedList<V>();
|
1024
|
//Clone the graph data to keep track of used edges.
|
1025
|
HashDictionary<V, HashedArrayList<V>> edges = new HashDictionary<V, HashedArrayList<V>>();
|
1026
|
V start = default(V);
|
1027
|
HashedArrayList<V> adjacent = null;
|
1028
|
foreach (KeyValuePair<V, HashDictionary<V, E>> p in graph)
|
1029
|
{
|
1030
|
adjacent = new HashedArrayList<V>();
|
1031
|
adjacent.AddAll(p.Value.Keys);
|
1032
|
start = p.Key;
|
1033
|
edges.Add(start, adjacent);
|
1034
|
}
|
1035
|
|
1036
|
path.Add(start);
|
1037
|
IList<V> view = path.View(0, 1);
|
1038
|
while (adjacent.Count > 0)
|
1039
|
{
|
1040
|
V current = view[0];
|
1041
|
if (debug) Console.WriteLine("==> {0}", current);
|
1042
|
//Augment the path (randomly) until we return here and all edges
|
1043
|
while (adjacent.Count > 0)
|
1044
|
{
|
1045
|
if (debug) Console.WriteLine(" => {0}, {1}", current, path.Count);
|
1046
|
V next = adjacent.RemoveFirst();
|
1047
|
view.Add(next);
|
1048
|
if (debug) Console.WriteLine("EDGE: " + current + "->" + next);
|
1049
|
if (!edges[next].Remove(current))
|
1050
|
Console.WriteLine("Bad");
|
1051
|
current = next;
|
1052
|
adjacent = edges[current];
|
1053
|
}
|
1054
|
//When we get here, the view contains a closed path, i.e.
|
1055
|
//view[view.Count-1] == view[0] and we have followed all edges from view[0]
|
1056
|
//We slide forward along the rest of the path constructed so far and stop at the
|
1057
|
//first vertex with still unfollwed edges.
|
1058
|
while (view.Offset < path.Count - 1 && adjacent.Count == 0)
|
1059
|
{
|
1060
|
view.Slide(1, 1);
|
1061
|
if (debug) Console.WriteLine(" -> {0}, {1}", view[0], path.Count);
|
1062
|
adjacent = edges[view[0]];
|
1063
|
}
|
1064
|
}
|
1065
|
if (path.Count <= edges.Count)
|
1066
|
throw new ArgumentException("Graph was not connected");
|
1067
|
return path;
|
1068
|
}
|
1069
|
|
1070
|
/// <summary>
|
1071
|
/// The purpose of this struct is to be able to create and add new,
|
1072
|
/// synthetic vertices to a graph.
|
1073
|
/// </summary>
|
1074
|
struct Vplus : IEquatable<Vplus>
|
1075
|
{
|
1076
|
internal readonly V vertex; internal readonly int id;
|
1077
|
static SCG.IEqualityComparer<V> vequalityComparer = EqualityComparer<V>.Default;
|
1078
|
internal Vplus(V v) { vertex = v; id = 0; }
|
1079
|
internal Vplus(int i) { vertex = default(V); id = i; }
|
1080
|
//We should override Equals and GetHashCode
|
1081
|
|
1082
|
public override string ToString()
|
1083
|
{ return id == 0 ? String.Format("real({0})", vertex) : String.Format("fake({0})", id); }
|
1084
|
|
1085
|
public override bool Equals(object obj) { throw new NotImplementedException(); }
|
1086
|
|
1087
|
public bool Equals(Vplus other) { return vequalityComparer.Equals(vertex, other.vertex) && id == other.id; }
|
1088
|
|
1089
|
public override int GetHashCode() { return vequalityComparer.GetHashCode(vertex) + id; }
|
1090
|
}
|
1091
|
|
1092
|
/// <summary>
|
1093
|
///
|
1094
|
/// </summary>
|
1095
|
/// <returns></returns>
|
1096
|
public IDirectedCollectionValue<V> ApproximateTSP2()
|
1097
|
{
|
1098
|
/* Construct a minimum spanning tree for the graph */
|
1099
|
V root;
|
1100
|
IGraph<V, E, W> tree = MinimumSpanningTree(out root);
|
1101
|
|
1102
|
//Console.WriteLine("========= Matching of odd vertices of mst =========");
|
1103
|
ArrayList<V> oddvertices = new ArrayList<V>();
|
1104
|
foreach (V v in tree.Vertices())
|
1105
|
if (tree.Adjacent(v).Count % 2 != 0)
|
1106
|
oddvertices.Add(v);
|
1107
|
|
1108
|
ICollectionValue<Edge<V, E>> matching = SubGraph(oddvertices).ApproximateMWPM();
|
1109
|
|
1110
|
//Console.WriteLine("========= Fuse matching and tree =========");
|
1111
|
//We must split the edges of the matching with fake temporary vertices
|
1112
|
//since the matching and the tree may have common edges
|
1113
|
|
1114
|
HashGraph<Vplus, E, W> fused = new HashGraph<Vplus, E, W>(weight);
|
1115
|
foreach (Edge<V, E> e in tree.Edges())
|
1116
|
fused.AddEdge(new Vplus(e.start), new Vplus(e.end), e.edgedata);
|
1117
|
int fakeid = 1;
|
1118
|
foreach (Edge<V, E> e in matching)
|
1119
|
{
|
1120
|
Vplus fakevertex = new Vplus(fakeid++);
|
1121
|
fused.AddEdge(new Vplus(e.start), fakevertex, e.edgedata);
|
1122
|
fused.AddEdge(fakevertex, new Vplus(e.end), e.edgedata);
|
1123
|
}
|
1124
|
fused.Print(Console.Out);
|
1125
|
|
1126
|
//Console.WriteLine("========= Remove fake vertices and perform shortcuts =========");
|
1127
|
IList<Vplus> fusedtour = fused.EulerTour();
|
1128
|
HashSet<V> seen = new HashSet<V>();
|
1129
|
IList<V> tour = new ArrayList<V>();
|
1130
|
|
1131
|
foreach (Vplus vplus in fused.EulerTour())
|
1132
|
{
|
1133
|
V v = vplus.vertex;
|
1134
|
if (vplus.id == 0 && !seen.FindOrAdd(ref v))
|
1135
|
tour.Add(v);
|
1136
|
}
|
1137
|
return tour;
|
1138
|
}
|
1139
|
|
1140
|
/// <summary>
|
1141
|
/// (Refer to the litterature, Vazirani)
|
1142
|
///
|
1143
|
/// (Describe: MST+Euler+shortcuts)
|
1144
|
/// </summary>
|
1145
|
/// <returns></returns>
|
1146
|
[UsedBy("testTSP")]
|
1147
|
public IDirectedCollectionValue<V> ApproximateTSP()
|
1148
|
{
|
1149
|
/* Construct a minimum spanning tree for the graph */
|
1150
|
V root;
|
1151
|
IGraph<V, E, W> tree = MinimumSpanningTree(out root);
|
1152
|
|
1153
|
/* (Virtually) double all edges of MST and construct an Euler tour of the vertices*/
|
1154
|
LinkedList<V> tour = new LinkedList<V>();
|
1155
|
tour.Add(root);
|
1156
|
tour.Add(root);
|
1157
|
IList<V> view = tour.View(1, 1);
|
1158
|
|
1159
|
Action<Edge<V, E>> onfollow = delegate(Edge<V, E> e)
|
1160
|
{
|
1161
|
//slide the view until it points to the last copy of e.start
|
1162
|
while (!view[0].Equals(e.start))
|
1163
|
view.Slide(1);
|
1164
|
//then insert two copies of e.end and slide the view one backwards
|
1165
|
view.InsertFirst(e.end);
|
1166
|
view.InsertFirst(e.end);
|
1167
|
view.Slide(1, 1);
|
1168
|
};
|
1169
|
|
1170
|
tree.TraverseVertices(false, root, onfollow);
|
1171
|
|
1172
|
/* Finally, slide along the Euler tour and shortcut by removing vertices already seen*/
|
1173
|
HashSet<V> seen = new HashSet<V>();
|
1174
|
view = tour.View(0, tour.Count);
|
1175
|
while (view.Offset < tour.Count - 1)
|
1176
|
{
|
1177
|
V v = view[0];
|
1178
|
if (seen.FindOrAdd(ref v))
|
1179
|
view.RemoveFirst();
|
1180
|
else
|
1181
|
view.Slide(1, view.Count - 1);
|
1182
|
}
|
1183
|
return tour;
|
1184
|
}
|
1185
|
|
1186
|
public void Print(System.IO.TextWriter output)
|
1187
|
{
|
1188
|
output.WriteLine("Graph has {0} vertices, {1} edges, {2} components", graph.Count, edgecount, ComponentCount);
|
1189
|
foreach (KeyValuePair<V, HashDictionary<V, E>> p in graph)
|
1190
|
{
|
1191
|
output.Write(" {0} -> ", p.Key);
|
1192
|
foreach (KeyValuePair<V, E> p2 in p.Value)
|
1193
|
output.Write("{1} (data {2}), ", p.Key, p2.Key, p2.Value);
|
1194
|
output.WriteLine();
|
1195
|
}
|
1196
|
}
|
1197
|
}
|
1198
|
|
1199
|
/// <summary>
|
1200
|
/// A weight on a graph that assigns the weight 1 to every edge.
|
1201
|
/// </summary>
|
1202
|
/// <typeparam name="E">(Ignored) type of edgedata</typeparam>
|
1203
|
class CountWeight<E> : IWeight<E, int>
|
1204
|
{
|
1205
|
public int Weight(E edgedata) { return 1; }
|
1206
|
|
1207
|
public int Add(int w1, int w2) { return w1 + w2; }
|
1208
|
}
|
1209
|
|
1210
|
/// <summary>
|
1211
|
/// A weight on an IGraph<V,int> that uses the value of the edgedata as the weight value.
|
1212
|
/// </summary>
|
1213
|
class IntWeight : IWeight<int, int>
|
1214
|
{
|
1215
|
|
1216
|
public int Weight(int edgedata) { return edgedata; }
|
1217
|
|
1218
|
public int Add(int w1, int w2) { return w1 + w2; }
|
1219
|
|
1220
|
}
|
1221
|
|
1222
|
/// <summary>
|
1223
|
/// A weight on an IGraph<V,double> that uses the value of the edgedata as the weight value.
|
1224
|
/// </summary>
|
1225
|
class DoubleWeight : IWeight<double, double>
|
1226
|
{
|
1227
|
|
1228
|
public double Weight(double edgedata) { return edgedata; }
|
1229
|
|
1230
|
public double Add(double w1, double w2) { return w1 + w2; }
|
1231
|
|
1232
|
}
|
1233
|
|
1234
|
/// <summary>
|
1235
|
/// Attribute used for marking which examples use a particuler graph method
|
1236
|
/// </summary>
|
1237
|
class UsedByAttribute : Attribute
|
1238
|
{
|
1239
|
string[] tests;
|
1240
|
internal UsedByAttribute(params string[] tests) { this.tests = tests; }
|
1241
|
|
1242
|
public override string ToString()
|
1243
|
{
|
1244
|
System.Text.StringBuilder sb = new System.Text.StringBuilder();
|
1245
|
for (int i = 0; i < tests.Length; i++)
|
1246
|
{
|
1247
|
if (i > 0)
|
1248
|
sb.Append(", ");
|
1249
|
sb.Append(tests[i]);
|
1250
|
}
|
1251
|
return sb.ToString();
|
1252
|
}
|
1253
|
}
|
1254
|
|
1255
|
/// <summary>
|
1256
|
/// Attribute for marking example methods with a description
|
1257
|
/// </summary>
|
1258
|
class ExampleDescriptionAttribute : Attribute
|
1259
|
{
|
1260
|
string text;
|
1261
|
internal ExampleDescriptionAttribute(string text) { this.text = text; }
|
1262
|
|
1263
|
public override string ToString() { return text; }
|
1264
|
}
|
1265
|
|
1266
|
/// <summary>
|
1267
|
/// A selection of test cases
|
1268
|
/// </summary>
|
1269
|
class Test
|
1270
|
{
|
1271
|
static SCG.IEnumerable<Edge<int, int>> Grid(int n)
|
1272
|
{
|
1273
|
Random ran = new Random(1717);
|
1274
|
for (int i = 1; i <= n; i++)
|
1275
|
{
|
1276
|
for (int j = 1; j <= n; j++)
|
1277
|
{
|
1278
|
yield return new Edge<int, int>(1000 * i + j, 1000 * (i + 1) + j, ran.Next(1, 100));
|
1279
|
yield return new Edge<int, int>(1000 * i + j, 1000 * i + j + 1, ran.Next(1, 100));
|
1280
|
}
|
1281
|
}
|
1282
|
}
|
1283
|
|
1284
|
static SCG.IEnumerable<Edge<string, int>> Snake(int n)
|
1285
|
{
|
1286
|
for (int i = 1; i <= n; i++)
|
1287
|
{
|
1288
|
yield return new Edge<string, int>("U" + i, "L" + i, 1);
|
1289
|
yield return new Edge<string, int>("U" + i, "U" + (i + 1), i % 2 == 0 ? 1 : 10);
|
1290
|
yield return new Edge<string, int>("L" + i, "L" + (i + 1), i % 2 == 0 ? 10 : 1);
|
1291
|
}
|
1292
|
}
|
1293
|
|
1294
|
/// <summary>
|
1295
|
/// Create the edges of a forest of complete binary trees.
|
1296
|
/// </summary>
|
1297
|
/// <param name="treeCount">Number of trees</param>
|
1298
|
/// <param name="height">Height of trees</param>
|
1299
|
/// <returns></returns>
|
1300
|
static SCG.IEnumerable<Edge<string, int>> Forest(int treeCount, int height)
|
1301
|
{
|
1302
|
for (int i = 0; i < treeCount; i++)
|
1303
|
{
|
1304
|
IList<string> q = new ArrayList<string>();
|
1305
|
string root = String.Format("[{0}]", i);
|
1306
|
int lmax = height + root.Length;
|
1307
|
q.Add(root);
|
1308
|
while (!q.IsEmpty)
|
1309
|
{
|
1310
|
string s = q.Remove();
|
1311
|
string s2 = s + "L";
|
1312
|
if (s2.Length < lmax)
|
1313
|
q.Add(s2);
|
1314
|
yield return new Edge<string, int>(s, s2, 0);
|
1315
|
s2 = s + "R";
|
1316
|
if (s2.Length < lmax)
|
1317
|
q.Add(s2);
|
1318
|
yield return new Edge<string, int>(s, s2, 0);
|
1319
|
}
|
1320
|
}
|
1321
|
}
|
1322
|
|
1323
|
/// <summary>
|
1324
|
/// Create edges of a graph correspondingto a "wheel" shape: the ecnter and equidistant
|
1325
|
/// points around the perimeter. The edgedata and edge weights are the euclidean distances.
|
1326
|
/// </summary>
|
1327
|
/// <param name="complete">True means the graph will be complete, false that the graph
|
1328
|
/// will have edges for the spokes and between neighboring perimeter vetices.</param>
|
1329
|
/// <param name="n">The number of perimeter vertices, must be at least 3.</param>
|
1330
|
/// <returns>An enumerable with the edges</returns>
|
1331
|
static SCG.IEnumerable<Edge<string, double>> Wheel(bool complete, int n)
|
1332
|
{
|
1333
|
if (n < 3)
|
1334
|
throw new ArgumentOutOfRangeException("n must be at least 3");
|
1335
|
string center = "C";
|
1336
|
string[] perimeter = new string[n];
|
1337
|
for (int i = 0; i < n; i++)
|
1338
|
{
|
1339
|
perimeter[i] = "P" + i;
|
1340
|
yield return new Edge<string, double>(perimeter[i], center, 1);
|
1341
|
}
|
1342
|
if (complete)
|
1343
|
for (int i = 0; i < n - 1; i++)
|
1344
|
for (int j = i + 1; j < n; j++)
|
1345
|
yield return new Edge<string, double>(perimeter[i], perimeter[j], 2 * Math.Sin((j - i) * Math.PI / n));
|
1346
|
else
|
1347
|
{
|
1348
|
for (int i = 0; i < n - 1; i++)
|
1349
|
yield return new Edge<string, double>(perimeter[i], perimeter[i + 1], 2 * Math.Sin(Math.PI / n));
|
1350
|
yield return new Edge<string, double>(perimeter[n - 1], perimeter[0], 2 * Math.Sin(Math.PI / n));
|
1351
|
}
|
1352
|
}
|
1353
|
|
1354
|
|
1355
|
/// <summary>
|
1356
|
/// []
|
1357
|
/// </summary>
|
1358
|
[ExampleDescription("Basic BFS and DFS using TraverseVertices method")]
|
1359
|
static void test1()
|
1360
|
{
|
1361
|
IGraph<int, int, int> g = new HashGraph<int, int, int>(new CountWeight<int>(), Grid(3));
|
1362
|
Console.WriteLine("Edge count: {0}", g.Edges().Count);
|
1363
|
Console.WriteLine("BFS:");
|
1364
|
g.TraverseVertices(true, 1001, delegate(Edge<int, int> e) { Console.WriteLine(e); });
|
1365
|
Console.WriteLine("DFS:");
|
1366
|
g.TraverseVertices(false, 1001, delegate(Edge<int, int> e) { Console.WriteLine(e); });
|
1367
|
}
|
1368
|
|
1369
|
/// <summary>
|
1370
|
///
|
1371
|
/// </summary>
|
1372
|
[ExampleDescription("Component methods")]
|
1373
|
static void testCOMP()
|
1374
|
{
|
1375
|
IGraph<string, int, int> g = new HashGraph<string, int, int>(new CountWeight<int>(), Forest(2, 2));
|
1376
|
Console.WriteLine("Forest has: Vertices: {0}, Edges: {1}, Components: {2}", g.VertexCount, g.EdgeCount, g.ComponentCount);
|
1377
|
//g.Print(Console.Out);
|
1378
|
foreach (KeyValuePair<string, IGraph<string, int, int>> comp in g.Components())
|
1379
|
{
|
1380
|
Console.WriteLine("Component of {0}:", comp.Key);
|
1381
|
comp.Value.Print(Console.Out);
|
1382
|
}
|
1383
|
}
|
1384
|
|
1385
|
//TODO: remove?
|
1386
|
static void test3()
|
1387
|
{
|
1388
|
HashGraph<int, int, int> g = new HashGraph<int, int, int>(new CountWeight<int>(), Grid(5));
|
1389
|
g.Print(Console.Out);
|
1390
|
//EdgeWeight<int, IntWeight> weight = delegate(int i) { return i; };
|
1391
|
Console.WriteLine("========= PFS accum =========");
|
1392
|
g.PriorityFirstTraverse(
|
1393
|
true,
|
1394
|
2002,
|
1395
|
delegate(Edge<int, int> e, int d) { Console.WriteLine("Edge: {0}, at distance {1}", e, d); return true; });
|
1396
|
Console.WriteLine("========= PFS not accum =========");
|
1397
|
g.PriorityFirstTraverse(
|
1398
|
false,
|
1399
|
2002,
|
1400
|
delegate(Edge<int, int> e, int d) { Console.WriteLine("Edge: {0}, at distance {1}", e, d); return true; });
|
1401
|
Console.WriteLine("========= MST =========");
|
1402
|
int root;
|
1403
|
g.MinimumSpanningTree(out root).Print(Console.Out);
|
1404
|
Console.WriteLine("========= SP =========");
|
1405
|
foreach (Edge<int, int> edge in g.ShortestPath(1001, 5005))
|
1406
|
Console.WriteLine(edge);
|
1407
|
}
|
1408
|
|
1409
|
static void test4()
|
1410
|
{
|
1411
|
IGraph<string, int, int> g = new HashGraph<string, int, int>(new IntWeight(), Snake(5));
|
1412
|
Console.WriteLine("Edge count: {0}", g.Edges().Count);
|
1413
|
Console.WriteLine("========= PFS =========");
|
1414
|
g.PriorityFirstTraverse(false,
|
1415
|
"U3",
|
1416
|
delegate(Edge<string, int> e, int d) { Console.WriteLine("Edge: {0}, at distance {1}", e, d); return true; });
|
1417
|
Console.WriteLine("========= MST =========");
|
1418
|
string root;
|
1419
|
IGraph<string, int, int> mst = g.MinimumSpanningTree(out root);
|
1420
|
mst.Print(Console.Out);
|
1421
|
Console.WriteLine("DFS:");
|
1422
|
mst.TraverseVertices(false, root, delegate(Edge<string, int> e) { Console.WriteLine(e); });
|
1423
|
Console.WriteLine("ATSP:");
|
1424
|
int first = 0;
|
1425
|
foreach (string s in g.ApproximateTSP())
|
1426
|
{
|
1427
|
Console.Write((first++ == 0 ? "" : " -> ") + s);
|
1428
|
}
|
1429
|
}
|
1430
|
|
1431
|
/// <summary>
|
1432
|
/// This example examines the two variants of a priority-first search:
|
1433
|
/// with accumulated weights, leading to shortest paths from start;
|
1434
|
/// with non-acumulated weights, leading to a minimum spanning tree.
|
1435
|
/// </summary>
|
1436
|
[ExampleDescription("Priority-first-search with and without accumulated weights")]
|
1437
|
static void testPFS()
|
1438
|
{
|
1439
|
IGraph<string, double, double> g = new HashGraph<string, double, double>(new DoubleWeight(), Wheel(false, 10));
|
1440
|
g.Print(Console.Out);
|
1441
|
Console.WriteLine("========= PFS non-accumulated weights (-> MST) =========");
|
1442
|
g.PriorityFirstTraverse(false,
|
1443
|
"P0",
|
1444
|
delegate(Edge<string, double> e, double d) { Console.WriteLine("Edge: {0}, at distance {1}", e, d); return true; });
|
1445
|
Console.WriteLine("========= PFS accumulated weights (-> Shortst paths from start) =========");
|
1446
|
g.PriorityFirstTraverse(true,
|
1447
|
"P0",
|
1448
|
delegate(Edge<string, double> e, double d) { Console.WriteLine("Edge: {0}, at distance {1}", e, d); return true; });
|
1449
|
}
|
1450
|
|
1451
|
/// <summary>
|
1452
|
///
|
1453
|
///
|
1454
|
/// (Refer to Vazirani, or do that where ApproximateTSP is implemented)
|
1455
|
///
|
1456
|
/// Note that the tour created is not optimal. [Describe why]
|
1457
|
/// </summary>
|
1458
|
[ExampleDescription("Approximate TSP")]
|
1459
|
static void testTSP()
|
1460
|
{
|
1461
|
IGraph<string, double, double> g = new HashGraph<string, double, double>(new DoubleWeight(), Wheel(true, 10));
|
1462
|
//g.Print(Console.Out);
|
1463
|
Console.WriteLine("========= MST =========");
|
1464
|
string root;
|
1465
|
IGraph<string, double, double> mst = g.MinimumSpanningTree(out root);
|
1466
|
mst.TraverseVertices(false,
|
1467
|
root,
|
1468
|
delegate(Edge<string, double> e) { Console.WriteLine("Edge: {0} -> {1}", e.start, e.end); });
|
1469
|
Console.WriteLine("========= Approximate TSP =========");
|
1470
|
int first = 0;
|
1471
|
foreach (string s in g.ApproximateTSP())
|
1472
|
{
|
1473
|
Console.Write((first++ == 0 ? "" : " -> ") + s);
|
1474
|
}
|
1475
|
}
|
1476
|
|
1477
|
/// <summary>
|
1478
|
///
|
1479
|
///
|
1480
|
/// (Refer to Vazirani, or do that where ApproximateTSP is implemented)
|
1481
|
///
|
1482
|
/// Note that the tour created is not optimal. [Describe why]
|
1483
|
/// </summary>
|
1484
|
[ExampleDescription("Approximate TSP2")]
|
1485
|
static void testTSP2()
|
1486
|
{
|
1487
|
HashGraph<string, double, double> g = new HashGraph<string, double, double>(new DoubleWeight(), Wheel(true, 20));
|
1488
|
|
1489
|
foreach (string s in g.ApproximateTSP2())
|
1490
|
Console.WriteLine("# " + s);
|
1491
|
//g.Print(Console.Out);
|
1492
|
/*
|
1493
|
Console.WriteLine("========= MST =========");
|
1494
|
string root;
|
1495
|
IGraph<string, double, double> mst = g.MinimumSpanningTree(out root);
|
1496
|
mst.TraverseVertices(false,
|
1497
|
root,
|
1498
|
delegate(Edge<string, double> e) { Console.WriteLine("Edge: {0} -> {1}", e.start, e.end); });
|
1499
|
ArrayList<string> oddvertices = new ArrayList<string>();
|
1500
|
foreach (string v in mst.Vertices())
|
1501
|
if (mst.Adjacent(v).Count % 2 != 0)
|
1502
|
oddvertices.Add(v);
|
1503
|
|
1504
|
Console.WriteLine("========= Matching of odd vertices of mst =========");
|
1505
|
ICollectionValue<Edge<string, double>> matching = g.SubGraph(oddvertices).ApproximateMWPM();
|
1506
|
|
1507
|
Console.WriteLine("========= Add matching to mst =========");
|
1508
|
//We must split the edges of the matchin with fake temporary vertices
|
1509
|
//(For a general vertex type, we would have to augment it to Pair<V,int>
|
1510
|
int fake = 0;
|
1511
|
foreach (Edge<string, double> e in matching)
|
1512
|
{
|
1513
|
string fakevertex = "_" + (fake++);
|
1514
|
mst.AddEdge(e.start, fakevertex, 0);
|
1515
|
mst.AddEdge(fakevertex, e.end, e.edgedata);
|
1516
|
}
|
1517
|
//mst.Print(Console.Out);
|
1518
|
|
1519
|
IList<string> tour = mst.EulerTour(), view = tour.View(1, tour.Count - 1);
|
1520
|
|
1521
|
//Remove fake vertices
|
1522
|
while (view.Count > 0)
|
1523
|
if (view[0].StartsWith("_"))
|
1524
|
view.RemoveFirst();
|
1525
|
else
|
1526
|
view.Slide(1, view.Count - 1);
|
1527
|
|
1528
|
Console.WriteLine("========= Approximate TSP 2 =========");
|
1529
|
//Short cut
|
1530
|
view = tour.View(1, tour.Count - 1);
|
1531
|
HashSet<string> seen = new HashSet<string>();
|
1532
|
|
1533
|
while (view.Count > 0)
|
1534
|
{
|
1535
|
string s = view[0];
|
1536
|
if (seen.FindOrAdd(ref s))
|
1537
|
view.RemoveFirst();
|
1538
|
else
|
1539
|
view.Slide(1, view.Count - 1);
|
1540
|
}
|
1541
|
|
1542
|
foreach (string s in tour)
|
1543
|
Console.WriteLine(". " + s);*/
|
1544
|
}
|
1545
|
|
1546
|
/// <summary>
|
1547
|
///
|
1548
|
/// </summary>
|
1549
|
static void testEuler()
|
1550
|
{
|
1551
|
HashGraph<string, double, double> g = new HashGraph<string, double, double>(new DoubleWeight(), Wheel(true, 6));
|
1552
|
foreach (string s in g.EulerTour())
|
1553
|
Console.Write(s + " ");
|
1554
|
Console.WriteLine();
|
1555
|
}
|
1556
|
|
1557
|
/// <summary>
|
1558
|
/// An articulation point in a graph is a vertex, whose removal will
|
1559
|
/// disconnect the graph (or its component). This example uses the
|
1560
|
/// extended DepthFirstSearch method to compute articulation points
|
1561
|
/// of a graph.
|
1562
|
///
|
1563
|
/// (Refer to Sedgewick. )
|
1564
|
///
|
1565
|
/// Each vertex is given an index in traversal order.
|
1566
|
/// For each vertex, we compute the least index reachable by going downwards
|
1567
|
/// in the DFS tree and then following a single non-dfs edge.
|
1568
|
///
|
1569
|
/// Since we cannot store the DFS indices in the vertices without changing the
|
1570
|
/// (assumed given) vertex type, V, we remember the indices in a V->int
|
1571
|
/// hash dictionary, index. The "least reachable" values are then stored in an
|
1572
|
/// array keyed by the index.
|
1573
|
///
|
1574
|
/// The root of the search is an articulation point if it has more than one
|
1575
|
/// outgoing DFS edges. Other articulation points are non-root vertices, va,
|
1576
|
/// with an outgoing DFS edge, where the the least reachable index of the other
|
1577
|
/// vertex is greater or equal to the index of va.
|
1578
|
/// </summary>
|
1579
|
[ExampleDescription("Using the advanced DFS to compute articulation points")]
|
1580
|
static void testDFS()
|
1581
|
{
|
1582
|
HashGraph<string, int, int> g = new HashGraph<string, int, int>(new IntWeight());
|
1583
|
g.AddEdge("A", "B", 0);
|
1584
|
g.AddEdge("A", "E", 0);
|
1585
|
g.AddEdge("B", "E", 0);
|
1586
|
g.AddEdge("B", "C", 0);
|
1587
|
g.AddEdge("B", "H", 0);
|
1588
|
g.AddEdge("H", "I", 0);
|
1589
|
g.AddEdge("B", "D", 0);
|
1590
|
g.AddEdge("C", "D", 0);
|
1591
|
g.AddEdge("C", "F", 0);
|
1592
|
g.AddEdge("C", "G", 0);
|
1593
|
g.AddEdge("F", "G", 0);
|
1594
|
|
1595
|
HashDictionary<string, int> index = new HashDictionary<string, int>();
|
1596
|
int[] leastIndexReachableFrom = new int[g.VertexCount];
|
1597
|
int nextindex = 0;
|
1598
|
int outgoingFromRoot = 0;
|
1599
|
Action<string> beforevertex = delegate(string v)
|
1600
|
{
|
1601
|
int i = (index[v] = nextindex++);
|
1602
|
leastIndexReachableFrom[i] = i;
|
1603
|
};
|
1604
|
Action<string> aftervertex = delegate(string v)
|
1605
|
{
|
1606
|
int i = index[v];
|
1607
|
if (i == 0 && outgoingFromRoot > 1)
|
1608
|
Console.WriteLine("Articulation point: {0} ({1}>1 outgoing DFS edges from start)",
|
1609
|
v, outgoingFromRoot);
|
1610
|
};
|
1611
|
Action<Edge<string, int>> onfollow = delegate(Edge<string, int> e)
|
1612
|
{
|
1613
|
};
|
1614
|
Action<Edge<string, int>> onfollowed = delegate(Edge<string, int> e)
|
1615
|
{
|
1616
|
int startind = index[e.start], endind = index[e.end];
|
1617
|
if (startind == 0)
|
1618
|
outgoingFromRoot++;
|
1619
|
else
|
1620
|
{
|
1621
|
int leastIndexReachable = leastIndexReachableFrom[endind];
|
1622
|
if (leastIndexReachable >= startind)
|
1623
|
Console.WriteLine("Articulation point: {0} (least index reachable via {3} is {1} >= this index {2})",
|
1624
|
e.start, leastIndexReachable, startind, e);
|
1625
|
if (leastIndexReachableFrom[startind] > leastIndexReachable)
|
1626
|
leastIndexReachableFrom[startind] = leastIndexReachable;
|
1627
|
}
|
1628
|
};
|
1629
|
Action<Edge<string, int>> onnotfollowed = delegate(Edge<string, int> e)
|
1630
|
{
|
1631
|
int startind = index[e.start], endind = index[e.end];
|
1632
|
if (leastIndexReachableFrom[startind] > endind)
|
1633
|
leastIndexReachableFrom[startind] = endind;
|
1634
|
};
|
1635
|
|
1636
|
string root = "C";
|
1637
|
g.DepthFirstSearch(root, beforevertex, aftervertex, onfollow, onfollowed, onnotfollowed);
|
1638
|
Console.WriteLine("Edges:");
|
1639
|
foreach (Edge<string, int> e in g.Edges())
|
1640
|
Console.WriteLine("/ {0}", e);
|
1641
|
}
|
1642
|
|
1643
|
static void Main(String[] args)
|
1644
|
{
|
1645
|
if (args.Length != 1)
|
1646
|
{
|
1647
|
Console.WriteLine("Usage: Graph.exe testno");
|
1648
|
System.Reflection.MethodInfo[] mis = typeof(Test).GetMethods(
|
1649
|
System.Reflection.BindingFlags.Static | System.Reflection.BindingFlags.NonPublic);
|
1650
|
foreach (System.Reflection.MethodInfo mi in mis)
|
1651
|
{
|
1652
|
if (mi.GetParameters().Length == 0 && mi.ReturnType == typeof(void) && mi.Name.StartsWith("test"))
|
1653
|
{
|
1654
|
object[] attrs = mi.GetCustomAttributes(typeof(ExampleDescriptionAttribute), false);
|
1655
|
Console.WriteLine(" {0} : {1}", mi.Name.Substring(4), attrs.Length > 0 ? attrs[0] : "");
|
1656
|
}
|
1657
|
}
|
1658
|
}
|
1659
|
else
|
1660
|
{
|
1661
|
string testMethodName = String.Format("test{0}", args[0]);
|
1662
|
|
1663
|
System.Reflection.MethodInfo mi = typeof(Test).GetMethod(testMethodName,
|
1664
|
System.Reflection.BindingFlags.Static | System.Reflection.BindingFlags.NonPublic);
|
1665
|
|
1666
|
if (mi == null)
|
1667
|
Console.WriteLine("No such testmethod, {0}", testMethodName);
|
1668
|
else
|
1669
|
{
|
1670
|
object[] attrs = mi.GetCustomAttributes(typeof(ExampleDescriptionAttribute), false);
|
1671
|
Console.WriteLine("============================== {0}() ==================================", testMethodName);
|
1672
|
Console.WriteLine("Description: {0}", attrs.Length > 0 ? attrs[0] : "None");
|
1673
|
Console.WriteLine("===========================================================================");
|
1674
|
mi.Invoke(null, null);
|
1675
|
}
|
1676
|
}
|
1677
|
}
|
1678
|
}
|
1679
|
}
|