Algorithm

Algorithm of Dijkstra function Dijkstra(Graph, source): for each vertex v in Graph: // Initializations dist[v] := infinity // Unknown distance function from source to v previous[v] := undefined // Previous node in optimal path from source dist[source] := 0 // Distance from source to source Q := the set of all nodes in Graph // All nodes in the graph are unoptimized - thus are in Q while Q is not empty: // The main loop u := vertex in Q with smallest dist[] if dist[u] = infinity: break // all remaining vertices are inaccessible remove u from Q for each neighbor v of u: // where v has not yet been removed from Q. alt := dist[u] + dist_between(u, v) if alt < dist[v]: // Relax (u,v,a) dist[v] := alt previous[v] := u return previous[]

Algorithm for Bandwidth Minimization for I = 1 to restart_times do initialize (labeling) for j-1 to NC_times do NC Labeling If j mod2 = 1then HC (Labeling) End if End for End for

Algorithm of NS Code class LinkDelay; class CIFQ : public Queue { public: CIFQ(); virtual int command(int argc, const char*const* argv);

Packet *deque(void); void enque(Packet *pkt); private: Packet *wf2q_deque(void); void wf2q_enque(Packet *pkt); int active(int flowid); /* judge the flow is active or not */ void leave(int flowid); /* when an empty and non-leading session leave,modify other active session's lag */ double sumw(void); /* sum of the weights of the active session */ int cansend(int flowid); /* determine whether packet of flow flowid can be send */ protected: /* flow structure */ struct flowState { PacketQueue q_; /* packet queue associated to the corresponding flow */ int qmaxSize_; /* maximum queue size (in bytes) */ int qcrtSize_; /* current queue size (in bytes) */ double weight_; /* Weight of the flow */ double S_; /* Starting time of flow , not checked for wraparound*/ double F_; /* Ending time of flow, not checked for wraparound */ double lag_; /* identify the difference between real sys and preference sys */ int rate_; /*uniform error rate*/ RandomVariable *ranvar_; /* the underlying random variate generator*/ } fs_[MAXFLOWS]; double V; /* Virtual time , not checked for wraparound!*/ LinkDelay* link_; /* To get the txt time of a packet */ }; static class CIFQClass : public TclClass { public: CIFQClass() : TclClass("Queue/CIFQ") {} TclObject* create(int argc, const char*const* argv) { return (new CIFQ); } } class_cifq; CIFQ::CIFQ() { /* initialize flow's structure */ for (int i = 0; i < MAXFLOWS; ++i) { fs_[i].qmaxSize_ = DEF_QUEUE_SIZE; fs_[i].qcrtSize_ = 0; fs_[i].weight_ = DEF_FLOW_WEIGHT; fs_[i].S_ = 0.0; fs_[i].F_ = 0.0;

fs_[i].lag_ //fs_[i].send_ fs_[i].ranvar_

} V = 0.0; link_ = NULL;

= 0.0; = 1; =NULL;

} /* * entry points from OTcL to set per flow state variables * - $q set-queue-size flow_id flow_queue_size * - $q set-flow-weight flow_id flow_weight * - $q ranvar flowid [new RandomVariable/Uniform] rate * * NOTE: $q represents the discipline queue variable in OTcl. */ int CIFQ::command(int argc, const char*const* argv) { //Tcl& tcl = Tcl::instance(); if (argc == 4) { if (strcmp(argv[1], "set-queue-size") == 0) { int flowId = atoi(argv[2]); if (flowId >= MAXFLOWS) { fprintf(stderr, "CIFQ: Flow id=%d too large; it should be < %d!\n", abort } fs_[flowId].qmaxSize_ = atoi(argv[3]); return (TCL_OK); } else if (strcmp(argv[1], "set-flow-weight") == 0) { int flowId = atoi(argv[2]); if (flowId >= MAXFLOWS) { fprintf(stderr, "CIFQ: Flow id=%d too large; it should be < %d!\n", flowId, MAXFLOWS); abort(); } double flowweight = atof(argv[3]); if (flowweight <= 0) { fprintf(stderr, "CIFQ: Flow Weight=%.4f > 0\n", flowweight); abort(); } fs_[flowId].weight_ = flowweight; return (TCL_OK); } } if (argc==5) { if (strcmp(argv[1], "ranvar") == 0) { int flowId = atoi(argv[2]); if (flowId >= MAXFLOWS) { fprintf(stderr, "CIFQ: Flow id=%d too large; it should be < %d!\n", flowId, MAXFLOWS);

abort(); } fs_[flowId].ranvar_ = (RandomVariable*) TclObject::lookup(argv[3]); fs_[flowId].rate_ =atoi(argv[4]); return (TCL_OK);

}

} } if (argc == 3){ if (strcmp(argv[1], "link") == 0) { LinkDelay* del = (LinkDelay*)TclObject::lookup(argv[2]); if (del == 0) { fprintf(stderr, "CIFQ: no LinkDelay object %s\n", argv[2]); return(TCL_ERROR); } // set ptc now link_ = del; return (TCL_OK); } } return (Queue::command(argc, argv));

/* * identify the flow state * */ int CIFQ::active(int flowid) { if (fs_[flowid].qcrtSize_||(!fs_[flowid].qcrtSize_&&fs_[flowid].lag_<0.0)) return 1; else return 0; } /* * when an empty and non-leading session leave,modify other active session's lag * */ void CIFQ::leave(int flowid) { printf("ok"); int m; for (m=0;m<MAXFLOWS;m++) { if (active(m)) { fs_[m].lag_+=fs_[flowid].lag_*fs_[flowid].weight_/sumw(); if (!fs_[m].qcrtSize_&&fs_[m].lag_>=0.0)

} }

leave(m);

}

/* *calculate the sum of the weights of the active session,return the sum * */ double CIFQ::sumw(void) { double sum=0.0; int n; for (n=0;n<MAXFLOWS;n++) { if (active(n)) sum+=fs_[n].weight_; } return sum; } /* *Determine wether a flow can send data packet */ int CIFQ::cansend(int flowid) { // if no random var is specified, assume uniform random variable double u = fs_[flowid].ranvar_ ? fs_[flowid].ranvar_->value() : Random::uniform(); return (u >= fs_[flowid].rate_); } /* * Receive a new packet. * * */ void CIFQ::enque(Packet *pkt) { wf2q_enque(pkt); } void CIFQ::wf2q_enque(Packet* pkt) { hdr_cmn* hdr = hdr_cmn::access(pkt); hdr_ip* hip = hdr_ip::access(pkt); int flowId = hip->flowid(); int pktSize = hdr->size(); if (flowId >= MAXFLOWS) { fprintf(stderr, "CIFQ::enqueue-Flow id=%d too large; it should be <

%d!\n", }

flowId, MAXFLOWS); drop(pkt);

/* if buffer full, drop the packet; else enqueue it */ if (fs_[flowId].qcrtSize_ + pktSize > fs_[flowId].qmaxSize_) { /* If the queue is not large enough for this packet */ drop(pkt); } else { if (!fs_[flowId].qcrtSize_) { /* If queue for the flow is empty, calculate start and finish times */ fs_[flowId].S_ = max(V, fs_[flowId].F_); fs_[flowId].F_ = fs_[flowId].S_ + ((double)pktSize/fs_[flowId].weight_); /* the weight_ parameter better not be 0! */ /* update system virutal clock */ double minS = fs_[flowId].S_; for (int i = 0; i < MAXFLOWS; ++i) { if (active(i)) // original wf2q:if (fs_[i].qcrtSize_) if (fs_[i].S_ < minS) minS = fs_[i].S_; } V = max(minS, V); } fs_[flowId].q_.enque(pkt); fs_[flowId].qcrtSize_ += pktSize; } } /* * Dequeue the packet. */ Packet* CIFQ::deque() { Packet *pkt = NULL, *nextPkt; Packet *pktj=NULL, *nextPktj; int i,j; int pktSize; int pktjSize; double minF = MAXDOUBLE; int flow = -1; int maxlagflow= -1; double W = 0.0; double maxlag;

/* look for the candidate flow with the earliest finish time */ for (i = 0; i< MAXFLOWS; i++){ if (!active(i)) continue; if (fs_[i].S_ <= V) if (fs_[i].F_ < minF){ flow = i; minF = fs_[i].F_; } } if (flow == -1 || minF == MAXDOUBLE) return (pkt); if (fs_[flow].lag_>=0.0&&cansend(flow)) { pkt = fs_[flow].q_.deque(); pktSize = ((hdr_cmn*)hdr_cmn::access(pkt))->size(); fs_[flow].qcrtSize_ -= pktSize; /* Set the start and the finish times of the remaining packets in the * queue */ nextPkt = fs_[flow].q_.head(); if (nextPkt) { fs_[flow].S_ = fs_[flow].F_; fs_[flow].F_ = fs_[flow].S_ + ((((hdr_cmn*)hdr_cmn::access(nextPkt))->size())/fs_[flow].weight_); /* the weight parameter better not be 0 */ } /* update the virtual clock */ double minS = fs_[flow].S_; for (i = 0; i < MAXFLOWS; ++i) { W += fs_[i].weight_; if (fs_[i].qcrtSize_) if (fs_[i].S_ < minS) minS = fs_[i].S_; } V = max(minS, (V + ((double)pktSize/W))); if (fs_[flow].lag_>=0.0&&!fs_[flow].qcrtSize_) leave (flow); return(pkt); } else /*search for the session that lag most and active and can send*/ { j=0; while(j<MAXFLOWS&&active(j)&&cansend(j)) { j=j+1;} if (j<MAXFLOWS)/*there has such flow that active and can send*/ {maxlag=fs_[j].lag_/fs_[j].weight_; maxlagflow=j;

for (;j<MAXFLOWS;j++) { if (active(j)&&cansend(j)) {if(maxlagsize(); fs_[maxlagflow].qcrtSize_ -= pktSize; pkt = fs_[flow].q_.deque(); pktSize = ((hdr_cmn*)hdr_cmn::access(pkt))->size(); fs_[flow].lag_+=pktSize ; fs_[maxlagflow].lag_-=pktjSize; /* update the virtual clock */ double minS = fs_[flow].S_; for (i = 0; i < MAXFLOWS; ++i) { W += fs_[i].weight_; if (fs_[i].qcrtSize_) if (fs_[i].S_ < minS) minS = fs_[i].S_; } V = max(minS, (V + ((double)pktSize/W))); if (!fs_[maxlagflow].qcrtSize_&&fs_[maxlagflow].lag_>+0) leave(maxlagflow); return(pktj); }

else/*there is no active session ready to send*/ { /* Set the start and the finish times of the session i */ fs_[flow].S_ = fs_[flow].F_; fs_[flow].F_ = fs_[flow].S_ + (DELTA/fs_[flow].weight_); /* the weight parameter better not be 0 */ /* update the virtual clock */ double minS = fs_[flow].S_; for (i = 0; i < MAXFLOWS; ++i) { W += fs_[i].weight_; if (fs_[i].qcrtSize_) if (fs_[i].S_ < minS) minS = fs_[i].S_; } V = max(minS, (V + (DELTA/W))); pkt = fs_[flow].q_.deque(); pktSize = ((hdr_cmn*)hdr_cmn::access(pkt))->size(); if (fs_[flow].lag_<0.0&&!pktSize)/*flow is leading and unbacklogged*/ /*search for session that lag most and active*/ j=0;

while(j<MAXFLOWS&&active(j)) { j=j+1;} if (j<MAXFLOWS)/*there has such flow that active */ { maxlag=fs_[j].lag_/fs_[j].weight_; maxlagflow=j; for (;j<MAXFLOWS;j++) { if (active(j)) {if(maxlag=0.0&&!fs_[flow].qcrtSize_) leave (flow); }

Force-based algorithms set up initial node velocities to (0,0) set up initial node positions randomly // make sure no 2 nodes are in exactly the same position loop total_kinetic_energy := 0 // running sum of total kinetic energy over all particles for each node net-force := (0, 0) // running sum of total force on this particular node for each other node net-force := net-force + Coulomb_repulsion( this_node, other_node ) next node for each spring connected to this node net-force := net-force + Hooke_attraction( this_node, spring ) next spring // without damping, it moves forever this_node.velocity := (this_node.velocity + timestep * net-force) * damping this_node.position := this_node.position + timestep * this_node.velocity total_kinetic_energy := total_kinetic_energy + this_node.mass * (this_node.velocity)^2 next node until total_kinetic_energy is less than some small number //the simulation has stopped moving

maximum flow Edmonds-Karp algorithm

algorithm EdmondsKarp input: C[1..n, 1..n] (Capacity matrix) E[1..n, 1..?] (Neighbour lists) s (Source) t (Sink) output: f (Value of maximum flow) F (A matrix giving a legal flow with the maximum value) f := 0 (Initial flow is zero) F := array(1..n, 1..n) (Residual capacity from u to v is C[u,v] - F[u,v]) forever m, P := BreadthFirstSearch(C, E, s, t) if m = 0 break f := f + m (Backtrack search, and write flow) v := t while v ≠ s u := P[v] F[u,v] := F[u,v] + m F[v,u] := F[v,u] - m v := u return (f, F) algorithm BreadthFirstSearch input: C, E, s, t output: M[t] (Capacity of path found) P (Parent table) P := array(1..n) for u in 1..n P[u] := -1 P[s] := -2 (make sure source is not rediscovered) M := array(1..n) (Capacity of found path to node) M[s] := ∞ Q := queue() Q.push(s) while Q.size() > 0 u := Q.pop() for v in E[u] (If there is available capacity, and v is not seen before in search) if C[u,v] - F[u,v] > 0 and P[v] = -1 P[v] := u M[v] := min(M[u], C[u,v] - F[u,v]) if v ≠ t Q.push(v) else return M[t], P return 0, P

Bellman-Ford algorithm procedure BellmanFord(list vertices, list edges, vertex source) // This implementation takes in a graph, represented as lists of vertices // and edges, and modifies the vertices so that their distance and // predecessor attributes store the shortest paths. // Step 1: Initialize graph for each vertex v in vertices: if v is source then v.distance := 0 else v.distance := infinity v.predecessor := null // Step 2: relax edges repeatedly for i from 1 to size(vertices)-1: for each edge uv in edges: // uv is the edge from u to v u := uv.source v := uv.destination if v.distance > u.distance + uv.weight: v.distance := u.distance + uv.weight v.predecessor := u // Step 3: check for negative-weight cycles for each edge uv in edges: u := uv.source v := uv.destination if v.distance > u.distance + uv.weight: error "Graph contains a negative-weight cycle"

Algorithm after n duplicate ACKs The pseudo code of the algorithm is the following: if (n DUPACKs are received) ssthresh = (BWE * RTTmin)/seg_size; if (cwin > ssthresh) /* congestion avoid */ cwin = ssthresh; endif endif Algorithm after coarse timeout expiration The pseudo code of the algorithm is: if (coarse timeout expires) ssthresh = (BWE * RTTmin)/seg_size; if (ssthresh < 2) ssthresh = 2; endif;

cwin = 1; endif

5.1 TEST CASES Next phase in the project development was testing. Testing phase basically involved two types of testing, namely α - testing and β - testing. α–testing comprised of extensive testing by the team members. All the modules and code segments were extensively tested for errors. The errors found during this phase of testing are listed below. The errors can be broadly classified into 2 categories namely, •

Planning errors

•

Designing errors

•

Coding errors

Black Box Testing Black box testing relates to tests that are performed at the software interface. Although they are designed to identify errors, black box tests are used to demonstrate that software functions are operational; that inputs are correctly accepted and the output is correctly produced. White Box Testing White box testing is test case design approach that employs the control architecture of the procedural design to produce test cases. Test case can be derived such that they:

 Guarantee that all independent paths within a module have been exercised at least once  Exercise all logical decisions on their true and false sides,  Execute all loops at their boundaries and within their operational bounds and  Exercise internal data structures to ensure their validity. Unit Testing This test focuses verification effort on the small unit of design module. Here using test plans prepared in design descriptions as guide, important control paths are tested to uncover errors within boundary of the module. Boundary condition are tested to ensure module operate properly at boundaries established to limit or restrict processing. All paths in the control structure are exercised to ensure all statements in a module are executed at least once.

5.2 – TEST DATASET Planning Errors: Planning errors are the errors which occurred during the planning and requirement analysis phase of project development. These errors came into attention when the ideas developed during the planning phase were actually implemented in coding. These errors included 1. Error in Database design: During coding it was discovered that some of the tables in the database didn’t have all the attributes

needed to implement some of the functionalities of the project. The database tables were then subsequently modified. 2. Error in code planning: There were some code planning errors like applying transactions at every place where database updating or insertion was made. These transactions were later inserted at proper places.

Designing Errors Designing errors are the errors which occurred in the designing phase of the project development. These errors included 1. Error in E-R diagram design: Some aspects of E-R diagram design were missed during the design phase. These errors cropped up when this E-R Diagram was actually implemented as the database in Access 2003. 2. Error in module designing: There were some inherent errors in dividing the entire project into user modules. The modules had to be redesigned once the group started working on the modules.

Coding Errors The major part of errors encountered during the project designing belonged to this phase of project development. This phase encountered a vast array of errors ranging from simple coding mistakes to big logical blunders. The errors can be listed as 1. Error in Database connectivity: This error was frequently encountered when the code was migrated from one terminal to another. The root cause of this error was the difference in server names at the respective terminals. 2. Error in the implementation of website security: This was realized when the values were posted between different forms

and they were visible in the query string. This was resolved by encrypting this secretive information and by avoiding passing these values wherever possible. 3. Error in the usage of web controls: In some portions of our code there was error in selection of the type of control i.e. dropdown list, textboxes, data grids, etc. We used ASP controls where web controls had to be used. 4. Error

in

usage

of

application

variables:

Error

was

encountered when we tried to create application variables and embed them in our functionality. 5. Error in keeping track of user sessions: We faced errors initially while trying to keep track of the different users visiting the website. This error was dealt with by creating a session table and session variables and using them as and when required. 6. Error in date range validation: Since this part of the code involved intensive usage of nested “if” and “while” loops it became tedious to work with this part of the code to achieve the desired end results. 7. Error in implementing session logout: We encountered a problem in which even after a user logged out he could access the sensitive content of the website.

5.3 5.3 ACCEPTANCE TESTING User Acceptance Testing

User acceptance of a system is the key factor for the success of any system. This is done with regard to following points:  Input screen design.  Output screen design.  On-line guide to the user.  Menu driven system.  Format of output, both on the screen and on the hard copy.

5.4 TESTING RESULT The database structure and the software developed in this project were put to testing to check the proper functioning of different queries in the software. All the known problems were looked into and rectified. This testing was performed with the hypothetical data.

Algo complete using System; using System.Diagnostics; using System.Collections.Generic; using System.Text; namespace VisualIntelligentScissors { /// <summary> /// Implements a generalized Dijkstra's algorithm to calculate /// both minimum distance and minimum path. /// /// /// For this algorithm, all nodes should be provided, and handled /// in the delegate methods, including the start and finish nodes.

/// public class Dijkstra { /// <summary> /// An optional delegate that can help optimize the algorithm /// by showing it a subset of nodes to consider. Very useful /// for limited connectivity graphs. (like pixels on a screen!) /// /// <param name="startingNode"> /// The node that is being traveled away FROM. /// /// /// An array of nodes that might be reached from the /// <paramref name="startingNode"/>. /// public delegate IEnumerable NearbyNodesHint(int startingNode); /// <summary> /// Determines the cost of moving from a given node to another given node. /// /// <param name="start"> /// The node being moved away from. /// /// <param name="finish"> /// The node that may be moved to. /// /// /// The cost of the transition from <paramref name="start"/> to /// <paramref name="finish"/>, or <see cref="Int32.MaxValue"/> /// if the transition is impossible (i.e. there is no edge between /// the two nodes). ///

public delegate int InternodeTraversalCost(int start, int finish); /// <summary> /// Creates an instance of the <see cref="Dijkstra"/> class. /// /// <param name="totalNodeCount"> /// The total number of nodes in the graph. /// /// <param name="traversalCost"> /// The delegate that can provide the cost of a transition between /// any two nodes. /// /// <param name="hint"> /// An optional delegate that can provide a small subset of nodes /// that a given node may be connected to. /// public Dijkstra(int totalNodeCount, InternodeTraversalCost traversalCost, NearbyNodesHint hint) { if (totalNodeCount < 3) throw new ArgumentOutOfRangeException("totalNodeCount", totalNodeCount, "Expected a minimum of 3."); if (traversalCost == null) throw new ArgumentNullException("traversalCost"); Hint = hint; TraversalCost = traversalCost; TotalNodeCount = totalNodeCount; } protected readonly NearbyNodesHint Hint; protected readonly InternodeTraversalCost TraversalCost; protected readonly int TotalNodeCount;

/// <summary> /// The composite product of a Dijkstra algorithm. /// public struct Results { /// <summary> /// Prepares a Dijkstra results package. /// /// <param name="minimumPath"> /// The minimum path array, where each array element index corresponds /// to a node designation, and the array element value is a pointer to /// the node that should be used to travel to this one. /// /// <param name="minimumDistance"> /// The minimum distance from the starting node to the given node. /// public Results(int[] minimumPath, int[] minimumDistance) { MinimumDistance = minimumDistance; MinimumPath = minimumPath; } /// <summary> /// The minimum path array, where each array element index corresponds /// to a node designation, and the array element value is a pointer to /// the node that should be used to travel to this one. /// public readonly int[] MinimumPath; /// <summary> /// The minimum distance from the starting node to the given node. ///

public readonly int[] MinimumDistance; } /// <summary> /// Performs the Dijkstra algorithm on the data provided when the /// <see cref="Dijkstra"/> object was instantiated. /// /// <param name="start"> /// The node to use as a starting location. /// /// /// A struct containing both the minimum distance and minimum path /// to every node from the given <paramref name="start"/> node. /// public virtual Results Perform(int start) { // Initialize the distance to every node from the starting node. int[] d = GetStartingTraversalCost(start); // Initialize best path to every node as from the starting node. int[] p = GetStartingBestPath(start); ICollection c = GetChoices(); c.Remove(start); // take starting node out of the list of choices //Debug.WriteLine("Step v C D P"); //Debug.WriteLine(string.Format("init - {{{0}}} [{1}] [{2}]", // ArrayToString(",", c), ArrayToString(",", d), ArrayToString(",", p))); //int step = 0; // begin greedy loop while (c.Count > 1)

{ // Find element v in c, that minimizes d[v] int v = FindMinimizingDinC(d, c); c.Remove(v); // remove v from the list of future solutions // Consider all unselected nodes and consider their cost from v. foreach (int w in (Hint != null ? Hint(v) : c)) { if (!c.Contains(w)) continue; // discard pixels not in c // At this point, relative(Index) points to a candidate pixel, // that has not yet been selected, and lies within our area of interest. // Consider whether it is now within closer reach. int cost = TraversalCost(v, w); if (cost < int.MaxValue && d[v] + cost < d[w]) // don't let wrap-around negatives slip by { // We have found a better way to get at relative d[w] = d[v] + cost; // record new distance // Record how we came to this new pixel p[w] = v; } } //Debug.WriteLine(string.Format("{4} {3} {{{0}}} [{1}] [{2}]", // ArrayToString(",", c), ArrayToString(",", d), ArrayToString(",", p), v + 1, ++step)); } return new Results(p, d); } /// <summary> /// Uses the Dijkstra algorithhm to find the minimum path

/// from one node to another. /// /// <param name="start"> /// The node to use as a starting location. /// /// <param name="finish"> /// The node to use as a finishing location. /// /// /// A struct containing both the minimum distance and minimum path /// to every node from the given <paramref name="start"/> node. /// public virtual int[] GetMinimumPath(int start, int finish) { Results results = Perform(start); return GetMinimumPath(start, finish, results.MinimumPath); } /// <summary> /// Finds an array of nodes that provide the shortest path /// from one given node to another. /// /// <param name="start"> /// The starting node. /// /// <param name="finish"> /// The finishing node. /// /// <param name="shortestPath"> /// The P array of the completed algorithm. ///

/// /// The list of nodes that provide the one step at a time path /// from <paramref name="start"/> to <paramref name="finish"/> nodes. /// protected virtual int[] GetMinimumPath(int start, int finish, int[] shortestPath) { Stack path = new Stack(); do { path.Push(finish); finish = shortestPath[finish]; // step back one step toward the start point } while (finish != start); return path.ToArray(); } /// <summary> /// Initializes the P array for the algorithm. /// /// <param name="startingNode"> /// The node that has been designated the starting node for the entire algorithm. /// /// /// The new P array. /// /// /// A fresh P array will set every single node's source node to be /// the starting node, including the starting node itself. /// protected virtual int[] GetStartingBestPath(int startingNode) {

int[] p = new int[TotalNodeCount]; for (int i = 0; i < p.Length; i++) p[i] = startingNode; return p; } /// <summary> /// Finds the yet-unconsidered node that has the least cost to reach. /// /// <param name="d"> /// The cost of reaching any node. /// /// <param name="c"> /// The nodes that are still available for picking. /// /// /// The node that is closest (has the shortest special path). /// protected virtual int FindMinimizingDinC(int[] d, ICollection c) { int bestIndex = -1; foreach (int ci in c) if (bestIndex == -1 || d[ci] < d[bestIndex]) bestIndex = ci; return bestIndex; } /// <summary> /// Initializes an collection of all nodes not yet considered. /// ///

/// The initialized collection. /// protected virtual ICollection GetChoices() { ICollection choices = new List(TotalNodeCount); for (int i = 0; i < TotalNodeCount; i++) choices.Add(i); return choices; } /// <summary> /// Initializes the D array for the start of the algorithm. /// /// <param name="start"> /// The starting node. /// /// /// The contents of the new D array. /// /// /// The traversal cost for every node will be set to impossible /// (int.MaxValue) unless a connecting edge is found between the /// <paramref name="start"/>ing node and the node in question. /// protected virtual int[] GetStartingTraversalCost(int start) { int[] subset = new int[TotalNodeCount]; for (int i = 0; i < subset.Length; i++) subset[i] = int.MaxValue; // all are unreachable subset[start] = 0; // zero cost from start to start foreach (int nearby in Hint(start))

subset[nearby] = TraversalCost(start, nearby); return subset; } /// <summary> /// Joins the elements of an array into a string, using /// a given separator. /// /// The type of element in the array. /// <param name="separator">The seperator to insert between each element. /// <param name="array">The array. /// The resulting string. /// /// This is very much like <see cref="string.Join"/>, except /// that it works on arrays of non-strings. /// protected string ArrayToString(string separator, IEnumerable array) { StringBuilder sb = new StringBuilder(); foreach (int t in array) sb.AppendFormat("{0}{1}", t < int.MaxValue ? t + 1 : t, separator); sb.Length -= separator.Length; return sb.ToString(); } } }