des.math.graph.fw source code

1 module des.math.graph.fw;
2 
3 import std.range;
4 import std.math;
5 import std.traits;
6 import std.algorithm;
7 
8 import des.math.graph.base;
9 
10 bool hasValue(T)( T v ) @property
11 if( isFloatingPoint!T )
12 { return abs(v) !is T.nan && abs(v) !is T.infinity; }
13 
14 bool hasValue(T)( T v ) @property
15 if( isIntegral!T ) { return v != -1; }
16 
17 /// Floyd–Warshall algorithm
18 auto findGraphShortestPathsFW(T)( WTable!T link_table )
19 {
20     static struct Result
21     {
22         WTable!T W;
23         WTable!ptrdiff_t H;
24 
25         auto opIndex( size_t from, size_t to ) const
26         {
27             Path!T ret;
28             if( !W[from,to].hasValue ) return ret;
29             
30             ret.cost = W[from,to];
31             auto s = from;
32             while( s != to )
33             {
34                 ret.nodes ~= s;
35                 s = H[s,to];
36             }
37             ret.nodes ~= to;
38             return ret;
39         }
40     }
41 
42     auto N = link_table.size;
43     auto W = WTable!T( N, T.infinity );
44     auto H = WTable!ptrdiff_t( N, -1 );
45 
46     foreach( from, to, w; link_table )
47     {
48         if( w.hasValue )
49         {
50             W[from,to] = w;
51             H[from,to] = to;
52         }
53     }
54 
55     foreach( C; iota(N) )
56         foreach( A; iota(N) )
57         {
58             if( C == A ) continue;
59             foreach( B; iota(N) )
60             {
61                 if( B == C || B == A ) continue;
62                 if( W[A,B] > W[A,C] + W[C,B] )
63                 {
64                     W[A,B] = W[A,C] + W[C,B];
65                     H[A,B] = H[A,C];
66                 }
67             }
68         }
69 
70     return Result( W, H );
71 }
72 
73 unittest
74 {
75     auto lt = WTable!float( 8, float.nan );
76 
77     lt[0,1] = lt[1,0] = 6.0;
78     lt[0,2] = lt[2,0] = 3.0;
79     lt[0,3] = lt[3,0] = 2.0;
80 
81     lt[1,2] = lt[2,1] = 3.0;
82     lt[1,3] = lt[3,1] = 1.0;
83     lt[1,4] = lt[4,1] = 1.0;
84 
85     lt[2,5] = lt[5,2] = 7.0;
86     lt[2,7] = lt[7,2] = 6.0;
87 
88     lt[3,4] = lt[4,3] = 3.0;
89 
90     lt[4,5] = lt[5,4] = 2.0;
91 
92     lt[5,7] = lt[7,5] = 1.0;
93     lt[5,6] = lt[6,5] = 3.0;
94 
95     lt[6,7] = lt[7,6] = 1.0;
96 
97     auto fwr = findGraphShortestPathsFW( lt );
98 
99     auto path = fwr[0,6];
100 
101     assert( equal( path.nodes, [0,3,1,4,5,7,6] ) );
102 }