Search Results

Search found 2666 results on 107 pages for 'graph traversal'.

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

  • Facebook - Publish Checkins using Graph API

    - by Zany
    I'm trying to publish Checkin using Facebook Graph API. I've gone through Facebook API documentation (checkins) and also have the publish_checkins permission. However, my checkin is not getting published. May I know is there anything wrong or am I missing anything else? Thank you for your time :) fbmain.php $user = $facebook->getUser(); $access_token = $facebook->getAccessToken(); // Session based API call if ($user) { try { $me = $facebook->api('/me'); if($me) { $_SESSION['fbID'] = $me['id']; $uid = $me['id']; } } catch (FacebookApiException $e) { error_log($e); } } else { echo "<script type='text/javascript'>top.location.href='$loginUrl';</script>"; exit; } $loginUrl = $facebook->getLoginUrl( array( 'redirect_uri' => $redirect_url, 'scope' => status_update, publish_stream, publish_checkins, user_checkins, user_location, user_status' ) ); main.php (Updated: 18/6/2012 11.12pm) <?php include_once "fbmain.php"; if (!isset($_POST['latitude']) && !isset($_POST['longitude'])) { ?> <html> <head> //ajax POST of latitude and longitude </head> <body> <script type="text/javascript"> window.fbAsyncInit = function() { FB.init({ appId: '<?php echo $facebook->getAppID() ?>', cookie: true, xfbml: true, oauth: true, frictionlessRequests: true }); FB.Canvas.setAutoGrow(); }; (function() { var e = document.createElement('script'); e.async = true; e.src = document.location.protocol + '//connect.facebook.net/en_US/all.js'; document.getElementById('fb-root').appendChild(e); }()); </script> ... <input type="button" value="Check In!" onclick="checkin(<?=$facebook?>);"/></span> </body> </html> <?php } else { print_r($_POST['latitude']); print_r($_POST['longitude']); ?> <script type="text/javascript"> // not using latitude and longitude to test function checkin($fb) { try { $tryCatch = $facebook->api('/'.$_SESSION['fbID'].'/checkins', 'POST', array( 'access_token' => $fb->getAccessToken(), //corrected 'place' => '165122993538708', 'message' =>'I went to placename today', 'coordinates' => json_encode(array( 'latitude' => '1.3019399200902', 'longitude' => '103.84067653695' )) )); } catch(FacebookApiException $e) { $tryCatch=$e->getMessage(); } return $tryCatch; } </script> <?php } ?>

    Read the article

  • Merging .net object graph

    - by Tiju John
    Hi guys, has anyone come across any scenario wherein you needed to merge one object with another object of same type, merging the complete object graph. for e.g. If i have a person object and one person object is having first name and other the last name, some way to merge both the objects into a single object. public class Person { public Int32 Id { get; set; } public string FirstName { get; set; } public string LastName { get; set; } } public class MyClass { //both instances refer to the same person, probably coming from different sources Person obj1 = new Person(); obj1.Id=1; obj1.FirstName = "Tiju"; Person obj2 = new Person(); ojb2.Id=1; obj2.LastName = "John"; //some way of merging both the object obj1.MergeObject(obj2); //?? //obj1.Id // = 1 //obj1.FirstName // = "Tiju" //obj1.LastName // = "John" } I had come across such type of requirement and I wrote an extension method to do the same. public static class ExtensionMethods { private const string Key = "Id"; public static IList MergeList(this IList source, IList target) { Dictionary itemData = new Dictionary(); //fill the dictionary for existing list string temp = null; foreach (object item in source) { temp = GetKeyOfRecord(item); if (!String.IsNullOrEmpty(temp)) itemData[temp] = item; } //if the same id exists, merge the object, otherwise add to the existing list. foreach (object item in target) { temp = GetKeyOfRecord(item); if (!String.IsNullOrEmpty(temp) && itemData.ContainsKey(temp)) itemData[temp].MergeObject(item); else source.Add(item); } return source; } private static string GetKeyOfRecord(object o) { string keyValue = null; Type pointType = o.GetType(); if (pointType != null) foreach (PropertyInfo propertyItem in pointType.GetProperties()) { if (propertyItem.Name == Key) { keyValue = (string)propertyItem.GetValue(o, null); } } return keyValue; } public static object MergeObject(this object source, object target) { if (source != null && target != null) { Type typeSource = source.GetType(); Type typeTarget = target.GetType(); //if both types are same, try to merge if (typeSource != null && typeTarget != null && typeSource.FullName == typeTarget.FullName) if (typeSource.IsClass && !typeSource.Namespace.Equals("System", StringComparison.InvariantCulture)) { PropertyInfo[] propertyList = typeSource.GetProperties(); for (int index = 0; index < propertyList.Length; index++) { Type tempPropertySourceValueType = null; object tempPropertySourceValue = null; Type tempPropertyTargetValueType = null; object tempPropertyTargetValue = null; //get rid of indexers if (propertyList[index].GetIndexParameters().Length == 0) { tempPropertySourceValue = propertyList[index].GetValue(source, null); tempPropertyTargetValue = propertyList[index].GetValue(target, null); } if (tempPropertySourceValue != null) tempPropertySourceValueType = tempPropertySourceValue.GetType(); if (tempPropertyTargetValue != null) tempPropertyTargetValueType = tempPropertyTargetValue.GetType(); //if the property is a list IList ilistSource = tempPropertySourceValue as IList; IList ilistTarget = tempPropertyTargetValue as IList; if (ilistSource != null || ilistTarget != null) { if (ilistSource != null) ilistSource.MergeList(ilistTarget); else propertyList[index].SetValue(source, ilistTarget, null); } //if the property is a Dto else if (tempPropertySourceValue != null || tempPropertyTargetValue != null) { if (tempPropertySourceValue != null) tempPropertySourceValue.MergeObject(tempPropertyTargetValue); else propertyList[index].SetValue(source, tempPropertyTargetValue, null); } } } } return source; } } However, this works when the source property is null, if target has it, it will copy that to source. IT can still be improved to merge when inconsistencies are there e.g. if FirstName="Tiju" and FirstName="John" Any commments appreciated. Thanks TJ

    Read the article

  • Scala: Recursively building all pathes in a graph?

    - by DarqMoth
    Trying to build all existing paths for an udirected graph defined as a map of edges using the following algorithm: Start: with a given vertice A Find an edge (X.A, X.B) or (X.B, X.A), add this edge to path Find all edges Ys fpr which either (Y.C, Y.B) or (Y.B, Y.C) is true For each Ys: A=B, goto Start Providing edges are defined as the following map, where keys are tuples consisting of two vertices: val edges = Map( ("n1", "n2") -> "n1n2", ("n1", "n3") -> "n1n3", ("n3", "n4") -> "n3n4", ("n5", "n1") -> "n5n1", ("n5", "n4") -> "n5n4") As an output I need to get a list of ALL pathes where each path is a list of adjecent edges like this: val allPaths = List( List(("n1", "n2") -> "n1n2"), List(("n1", "n3") -> "n1n3", ("n3", "n4") -> "n3n4"), List(("n5", "n1") -> "n5n1"), List(("n5", "n4") -> "n5n4"), List(("n2", "n1") -> "n1n2", ("n1", "n3") -> "n1n3", ("n3", "n4") -> "n3n4", ("n5", "n4") -> "n5n4")) //... //... more pathes to go } Note: Edge XY = (x,y) - "xy" and YX = (y,x) - "yx" exist as one instance only, either as XY or YX So far I have managed to implement code that duplicates edges in the path, which is wrong and I can not find the error: object Graph2 { type Vertice = String type Edge = ((String, String), String) type Path = List[((String, String), String)] val edges = Map( //(("v1", "v2") , "v1v2"), (("v1", "v3") , "v1v3"), (("v3", "v4") , "v3v4") //(("v5", "v1") , "v5v1"), //(("v5", "v4") , "v5v4") ) def main(args: Array[String]): Unit = { val processedVerticies: Map[Vertice, Vertice] = Map() val processedEdges: Map[(Vertice, Vertice), (Vertice, Vertice)] = Map() val path: Path = List() println(buildPath(path, "v1", processedVerticies, processedEdges)) } /** * Builds path from connected by edges vertices starting from given vertice * Input: map of edges * Output: list of connected edges like: List(("n1", "n2") -> "n1n2"), List(("n1", "n3") -> "n1n3", ("n3", "n4") -> "n3n4"), List(("n5", "n1") -> "n5n1"), List(("n5", "n4") -> "n5n4"), List(("n2", "n1") -> "n1n2", ("n1", "n3") -> "n1n3", ("n3", "n4") -> "n3n4", ("n5", "n4") -> "n5n4")) */ def buildPath(path: Path, vertice: Vertice, processedVerticies: Map[Vertice, Vertice], processedEdges: Map[(Vertice, Vertice), (Vertice, Vertice)]): List[Path] = { println("V: " + vertice + " VM: " + processedVerticies + " EM: " + processedEdges) if (!processedVerticies.contains(vertice)) { val edges = children(vertice) println("Edges: " + edges) val x = edges.map(edge => { if (!processedEdges.contains(edge._1)) { addToPath(vertice, processedVerticies.++(Map(vertice -> vertice)), processedEdges, path, edge) } else { println("ALready have edge: "+edge+" Return path:"+path) path } }) val y = x.toList y } else { List(path) } } def addToPath( vertice: Vertice, processedVerticies: Map[Vertice, Vertice], processedEdges: Map[(Vertice, Vertice), (Vertice, Vertice)], path: Path, edge: Edge): Path = { val newPath: Path = path ::: List(edge) val key = edge._1 val nextVertice = neighbor(vertice, key) val x = buildPath (newPath, nextVertice, processedVerticies, processedEdges ++ (Map((vertice, nextVertice) -> (vertice, nextVertice))) ).flatten // need define buidPath type x } def children(vertice: Vertice) = { edges.filter(p => (p._1)._1 == vertice || (p._1)._2 == vertice) } def containsPair(x: (Vertice, Vertice), m: Map[(Vertice, Vertice), (Vertice, Vertice)]): Boolean = { m.contains((x._1, x._2)) || m.contains((x._2, x._1)) } def neighbor(vertice: String, key: (String, String)): String = key match { case (`vertice`, x) => x case (x, `vertice`) => x } } Running this results in: List(List(((v1,v3),v1v3), ((v1,v3),v1v3), ((v3,v4),v3v4))) Why is that?

    Read the article

  • design pattern advice: graph -> computation

    - by csetzkorn
    I have a domain model, persisted in a database, which represents a graph. A graph consists of nodes (e.g. NodeTypeA, NodeTypeB) which are connected via branches. The two generic elements (nodes and branches will have properties). A graph will be sent to a computation engine. To perform computations the engine has to be initialised like so (simplified pseudo code): Engine Engine = new Engine() ; Object ID1 = Engine.AddNodeTypeA(TypeA.Property1, TypeA.Property2, …, TypeA.Propertyn); Object ID2 = Engine.AddNodeTypeB(TypeB.Property1, TypeB.Property2, …, TypeB.Propertyn); Engine.AddBranch(ID1,ID2); Finally the computation is performed like this: Engine.DoSomeComputation(); I am just wondering, if there are any relevant design patterns out there, which help to achieve the above using good design principles. I hope this makes sense. Any feedback would be very much appreciated.

    Read the article

  • Oracle Spatial and Graph – A year in review

    - by Mandy Ho
    Normal 0 false false false EN-US X-NONE X-NONE MicrosoftInternetExplorer4 /* Style Definitions */ table.MsoNormalTable {mso-style-name:"Table Normal"; mso-tstyle-rowband-size:0; mso-tstyle-colband-size:0; mso-style-noshow:yes; mso-style-priority:99; mso-style-qformat:yes; mso-style-parent:""; mso-padding-alt:0in 5.4pt 0in 5.4pt; mso-para-margin:0in; mso-para-margin-bottom:.0001pt; mso-pagination:widow-orphan; font-size:11.0pt; font-family:"Calibri","sans-serif"; mso-ascii-font-family:Calibri; mso-ascii-theme-font:minor-latin; mso-fareast-font-family:"Times New Roman"; mso-fareast-theme-font:minor-fareast; mso-hansi-font-family:Calibri; mso-hansi-theme-font:minor-latin; mso-bidi-font-family:"Times New Roman"; mso-bidi-theme-font:minor-bidi;} What a great year for Oracle Spatial! Or shall I now say, Oracle Spatial and Graph, with our official name change this summer. There were so many exciting events and updates we had this year, and this blog will review and link to some of the events you may have missed over the year. We kicked off 2012 with our webinar: Situational Analysis at OnStar with Oracle Spatial and Graph. We collaborated with OnStar’s Emergency Strategy and Outreach expert, Jeff Joyner ,on how Onstar uses Google Earth Visualization, NAVTEQ data and Oracle Database to deliver fast, accurate emergency services to its customers. In the next webinar in our 2012 series, Oracle partner TARGUSinfo showcased how to build a robust, scalable and secure customer relationship management systems – with built-in mapping and spatial analysis, and deployed in the cloud. This is a very cool system using all Oracle technologies including Oracle Database and Fusion Middleware MapViewer. Attendees learned how to gather market insight, score prospects and customers and perform location analysis. The replay is available here. Our final webinar of the year focused on using Oracle Business Intelligence tools, along with Oracle Spatial and Graph to perform location-aware predictive analysis. Watch the webcast here: In June, we joined up with the Location Intelligence conference in Washington, DC, and had a very successful 2012 Oracle Spatial User Conference. Customers and partners from the US, as well as from EMEA and Asia, flew in to share experiences and ideas, and get technical updates from Oracle experts. Users were excited to hear about spatial-Exadata performance, and advances in MapViewer and BI. Peter Doolan of Oracle Public Sector kicked off the event with a great keynote, and US Census, NOAA, and Ordnance Survey Great Britain were just a few of the presenters. Presentation archive here. We recognized some of the most exceptional partners and customers for their contributions to advancing mainstream solutions using geospatial technologies. Planning for 2013’s conference has already started. Please contribute your papers for consideration here. http://www.locationintelligence.net/ We also launched a new Oracle PartnerNetwork Spatial Specialization – to enable partners to get validated in the marketplace for their expertise in taking solutions to market. Individuals can also get individual certifications. Learn more here. Oracle Open World was not to disappoint, with news regarding our next Oracle Spatial and Graph release, as well as the announcement of our new Oracle Spatial and Graph SIG board! Join the SIG today. One more exciting event as we look to 2013. Spatial and location technologies have a dedicated track at the January BIWA SIG Summit – on January 9-10 in Redwood Shores, CA. View the agenda and register here: www.biwasummit.org. We thank you for all your support during the year of 2012 and look towards an even more exciting 2013! Wishing you and your family a prosperous New Year and Happy Holidays!

    Read the article

  • Help:Graph contest problem: maybe a modified Dijkstra or another alternative algorithm

    - by newba
    Hi you all, I'm trying to do this contest exercise about graphs: XPTO is an intrepid adventurer (a little too temerarious for his own good) who boasts about exploring every corner of the universe, no matter how inhospitable. In fact, he doesn't visit the planets where people can easily live in, he prefers those where only a madman would go with a very good reason (several millions of credits for instance). His latest exploit is trying to survive in Proxima III. The problem is that Proxima III suffers from storms of highly corrosive acids that destroy everything, including spacesuits that were especially designed to withstand corrosion. Our intrepid explorer was caught in a rectangular area in the middle of one of these storms. Fortunately, he has an instrument that is capable of measuring the exact concentration of acid on each sector and how much damage it does to his spacesuit. Now, he only needs to find out if he can escape the storm. Problem The problem consists of finding an escape route that will allow XPTOto escape the noxious storm. You are given the initial energy of the spacesuit, the size of the rectangular area and the damage that the spacesuit will suffer while standing in each sector. Your task is to find the exit sector, the number of steps necessary to reach it and the amount of energy his suit will have when he leaves the rectangular area. The escape route chosen should be the safest one (i.e., the one where his spacesuit will be the least damaged). Notice that Rodericus will perish if the energy of his suit reaches zero. In case there are more than one possible solutions, choose the one that uses the least number of steps. If there are at least two sectors with the same number of steps (X1, Y1) and (X2, Y2) then choose the first if X1 < X2 or if X1 = X2 and Y1 < Y2. Constraints 0 < E = 30000 the suit's starting energy 0 = W = 500 the rectangle's width 0 = H = 500 rectangle's height 0 < X < W the starting X position 0 < Y < H the starting Y position 0 = D = 10000 the damage sustained in each sector Input The first number given is the number of test cases. Each case will consist of a line with the integers E, X and Y. The following line will have the integers W and H. The following lines will hold the matrix containing the damage D the spacesuit will suffer whilst in the corresponding sector. Notice that, as is often the case for computer geeks, (1,1) corresponds to the upper left corner. Output If there is a solution, the output will be the remaining energy, the exit sector's X and Y coordinates and the number of steps of the route that will lead Rodericus to safety. In case there is no solution, the phrase Goodbye cruel world! will be written. Sample Input 3 40 3 3 7 8 12 11 12 11 3 12 12 12 11 11 12 2 1 13 11 11 12 2 13 2 14 10 11 13 3 2 1 12 10 11 13 13 11 12 13 12 12 11 13 11 13 12 13 12 12 11 11 11 11 13 13 10 10 13 11 12 8 3 4 7 6 4 3 3 2 2 3 2 2 5 2 2 2 3 3 2 1 2 2 3 2 2 4 3 3 2 2 4 1 3 1 4 3 2 3 1 2 2 3 3 0 3 4 10 3 4 7 6 3 3 1 2 2 1 0 2 2 2 4 2 2 5 2 2 1 3 0 2 2 2 2 1 3 3 4 2 3 4 4 3 1 1 3 1 2 2 4 2 2 1 Sample Output 12 5 1 8 Goodbye cruel world! 5 1 4 2 Basically, I think we have to do a modified Dijkstra, in which the distance between nodes is the suit's energy (and we have to subtract it instead of suming up like is normal with distances) and the steps are the ....steps made along the path. The pos with the bester binomial (Energy,num_Steps) is our "way out". Important : XPTO obviously can't move in diagonals, so we have to cut out this cases. I have many ideas, but I have such a problem implementing them... Could someone please help me thinking about this with some code or, at least, ideas? Am I totally wrong?

    Read the article

  • Graph spacing algorithm

    - by David
    Hi, I am looking for an algorithm that would be useful for determining x y coordinates for a number objects to display on screen. Each object can be related to another object and there can be any number of relationships and there can be any number of these objects. There is no restriction on the overall size of area on which to display these object. I am writing this in php and would be looking to store the coordinates in an array.

    Read the article

  • create graph using adjacency list

    - by sum1needhelp
    #include<iostream> using namespace std; class TCSGraph{ public: void addVertex(int vertex); void display(); TCSGraph(){ head = NULL; } ~TCSGraph(); private: struct ListNode { string name; struct ListNode *next; }; ListNode *head; } void TCSGraph::addVertex(int vertex){ ListNode *newNode; ListNode *nodePtr; string vName; for(int i = 0; i < vertex ; i++ ){ cout << "what is the name of the vertex"<< endl; cin >> vName; newNode = new ListNode; newNode->name = vName; if (!head) head = newNode; else nodePtr = head; while(nodePtr->next) nodePtr = nodePtr->next; nodePtr->next = newNode; } } void TCSGraph::display(){ ListNode *nodePtr; nodePtr = head; while(nodePtr){ cout << nodePtr->name<< endl; nodePtr = nodePtr->next; } } int main(){ int vertex; cout << " how many vertex u wan to add" << endl; cin >> vertex; TCSGraph g; g.addVertex(vertex); g.display(); return 0; }

    Read the article

  • Finding backedges in a graph, with special conditions.

    - by Morteza M.
    There is a vertex v, such that from the subtree rooted at v, there are at least two backedges to proper ancestors of v. The problem is finding whether such backedges exist or not ( finding v is not important at all). I run DFS algorithm, I can find backedges and save them in an array. I know which backedges in this array belong to a common tree. but I have problem on matching this condition in O(E) time. can anyone help me with that?

    Read the article

  • How to perform undirected graph processing from SQL data

    - by recipriversexclusion
    I ran into the following problem in dynamically creating topics for our ActiveMQ system: I have a number of processes (M_1, ..., M_n), where n is not large, typically 5-10. Some of the processes will listen to the output of others, through a message queue; these edges are specified in an XML file, e.g. <link from="M1" to="M3"</link> <link from="M2" to="M4"</link> <link from="M3" to="M4"</link> etc. The edges are sparse, so there won't be many of them. I will parse this XML and store this information in an SQL DB, one table for nodes and another for edges. Now, I need to dynamically create strings of the form M1.exe --output_topic=T1 M2.exe --output_topic=T2 M3.exe --input_topic=T1 --output_topic=T3 M4.exe --input_topic=T2 --input_topic=T3 where the tags are sequentially generated. What is the best way to go about querying SQL to obtain these relationships? Are there any tools or other tutorials you can point me to? I've never done graps with SQL. Using SQL is imperative, because we use it for other stuff, too. Thanks!

    Read the article

  • Graph diffing and versioning tool

    - by hashable
    I am working with a team that edits large DAGs represented as single files. Currently we are unable to work with multiple users concurrently modifying the DAG. Is there a tool (somewhat like the Eclipse SVN plugin) that can do do revision control on the file (manage timestamps/revision stamps) to identify incoming/outgoing/conflicting changes (Node/Link insertion/deletion/modification) and merge changes just like programmers do with source code files? The system should be able to do dependency management also. E.g. an incoming Link must not be accepted when one of the two Nodes is absent. That is, it should not "break" the existing DAG by allowing partial updates. If there is a framework to do this using generic "Node" and "Link" interfaces? Note: I am aware of Protege and its plugins. They currently do not satisfy my requirements.

    Read the article

  • How to modify preorder tree traversal algorithm to handle nodes with multiple parents?

    - by poldo
    I've been searching for a while now and can't seem to find an alternative solution. I need the tree traversal algorithm in such a way that a node can have more than 1 parent, if it's possible (found a great article here: Storing Hierarchical Data in a Database). Are there any algorithms so that, starting from a root node, we can determine the sequence and dependencies of nodes (currently reading topological sorting)?

    Read the article

  • how to get large pictures from photo album via facebook graph api

    - by Nav
    I am currently using the following code to retrieve all the photos from a user profile FB.api('/me/albums?fields=id,name', function(response) { //console.log(response.data.length); for (var i = 0; i < response.data.length; i++) { var album = response.data[i]; FB.api('/' + album.id + '/photos', function(photos) { if (photos && photos.data && photos.data.length) { for (var j = 0; j < photos.data.length; j++) { var photo = photos.data[j]; // photo.picture contain the link to picture var image = document.createElement('img'); image.src = photo.picture; document.body.appendChild(image); image.className = "border"; image.onclick = function() { //this.parentNode.removeChild(this); document.getElementById(info.id).src = this.src; document.getElementById(info.id).style.width = "220px"; document.getElementById(info.id).style.height = "126px"; }; } } }); } }); but, the photos that it returns are of poor quality and are basically like thumbnails.How to retrieve larger photos from the albums. Generally for profile picture I use ?type=large which returns a decent profile image but the type=large is not working in the case of photos from photo albums and also is there a way to get the photos in zip format from facebook once I specify the photo url as I want users to be able to download the photos.

    Read the article

  • PHP SDK for Facebook: Uploading an Image for an Event created using the Graph API

    - by wenbert
    Can anyone shed some light on my problem? <?php $config = array(); $config['appId'] = "foo"; $config['secret'] = "bar"; $config['cookie'] = true; $config['fileUpload'] = true; $facebook = new Facebook($config); $eventParams = array( "privacy_type" => $this->request->data['Event']['privacy'], "name" => $this->request->data['Event']['event'], "description" => $this->request->data['Event']['details'], "start_time" => $this->request->data['Event']['when'], "country" => "NZ" ); //around 300x300 pixels //I have set the permissions to Everyone $imgpath = "C:\\Yes\\Windows\\Path\\Photo_for_the_event_app.jpg"; $eventParams["@file.jpg"] = "@".$imgpath; $fbEvent = $facebook->api("me/events", "POST", $eventParams); var_dump($fbEvent); //I get the event id I also have this in my "scope" when the user is asked to Allow the app to post on his behalf: user_about_me,email,publish_stream,create_event,photo_upload This works. It creates the event with all the details I have specified. EXCEPT for the event image. I have been to most of Stackoverflow posts related to my problem but all of them are not working for me. (EG: http://stackoverflow.com/a/4245260/66767) I also do not get any error. Any ideas? THanks!

    Read the article

  • A Plot Graph .NET WindowsForm Component Free

    - by user255946
    Hello All, I'm searching for a plot .NET component to plot a 2D line chart, given an array of data. It will be used with WindowsForm (C#) and It will be very helpful if it could be freeware. It is for a scientific application. This is my first asked question in stackoverflow, and excuse me for my terrible English written.

    Read the article

  • Hopcroft–Karp algorithm in Python

    - by Simon
    I am trying to implement the Hopcroft Karp algorithm in Python using networkx as graph representation. Currently I am as far as this: #Algorithms for bipartite graphs import networkx as nx import collections class HopcroftKarp(object): INFINITY = -1 def __init__(self, G): self.G = G def match(self): self.N1, self.N2 = self.partition() self.pair = {} self.dist = {} self.q = collections.deque() #init for v in self.G: self.pair[v] = None self.dist[v] = HopcroftKarp.INFINITY matching = 0 while self.bfs(): for v in self.N1: if self.pair[v] and self.dfs(v): matching = matching + 1 return matching def dfs(self, v): if v != None: for u in self.G.neighbors_iter(v): if self.dist[ self.pair[u] ] == self.dist[v] + 1 and self.dfs(self.pair[u]): self.pair[u] = v self.pair[v] = u return True self.dist[v] = HopcroftKarp.INFINITY return False return True def bfs(self): for v in self.N1: if self.pair[v] == None: self.dist[v] = 0 self.q.append(v) else: self.dist[v] = HopcroftKarp.INFINITY self.dist[None] = HopcroftKarp.INFINITY while len(self.q) > 0: v = self.q.pop() if v != None: for u in self.G.neighbors_iter(v): if self.dist[ self.pair[u] ] == HopcroftKarp.INFINITY: self.dist[ self.pair[u] ] = self.dist[v] + 1 self.q.append(self.pair[u]) return self.dist[None] != HopcroftKarp.INFINITY def partition(self): return nx.bipartite_sets(self.G) The algorithm is taken from http://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm However it does not work. I use the following test code G = nx.Graph([ (1,"a"), (1,"c"), (2,"a"), (2,"b"), (3,"a"), (3,"c"), (4,"d"), (4,"e"),(4,"f"),(4,"g"), (5,"b"), (5,"c"), (6,"c"), (6,"d") ]) matching = HopcroftKarp(G).match() print matching Unfortunately this does not work, I end up in an endless loop :(. Can someone spot the error, I am out of ideas and I must admit that I have not yet fully understand the algorithm, so it is mostly an implementation of the pseudo code on wikipedia

    Read the article

  • How can I use the Boost Graph Library to lay out verticies?

    - by Mike
    I'm trying to lay out vertices using the Boost Graph Library. However, I'm running into some compilation issues which I'm unsure about. Am I using the BGL in an improper manner? My code is: PositionVec position_vec(2); PositionMap position(position_vec.begin(), get(vertex_index, g)); int iterations = 100; double width = 100.0; double height = 100.0; minstd_rand gen; rectangle_topology<> topology(gen, 0, 0, 100, 100); fruchterman_reingold_force_directed_layout(g, position, topology); //Compile fails on this line The diagnostics produced by clang++(I've also tried GCC) are: In file included from test.cpp:2: /Volumes/Data/mike/Downloads/boost_1_43_0/boost/graph/fruchterman_reingold.hpp:95:3: error: no member named 'dimensions' in 'boost::simple_point<double>' BOOST_STATIC_ASSERT (Point::dimensions == 2); ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ In file included from test.cpp:2: In file included from /Volumes/Data/mike/Downloads/boost_1_43_0/boost/graph/fruchterman_reingold.hpp:13: In file included from /Volumes/Data/mike/Downloads/boost_1_43_0/boost/graph/graph_traits.hpp:15: In file included from /Volumes/Data/mike/Downloads/boost_1_43_0/boost/tuple/tuple.hpp:24: /Volumes/Data/mike/Downloads/boost_1_43_0/boost/static_assert.hpp:118:49: note: instantiated from: sizeof(::boost::STATIC_ASSERTION_FAILURE< BOOST_STATIC_ASSERT_BOOL_CAST( B ) >)>\ ^ In file included from test.cpp:2: /Volumes/Data/mike/Downloads/boost_1_43_0/boost/graph/fruchterman_reingold.hpp:95:3: note: instantiated from: BOOST_STATIC_ASSERT (Point::dimensions == 2); ^ ~~~~~~~ /Volumes/Data/mike/Downloads/boost_1_43_0/boost/graph/fruchterman_reingold.hpp:95:31: note: instantiated from: BOOST_STATIC_ASSERT (Point::dimensions == 2); ~~~~~~~^ /Volumes/Data/mike/Downloads/boost_1_43_0/boost/graph/fruchterman_reingold.hpp:417:19: note: in instantiation of template class 'boost::grid_force_pairs<boost::rectangle_topology<boost::random::linear_congruential<int, 48271, 0, 2147483647, 399268537> >, boost::iterator_property_map<__gnu_cxx::__normal_iterator<boost::simple_point<double> *, std::vector<boost::simple_point<double>, std::allocator<boost::simple_point<double> > > >, boost::vec_adj_list_vertex_id_map<boost::property<boost::vertex_name_t, std::basic_string<char>, boost::no_property>, unsigned long>, boost::simple_point<double>, boost::simple_point<double> &> >' requested here make_grid_force_pairs(topology, position, g)), ^ /Volumes/Data/mike/Downloads/boost_1_43_0/boost/graph/fruchterman_reingold.hpp:431:3: note: in instantiation of function template specialization 'boost::fruchterman_reingold_force_directed_layout<boost::rectangle_topology<boost::random::linear_congruential<int, 48271, 0, 2147483647, 399268537> >, boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS, boost::property<boost::vertex_name_t, std::basic_string<char>, boost::no_property>, boost::no_property, boost::no_property, boost::listS>, boost::iterator_property_map<__gnu_cxx::__normal_iterator<boost::simple_point<double> *, std::vector<boost::simple_point<double>, std::allocator<boost::simple_point<double> > > >, boost::vec_adj_list_vertex_id_map<boost::property<boost::vertex_name_t, std::basic_string<char>, boost::no_property>, unsigned long>, boost::simple_point<double>, boost::simple_point<double> &>, boost::square_distance_attractive_force, boost::attractive_force_t, boost::no_property>' requested here fruchterman_reingold_force_directed_layout ^ test.cpp:48:3: note: in instantiation of function template specialization 'boost::fruchterman_reingold_force_directed_layout<boost::rectangle_topology<boost::random::linear_congruential<int, 48271, 0, 2147483647, 399268537> >, boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS, boost::property<boost::vertex_name_t, std::basic_string<char>, boost::no_property>, boost::no_property, boost::no_property, boost::listS>, boost::iterator_property_map<__gnu_cxx::__normal_iterator<boost::simple_point<double> *, std::vector<boost::simple_point<double>, std::allocator<boost::simple_point<double> > > >, boost::vec_adj_list_vertex_id_map<boost::property<boost::vertex_name_t, std::basic_string<char>, boost::no_property>, unsigned long>, boost::simple_point<double>, boost::simple_point<double> &> >' requested here fruchterman_reingold_force_directed_layout(g, position, topology); ^ 1 error generated.

    Read the article

  • finding shortest valid path in a colored-edge graphs

    - by user1067083
    Given a directed graph G, with edges colored either green or purple, and a vertex S in G, I must find an algorithm that finds the shortest path from s to each vertex in G so the path includes at most two purple edges (and green as much as needed). I thought of BFS on G after removing all the purple edges, and for every vertex that the shortest path is still infinity, do something to try to find it, but I'm kinda stuck, and it takes alot of the running time as well... Any other suggestions? Thanks in advance

    Read the article

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