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
23 views
pythonw.exe has stopped working
I'm implementing Kosaraju’s two-pass algorithm that can calculate strongly connected components in a directed graph.
I can get the correct result with small input data, but when the input data is ...
1
vote
1answer
13 views
What is an algorithm to find the circuit with max weight in a directed graph?
First problem was that i couldn't find an algorithm that,given an directed graph as input, gives as output a list of all cycles present in the graph. (This problem should be NP-complete).
After ...
0
votes
1answer
11 views
Shortest way to find the focused point
I am writing an algorithm for auto focus. For that I am using a stepper motor which has 3318 steps for focus.
To find the focus, after every frame from the camera I am taking the statistics and ...
1
vote
1answer
52 views
Directed weighted graph shortest path with obligatory nodes to pass
Hello i'm trying to find the best algorithm to solve this problem.
I have a a graph that i must find the shortest path between Start and End node specified but that must pass on specific user input ...
-1
votes
0answers
58 views
Travelling salesman (TSP) in java with different starting and end destinations visiting all the nodes exactly once
I am looking for recommendation on which algorithm makes sense for my problem. I'll have 50-100 places in the given city/state with latitude and longitude, the target is to find an optimal way from ...
0
votes
0answers
33 views
Graph building algorithm given an infinite walk
I need help writing a resilient, mapping (graph building) algorithm. Here is the problem:
Imagine you have a text oriented virtual reality(TORG/MUD) where you can send movement commands (n, s, w, e, ...
0
votes
0answers
43 views
Choosing a particular route for a shuttle vehicle upon demand
I'm trying to solve a problem where I have no idea what algorithm is to be used here to get the optimized answer. The problem is like this...
Consider there are 10 shuttle vehicles and 2 different ...
4
votes
1answer
52 views
Computing a company's shareholders ownership percentage
I have a graph that contains two types of nodes: Companies and Persons.
A Company node has a list of edges that represent Shareholders. A Shareholder has a percentage of shares and is either a ...
0
votes
1answer
43 views
Finding right triangle coordinates in binary array
Say I have an MxN binary matrix. It is not necessarily sparse. I'm interested in finding the coordinates of the apexes of all of the right triangles in the array. By right triangle, I mean: pretend ...
0
votes
1answer
29 views
CTCI 4.3: Given a binary tree, design an algorithm which creates a linked list of all the nodes at each depth
I'm solving this problem with Ruby, and I used a modified DFS algorithm to do it. The idea is that, every time DFS has to look at adjacent nodes, then it's looking at the children and therefore that's ...
-3
votes
2answers
75 views
Floyd-Warshall algorithm - shortest path - save paths index to array
I'm implementing a Floyd-Warshall algorithm for symmetrical, undirected graph. At the moment, I have calculated the best path for each connection point. My problem is that I want to save index points ...
0
votes
4answers
48 views
defining a circle by algorithm
I've got a 100px*100px image
Gotta draw some filled circles with random position and radius.the problem is not the random stuff.
I just don't know the algorithm to define a circle with position(x,y) ...
1
vote
1answer
48 views
How many cells will have finite values
I encountered one programming question.
Consider I have N cells.These cells can have some integer value or expression.
There can be T number of iterations.In every iteration ,some cells can be ...
1
vote
1answer
38 views
Bellman-Ford Algorithm Space Complexity
I have been searching about Bellman-Ford Algorithm's space complexity but on wikipedia Bellman-Ford Algorithm and it says space complexity is O(V). on this link it says O(V^2) . My question is; what ...
1
vote
2answers
60 views
Why do I get same results directly within same run in second time without run random function in it in Python?
I write a KargerMinCut function in which I have written a random function in Python, but I get the same result within the same run. If I restart the function, different results printed.
Here's the ...
1
vote
1answer
39 views
How to solve this optimally?
I have a tree of n vertices n<=10^5 where each vertex has a score[i] and q queries q<=10^5
Each query has two parameters u and L, I need to find
sum(score[i]) for all i where lca(i,u)=u and ...
1
vote
1answer
24 views
Identifying paths between nodes on a graph, whilst finding potential loops
Lets say I have a graph like the following:
It is directed, and can also have cycles. If I wanted to find all the possible routes from node 0 to node 9, I have found that I could use a depth-first ...
1
vote
2answers
22 views
Longest Increasing Sub-sequence such that last-First element in LIS is maximum
How to find the difference between the last and first element of the longest increasing sub-sequence such that value of (last element - first element) in LIS is maximum ?
1
vote
0answers
25 views
How to output the top $k$ “diverse” strings from a set of $n$ strings
Suppose I am given n strings of equal length. I want to output a subset of them of size k such that they are as diverse as possible, for example, if n=3 and k=2
Strings: AAABC, AAACB, XYZWR
I would ...
0
votes
0answers
22 views
best way to maximum utilization of print sheet by placing irregular shape
I am developing the maximum utilization of print sheet since long days. I have learnt many things about this but I am not getting any suitable algorithm or sample project that will help me to make ...
0
votes
3answers
43 views
Changing the value of a Boolean Function in Python
I want to set the default value of a boolean function to be False and want to change it to True only for certain values of the input in between the code. Is there a way to do it?
I'm trying to write ...
0
votes
0answers
20 views
Representing very large road network
I need to create a (very large) graph to represent a real world road network. In this road network, I have about 20M road junctions and 25M roads. Some roads are one-way. In order to support long ...
0
votes
0answers
44 views
Understanding the minmax algorithm of tic-tac-toe (without recursion)
I'm trying to write a minimax algorithm for a tic-tac-toe at Python.
I don't need help with the code, just with the algorithm... :-)
I'm trying to do it without recursion, and to understand it better ...
1
vote
1answer
20 views
What is the correct vertex order of Prim algorithm from this graph?
I want to know the vertex order of the Prim algorithm from this graph:
My answer is {a,c,b,e,f,g,d}, but others said {a,c,b,e,d,f,g} or {a,c,d,e,b,f,g}.
Which answer is correct?
-2
votes
1answer
22 views
PageRank - How is a link defined?
I am trying to learn more about the PageRank algorithm. I have a task to implement a wikipedia search engine implementation using PageRank. I wanted to know how a links are defined. So if Page A has a ...
0
votes
0answers
23 views
Weighted A* versus A*
With the A8 and weighted A*(without allowing re-expansion of states) algorithms, will weighted A* never expand more states than regular A*?
Can you explain, the difference in expansion please(...
1
vote
1answer
37 views
Optimal clusterization
There is a graph (E,V). For each edge (i,j), there is a payment P[i,j] which may be positive, zero, or negative. We divide the vertices by clusters. Each time two neighbour vertices v1 and v2 belong ...
1
vote
1answer
45 views
Space complexity of BFS
Here is a code snippet from BFS implementation-
public static void findShortestReach(LinkedList<Integer>[] adjList,int start,int nodes)
{
int[] level=new int[nodes]; //keeps track of ...
0
votes
1answer
125 views
Shortest path in a grid collecting coins [closed]
It's holiday season. A mall is empty except of air, money, and a very clever thief that is you.
The mall consists of n floors. Each floor can be represented as a rectangular 2D grid. All floors have ...
0
votes
2answers
92 views
How can we find maximum spanning tree in complete graph
Given an array of n positive integers, how can we find maximum spanning tree in complete graph, considering weight of edge (i, j) = gcd(a[i], a[j])?
I know one solution with complexity O(n^2), but n&...
0
votes
3answers
39 views
Why does Kruskal's algorithm find the minimum spanning tree if it's greedy?
Why does Kruskal's algorithm find the minimum spanning tree if it's greedy? Isn't a minimum spanning tree a global optimization problem? Isn't the point of being greedy is that there is a chance you ...
3
votes
1answer
50 views
Assigning jobs to workers
There are N plumbers, and M jobs for them to do, where M > N in general.
If N > M then it's time for layoffs! :)
Properties of a job:
Each job should be performed in a certain time window which ...
1
vote
2answers
30 views
Do connected graphs with more than N-1 edges always contain connected graph with N-1 edges?
We know that:
If we have N vertices
To build a connected undirected graph, you'll need at least N-1 edges.
Let M be the set of possible connected undirected graphs with N-1 edges.
...
1
vote
1answer
27 views
Finding Min Distance From Start Node to Other Nodes in DFS Tree and Their Back Edges
The problem is this:
Find DFS and compute distance from start node to each of the other
nodes in the graph, assign each of the nodes v their distance from start node
Next find the min of each of the ...
1
vote
0answers
10 views
Difference between GAS model and BSP model
I know Pregel's graph computation framework is based on BSP and GraphLab is based on GAS. What is the difference between BSP and GAS? and Advantage and disadvantage of each one?
1
vote
1answer
55 views
Algorithm: How to re-arrange a time-range event (interval) list based on wether time events overlap, faster than O(n^2)?
Let's say I have an array of time ranges like so:
[
{ name: 'A', startTime: '10:15', endTime: '11:15'},
{ name: 'B', startTime: '10:45', endTime: '14:15'},
{ name: 'C', startTime: '15:35', ...
0
votes
0answers
29 views
How do I implement breadth first search for a graph using type string vectors?
okay, so I get the mechanics of what breadth first search is. The problem is, I cannot figure out what am I to use as an iterator for the adjacency list?
Here's a snippet of my class code:
class ...
1
vote
0answers
24 views
Partitioning with constraints of edge weighted graph
I have an edge weighted connected graph. It is not a directed one. My task is to remove a few edges so that the graph become divided into at least two half and the sum of weights of the removed edges ...
3
votes
3answers
80 views
Shortest path in graph where cost depends on the history of traversing
My goal is to find the shortest path (lowest cost) between given cities (vertices) connected with roads (edges).
Each road and each city has charge (cost) that has to be paid before entering that road/...
0
votes
0answers
24 views
jGraphT library for java
I'm trying to run Dijkstra's algorithm on a graph. I need to read a graph modelling language (gml file into my Graph, Vertex and Edges Data structures).
The gml file is somewhat like this
graph
[
...
1
vote
1answer
88 views
Shortest-path algorithm: multiple source, closest destination
Algorithms like the Bellman-Ford algorithm and Dijkstra's algorithm exist to find the shortest path from a single starting vertex on a graph to every other vertex. Their multiple source version can be ...
0
votes
1answer
29 views
Perform Group Action using MapReduce
I am trying to implement a sequential Graph Algorithm in MapReduce.
In this I have to perform Group Action. Please visit Wikipedia to understand what is a Group action.
Suppose I have groups {a1,...
0
votes
1answer
42 views
count paths from source to destination in a matrix moving in all 4 directions
Say, I have a matrix of size n*n and I want to traverse from 0,0 to n-1,n-1 if I'm allowed to move in all four directions - right,left,up and down. How do I find all paths using recursion.
Below is ...
3
votes
1answer
87 views
SHORTEST delivery time by 2 transporters
I am dealing with an algorithmic problem. I have a known graph algorithm with a single central node. The aim is to deliver goods from this central node to some other, specified nodes by TWO ...
0
votes
0answers
31 views
How to keep track of the depth of the search? Prolog
I'm having a problem finding a way to keep track of the depth of the search. I have a working algorithm that gives me a path, the number of visited and expanded states and guaranties that the search ...
2
votes
0answers
45 views
Which graph algorithm to solve this?
Given is a undirected, weighted Graph. Each Node is either a "city" or a "village"; nodes are connected via the edges (=roads).
I start at Node 1 and have to bring a message to all of the cities.
In ...
0
votes
0answers
51 views
Breadth First Search Implementation using adjacency matrix
I am trying to implement a work-around for this BFS algorithm from Coremen1.I am using adjacency matrix and queue.
Consider the following graph:
Adjacency list:
1->2
2->4->3
3->NULL
4->3
5->2
...
1
vote
0answers
52 views
Find all cycles in an undirected graph
I found a question on how to find cycle in an undirected graph. The solution to the problem was
bool dfs(int x)
{
state[x] = 1;
for(int j = 0; j < ls[x].size(); j++)
{
if(...
0
votes
1answer
28 views
Distributed topological sort algorithm
In my current project I have a large amount of data to be processed. The order of processing is important as there is a child/parent dependency in the data. At this point I'm building the dependency ...
0
votes
0answers
30 views
How to check whether person A is within N degrees of separation of person B using only in memory options
No databases, no multithreading/distributed systems, just a computer that can run code sychronously.
My theory is to use a Graph (an adjacency list) to represent the network of people. Then I would ...
