Search Results

Search found 1933 results on 78 pages for 'genetic algorithms'.

Page 12/78 | < Previous Page | 8 9 10 11 12 13 14 15 16 17 18 19  | Next Page >

  • evaluating a code of a graph [migrated]

    - by mazen.r.f
    This is relatively a long code,if you have the tolerance and the will to find out how to make this code work then take a look please, i will appreciate your feed back. i have spent two days trying to come up with a code to represent a graph , then calculate the shortest path using dijkastra algorithm , but i am not able to get the right result , even the code runs without errors , but the result is not correct , always i am getting 0. briefly,i have three classes , Vertex, Edge, Graph , the Vertex class represents the nodes in the graph and it has id and carried ( which carry the weight of the links connected to it while using dijkastra algorithm ) and a vector of the ids belong to other nodes the path will go through before arriving to the node itself , this vector is named previous_nodes. the Edge class represents the edges in the graph it has two vertices ( one in each side ) and a wight ( the distance between the two vertices ). the Graph class represents the graph , it has two vectors one is the vertices included in this graph , and the other is the edges included in the graph. inside the class Graph there is a method its name shortest takes the sources node id and the destination and calculates the shortest path using dijkastra algorithm, and i think that it is the most important part of the code. my theory about the code is that i will create two vectors one for the vertices in the graph i will name it vertices and another vector its name is ver_out it will include the vertices out of calculation in the graph, also i will have two vectors of type Edge , one its name edges for all the edges in the graph and the other its name is track to contain temporarily the edges linked to the temporarily source node in every round , after the calculation of every round the vector track will be cleared. in main() i created five vertices and 10 edges to simulate a graph , the result of the shortest path supposedly to be 4 , but i am always getting 0 , that means i am having something wrong in my code , so if you are interesting in helping me find my mistake and how to make the code work , please take a look. the way shortest work is as follow at the beginning all the edges will be included in the vector edges , we select the edges related to the source and put them in the vector track , then we iterate through track and add the wight of every edge to the vertex (node ) related to it ( not the source vertex ) , then after we clear track and remove the source vertex from the vector vertices and select a new source , and start over again select the edges related to the new source , put them in track , iterate over edges in tack , adding the weights to the corresponding vertices then remove this vertex from the vector vertices, and clear track , and select a new source , and so on . here is the code. #include<iostream> #include<vector> #include <stdlib.h> // for rand() using namespace std; class Vertex { private: unsigned int id; // the name of the vertex unsigned int carried; // the weight a vertex may carry when calculating shortest path vector<unsigned int> previous_nodes; public: unsigned int get_id(){return id;}; unsigned int get_carried(){return carried;}; void set_id(unsigned int value) {id = value;}; void set_carried(unsigned int value) {carried = value;}; void previous_nodes_update(unsigned int val){previous_nodes.push_back(val);}; void previous_nodes_erase(unsigned int val){previous_nodes.erase(previous_nodes.begin() + val);}; Vertex(unsigned int init_val = 0, unsigned int init_carried = 0) :id (init_val), carried(init_carried) // constructor { } ~Vertex() {}; // destructor }; class Edge { private: Vertex first_vertex; // a vertex on one side of the edge Vertex second_vertex; // a vertex on the other side of the edge unsigned int weight; // the value of the edge ( or its weight ) public: unsigned int get_weight() {return weight;}; void set_weight(unsigned int value) {weight = value;}; Vertex get_ver_1(){return first_vertex;}; Vertex get_ver_2(){return second_vertex;}; void set_first_vertex(Vertex v1) {first_vertex = v1;}; void set_second_vertex(Vertex v2) {second_vertex = v2;}; Edge(const Vertex& vertex_1 = 0, const Vertex& vertex_2 = 0, unsigned int init_weight = 0) : first_vertex(vertex_1), second_vertex(vertex_2), weight(init_weight) { } ~Edge() {} ; // destructor }; class Graph { private: std::vector<Vertex> vertices; std::vector<Edge> edges; public: Graph(vector<Vertex> ver_vector, vector<Edge> edg_vector) : vertices(ver_vector), edges(edg_vector) { } ~Graph() {}; vector<Vertex> get_vertices(){return vertices;}; vector<Edge> get_edges(){return edges;}; void set_vertices(vector<Vertex> vector_value) {vertices = vector_value;}; void set_edges(vector<Edge> vector_ed_value) {edges = vector_ed_value;}; unsigned int shortest(unsigned int src, unsigned int dis) { vector<Vertex> ver_out; vector<Edge> track; for(unsigned int i = 0; i < edges.size(); ++i) { if((edges[i].get_ver_1().get_id() == vertices[src].get_id()) || (edges[i].get_ver_2().get_id() == vertices[src].get_id())) { track.push_back (edges[i]); edges.erase(edges.begin()+i); } }; for(unsigned int i = 0; i < track.size(); ++i) { if(track[i].get_ver_1().get_id() != vertices[src].get_id()) { track[i].get_ver_1().set_carried((track[i].get_weight()) + track[i].get_ver_2().get_carried()); track[i].get_ver_1().previous_nodes_update(vertices[src].get_id()); } else { track[i].get_ver_2().set_carried((track[i].get_weight()) + track[i].get_ver_1().get_carried()); track[i].get_ver_2().previous_nodes_update(vertices[src].get_id()); } } for(unsigned int i = 0; i < vertices.size(); ++i) if(vertices[i].get_id() == src) vertices.erase(vertices.begin() + i); // removing the sources vertex from the vertices vector ver_out.push_back (vertices[src]); track.clear(); if(vertices[0].get_id() != dis) {src = vertices[0].get_id();} else {src = vertices[1].get_id();} for(unsigned int i = 0; i < vertices.size(); ++i) if((vertices[i].get_carried() < vertices[src].get_carried()) && (vertices[i].get_id() != dis)) src = vertices[i].get_id(); //while(!edges.empty()) for(unsigned int round = 0; round < vertices.size(); ++round) { for(unsigned int k = 0; k < edges.size(); ++k) { if((edges[k].get_ver_1().get_id() == vertices[src].get_id()) || (edges[k].get_ver_2().get_id() == vertices[src].get_id())) { track.push_back (edges[k]); edges.erase(edges.begin()+k); } }; for(unsigned int n = 0; n < track.size(); ++n) if((track[n].get_ver_1().get_id() != vertices[src].get_id()) && (track[n].get_ver_1().get_carried() > (track[n].get_ver_2().get_carried() + track[n].get_weight()))) { track[n].get_ver_1().set_carried((track[n].get_weight()) + track[n].get_ver_2().get_carried()); track[n].get_ver_1().previous_nodes_update(vertices[src].get_id()); } else if(track[n].get_ver_2().get_carried() > (track[n].get_ver_1().get_carried() + track[n].get_weight())) { track[n].get_ver_2().set_carried((track[n].get_weight()) + track[n].get_ver_1().get_carried()); track[n].get_ver_2().previous_nodes_update(vertices[src].get_id()); } for(unsigned int t = 0; t < vertices.size(); ++t) if(vertices[t].get_id() == src) vertices.erase(vertices.begin() + t); track.clear(); if(vertices[0].get_id() != dis) {src = vertices[0].get_id();} else {src = vertices[1].get_id();} for(unsigned int tt = 0; tt < edges.size(); ++tt) { if(vertices[tt].get_carried() < vertices[src].get_carried()) { src = vertices[tt].get_id(); } } } return vertices[dis].get_carried(); } }; int main() { cout<< "Hello, This is a graph"<< endl; vector<Vertex> vers(5); vers[0].set_id(0); vers[1].set_id(1); vers[2].set_id(2); vers[3].set_id(3); vers[4].set_id(4); vector<Edge> eds(10); eds[0].set_first_vertex(vers[0]); eds[0].set_second_vertex(vers[1]); eds[0].set_weight(5); eds[1].set_first_vertex(vers[0]); eds[1].set_second_vertex(vers[2]); eds[1].set_weight(9); eds[2].set_first_vertex(vers[0]); eds[2].set_second_vertex(vers[3]); eds[2].set_weight(4); eds[3].set_first_vertex(vers[0]); eds[3].set_second_vertex(vers[4]); eds[3].set_weight(6); eds[4].set_first_vertex(vers[1]); eds[4].set_second_vertex(vers[2]); eds[4].set_weight(2); eds[5].set_first_vertex(vers[1]); eds[5].set_second_vertex(vers[3]); eds[5].set_weight(5); eds[6].set_first_vertex(vers[1]); eds[6].set_second_vertex(vers[4]); eds[6].set_weight(7); eds[7].set_first_vertex(vers[2]); eds[7].set_second_vertex(vers[3]); eds[7].set_weight(1); eds[8].set_first_vertex(vers[2]); eds[8].set_second_vertex(vers[4]); eds[8].set_weight(8); eds[9].set_first_vertex(vers[3]); eds[9].set_second_vertex(vers[4]); eds[9].set_weight(3); unsigned int path; Graph graf(vers, eds); path = graf.shortest(2, 4); cout<< path << endl; return 0; }

    Read the article

  • Card deck and sparse matrix interview questions

    - by MrDatabase
    I just had a technical phone screen w/ a start-up. Here's the technical questions I was asked ... and my answers. What do think of these answers? Feel free to post better answers :-) Question 1: how would you represent a standard 52 card deck in (basically any language)? How would you shuffle the deck? Answer: use an array containing a "Card" struct or class. Each instance of card has some unique identifier... either it's position in the array or a unique integer member variable in the range [0, 51]. Shuffle the cards by traversing the array once from index zero to index 51. Randomly swap ith card with "another card" (I didn't remember how this shuffle algorithm works exactly). Watch out for using the same probability for each card... that's a gotcha in this algorithm. I mentioned the algorithm is from Programming Pearls. Question 2: how to represent a large sparse matrix? the matrix can be very large... like 1000x1000... but only a relatively small number (~20) of the entries are non-zero. Answer: condense the array into a list of the non-zero entries. for a given entry (i,j) in the array... "map" (i,j) to a single integer k... then use k as a key into a dictionary or hashtable. For the 1000x1000 sparse array map (i,j) to k using something like f(i, j) = i + j * 1001. 1001 is just one plus the maximum of all i and j. I didn't recall exactly how this mapping worked... but the interviewer got the idea (I think). Are these good answers? I'm wondering because after I finished the second question the interviewer said the dreaded "well that's all the questions I have for now." Cheers!

    Read the article

  • How to create single integer index value based on two integers where first is unlimited?

    - by Jan Doggen
    I have table data containing an integer value X ranging from 1.... unknown, and an integer value Y ranging from 1..9 The data need to be presented in order 'X then Y'. For one visual component I can set multiple index names: X;Y But for another component I need a one-dimensional integer value as index (sort order). If X were limited to an upper bound of say 100, the one-dimensional value could simply be X*100 + Y. If the one-dimensional value could have been a real, it could be X + Y/10. But if I want to keep X unlimited, is there a way to calculate a single integer 'indexing' value from X and Y? [Added] Background information: I have a Gantt/TreeList component where the tasks are ordered on a TaskIndex integer. This does not need to be a real database field, I can make it a calculated field in the underlying client dataset. My table data is e.g. as follows: ID Baseline ParentID 1 0 0 (task) 5 2 1 (baseline) 8 1 1 (baseline) 9 0 0 (task) 12 0 0 (task) 16 1 12 (baseline) Task 1 has two baselines numbered 1 and 2 (IDs 8 and 5) Task 9 has no baselines Task 12 has one baseline numbered 1 (ID 16) Baselines number 1-9 (the Y variable from my question); 0 or null identify the tasks ID's are unlimited (the X variable) The user plays with visibility of baselines, e.g. he wants to see all tasks with all baselines labeled 1. This is done by updating a filter on the table. Right now I constantly have to recalculate TaskIndex after changing the filter (looping through records). It would be nice if TaskIndex could be calculated on the fly for each record knowing only the data in the current record (I work in Delphi where a client dataset has an OnCalcFields event handler, that is triggered for each record when necessary). I have no control over the inner workings of the visual component.

    Read the article

  • Algorithm for tracking progress of controller method running in background

    - by SilentAssassin
    I am using Codeigniter framework for PHP on Windows platform. My problem is I am trying to track progress of a controller method running in background. The controller extracts data from the database(MySQL) then does some processing and then stores the results again in the database. The complete aforesaid process can be considered as a single task. A new task can be assigned while another task is running. The newly assigned task will be added in a queue. So if I can track progress of the controller, I can show status for each of these tasks. Like I can show "Pending" status for tasks in the queue, "In Progress" for tasks running and "Done" for tasks that are completed. Main Issue: Now first thing I need to find is an algorithm to track the progress of how much amount of execution the controller method has completed and that means tracking how much amount of method has completed execution. For instance, this PHP script tracks progress of array being counted. Here the current state and state after total execution are known so it is possible to track its progress. But I am not able to devise anything analogous to it in my case. Maybe what I am trying to achieve is programmtically not possible. If its not possible then suggest me a workaround or a completely new approach. If some details are pending you can mention them. Sorry for my ignorance this is my first post here. I welcome you to point out my mistakes. EDIT: Database outline: The URL(s) and keyword(s) are first entered by user which are stored in a database table called link_master and keyword_master respectively. Then keywords are extracted from all the links present in this table and compared with keywords entered by user and their frequency is calculated which is the final result. And the results are stored in another table called link_result. Now sub-links are extracted from the domain links and stored in a table called sub_link_master. Now again the keywords are extracted from these sub-links and the corresponding results are stored in a table called sub_link_result. The number of records cannot be defined beforehand as the number of links on any web page can be different. Only the cardinality of *link_result* table can be known which will be equal to multiplication of number of keyword(s) and URL(s) . I insert multiple records at a time using this resource. Controller outline: The controller extracts keywords from a web page and also extracts keywords from all the links present on that page. There is a method called crawlLink. I used Rolling Curl to extract keywords and web page content. It has callback function which I used for extracting keywords alongwith generating results and extracting valid sub-links. There is a insertResult method which stores results for links and sub-links in the respective tables. Yes, the processing depends on the number of records. The more the number of records, the more time it takes to execute: Consider this scenario: Number of Domain Links = 1 Number of Keywords = 3 Number of Domain Links Result generated = 3 (3 x 1 as described in the question) Number of Sub Links generated = 41 Number of Sub Links Result = 117 (41 x 3 = 123 but some links are not valid or searchable) Approximate time taken for above process to complete = 55 seconds. The above result is for a single link. I want to track the progress of the above results getting stored in database. When all results are stored, the task is complete. If results are getting stored, the task is In Progress. I am not clear how can I track this progress.

    Read the article

  • How can I rank teams based off of head to head wins/losses

    - by TMP
    I'm trying to write an algorithm (specifically in Ruby) that will rank teams based on their record against each other. If a team A and team B have won the same amount of games against each other, then it goes down to point differentials. Here's an example: A beat B two times B beats C one time A beats D three times C bests D two times D beats C one time B beats A one time Which sort of reduces to A[B] = 2 B[C] = 1 A[D] = 3 C[D] = 2 D[C] = 1 B[A] = 1 Which sort of reduces to A[B] = 1 B[C] = 1 A[D] = 3 C[D] = 1 D[C] = -1 B[A] = -1 Which is about how far I've got I think the results of this specific algorithm would be: A, B, C, D But I'm stuck on how to transition from my nested hash-like structure to the results. My psuedo-code is as follows (I can post my ruby code too if someone wants): For each game(g): hash[g.winner][g.loser] += 1 That leaves hash as the first reduction above hash2 = clone of hash For each key(winner), value(losers hash) in hash: For each key(loser), value(losses against winner): hash2[loser][winner] -= losses Which leaves hash2 as the second reduction Feel free to as me question or edit this to be more clear, I'm not sure of how to put it in a very eloquent way. Thanks!

    Read the article

  • Improve the business logic

    - by Victor
    In my application,I have a feature like this: The user wants to add a new address to the database. Before adding the address, he needs to perform a search(using input parameters like country,city,street etc) and when the list comes up, he will manually check if the address he wants to add is present or not. If present, he will not add the address. Is there a way to make this process better. maybe somehow eliminate a step, avoid need for manual verification etc.

    Read the article

  • moore's law and quadratic algorithm

    - by damon
    I was going thru a video (from coursera - by sedgewick) in which he argues that you cannot sustain Moore's law using a quadratic algorithm.He elaborates like this In year 197* you build a computer of power X ,and need to count N objects.This takes M days According to Moore's law,you have a computer of power 2X after 1.5 years.But now you have 2N objects to count. If you use a quadratic algorithm, In year 197*+1.5 ,it takes (4M)/2 = 2M days 4M because the algorithm is quadratic,and division by 2 because of doubling computer power. I find this hard to understand.I tried to work thru this as below To count N objects using comp=X , it takes M days. -> N/X = M After 1.5 yrs ,you need to count 2N objects using comp=2X -> 2N/(2X) -> N/X -> M days where do I go wrong? can someone please help me understand?

    Read the article

  • Simple method for reliably detecting code in text?

    - by Jeff Atwood
    GMail has this feature where it will warn you if you try to send an email that it thinks might have an attachment. Because GMail detected the string see the attached in the email, but no actual attachment, it warns me with an OK / Cancel dialog when I click the Send button. We have a related problem on Stack Overflow. That is, when a user enters a post like this one: my problem is I need to change the database but I don't won't to create a new connection. example: DataSet dsMasterInfo = new DataSet(); Database db = DatabaseFactory.CreateDatabase("ConnectionString"); DbCommand dbCommand = db.GetStoredProcCommand("uspGetMasterName"); This user did not format their code as code! That is, they didn't indent by 4 spaces per Markdown, or use the code button (or the keyboard shortcut ctrl+k) which does that for them. Thus, our system is accreting a lot of edits where people have to go in and manually format code for people that are somehow unable to figure this out. This leads to a lot of bellyaching. We've improved the editor help several times, but short of driving over to the user's house and pressing the correct buttons on their keyboard for them, we're at a loss to see what to do next. That's why we are considering a Google GMail style warning: Did you mean to post code? You wrote stuff that we think looks like code, but you didn't format it as code by indenting 4 spaces, using the toolbar code button or the ctrl+k code formatting command. However, presenting this warning requires us to detect the presence of what we think is unformatted code in a question. What is a simple, semi-reliable way of doing this? Per Markdown, code is always indented by 4 spaces or within backticks, so anything correctly formatted can be discarded from the check immediately. This is only a warning and it will only apply to low-reputation users asking their first questions (or providing their first answers), so some false positives are OK, so long as they are about 5% or less. Questions on Stack Overflow can be in any language, though we can realistically limit our check to, say, the "big ten" languages. Per the tags page that would be C#, Java, PHP, JavaScript, Objective-C, C, C++, Python, Ruby. Use the Stack Overflow creative commons data dump to audit your potential solution (or just pick a few questions in the top 10 tags on Stack Overflow) and see how it does. Pseudocode is fine, but we use c# if you want to be extra friendly. The simpler the better (so long as it works). KISS! If your solution requires us to attempt to compile posts in 10 different compilers, or an army of people to manually train a bayesian inference engine, that's ... not exactly what we had in mind.

    Read the article

  • Figuring a max repetitive sub-tree in an object tree

    - by bonomo
    I am trying to solve a problem of finding a max repetitive sub-tree in an object tree. By the object tree I mean a tree where each leaf and node has a name. Each leaf has a type and a value of that type associated with that leaf. Each node has a set of leaves / nodes in certain order. Given an object tree that - we know - has a repetitive sub-tree in it. By repetitive I mean 2 or more sub-trees that are similar in everything (names/types/order of sub-elements) but the values of leaves. No nodes/leaves can be shared between sub-trees. Problem is to identify these sub-trees of the max height. I know that the exhaustive search can do the trick. I am rather looking for more efficient approach.

    Read the article

  • Quickly compute added and removed lines

    - by Philippe Marschall
    I'm trying to compare two text files. I want to compute how many lines were added and removed. Basically what git diff --stat is doing. Bonus points for not having to store the entire file contents in memory. The approach I'm currently having in mind is: read each line of the old file compute a hash (probably MD5 or SHA-1) for each line store the hashes in a set do the same for each line in the new file every hash from the old file set that's missing in the new file set was removed every hash from the new file set that's missing in the old file set was added I'll probably want to exclude empty and all white space lines. There is a small issue with duplicated lines. This can either be solved by additionally storing how often a hash appears or comparing the number of lines in the old and new file and adjust either the added or removed lines so that the numbers add up. Do you see room for improvements or a better approach?

    Read the article

  • Searching integer sequences

    - by David Gibson
    I have a fairly complex search problem that I've managed to reduce to the following description. I've been googling but haven't been able to find an algorithm that seems to fit my problem cleanly. In particular the need to skip arbitrary integers. Maybe someone here can point me to something? Take a sequence of integers A, for example (1 2 3 4) Take various sequences of integers and test if any of them match A such that. A contains all of the integers in the tested sequence The ordering of the integers in the tested sequence are the same in A We don't care about any integers in A that are not in the test sequence We want all matching test sequences, not just the first. An example A = (1 2 3 4) B = (1 3) C = (1 3 4) D = (3 1) E = (1 2 5) B matches A C matches A D does not match A as the ordering is different E does not match A as it contains an integer not in A I hope that this explanation is clear enough. The best I've managed to do is to contruct a tree of the test sequences and iterate over A. The need to be able to skip integers leads to a lot of unsuccessful search paths. Thanks Reading some suggestions I feel that I have to clarify a couple of points that I left too vague. Repeated numbers are allowed, in fact this is quite important as it allows a single test sequence to match A is multiple ways A = (1234356), B = (236), matches could be either -23---6 or -2--3-6 I expect there to be a very large number of test sequences, in the thousands at least and sequence A will tend to have a max length of maybe 20. Thus simply trying to match each test sequence one by one by iterating becomes extremely inefficient. Sorry if this wasn't clear.

    Read the article

  • String patterns that can be used to filter and group files

    - by Louis Rhys
    One of our application filters files in certain directory, extract some data from it and export a document from the extracted data. The algorithm for extracting the data depends on the file, and so far we use regex to select the algorithm to be used, for example .*\.txt will be processed by algorithm A, foo[0-5]\.xml will be processed by algo B, etc. However now we need some files to be processed together. For example, in one case we need two files, foo.*\.xml and bar.*\.xml. Part of the information to be extracted exist in the foo file, and the other part in the bar file. Moreover, we need to make sure the wild card is compatible. For example, if there are 6 files foo1.xml foo23.xml bar1.xml bar9.xml bar23.xml foo4.xml I would expect foo1 and bar1 to be identified as a group, and foo23 and bar23 as another group. bar9 and foo4 has no pair, so they will not be treated. Now, since the filter is configured by user, we need to have a pattern that can express the above requirement. I don't think you can express meaning like above in standard regex. (foo|bar).*\.xml will match all 6 file above and we can't identify which file is paired for a particular file. Is there any standard pattern that can express it? Or any idea how to modify regex to support this, that can be implemented easily?

    Read the article

  • Evaluating code for a graph [migrated]

    - by mazen.r.f
    This is relatively long code. Please take a look at this code if you are still willing to do so. I will appreciate your feedback. I have spent two days trying to come up with code to represent a graph, calculating the shortest path using Dijkstra's algorithm. But I am not able to get the right result, even though the code runs without errors. The result is not correct and I am always getting 0. I have three classes: Vertex, Edge, and Graph. The Vertex class represents the nodes in the graph and it has id and carried (which carry the weight of the links connected to it while using Dijkstra's algorithm) and a vector of the ids belong to other nodes the path will go through before arriving to the node itself. This vector is named previous_nodes. The Edge class represents the edges in the graph and has two vertices (one in each side) and a width (the distance between the two vertices). The Graph class represents the graph. It has two vectors, where one is the vertices included in this graph, and the other is the edges included in the graph. Inside the class Graph, there is a method named shortest() that takes the sources node id and the destination and calculates the shortest path using Dijkstra's algorithm. I think that it is the most important part of the code. My theory about the code is that I will create two vectors, one for the vertices in the graph named vertices, and another vector named ver_out (it will include the vertices out of calculation in the graph). I will also have two vectors of type Edge, where one is named edges (for all the edges in the graph), and the other is named track (to temporarily contain the edges linked to the temporary source node in every round). After the calculation of every round, the vector track will be cleared. In main(), I've created five vertices and 10 edges to simulate a graph. The result of the shortest path supposedly is 4, but I am always getting 0. That means I have something wrong in my code. If you are interesting in helping me find my mistake and making the code work, please take a look. The way shortest work is as follow: at the beginning, all the edges will be included in the vector edges. We select the edges related to the source and put them in the vector track, then we iterate through track and add the width of every edge to the vertex (node) related to it (not the source vertex). After that, we clear track and remove the source vertex from the vector vertices and select a new source. Then we start over again and select the edges related to the new source, put them in track, iterate over edges in track, adding the weights to the corresponding vertices, then remove this vertex from the vector vertices. Then clear track, and select a new source, and so on. #include<iostream> #include<vector> #include <stdlib.h> // for rand() using namespace std; class Vertex { private: unsigned int id; // the name of the vertex unsigned int carried; // the weight a vertex may carry when calculating shortest path vector<unsigned int> previous_nodes; public: unsigned int get_id(){return id;}; unsigned int get_carried(){return carried;}; void set_id(unsigned int value) {id = value;}; void set_carried(unsigned int value) {carried = value;}; void previous_nodes_update(unsigned int val){previous_nodes.push_back(val);}; void previous_nodes_erase(unsigned int val){previous_nodes.erase(previous_nodes.begin() + val);}; Vertex(unsigned int init_val = 0, unsigned int init_carried = 0) :id (init_val), carried(init_carried) // constructor { } ~Vertex() {}; // destructor }; class Edge { private: Vertex first_vertex; // a vertex on one side of the edge Vertex second_vertex; // a vertex on the other side of the edge unsigned int weight; // the value of the edge ( or its weight ) public: unsigned int get_weight() {return weight;}; void set_weight(unsigned int value) {weight = value;}; Vertex get_ver_1(){return first_vertex;}; Vertex get_ver_2(){return second_vertex;}; void set_first_vertex(Vertex v1) {first_vertex = v1;}; void set_second_vertex(Vertex v2) {second_vertex = v2;}; Edge(const Vertex& vertex_1 = 0, const Vertex& vertex_2 = 0, unsigned int init_weight = 0) : first_vertex(vertex_1), second_vertex(vertex_2), weight(init_weight) { } ~Edge() {} ; // destructor }; class Graph { private: std::vector<Vertex> vertices; std::vector<Edge> edges; public: Graph(vector<Vertex> ver_vector, vector<Edge> edg_vector) : vertices(ver_vector), edges(edg_vector) { } ~Graph() {}; vector<Vertex> get_vertices(){return vertices;}; vector<Edge> get_edges(){return edges;}; void set_vertices(vector<Vertex> vector_value) {vertices = vector_value;}; void set_edges(vector<Edge> vector_ed_value) {edges = vector_ed_value;}; unsigned int shortest(unsigned int src, unsigned int dis) { vector<Vertex> ver_out; vector<Edge> track; for(unsigned int i = 0; i < edges.size(); ++i) { if((edges[i].get_ver_1().get_id() == vertices[src].get_id()) || (edges[i].get_ver_2().get_id() == vertices[src].get_id())) { track.push_back (edges[i]); edges.erase(edges.begin()+i); } }; for(unsigned int i = 0; i < track.size(); ++i) { if(track[i].get_ver_1().get_id() != vertices[src].get_id()) { track[i].get_ver_1().set_carried((track[i].get_weight()) + track[i].get_ver_2().get_carried()); track[i].get_ver_1().previous_nodes_update(vertices[src].get_id()); } else { track[i].get_ver_2().set_carried((track[i].get_weight()) + track[i].get_ver_1().get_carried()); track[i].get_ver_2().previous_nodes_update(vertices[src].get_id()); } } for(unsigned int i = 0; i < vertices.size(); ++i) if(vertices[i].get_id() == src) vertices.erase(vertices.begin() + i); // removing the sources vertex from the vertices vector ver_out.push_back (vertices[src]); track.clear(); if(vertices[0].get_id() != dis) {src = vertices[0].get_id();} else {src = vertices[1].get_id();} for(unsigned int i = 0; i < vertices.size(); ++i) if((vertices[i].get_carried() < vertices[src].get_carried()) && (vertices[i].get_id() != dis)) src = vertices[i].get_id(); //while(!edges.empty()) for(unsigned int round = 0; round < vertices.size(); ++round) { for(unsigned int k = 0; k < edges.size(); ++k) { if((edges[k].get_ver_1().get_id() == vertices[src].get_id()) || (edges[k].get_ver_2().get_id() == vertices[src].get_id())) { track.push_back (edges[k]); edges.erase(edges.begin()+k); } }; for(unsigned int n = 0; n < track.size(); ++n) if((track[n].get_ver_1().get_id() != vertices[src].get_id()) && (track[n].get_ver_1().get_carried() > (track[n].get_ver_2().get_carried() + track[n].get_weight()))) { track[n].get_ver_1().set_carried((track[n].get_weight()) + track[n].get_ver_2().get_carried()); track[n].get_ver_1().previous_nodes_update(vertices[src].get_id()); } else if(track[n].get_ver_2().get_carried() > (track[n].get_ver_1().get_carried() + track[n].get_weight())) { track[n].get_ver_2().set_carried((track[n].get_weight()) + track[n].get_ver_1().get_carried()); track[n].get_ver_2().previous_nodes_update(vertices[src].get_id()); } for(unsigned int t = 0; t < vertices.size(); ++t) if(vertices[t].get_id() == src) vertices.erase(vertices.begin() + t); track.clear(); if(vertices[0].get_id() != dis) {src = vertices[0].get_id();} else {src = vertices[1].get_id();} for(unsigned int tt = 0; tt < edges.size(); ++tt) { if(vertices[tt].get_carried() < vertices[src].get_carried()) { src = vertices[tt].get_id(); } } } return vertices[dis].get_carried(); } }; int main() { cout<< "Hello, This is a graph"<< endl; vector<Vertex> vers(5); vers[0].set_id(0); vers[1].set_id(1); vers[2].set_id(2); vers[3].set_id(3); vers[4].set_id(4); vector<Edge> eds(10); eds[0].set_first_vertex(vers[0]); eds[0].set_second_vertex(vers[1]); eds[0].set_weight(5); eds[1].set_first_vertex(vers[0]); eds[1].set_second_vertex(vers[2]); eds[1].set_weight(9); eds[2].set_first_vertex(vers[0]); eds[2].set_second_vertex(vers[3]); eds[2].set_weight(4); eds[3].set_first_vertex(vers[0]); eds[3].set_second_vertex(vers[4]); eds[3].set_weight(6); eds[4].set_first_vertex(vers[1]); eds[4].set_second_vertex(vers[2]); eds[4].set_weight(2); eds[5].set_first_vertex(vers[1]); eds[5].set_second_vertex(vers[3]); eds[5].set_weight(5); eds[6].set_first_vertex(vers[1]); eds[6].set_second_vertex(vers[4]); eds[6].set_weight(7); eds[7].set_first_vertex(vers[2]); eds[7].set_second_vertex(vers[3]); eds[7].set_weight(1); eds[8].set_first_vertex(vers[2]); eds[8].set_second_vertex(vers[4]); eds[8].set_weight(8); eds[9].set_first_vertex(vers[3]); eds[9].set_second_vertex(vers[4]); eds[9].set_weight(3); unsigned int path; Graph graf(vers, eds); path = graf.shortest(2, 4); cout<< path << endl; return 0; }

    Read the article

  • Automatic Appointment Conflict Resolution

    - by Thomas
    I'm trying to figure out an algorithm for resolving appointment times. I currently have a naive algorithm that pushes down conflicting appointments repeatedly, until there are no more appointments. # The appointment list is always sorted on start time appointment_list = [ <Appointment: 10:00 -> 12:00>, <Appointment: 11:00 -> 12:30>, <Appointment: 13:00 -> 14:00>, <Appointment: 13:30 -> 14:30>, ] Constraints are that appointments: cannot be after 15:00 cannot be before 9:00 This is the naive algorithm for i, app in enumerate(appointment_list): for possible_conflict in appointment_list[i+1:]: if possible_conflict.start < app.end: difference = app.end - possible_conflict.start possible_conflict.end += difference possible_conflict.start += difference else: break This results in the following resolution, which obviously breaks those constraints, and the last appointment will have to be pushed to the following day. appointment_list = [ <Appointment: 10:00 -> 12:00>, <Appointment: 12:00 -> 13:30>, <Appointment: 13:30 -> 14:30>, <Appointment: 14:30 -> 15:30>, ] Obviously this is sub-optimal, It performs 3 appointment moves when the confict could have been resolved with one: if we were able to push the first appointment backwards, we could avoid moving all the subsequent appointments down. I'm thinking that there should be a sort of edit-distance approach that would calculate the least number of appointments that should be moved in order to resolve the scheduling conflict, but I can't get the a handle on the methodology. Should it be breadth-first or depth first solution search. When do I know if the solution is "good enough"?

    Read the article

  • Runtime analysis

    - by Joe Smith
    can someone please help me with the analysis of the following function (for inputs of size n). The part that confuses me the most is the inner for loop. def prefix_sums(L): # Total cost = ? pSum = [] #cost = 1 for a in range(len(L)+1): # range + body of function = (n+1) + (n+1)*(body) ? s = 0 #cost = 1 for b in range(a): # cost = ? s = s + L[b] #cost = operation + accessing list = 2 pSum.append(s) #cost = 1 return pSum #cost = 1 What I need to do is figure out the cost of each statement.

    Read the article

  • Need suggestion for Mutiple Windows application design

    - by King Chan
    This was previously posted in StackOverflow, I just moved to here... I am using VS2008, MVVM, WPF, Prism to make a mutiple window CRM Application. I am using MidWinow in my MainWindow, I want Any ViewModel would able to make request to MainWindow to create/add/close MidChildWindow, ChildWindow(from WPF Toolkit), Window (the Window type). ViewModel can get the DialogResult from the ChildWindow its excutes. MainWindow have control on all opened window types. Here is my current approach: I made Dictionary of each of the windows type and stores them into MainWindow class. For 1, i.e in a CustomerInformationView, its CustomerInformationViewModel can execute EditCommand and use EventAggregator to tell MainWindow to open a new ChildWindow. CustomerInformationViewModel: CustomerEditView ceView = new CustomerEditView (); CustomerEditViewModel ceViewModel = CustomerEditViewModel (); ceView.DataContext = ceViewModel; ChildWindow cWindow = new ChildWindow(); cWindow.Content = ceView; MainWindow.EvntAggregator.GetEvent<NewWindowEvent>().Publish(new WindowEventArgs(ceViewModel.ViewModeGUID, cWindow )); cWindow.Show(); Notice that all my ViewModel will generates a Guid for help identifies the ChildWindow from MainWindow's dictionary. Since I will only be using 1 View 1 ViewModel for every Window. For 2. In CustomerInformationViewModel I can get DialogResult by OnClosing event from ChildWindow, in CustomerEditViewModel can use Guid to tell MainWindow to close the ChildWindow. Here is little question and problems: Is it good idea to use Guid here? Or should I use HashKey from ChildWindow? My MainWindows contains windows reference collections. So whenever window close, it will get notifies to remove from the collection by OnClosing event. But all the Windows itself doesn't know about its associated Guid, so when I remove it, I have to search for every KeyValuePair to compares... I still kind of feel wrong associate ViewModel's Guid for ChildWindow, it would make more sense if ChildWindow has it own ID then ViewModel associate with it... But most important, is there any better approach on this design? How can I improve this better?

    Read the article

  • Algorithm to Solve Most of a Problem

    - by Mike G
    I need an Algorithm/Design Pattern that allows me to try to get the maximum number of rules followed. So I have a couple teams and I need to pair them with a referee and against each other into a round robin. There a rules on who can compete with who and who can judge who so I need to find the configuration that satisfies the most of these. Some rules are more important than others and are "worth more" when evaluating "what satisfies the most of them" There probably isn't a algorithm for this, but is there a design pattern that could help me maximize my chances of finding this configuration?

    Read the article

  • Checking whether php script was resolved by optimal way

    - by user2135931
    Can anybody give some advise how to check the arbitrary php code on optimal solution. For example I create a simple algorithm and sent it on the special resource. After proccessing my algorithm this resource give me result whether my code is nice. If no it give me some advice and tell what is wrong (maybe I forgot check devision by zero etc). I looked for php code analyzer but could't find any variants. Maybe someone give me a resource where I can research this problem. Thanks in advance!

    Read the article

  • is Microsoft LC random generator patented?

    - by user396672
    I need a very simple pseudo random generator (no any specific quality requirements) and I found Microsoft's variant of LCG algorithm used for rand() C runtime library function fit my needs (gcc's one seems too complex). I found the algorithm here: http://rosettacode.org/wiki/Linear_congruential_generator#C However, I worry the algorithm (including its "magic numbers" i.e coefficients) may by patented or restricted for use in some another way. Is it allowed to use this algorithm without any licence or patent restrictions or not? I can't use library rand() because I need my results to be exactly reproducible on different platforms

    Read the article

  • Filling array with numbers from given range so that sum of adjacent numbers is square number

    - by REACHUS
    Problem: Fill all the cells using distinct numbers from <1,25 set, so that sum of two adjacent cells is a square number. (source: http://grymat.im.pwr.wroc.pl/etap1/zad1etp1213.pdf; numbers 20 and 13 have been given) I've already solved this problem analytically and now I would like to approach it using an algorithm. I would like to know how should I approach these kind of problems in general (not a solution, just a point for me to start).

    Read the article

  • Java Alphabetize Algorithm Insertion sort vs Bubble Sort

    - by Chris Okyen
    I am supposed to "Develop a program that alphabetizes three strings. The program should allow the user to enter the three strings, and then display the strings in alphabetical order." It's instructed that I need to use the String library compareTo()/charAt()/toLowerCase() to make all the characters lowercase so the Lexicon comparison is also a alphabetical comparison. Input Pseudo Code: String input[3]; Scanner keyboard = new Scanner(System.in); System.out.println("Enter three strings: "); for(byte i = 0; i < 3; i++) input[i] = keyboard.next() The sorting would be Insertion Sort: 321 2 3 1 2 31 231 1 23 1 2 3 1 23 1 23 123 Bubble Sort 321 231 213 123 Which would be more efficient in this case? The bubble sort seems to be more efficient though they seem to have equal stats for worst best and avg case, but I read the Insertion Sort is quicker for small amounts of data like my case.

    Read the article

  • Can anyone help solve this complex algorithmic problem?

    - by Locaaaaa
    I got this question in an interview and I was not able to solve it. You have a circular road, with N number of gas stations. You know the ammount of gas that each station has. You know the ammount of gas you need to GO from one station to the next one. Your car starts with 0. The question is: Create an algorithm, to know from which gas station you must start driving. As an exercise to me, I would translate the algorithm to C#.

    Read the article

  • MATLAB: Best fitness vs mean fitness, initial range

    - by Sa Ta
    Based on the example of Rastrigin's function. At the plot function, if I chose 'best fitness', on the same graph 'mean fitness' will also be plotted. I understand well about 'best fitness' whereby it plots the best function value in each generation versus iteration number. It will reach value zero after some times. I don't understand about 'mean fitness'in the graph plotted. What do those 'mean fitness' values mean? How does the 'mean fitness' graph help to understand Rastrigin's function? What are the meaning of the term initial population, initial score and initial range? I wish to have a better understanding of these terms. The default value for initial range is [0,1]. Does it mean that 0 is the lower bound (lb) and 1 is the upper bound (ub)? Do these values interfere with the lb and ub values I set in the constraints? I try to better understand about lb and ub. If my lb is 0 and ub is 5, does it mean that my final point values will be within 0 and 5? If I know the lb and ub for my problem is between 0 and 5, do I just set the initial range as [0,5] at all times and may I assume that this is the best option for initial range, and I need not try it with any other values?

    Read the article

  • How can I approach creating an efficient algorithm for maximizing value with these specific constraints?

    - by sway
    I'm having trouble coming up with an approach that isn't n^2 for this problem. Here's a contrived, simplified version I've come up with: Let's say you're a company that needs 4 employees to launch in a new city, a manager, two salespeople, and a customer support rep, and you magically know how much impact every candidate will have and how much salary they require to take the job. Your table of potential employees looks something like this: Name Position Salary Impact Adam Smith Manager 60,000 11 Allison Brown Salesperson 40,000 9 Brad Stewart Manager 55,000 9 ...etc (thousands of records) What algorithmic approach can be taken to find the maximum "impact" while still filling all the positions and remaining under, say, a 200,000 budget? Thanks!

    Read the article

  • find second smallest element in Fibonacci Heap

    - by Longeyes
    I need to describe an algorithm that finds the second smallest element in a Fibonacci-Heap using the Operations: Insert, ExtractMin, DecreaseKey and GetMin. The last one is an algorithm previously implemented to find and return the smallest element of the heap. I thought I'd start by extracting the minimum, which results in its children becoming roots. I could then use GetMin to find the second smallest element. But it seems to me that I'm overlooking other cases because I don't know when to use Insert and DecreaseKey, and the way the question is phrased seems to suggest I should need them.

    Read the article

< Previous Page | 8 9 10 11 12 13 14 15 16 17 18 19  | Next Page >