Graph Algorithms are a sequence of well-defined steps that will solve a problem related to Graph Theory, where a Graph in this context is a collection of vertices ("nodes") and edges that connect these vertices.
0
votes
0answers
8 views
Graph Traversal Algorithm with discount
I have a directed graph with weighted edges and I would like to find the all pairs shortest paths in my graph. But I want to be able to take discounts into consideration.
For example:
A->B ...
0
votes
1answer
20 views
Understanding A* Search on Tropical Island
I am working on an online MOOC on AI and I am now working to understand A* better.
Basically, right now I am working on a problem where: we live on a tropical island and we're trying to navigate ...
-3
votes
0answers
41 views
flow network algorithm: Professor Gore wants to open up an algorithmic consulting company
Professor Gore wants to open up an algorithmic consulting company. He has identified n important subareas of algorithms (roughly corresponding to different portions of this textbook), which he ...
0
votes
0answers
12 views
How to model a Directed Acyclic Graph if two nodes have same precedence relationship?
I need help with this problem that I'm currently working on, which involves finding a cycle in topological sort.
I need to construct a DAG for the following scenario:
Assume that there are any ...
1
vote
1answer
18 views
Graph generation tool
Is there a free tool out there that would allow me to generate a directed/undirected weighted graph?
I'm thinking about something that I can draw the graph on some sort of canvas and then save it in ...
0
votes
0answers
43 views
Loop in a dynamic shuffling list
Here is the case: Given two lists [A,B,C,D] and [Ob,Od,Oa,Oc] (Object O has a parameter A,B,C or D)
The first listed was sorted according to a specific condition (if A was a product, it's the ...
0
votes
0answers
38 views
Introducing correlations in the adjacency (or connectivity ) matrix
I am trying to build an adjacency matrix with correlation. i.e The probability of connection from node A to node B is set to a constant factor of order 1 (say α ), if node B is connected to node A. I ...
0
votes
1answer
37 views
How to find a minimal set of routes to visit all nodes in a graph from a given set of routes?
From a given graph, not necessarily connected, and a set of paths, where each path visit a set of nodes in the graph. And the nodes visited by two different paths may or may not be exclusive.
With ...
0
votes
1answer
28 views
0
votes
1answer
39 views
Finding path from cell x to cell y in a grid so that all cells are parsed once
I am trying to code an algorithm so that it can start from any "start" cell of a grid ( eg.cell no. 4 in the pic) and parse through each cell of a grid once. The grid can be of any size 3x3, 4x4, 8x8 ...
0
votes
0answers
33 views
Using my own force-directed algorithm with Networkx
I'm trying to get a force directed algorithm working that I'm writing. I'm not using one that comes with Networkx because we want to later modify it for our own purposes. Currently when I run it, I ...
-2
votes
1answer
29 views
Approach with Magical Bridges
I'm trying to solve http://www.spoj.com/problems/AMR11F/ .
Hogwarts School of Witchcraft and Wizardry has a circular lane having
N towers numbered 1 to N. Towers i and i+1 are adjacent to each ...
-1
votes
0answers
48 views
Java very slow execution of A* Pathfinding Algorithm
I am creating a Maze game in java and wants to add a smarty ghost (like Pacman) that move towards user location to catch him. For smarty ghost I chose A* PathFinding Algorithm and found below links ...
android
6
votes
1answer
131 views
How can I find a way to minimum the number of edges?
I am thinking an algorithm to solve the problem below:
A given graph composed of vertices and edges.
There are N customers who want to travel from a vertex to another vertex.
And each ...
0
votes
1answer
78 views
A* Pathfinding java not working properly [closed]
I am creating a Maze game in java and wants to add a smarty ghost (like Pacman) that move towards user location to catch him. For smarty ghost I chose A* PathFinding Algorithm and found below links ...
0
votes
2answers
74 views
Matching Algorithm in Javascript
I'm looking for an implementation of the Blossom algorithm for JavaScript or something similar.
I have a set of pairs
A - B
A - C
B - D
and I need to pick pairs, assuming that each letter can ...
0
votes
1answer
36 views
BFS (Breadth First Search) Time complexity at every step
BFS(G,s)
1 for each vertex u ∈ G.V-{s}
2 u.color = WHITE
3 u.d = ∞
4 u.π = NIL
5 s.color = GRAY
6 s.d = 0
7 s.π = NIL
8 Q ≠ Ø
9 ENQUEUE(Q, s)
10 while Q ≠ Ø
11 u = ...
0
votes
2answers
54 views
Sentence ranking algorithms based on importance to the document
Given any document, what are some algorithms to rank each sentence in it based on it's importance to the document? An important sentence would be one whose removal drastically changes the meaning ...
0
votes
0answers
19 views
graph cut, cutting at least half the edges
Can anyone help me find a greedy algorithm that find a cut in a graph with at least half the edges?
I think the right way has something to do with separating vertexes using DFS, but I am not sure.
1
vote
0answers
57 views
Get the best route between two dirrent paths in wp8
I have created a bus transit application for a city in windows phone 8. I have stored all my routes and bus stops in a separate table in the database.
My bus stop table contains:
stop_id | ...
0
votes
1answer
32 views
Neo4j Hamiltonian path (TSP)
Being a newbie with graphs, I'm looking whether it's possible to use Neo4j to calculate an optimal route which passes through all entered waypoints (distances are weights of the edges).
I'm familiar ...
0
votes
1answer
50 views
Find Checkboxes and the State in the Image (Jpg or Png) C#
Hi I have a list of scanned images (Survey) which contains check boxes.
I need to find all the checkboxes in the image and I need to find whether the checkbox checked or not.
Please advise me. I ...
2
votes
3answers
85 views
Path with least maximum edge weight
Let's say we have a directed non-negative-weighted graph.
We have to find the least cost path between (u, v).
The cost of a path is defined as the maximum cost of the second most expensive edge that ...
0
votes
1answer
86 views
Dijkstra's (or other shortest path algorithm) where end node can be start node
The traditional* implementation of Dijkstra's does not handle this case well. I think I've come up with some solutions that will work, but they are not particularly elegant**. Is this is a known ...
0
votes
0answers
19 views
Find edges connected to a source node in a graph
I have a java SortedSet which contains edges of a directed graph. Each element of the SortedSet is a 2 element list , first is the source node and second is the destination node. Given a source node, ...
0
votes
2answers
77 views
Algorithm to find and print simple cycle in complexity of O(n) on undirected graph
Given graph G(V,E), un-directed graph.
|E| = m, |V| = n
The graph's data structure is Adjacency list
How to find and print simple cycle (or print that there is no such cycle) in complexity of ...
2
votes
1answer
51 views
path finding: calculating the optimal path, where “optimal” means maximum distance within a given time
Not sure if this is the right place to ask this, but here's my problem:
I have a large set of points, where each point represents a coordinate. I need to develop an algorithm that calculates which ...
0
votes
4answers
50 views
Traversing all descendants of an object
I'm having problems with traversing all descendants of an object.
The 'unit' in the code below is of type Unit in my program. It has a property ChildUnits which returns a List<Unit> of the ...
0
votes
1answer
48 views
How to create a graph and call the algorithm with this code
I've been trying to understand this code; it's an implementation of the push-relabel algorithm in C++:
// Adjacency list implementation of FIFO push relabel maximum flow
// with the gap relabeling ...
0
votes
2answers
20 views
How to remove path in tree starting from leaf?
I've got objects organized in a tree (not binary one). Every node has collection of its Children and Parent property. It is all presented in a TreeView already. I would like to click on the leaf and ...
0
votes
0answers
8 views
The Sleator and Tarjan's dynamic trees modification for the dinitz algorithm
I've been reading about the Dinitz (Dinic) max flow algorithm. it is said that by using special data structures -- namely, Sleator and Tarjan's dynamic trees -- the part where we find the blocking ...
3
votes
1answer
54 views
Shortest path between two vertices when exactly one edge weight can be reduced by 50%?
This is an interview question I came across:
You are given a the map of airplanes between the cities in a country, basically a directed graph was given with weights as the cost of planes between the ...
1
vote
2answers
52 views
Check if a word is combo of some given symbols
I have an array of symbols (not only characters, but also syllables, such as 'p', 'pa', etc.) and I'm trying to come up with a good algorithm to identify words that can be created by concatenating ...
0
votes
0answers
32 views
Graph theory - finding a fixed-length path that maximizes weight
Let there be a finite, directed, edge-weighted graph.
Given a start point and an exact length, I'd like to get a path that maximizes total sum of edge weights. The path does not need to be simple ...
0
votes
1answer
51 views
Is it a convention that the distance of a vertex to itself is 1?
I was reading this file, and on the 27th page, it has a pseudo code about determining if a vertex is a articulation point in a network.
In the code, the count is increased before it is saved in the d ...
0
votes
2answers
83 views
Implementing Packed bubble Graph in WinRT
How I can implement packed bubble graph in WinRT. I am trying to achieve graph similar to attached image..
I tried for a similar implementation / sample for silverlight / Windows 8 in google, But ...
0
votes
3answers
112 views
Looking for an algorithm for an efficient itinerary
Am wanting to write an app that helps say a travelling salesman / musician plan their tour.
So this is about making an efficient itinerary.
So they would put in their start and end points and the ...
0
votes
0answers
27 views
Constructon of a huffman tree
My task is the following:
Provide an example for the following:
A complete Huffmann tree with n=5, q=2, lengths l1,......,l5 and l1>l2>l3>l4.
(Draw the tree and give weights p1,...,p5 to the leaves ...
0
votes
1answer
99 views
Directed Acyclic Graph with multi-parent nodes
Given: A directed acyclic graph with weighted edges, where a node can have multiple parents.
Problem: For each child of root node, find a minimum-cost(sum of weights) path from such a child to some ...
1
vote
1answer
71 views
Calculate maximum profit under given path cost
Rooted Graph is given. Here, nodes is "home" that contains some valuable item. Entry node is given, i.e., root of the graph.
Cost is also given to move from one node to other, i.e., Egde weight.
...
1
vote
1answer
33 views
What is the neatest way to go from recursion to iteration when there is logic after the recursive call?
Say I had a method like the following where the call to tidy() had to be after the call to recurse():
void recurse(Node node)
{
foreach(Node child in node.children)
{
recurse(child);
...
0
votes
1answer
31 views
Graph partitioning optimization
The problem
I have a set of locations on a plane (actually they are pins in a KML file) and I want to partition this graph into subgraphs. Connectivity is pretty good - as with all real world road ...
0
votes
1answer
43 views
What is the most efficient way of analysing and identifing candle sticks?
A candlestick (chart), is a tool used for technical analysis of usually market movements. In a market or a specific equity:
open: opening price
close: closing price
high: highest price for the day
...
2
votes
3answers
82 views
What structure and algorithm use for building genealogy tree?
I found in one book, that for presenting genealogy (family) tree good to use DAG (directed acyclic graph) with topological sorting, but this algorithm is depending on order of input data.
0
votes
1answer
87 views
Triangulation: Find a 3D point minimizing the Distance from N 3D Lines/Rays
Given Multiple (N) lines in 3D space, find the 3D Point minimizing the distance to all lines using Least Squares.
How can I express this in Least Square Matrix Form? Thus, Having:
[A] - Variables ...
0
votes
1answer
46 views
Find minimum distance to visit set of disconnected routes
Let's say I have set of disconnected road routes, like in this example. Each route has Start and Finish points, which might be the same (if route is circular). Route can be "open" (different ...
google-maps
2
votes
3answers
124 views
Topological Sorting of a directed acyclic graph
How would you output all the possible topological sorts for a directed acyclic graph? For example, given a graph where V points to W and X, W points to Y and Z, and X points to Z:
V --> W --> Y
...
-1
votes
1answer
28 views
Is a Minheap with all operations in O(1) possible?
Dijkstra's algorithm can be used to find, in O(|V| log (|V|) + |E|), the shortest path from a node to any other node in a Graph G = (V, E), where V denotes vertices and E edges, together with a ...
0
votes
1answer
25 views
Path Algorithm: How to tell whether a path from A to B to A on a grid goes around anything?
I need to figure out if the path from A to B and back to A goes around anything.
Example:
The path here is APPPPPPBA. It goes around an X, so the result is TRUE.
XXXXXXXX
XPPPXXXX
XBXPXXXX
XAPPXXXX
...
0
votes
1answer
37 views
Relation between node to other nodes in a graph
I am simulating a system and in this system there are number of variables that affect each other. Despite what or how the effect is, I am presenting this as an undirected, weighted graph where ...
