Search Results

Search found 619 results on 25 pages for 'edges'.

Page 3/25 | < Previous Page | 1 2 3 4 5 6 7 8 9 10 11 12  | Next Page >

• Generic Adjacency List Graph implementation

  - by DmainEvent

  I am trying to come up with a decent Adjacency List graph implementation so I can start tooling around with all kinds of graph problems and algorithms like traveling salesman and other problems... But I can't seem to come up with a decent implementation. This is probably because I am trying to dust the cobwebs off my data structures class. But what I have so far... and this is implemented in Java... is basically an edgeNode class that has a generic type and a weight-in the event the graph is indeed weighted. public class edgeNode<E> { private E y; private int weight; //... getters and setters as well as constructors... } I have a graph class that has a list of edges a value for the number of Vertices and and an int value for edges as well as a boolean value for whether or not it is directed. The brings up my first question, if the graph is indeed directed, shouldn't I have a value in my edgeNode class? Or would I just need to add another vertices to my LinkedList? That would imply that a directed graph is 2X as big as an undirected graph wouldn't it? public class graph { private List<edgeNode<?>> edges; private int nVertices; private int nEdges; private boolean directed; //... getters and setters as well as constructors... } Finally does anybody have a standard way of initializing there graph? I was thinking of reading in a pipe-delimited file but that is so 1997. public graph GenereateGraph(boolean directed, String file){ List<edgeNode<?>> edges; graph g; try{ int count = 0; String line; FileReader input = new FileReader("C:\\Users\\derekww\\Documents\\JavaEE Projects\\graphFile"); BufferedReader bufRead = new BufferedReader(input); line = bufRead.readLine(); count++; edges = new ArrayList<edgeNode<?>>(); while(line != null){ line = bufRead.readLine(); Object edgeInfo = line.split("|")[0]; int weight = Integer.parseInt(line.split("|")[1]); edgeNode<String> e = new edgeNode<String>((String) edges.add(e); } return g; } catch(Exception e){ return null; } } I guess when I am adding edges if boolean is true I would be adding a second edge. So far, this all depends on the file I write. So if I wrote a file with the following Vertices and weights... Buffalo | 18 br Pittsburgh | 20 br New York | 15 br D.C | 45 br I would obviously load them into my list of edges, but how can I represent one vertices connected to the other... so on... I would need the opposite vertices? Say I was representing Highways connected to each city weighted and un-directed (each edge is bi-directional with weights in some fictional distance unit)... Would my implementation be the best way to do that? I found this tutorial online Graph Tutorial that has a connector object. This appears to me be a collection of vertices pointing to each other. So you would have A and B each with there weights and so on, and you would add this to a list and this list of connectors to your graph... That strikes me as somewhat cumbersome and a little dismissive of the adjacency list concept? Am I wrong and that is a novel solution? This is all inspired by steve skiena's Algorithm Design Manual. Which I have to say is pretty good so far. Thanks for any help you can provide.

  Read the article

• Is there any automatic tool to remove edges from an image that has been anti-aliased onto a white ba

  - by Macha

  I have a few images that have been anti-aliased onto a white background that I want to put on a transparent background. Just selecting it with the -wand tool/fuzzy select tool/select your terminology of choice- and deleting the background tends to leave a ring of off-white pixels around the image, or eat into the image depending on the tolerance setting. Is there some better way to do this, preferably an automatic tool? (I'm on Linux)

  Read the article

• How to scan convert right edges and slopes less than one?

  - by Zachary

  I'm writing a program which will use scan conversion on triangles to fill in the pixels contained within the triangle. One thing that has me confused is how to determine the x increment for the right edge of the triangle, or for slopes less than or equal to one. Here is the code I have to handle left edges with a slope greater than one (obtained from Computer Graphics: Principles and Practice second edition): for(y=ymin;y<=ymax;y++) { edge.increment+=edge.numerator; if(edge.increment>edge.denominator) { edge.x++; edge.increment -= edge.denominator; } } The numerator is set from (xMax-xMin), and the denominator is set from (yMax-yMin)...which makes sense as it represents the slope of the line. As you move up the scan lines (represented by the y values). X is incremented by 1/(denomniator/numerator) ...which results in x having a whole part and a fractional part. If the fractional part is greater than one, then the x value has to be incremented by 1 (as shown in edge.incrementedge.denominator). This works fine for any left handed lines with a slope greater than one, but I'm having trouble generalizing it for any edge, and google-ing has proved fruitless. Does anyone know the algorithm for that?

  Read the article

• A weird crash...

  - by Nima

  Hi, I have a piece of code that runs in debug mode in VS2008, C++. The problem is that when I am debugging the code line by line, at a very weird point of the code, it crashes and says: debug assertion faild. Expression: _BLOCK_TYPE_IS_VALID(pHead-nBlockUse) The crash point is on the first closed curly bracket (after mesh-edges[e].needsUpdate=false;) I don't understand why on a curly bracket? does that make sense to you guys? Can anybody help me understanding what is going on..? for(int e=0; e<mesh->edges.size(); e++) { if(mesh->edges[e].valid && mesh->edges[e].v[0]>=0 && mesh->edges[e].v[1]>=0 && mesh->points[mesh->edges[e].v[0]].writable && mesh->points[mesh->edges[e].v[1]].writable) { //update v_hat and its corresponding error DecEdge Current = DecEdge(e); pair<Point, float> ppf = computeVhat(e); Current.v_hat = ppf.first; Current.error = ppf.second; edgeSoup.push(Current); mesh->edges[e].needsUpdate=false; } }

  Read the article

• graphviz segmentation fault

  - by LucaB

  Hi I'm building a graph with many nodes, around 3000. I wrote a simple python program to do the trick with graphviz, but it gives me segmentation fault and I don't know why, if the graph is too big or if i'm missing something. The code is: #!/usr/bin/env python # Import graphviz import sys sys.path.append('..') sys.path.append('/usr/lib/graphviz') import gv # Import pygraph from pygraph.classes.graph import graph from pygraph.classes.digraph import digraph from pygraph.algorithms.searching import breadth_first_search from pygraph.readwrite.dot import write # Graph creation gr = graph() file = open('nodes.dat', 'r') line = file.readline() while line: gr.add_nodes([line[0:-1]]) line = file.readline() file.close() print 'nodes finished, beginning edges' edges = open('edges_ok.dat', 'r') edge = edges.readline() while edge: gr.add_edge((edge.split()[0], edge.split()[1])) edge = edges.readline() edges.close() print 'edges finished' print 'Drawing' # Draw as PNG dot = write(gr) gvv = gv.readstring(dot) gv.layout(gvv,'dot') gv.render(gvv,'svg','graph.svg') and it crashes at the gv.layout() call. The files are somthing like: nodes: node1 node2 node3 edges_ok: node1 node2 node2 node3

  Read the article

• How do I get an Iterator over a vector of objects from a Template?

  - by nieldw

  I'm busy implementing a Graph ADT in C++. I have templates for the Edges and the Vertices. At each Vertex I have a vector containing pointers to the Edges that are incident to it. Now I'm trying to get an iterator over those edges. These are the lines of code: vector<Edge<edgeDecor, vertexDecor, dir>*> edges = this->incidentEdges(); vector<Edge<edgeDecor, vertexDecor, dir>*>::const_iterator i; for (i = edges.begin(); i != edges.end(); ++i) { However, the compiler won't accept the middle line. I'm pretty new to C++. Am I missing something? Why can't I declare an iterator over objects from the Edge template? The compiler isn't giving any useful feedback. Much thanks niel

  Read the article

• Splitting Graph into distinct polygons in O(E) complexity

  - by Arthur Wulf White

  If you have seen my last question: trapped inside a Graph : Find paths along edges that do not cross any edges How do you split an entire graph into distinct shapes 'trapped' inside the graph(like the ones described in my last question) with good complexity? What I am doing now is iterating over all edges and then starting to traverse while always taking the rightmost turn. This does split the graph into distinct shapes. Then I eliminate all the excess shapes (that are repeats of previous shapes) and return the result. The complexity of this algorithm is O(E^2). I am wondering if I could do it in O(E) by removing edges I already traversed previously. My current implementation of that returns unexpected results.

  Read the article

• Finding most Important Node(s) in a Directed Graph

  - by Srikar Appal

  I have a large (˜ 20 million nodes) directed Graph with in-edges & out-edges. I want to figure out which parts of of the graph deserve the most attention. Often most of the graph is boring, or at least it is already well understood. The way I am defining "attention" is by the concept of "connectedness" i.e. How can i find the most connected node(s) in the graph? In what follows, One can assume that nodes by themselves have no score, the edges have no weight & they are either connected or not. This website suggest some pretty complicated procedures like n-dimensional space, Eigen Vectors, graph centrality concepts, pageRank etc. Is this problem that complex? Can I not do a simple Breadth-First Traversal of the entire graph where at each node I figure out a way to find the number of in-edges. The node with most in-edges is the most important node in the graph. Am I missing something here?

  Read the article

• How do I prevent jagged edges alongside the surfaces of my 3d model?

  - by badcodenotreat

  Lets say I've implemented in openGL a crude model viewer with shading which renders a series of blocks, such that I have something that looks like this. http://i.imgur.com/TsF7K.jpg Whenever I rotate my model to the side, it causes an unwanted jagged effect along any surface with a steep viewing angle. http://i.imgur.com/Bgl9o.jpg I'm pretty sure this is due to the polygon offset I used to prevent z-fighting between the model and the wireframe, however I'm not able to find the factor/unit parameters in openGL which prevent this unwanted effect. what are the best values of factor and unit for glPolygonOffset to prevent this? would implementing anti-aliasing alleviate the problem? is the trade off in performance trivial/significant? is this perhaps a shading issue? should i try a solution along this line of thought?

  Read the article

• Prim's MST algorithm implementation with Java

  - by user1290164

  I'm trying to write a program that'll find the MST of a given undirected weighted graph with Kruskal's and Prim's algorithms. I've successfully implemented Kruskal's algorithm in the program, but I'm having trouble with Prim's. To be more precise, I can't figure out how to actually build the Prim function so that it'll iterate through all the vertices in the graph. I'm getting some IndexOutOfBoundsException errors during program execution. I'm not sure how much information is needed for others to get the idea of what I have done so far, but hopefully there won't be too much useless information. This is what I have so far: I have a Graph, Edge and a Vertex class. Vertex class mostly just an information storage that contains the name (number) of the vertex. Edge class can create a new Edge that has gets parameters (Vertex start, Vertex end, int edgeWeight). The class has methods to return the usual info like start vertex, end vertex and the weight. Graph class reads data from a text file and adds new Edges to an ArrayList. The text file also tells us how many vertecis the graph has, and that gets stored too. In the Graph class, I have a Prim() -method that's supposed to calculate the MST: public ArrayList<Edge> Prim(Graph G) { ArrayList<Edge> edges = G.graph; // Copies the ArrayList with all edges in it. ArrayList<Edge> MST = new ArrayList<Edge>(); Random rnd = new Random(); Vertex startingVertex = edges.get(rnd.nextInt(G.returnVertexCount())).returnStartingVertex(); // This is just to randomize the starting vertex. // This is supposed to be the main loop to find the MST, but this is probably horribly wrong.. while (MST.size() < returnVertexCount()) { Edge e = findClosestNeighbour(startingVertex); MST.add(e); visited.add(e.returnStartingVertex()); visited.add(e.returnEndingVertex()); edges.remove(e); } return MST; } The method findClosesNeighbour() looks like this: public Edge findClosestNeighbour(Vertex v) { ArrayList<Edge> neighbours = new ArrayList<Edge>(); ArrayList<Edge> edges = graph; for (int i = 0; i < edges.size() -1; ++i) { if (edges.get(i).endPoint() == s.returnVertexID() && !visited(edges.get(i).returnEndingVertex())) { neighbours.add(edges.get(i)); } } return neighbours.get(0); // This is the minimum weight edge in the list. } ArrayList<Vertex> visited and ArrayList<Edges> graph get constructed when creating a new graph. Visited() -method is simply a boolean check to see if ArrayList visited contains the Vertex we're thinking about moving to. I tested the findClosestNeighbour() independantly and it seemed to be working but if someone finds something wrong with it then that feedback is welcome also. Mainly though as I mentioned my problem is with actually building the main loop in the Prim() -method, and if there's any additional info needed I'm happy to provide it. Thank you. Edit: To clarify what my train of thought with the Prim() method is. What I want to do is first randomize the starting point in the graph. After that, I will find the closest neighbor to that starting point. Then we'll add the edge connecting those two points to the MST, and also add the vertices to the visited list for checking later, so that we won't form any loops in the graph. Here's the error that gets thrown: Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 0, Size: 0 at java.util.ArrayList.rangeCheck(Unknown Source) at java.util.ArrayList.get(Unknown Source) at Graph.findClosestNeighbour(graph.java:203) at Graph.Prim(graph.java:179) at MST.main(MST.java:49) Line 203: return neighbour.get(0); in findClosestNeighbour() Line 179: Edge e = findClosestNeighbour(startingVertex); in Prim()

  Read the article

• Robust line of sight test on the inside of a polygon with tolerance

  - by David Gouveia

  Foreword This is a followup to this question and the main problem I'm trying to solve. My current solution is an hack which involves inflating the polygon, and doing most calculations on the inflated polygon instead. My goal is to remove this step completely, and correctly solve the problem with calculations only. Problem Given a concave polygon and treating all of its edges as if they were walls in a level, determine whether two points A and B are in line of sight of each other, while accounting for some degree of floating point errors. I'm currently basing my solution on a series of line-segment interection tests. In other words: If any of the end points are outside the polygon, they are not in line of sight. If both end points are inside the polygon, and the line segment from A to B crosses any of the edges from the polygon, then they are not in line of sight. If both end points are inside the polygon, and the line segment from A to B does not cross any of the edges from the polygon, then they are in line of sight. But the problem is dealing correctly with all the edge cases. In particular, it must be able to deal with all the situations depicted below, where red lines are examples that should be rejected, and green lines are examples that should be accepted. I probably missed a few other situations, such as when the line segment from A to B is colinear with an edge, but one of the end points is outside the polygon. One point of particular interest is the difference between 1 and 9. In both cases, both end points are vertices of the polygon, and there are no edges being intersected, but 1 should be rejected while 9 should be accepted. How to distinguish these two? I could check some middle point within the segment to see if it falls inside or not, but it's easy to come up with situations in which it would fail. Point 7 was also pretty tricky and I had to to treat it as a special case, which checks if two points are adjacent vertices of the polygon directly. But there are also other chances of line segments being col linear with the edges of the polygon, and I'm still not entirely sure how I should handle those cases. Is there any well known solution to this problem?

  Read the article

• Adding tolerance to a point in polygon test

  - by David Gouveia

  I've been using this method which was taken from Game Coding Complete to detect whether a point is inside of a polygon. It works in almost every case, but is failing on a few edge cases, and I can't figure out the reason. For example, given a polygon with vertices at (0,0) (0,100) and (100,100), the algorithm is returning: True for any point strictly inside the polygon False for any of the vertices False for (0, 50) which lies on one of the edges of the polygon True (?) for (50,50) which is also on one of the edges of the polygon I'd actually like to relax the algorithm so that it returns true in all of these cases. In other words, it should return true for points that are strictly inside, for the vertices themselves, and for points on the edges of the polygon. If possible I'd also like to give it enough tolerance so that it always tend towards "true" in face of floating point fluctuations. For example, I have another method, that given a line segment and a point, returns the closest location on the line segment to the given point. Currently, given any point outside the polygon and one of its edges, there are cases where the result is categorized as being inside by the method above, while other points are considered outside. I'd like to give it enough tolerance so that it always returns true in this situation. The way I've currently solved the problem is an hack, which consists of using an external library to inflate the polygon by a few pixels, and performing the tests on the inflated polygon, but I'd really like to replace this with a proper solution.

  Read the article

• How to make my simple round sprite look right in XNA

  - by Joshua Perina

  Ok, I'm very new to graphics programming (but not new to coding). I'm trying to load a simple image in XNA which I can do fine. It is a simple round circle which I made in photoshop. The problem is the edges show up rough when I draw it on the screen even with the exact size. The anti-aliasing is missing. I'm sure I'm missing something very simple: GraphicsDevice.Clear(Color.Black); // TODO: Add your drawing code here spriteBatch.Begin(); spriteBatch.Draw(circle, new Rectangle(10, 10, 10, 10), Color.White); spriteBatch.End(); Couldn't post picture because I'm a first time poster. But my smooth png circle has rough edges. So I found that if I added: spriteBatch.Begin(SpriteSortMode.FrontToBack, BlendState.NonPremultiplied); I can get a smooth image when the image is the same size as the original png. But if I want to scale that image up or down then the rough edges return. How do I get XNA to smoothly resize my simple round image to a smaller size without getting the rough edges?

  Read the article

• When can I be sure a directed graph is acyclic?

  - by Daniel Scocco

  The definition for directed acyclic graph is this: "there is no way to start at some vertex v and follow a sequence of edges that eventually loops back to v again." So far so good, but I am trying to find some premises that will be simpler to test and that will also guarantee the graph is acyclic. I came up with those premises, but they are pretty basic so I am sure other people figured it out in the past (or they are incorrect). The problem is I couldn't find anything related on books/online, hence why I decided to post this question. Premise 1: If all vertices of the graph have an incoming edge, then the graph can't be acyclic. Is this correct? Premise 2: Assume the graph in question does have one vertex with no incoming edges. In this case, in order to have a cycle, at least one of the other vertices would need to have two or more incoming edges. Is this correct?

  Read the article

• Box2Dweb very slow on node.js

  - by Peteris

  I'm using Box2Dweb on node.js. I have a rotated box object that I apply an impulse to move around. The timestep is set at 50ms, however, it bumps up to 100ms and even 200ms as soon as I add any more edges or boxes. Here are the edges I would like to use as bounds around the playing area: // Computing the corners var upLeft = new b2Vec2(0, 0), lowLeft = new b2Vec2(0, height), lowRight = new b2Vec2(width, height), upRight = new b2Vec2(width, 0) // Edges bounding the visible game area var edgeFixDef = new b2FixtureDef edgeFixDef.friction = 0.5 edgeFixDef.restitution = 0.2 edgeFixDef.shape = new b2PolygonShape var edgeBodyDef = new b2BodyDef; edgeBodyDef.type = b2Body.b2_staticBody edgeFixDef.shape.SetAsEdge(upLeft, lowLeft) world.CreateBody(edgeBodyDef).CreateFixture(edgeFixDef) edgeFixDef.shape.SetAsEdge(lowLeft, lowRight) world.CreateBody(edgeBodyDef).CreateFixture(edgeFixDef) edgeFixDef.shape.SetAsEdge(lowRight, upRight) world.CreateBody(edgeBodyDef).CreateFixture(edgeFixDef) edgeFixDef.shape.SetAsEdge(upRight, upLeft) world.CreateBody(edgeBodyDef).CreateFixture(edgeFixDef) Can box2d really become this slow for even two bodies or is there some pitfall? It would be very surprising given all the demos which successfully use tens of objects.

  Read the article

• Am I right about the differences between Floyd-Warshall, Dijkstra's and Bellman-Ford algorithms?

  - by Programming Noob

  I've been studying the three and I'm stating my inferences from them below. Could someone tell me if I have understood them accurately enough or not? Thank you. Dijkstra's algorithm is used only when you have a single source and you want to know the smallest path from one node to another, but fails in cases like this Floyd-Warshall's algorithm is used when any of all the nodes can be a source, so you want the shortest distance to reach any destination node from any source node. This only fails when there are negative cycles (this is the most important one. I mean, this is the one I'm least sure about:) 3.Bellman-Ford is used like Dijkstra's, when there is only one source. This can handle negative weights and its working is the same as Floyd-Warshall's except for one source, right? If you need to have a look, the corresponding algorithms are (courtesy Wikipedia): Bellman-Ford: 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 u.distance + uv.weight < v.distance: 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 u.distance + uv.weight < v.distance: error "Graph contains a negative-weight cycle" Dijkstra: 1 function Dijkstra(Graph, source): 2 for each vertex v in Graph: // Initializations 3 dist[v] := infinity ; // Unknown distance function from 4 // source to v 5 previous[v] := undefined ; // Previous node in optimal path 6 // from source 7 8 dist[source] := 0 ; // Distance from source to source 9 Q := the set of all nodes in Graph ; // All nodes in the graph are 10 // unoptimized - thus are in Q 11 while Q is not empty: // The main loop 12 u := vertex in Q with smallest distance in dist[] ; // Start node in first case 13 if dist[u] = infinity: 14 break ; // all remaining vertices are 15 // inaccessible from source 16 17 remove u from Q ; 18 for each neighbor v of u: // where v has not yet been 19 removed from Q. 20 alt := dist[u] + dist_between(u, v) ; 21 if alt < dist[v]: // Relax (u,v,a) 22 dist[v] := alt ; 23 previous[v] := u ; 24 decrease-key v in Q; // Reorder v in the Queue 25 return dist; Floyd-Warshall: 1 /* Assume a function edgeCost(i,j) which returns the cost of the edge from i to j 2 (infinity if there is none). 3 Also assume that n is the number of vertices and edgeCost(i,i) = 0 4 */ 5 6 int path[][]; 7 /* A 2-dimensional matrix. At each step in the algorithm, path[i][j] is the shortest path 8 from i to j using intermediate vertices (1..k-1). Each path[i][j] is initialized to 9 edgeCost(i,j). 10 */ 11 12 procedure FloydWarshall () 13 for k := 1 to n 14 for i := 1 to n 15 for j := 1 to n 16 path[i][j] = min ( path[i][j], path[i][k]+path[k][j] );

  Read the article

• Tile Collision & Sliding against tiles

  - by Devin Rawlek

  I have a tile based map with a top down camera. My sprite stops moving when he collides with a wall in any of the four directions however I am trying to get the sprite to slide along the wall if more than one directional key is pressed after being stopped. Tiles are set to 32 x 32. Here is my code; // Gets Tile Player Is Standing On var splatterTileX = (int)player.Position.X / Engine.TileWidth; var splatterTileY = (int)player.Position.Y / Engine.TileHeight; // Foreach Layer In World Splatter Map Layers foreach (var layer in WorldSplatterTileMapLayers) { // If Sprite Is Not On Any Edges if (splatterTileX < layer.Width - 1 && splatterTileX > 0 && splatterTileY < layer.Height - 1 && splatterTileY > 0) { tileN = layer.GetTile(splatterTileX, splatterTileY - 1); // North tileNE = layer.GetTile(splatterTileX + 1, splatterTileY - 1); // North-East tileE = layer.GetTile(splatterTileX + 1, splatterTileY); // East tileSE = layer.GetTile(splatterTileX + 1, splatterTileY + 1); // South-East tileS = layer.GetTile(splatterTileX, splatterTileY + 1); // South tileSW = layer.GetTile(splatterTileX - 1, splatterTileY + 1); // South-West tileW = layer.GetTile(splatterTileX - 1, splatterTileY); // West tileNW = layer.GetTile(splatterTileX - 1, splatterTileY - 1); // North-West } // If Sprite Is Not On Any X Edges And Is On -Y Edge if (splatterTileX < layer.Width - 1 && splatterTileX > 0 && splatterTileY == 0) { tileE = layer.GetTile(splatterTileX + 1, splatterTileY); // East tileSE = layer.GetTile(splatterTileX + 1, splatterTileY + 1); // South-East tileS = layer.GetTile(splatterTileX, splatterTileY + 1); // South tileSW = layer.GetTile(splatterTileX - 1, splatterTileY + 1); // South-West tileW = layer.GetTile(splatterTileX - 1, splatterTileY); // West } // If Sprite Is On +X And -Y Edges if (splatterTileX == layer.Width - 1 && splatterTileY == 0) { tileS = layer.GetTile(splatterTileX, splatterTileY + 1); // South tileSW = layer.GetTile(splatterTileX - 1, splatterTileY + 1); // South-West tileW = layer.GetTile(splatterTileX - 1, splatterTileY); // West } // If Sprite Is On +X Edge And Y Is Not On Any Edge if (splatterTileX == layer.Width - 1 && splatterTileY < layer.Height - 1 && splatterTileY > 0) { tileS = layer.GetTile(splatterTileX, splatterTileY + 1); // South tileSW = layer.GetTile(splatterTileX - 1, splatterTileY + 1); // South-West tileW = layer.GetTile(splatterTileX - 1, splatterTileY); // West tileNW = layer.GetTile(splatterTileX - 1, splatterTileY - 1); // North-West tileN = layer.GetTile(splatterTileX, splatterTileY - 1); // North } // If Sprite Is On +X And +Y Edges if (splatterTileX == layer.Width - 1 && splatterTileY == layer.Height - 1) { tileW = layer.GetTile(splatterTileX - 1, splatterTileY); // West tileNW = layer.GetTile(splatterTileX - 1, splatterTileY - 1); // North-West tileN = layer.GetTile(splatterTileX, splatterTileY - 1); // North } // If Sprite Is Not On Any X Edges And Is On +Y Edge if (splatterTileX < (layer.Width - 1) && splatterTileX > 0 && splatterTileY == layer.Height - 1) { tileW = layer.GetTile(splatterTileX - 1, splatterTileY); // West tileNW = layer.GetTile(splatterTileX - 1, splatterTileY - 1); // North-West tileN = layer.GetTile(splatterTileX, splatterTileY - 1); // North tileNE = layer.GetTile(splatterTileX + 1, splatterTileY - 1); // North-East tileE = layer.GetTile(splatterTileX + 1, splatterTileY); // East } // If Sprite Is On -X And +Y Edges if (splatterTileX == 0 && splatterTileY == layer.Height - 1) { tileN = layer.GetTile(splatterTileX, splatterTileY - 1); // North tileNE = layer.GetTile(splatterTileX + 1, splatterTileY - 1); // North-East tileE = layer.GetTile(splatterTileX + 1, splatterTileY); // East } // If Sprite Is On -X Edge And Y Is Not On Any Edges if (splatterTileX == 0 && splatterTileY < (layer.Height - 1) && splatterTileY > 0) { tileN = layer.GetTile(splatterTileX, splatterTileY - 1); // North tileNE = layer.GetTile(splatterTileX + 1, splatterTileY - 1); // North-East tileE = layer.GetTile(splatterTileX + 1, splatterTileY); // East tileSE = layer.GetTile(splatterTileX + 1, splatterTileY + 1); // South-East tileS = layer.GetTile(splatterTileX, splatterTileY + 1); // South } // If Sprite Is In The Top Left Corner if (splatterTileX == 0 && splatterTileY == 0) { tileE = layer.GetTile(splatterTileX + 1, splatterTileY); // East tileSE = layer.GetTile(splatterTileX + 1, splatterTileY + 1); // South-East tileS = layer.GetTile(splatterTileX, splatterTileY + 1); // South } // Creates A New Rectangle For TileN tileN.TileRectangle = new Rectangle(splatterTileX * Engine.TileWidth, (splatterTileY - 1) * Engine.TileHeight, Engine.TileWidth, Engine.TileHeight); // Tile Collision Detection Between Player Rectangle And N Tile var tileNCollision = player.Rectangle.Intersects(tileN.TileRectangle); // Creates A New Rectangle For TileNE tileNE.TileRectangle = new Rectangle((splatterTileX + 1) * Engine.TileWidth, (splatterTileY - 1) * Engine.TileHeight, Engine.TileWidth, Engine.TileHeight); // Tile Collision Detection Between Player Rectangle And NE Tile var tileNECollision = player.Rectangle.Intersects(tileNE.TileRectangle); // Creates A New Rectangle For TileE tileE.TileRectangle = new Rectangle((splatterTileX + 1) * Engine.TileWidth, splatterTileY * Engine.TileHeight, Engine.TileWidth, Engine.TileHeight); // Tile Collision Detection Between Player Rectangle And E Tile var tileECollision = player.Rectangle.Intersects(tileE.TileRectangle); // Creates A New Rectangle For TileSE tileSE.TileRectangle = new Rectangle((splatterTileX + 1) * Engine.TileWidth, (splatterTileY + 1) * Engine.TileHeight, Engine.TileWidth, Engine.TileHeight); // Tile Collision Detection Between Player Rectangle And SE Tile var tileSECollision = player.Rectangle.Intersects(tileSE.TileRectangle); // Creates A New Rectangle For TileS tileS.TileRectangle = new Rectangle(splatterTileX * Engine.TileWidth, (splatterTileY + 1) * Engine.TileHeight, Engine.TileWidth, Engine.TileHeight); // Tile Collision Detection Between Player Rectangle And S Tile var tileSCollision = player.Rectangle.Intersects(tileS.TileRectangle); // Creates A New Rectangle For TileSW tileSW.TileRectangle = new Rectangle((splatterTileX - 1) * Engine.TileWidth, (splatterTileY + 1) * Engine.TileHeight, Engine.TileWidth, Engine.TileHeight); // Tile Collision Detection Between Player Rectangle And SW Tile var tileSWCollision = player.Rectangle.Intersects(tileSW.TileRectangle); // Creates A New Rectangle For TileW tileW.TileRectangle = new Rectangle((splatterTileX - 1) * Engine.TileWidth, splatterTileY * Engine.TileHeight, Engine.TileWidth, Engine.TileHeight); // Tile Collision Detection Between Player Rectangle And Current Tile var tileWCollision = player.Rectangle.Intersects(tileW.TileRectangle); // Creates A New Rectangle For TileNW tileNW.TileRectangle = new Rectangle((splatterTileX - 1) * Engine.TileWidth, (splatterTileY - 1) * Engine.TileHeight, Engine.TileWidth, Engine.TileHeight); // Tile Collision Detection Between Player Rectangle And Current Tile var tileNWCollision = player.Rectangle.Intersects(tileNW.TileRectangle); // Allow Sprite To Occupy More Than One Tile if (tileNCollision && tileN.TileBlocked == false) { tileN.TileOccupied = true; } if (tileECollision && tileE.TileBlocked == false) { tileE.TileOccupied = true; } if (tileSCollision && tileS.TileBlocked == false) { tileS.TileOccupied = true; } if (tileWCollision && tileW.TileBlocked == false) { tileW.TileOccupied = true; } // Player Up if (keyState.IsKeyDown(Keys.W) || (gamePadOneState.DPad.Up == ButtonState.Pressed)) { player.CurrentAnimation = AnimationKey.Up; if (tileN.TileOccupied == false) { if (tileNWCollision && tileNW.TileBlocked || tileNCollision && tileN.TileBlocked || tileNECollision && tileNE.TileBlocked) { playerMotion.Y = 0; } else playerMotion.Y = -1; } else if (tileN.TileOccupied) { if (tileNWCollision && tileNW.TileBlocked || tileNECollision && tileNE.TileBlocked) { playerMotion.Y = 0; } else playerMotion.Y = -1; } } // Player Down if (keyState.IsKeyDown(Keys.S) || (gamePadOneState.DPad.Down == ButtonState.Pressed)) { player.CurrentAnimation = AnimationKey.Down; // Check Collision With Tiles if (tileS.TileOccupied == false) { if (tileSWCollision && tileSW.TileBlocked || tileSCollision && tileS.TileBlocked || tileSECollision && tileSE.TileBlocked) { playerMotion.Y = 0; } else playerMotion.Y = 1; } else if (tileS.TileOccupied) { if (tileSWCollision && tileSW.TileBlocked || tileSECollision && tileSE.TileBlocked) { playerMotion.Y = 0; } else playerMotion.Y = 1; } } // Player Left if (keyState.IsKeyDown(Keys.A) || (gamePadOneState.DPad.Left == ButtonState.Pressed)) { player.CurrentAnimation = AnimationKey.Left; if (tileW.TileOccupied == false) { if (tileNWCollision && tileNW.TileBlocked || tileWCollision && tileW.TileBlocked || tileSWCollision && tileSW.TileBlocked) { playerMotion.X = 0; } else playerMotion.X = -1; } else if (tileW.TileOccupied) { if (tileNWCollision && tileNW.TileBlocked || tileSWCollision && tileSW.TileBlocked) { playerMotion.X = 0; } else playerMotion.X = -1; } } // Player Right if (keyState.IsKeyDown(Keys.D) || (gamePadOneState.DPad.Right == ButtonState.Pressed)) { player.CurrentAnimation = AnimationKey.Right; if (tileE.TileOccupied == false) { if (tileNECollision && tileNE.TileBlocked || tileECollision && tileE.TileBlocked || tileSECollision && tileSE.TileBlocked) { playerMotion.X = 0; } else playerMotion.X = 1; } else if (tileE.TileOccupied) { if (tileNECollision && tileNE.TileBlocked || tileSECollision && tileSE.TileBlocked) { playerMotion.X = 0; } else playerMotion.X = 1; } } I have my tile detection setup so the 8 tiles around the sprite are the only ones detected. The collision variable is true if the sprites rectangle intersects with one of the detected tiles. The sprites origin is centered at 16, 16 on the image so whenever this point goes over to the next tile it calls the surrounding tiles. I am trying to have collision detection like in the game Secret of Mana. If I remove the diagonal checks the sprite will pass through thoses tiles because whichever tile the sprites origin is on will be the detection center. So if the sprite is near the edge of the tile and then goes up it looks like half the sprite is walking through the wall. Is there a way for the detection to occur for each tile the sprite's rectangle touches?

  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

• How to iterate properly across a const set?

  - by Jared

  I'm working on a program that's supposed to represent a graph. My issue is in my printAdjacencyList function. Basically, I have a Graph ADT that has a member variable "nodes", which is a map of the nodes of that graph. Each Node has a set of Edge* to the edges it is connected to. I'm trying to iterate across each node in the graph and each edge of a node. void MyGraph::printAdjacencyList() { std::map<std::string, MyNode*>::iterator mit; std::set<MyEdge*>::iterator sit; for (mit = nodes.begin(); mit != nodes.end(); mit++ ) { std::cout << mit->first << ": {"; const std::set<MyEdge*> edges = mit->second->getEdges(); for (sit = edges.begin(); sit != edges.end(); sit++) { std::pair<MyNode*, MyNode*> edgeNodes = *sit->getEndpoints(); } } std::cout << " }" << std::endl; } getEdges is declared as: const std::set<MyEdge*>& getEdges() { return edges; }; and get Endpoints is declared as: const std::pair<MyNode*, MyNode*>& getEndpoints() { return nodes; }; The compiler error I'm getting is: MyGraph.cpp:63: error: request for member `getEndpoints' in `*(&sit)->std::_Rb_tree_const_iterator<_Tp>::operator-> [with _Tp = MyEdge*]()', which is of non-class type `MyEdge* const' MyGraph.cpp:63: warning: unused variable 'edgeNodes' I have figured out that this probably means I'm misusing const somewhere, but I can't figure out where for the life of me. Any information would be appreciated. Thanks!

  Read the article

• Creating an adjacency List for DFS

  - by user200081

  I'm having trouble creating a Depth First Search for my program. So far I have a class of edges and a class of regions. I want to store all the connected edges inside one node of my region. I can tell if something is connected by the getKey() function I have already implemented. If two edges have the same key, then they are connected. For the next region, I want to store another set of connected edges inside that region, etc etc. However, I am not fully understanding DFS and I'm having some trouble implementing it. I'm not sure when/where to call DFS again. Any help would be appreciated! class edge { private: int source, destination, length; int key; edge *next; public: getKey(){ return key; } } class region { edge *data; edge *next; region() { data = new edge(); next = NULL; } }; void runDFS(int i, edge **edge, int a) { region *head = new region(); aa[i]->visited == true;//mark the first vertex as true for(int v = 0; v < a; v++) { if(tem->edge[i].getKey() == tem->edge[v].getKey()) //if the edges of the vertex have the same root { if(head->data == NULL) { head->data = aa[i]; head->data->next == NULL; } //create an edge if(head->data) { head->data->next = aa[i]; head->data->next->next == NULL; }//if there is already a node connected to ti } if(aa[v]->visited == false) runDFS(v, edge, a); //call the DFS again } //for loop }

  Read the article

• Clustered Graphs Visualization Techniques

  - by jameszhao00

  I need to visualize a relatively large graph (6K nodes, 8K edges) that has the following properties: Distinct Clusters. Approximately 50-100 Nodes per cluster and moderate interconnectivity at the cluster level Minimal (5-10 inter-cluster edges per cluster) interconnectivity between clusters Let global edge overlap = The edge overlaps caused by directly visualizing a graph of Clusters = {A, B, C, D, E}, Edges = {Pentagram of those clusters, which is non-planar by the way and will definitely generate edge overlap if you draw it out directly} Let Local Edge Overlap = the above but { A, B, C, D, E } are just nodes. I need to visualize graphs with the above in a way that satisfies the following requirements No global edge overlap (i.e. edge overlaps caused by inter-cluster properties is not okay) Local edge overlap within a cluster is fine Anyone have thoughts on how to best visualize a graph with the requirements above? One solution I've come up with to deal with the global edge overlap is to make sure a cluster A can only have a max of 1 direct edge to another cluster (B) during visualization. Any additional inter-cluster edges between cluster A - C, A - D, ... are disconnected and additional node/edges A - A_C, C - C_A, A - A_D, D - D_A... are created. Anyone have any thoughts?

  Read the article

• looking for dark, high contrast theme

  - by d3pd

  I am looking for a dark, contrast theme. Most dark, high-contrast themes I have tried do not give sufficient contrast to many edges, such as the edges of buttons, tabs, windows and other borders. Could you recommend themes that would provide such features? Alternatively, could you recommend a guide to changing a fairly dark theme, such as Numix-Cyanogen, such that it would feature light button, tab, window and other borders? Roughly visually, what I mean is to from this: to something like this:

  Read the article

• Calculate geometric mean in Excel

  - by Libby

  I have some email network data in Excel as a edgelist meaning I have columns Vertex1, Vertex2, and then N columns of properties of that edge like how many emails were sent from one person to another. For each row in the data, Vertex1 is the source of a message, and Vertex2 is the target, so edges are directed. Here's some sample data Vertex1 Vertex2 nMessages Bob Cindy 12 Cindy Bob 3 Bob Mike 11 Cindy Mike 1 I'm trying to calculate a geometric mean of the form gm = sqrt[(# of edges ij)*(# of edges ji)] So gm for Bob and Cindy is gm = sqrt[(messages from Bob to Cindy)*(messages from Cindy to Bob)] or sqrt(12*3) = 6. Is there a way to make that a formula in Excel?

  Read the article

• Algorithm to infer tag hierarchy

  - by Tom

  I'm looking for an algorithm to infer a hierarchy from a set of tagged items. E.g. if the following items have the tags: 1 a 2 a,b 3 a,c 4 a,c,e 5 a,b 6 a,c 7 d 8 d,f Then I can construct an undirected graph (or graphs) by tallying the node weights and edge weights: node weights edge weights a 6 a-b 2 b 2 a-c 3 c 3 c-e 1 d 2 a-e 1 <-- this edge is parallel to a-c and c-e and not wanted e 1 d-f 1 f 1 The first problem is how to drop any redundant edges to get to the simplified graph? Note that it's only appropriate to remove that redundant a-e edge in this case because something is tagged as a-c-e, if that wasn't the case and the tag was a-e, that edge would have to remain. I suspect that means the removal of edges can only happen during the construction of the graph, not after everything has been tallied up. What I'd then like to do is identify the direction of the edges to create a directed graph (or graphs) and pick out root nodes to hopefully create a tree (or trees): trees a d // \\ | b c f \ e It seems like it could be a string algorithm - longest common subsequences/prefixes - or a tree/graph algorithm, but I am a little stuck since I don't know the correct terminology to search for it.

  Read the article

• Why isn't one of the constant buffers being loaded inside the shader?

  - by Paul Ske

  I however got the model to load under tessellation; only problem is that one of the constant buffers aren't actually updating the shader's tessellation factor inside the hullshader. I created a messagebox at the rendering point so I know for sure the tessellation factor is assigned to the dynamic constant buffer. Inside the shader code where it says .Edges[1] = tessellationAmount; the tessellationAmount is suppose to be sent from the dynamic buffer to the shader. Otherwise it's just a plain box. In better explanation; there's a matrixBuffer, cameraBuffer, TessellationBuffer for constant. There's a multiBuffer array that assigns the matrix, camera, tesselation. So, when I set the Hull Shader, PixelShader, VertexShader, DomainShader it gets assigned by the multibuffer. E.G. devcon-HSSetConstantBuffers(0,3,multibuffer); The only way around the whole ideal would be to go in the shader and change how much the edges tessellate and inside the edges as well with the same number. My question is why wouldn't the tessellationBuffer not work in the shader?

  Read the article

< Previous Page | 1 2 3 4 5 6 7 8 9 10 11 12  | Next Page >