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.
3
votes
0answers
820 views
How do I auto-layout boxes on a flowchart?
I have some data that represents a flowchart. (A bunch of Jira statuses and their transitions to other statuses.)
I also have a crude way to position each flowchart item on an A4 page in an ...
2
votes
0answers
82 views
A* circular path finding algorithm with restrictions
I have a road map represented as a directed graph of junctions and links leading from one junction to another, each link is weighted with it's own traversal time (the time it takes to cross the link) ...
2
votes
0answers
190 views
Recursive best first search and finding the best path
In a Recursive Best-First Search, how would I modify it, to be able to track back the route?
Would I need to have a data structure that keeps track of which nodes are unwound after last recursion ...
2
votes
0answers
123 views
Meeting scheduling algorithm with Overlapping Time Slots
I want to do something similar to Appointment scheduling algorithm (N people with N free-busy slots, constraint-satisfaction). using Hopcroft-Karp Algorithm. But my additional requirement is that my ...
2
votes
0answers
106 views
Building multi child tree from list items
I have a input data structure like this:
{
{ {x1,y1,z1,p1}, {x1,y2,z1,p1}, {x1,y3,z1,p1}, {x1,y4,z1,p1} },
{ {x1,y1,z2,p2}, {x1,y2,z2,p2}, {x1,y3,z2,p2}, {x1,y4,z2,p2} },
{ {x1,y1,z3,p3}, ...
2
votes
0answers
421 views
Deleting element in Binary Search Tree (BST)
I have difficulties with deleting element from BST. This code is based on algorithm from Cormen's book. Here are two functions needed to delete element:
el *TreeSuccessor(el *x)
{
el *y;
if ...
1
vote
0answers
41 views
How is the supply/demand calculated?
In this Minimum Cost Flow tutorial given on TopCoder, the vertices of the graph had supply/demand values. How were they calculated? I couldn't figure out from the graph given.
1
vote
0answers
187 views
Python - Correctness of Iterative Deepening Implementation
I just finished a long project and I've been toying with adding in iterative deepening (this is not anything they asked us to do).
My implementation returns a path for really small graphs, but seems ...
1
vote
0answers
65 views
How to connect the neighborhood vertices
I have the number of vertices's having random position.Now i want to connect that vertices's to form the graph as shown in this figure ,this graph is based on neighborhood graph theory.I want to write ...
1
vote
0answers
104 views
detecting general pattern of local maxima in 1D Java array
I am trying to make a simple pitch detection application for an Android phone. I have gotten the phone to display a graph of the autocorrelation values I have computed, which are stored in a one ...
android
1
vote
0answers
94 views
What algorithms do you know for beltway reconstruction?
I've faced the beltway reconstruction problem and I've developed a simple backtrack algorithm, what algorithms do you know for this problem?
Beltway Reconstruction Problem:
Assume there is a set of ...
1
vote
0answers
284 views
Route planning in public transport application
I'm making a journey planner (or a general timetable application) for all the public transport in my country (bus/train/air).
The state of the project is at midpoint, now I'm having a bit of a hard ...
1
vote
0answers
138 views
Breadth-First Search for Six Degrees of Separation in mongodb
I have a video-game themed Six Degrees of Separation app and I want to know the best way to implement breadth-first search using node.js and MongoDB.
My app uses ...
1
vote
0answers
109 views
Given a Flow Network and an Edge e, Describe an Algorithm that Determines Whether e Crosses Some Minimum Cut
Given a flow network G = (V,E) with a source s, a sink t and and edge e = (u,v), describe an algorithm that determines whether the edge e crosses some minimum cut (S,T).
My first idea was to ...
1
vote
0answers
59 views
Directed or bi-directed and MSSP
Firstly i wanted to ask. If I have a undirected graph and split all the edges into two directed edges is it still called directed or it becomes bi-directed?
The main question is i have a graph with ...
