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.
4
votes
0answers
142 views
Surface reconstruction from 2 planar contours
There is a class of algorithms for triangulation between two planar contours. These algorithms try to make a "good triangulation" to fill a space between these contours:
One of them (Optimal ...
4
votes
0answers
709 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 ...
4
votes
0answers
922 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 ...
3
votes
0answers
56 views
Tarjan's algorithm: do lowest-links have to be similar for two or more nodes to be inside the same SCC
I'm having some trouble with a homework question involving using Tarjan's algorithm on a provided graph to find the particular SCC's for that graph. While (according to my professor) I have found the ...
2
votes
0answers
128 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
334 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
137 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
498 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 ...
2
votes
0answers
202 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 ...
mongodb
1
vote
0answers
26 views
Find all paths in directed cyclic graph as regular expression
Let G = (V,E,r) a rooted directed graph, defined by a set of vertices V and a set of edges E with a designated root node r. The graph may contain cycles. The task: Given two vertices x and y from V, ...
1
vote
0answers
102 views
Gilmore-Lawler lower bound
Does anyone know how to implement or where can I find an implementation of Gilmore-Lawler lower bound for Quadratic Assignment Problem?
I've read several mathematics papers and the idea is to convert ...
1
vote
0answers
47 views
How travelling portals finds best routes from A to B?
I am really stuck on this, days are gone and I still can't even imagine, how it can be possible.
I am sure you know some travelling portals. You set source and destination and it prints possible ...
1
vote
0answers
50 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
252 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
79 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
134 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
116 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
84 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 ...
1
vote
0answers
133 views
Barnes-Hut force directed layout for Boost Graph library?
The default Fruchterman-Reingold algorithm that boost graph library uses for directed graphs takes O(n^2) time, is there any implementation of an O(n log n) layout algorithm like Barnes-Hut for Boost ...
1
vote
0answers
69 views
Is there a way to approximate the Laplacian matrix eigenvalues by using random walk like algorithm
It seems to me that many advanced graph analysis algorithm are based on spectral graph analysis, relying more specifically on the Laplacian matrix properties.
I know there are some alternative for ...
1
vote
0answers
169 views
Correlation Network Implementation
I have been working on my graph/network problem, and I think I finally know what I want to do. Now that I am getting into the implementation, I am having issues deciding what libraries to use. The ...
1
vote
0answers
117 views
Scotch/PT-Scotch graph vertex reordering for minimizing adjacency matrix bandwidth
Although the Scotch documentation is pretty clear it lacks examples of using the API. Even using Google for finding other third party documents, examples or tutorials is a dead end.
My problem is ...
1
vote
0answers
420 views
Find a vertex ordering of a finite graph G
I've tried to implement this algorithm in C++ but it has some problems. I need some advice how to get it work faster and propertly.
Algorithm
As Batagelj & Zaversnik (2003) describe, it is ...
1
vote
0answers
432 views
Java library for a clique cover of a graph
Does anyone know of a library (preferably Java) that solves the clique cover problem?
I found an OCaml version, but I would like to use something I can more easily integrate with.
I've also found ...
1
vote
0answers
477 views
Euler depth first search algorithm
I've coded a depth first search from a graph using euler algorithm of getting a cycle and splice subcicles into the result.
The problem is, to very large data, it isn't fast enough to find the ...
1
vote
0answers
321 views
edmond karps in Boost Graph Library
A part of my algorithm requires to compute maximum flow in a network with integer capacities. I want to use boost::edmonds_karp_max_flow algorithm to find the maximum flow.
I tried reading the ...
1
vote
0answers
590 views
Viterbi algorithm, unhardcode for general case Java
my task is to find the most probable sequences of words in a sentence using viterbi algorithm.
The given sequence of states is here:
I have to introduce initial probabilities and transition ...
0
votes
0answers
10 views
Iteration size Weighted Pagerank
I have implemented a PageRank algorithm in java correctly and want to adjust its weights.
But the problem is if the iteration size of PageRank is more than 3, changing the weights does not affect the ...
0
votes
0answers
18 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
0answers
20 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
0answers
30 views
Data structures in Clauset-Newman-Moore algorithm for finding community structure in networks?
I am trying to implement the Clauset-Newman-Moore algorithm for discovering community structure in python. The paper describing the algorithm is here:
...
0
votes
0answers
26 views
Basic python program error : NZEC
I have this basic program which computes the a sequence of names from a list such that the length of the sequence is maximized and the sequence contains only those names such that
for i,j in the ...
0
votes
0answers
23 views
printing next line in pre-ordered tree traversal
I have problems printing 2 and more nodes on the same line. The jsfiddle is here. Given the following code:
var s = '\
01001, Toyota, Corolla\
\n01002, Toyota, Prius, A\
\n01145, Toyota, Camry\
...
0
votes
0answers
28 views
algo of king graffs trol spoj
I was trying to solve http://www.spoj.com/problems/GRAFFTOL/ problem on SPOJ ,
As the problem states that there are two types of Queries:
Update cost of Town
Total cost of trip from Town x to Town ...
0
votes
0answers
58 views
Looking for DFS and BFS implementation in PHP giving a specific data structure
Giving a structure as follows:
$a = array(
array('id' => 1, 'name' => 'a', 'parentId' => 0),
array('id' => 2, 'name' => 'b', 'parentId' => 1),
array('id' => 3, 'name' ...
0
votes
0answers
28 views
Populating a Graph with Vertices?
I am in the process of planning a graph with Objective-C. I've organized my "Vertex" and "Edge" abstract data types and am starting work on the Graph implementation.
My question is, when one creates ...
0
votes
0answers
47 views
get nearest edge on mousemove in arborjs
I have a graph built on arbor.js, but the question is, how can I get the nearest edge from the mouse pointer. One function for getting nearest node is already there in renderer.js. The code for ...
0
votes
0answers
38 views
Algorithm to find ALL minimal dominating sets of a given small graph?
I understand that the graph dominating set is NP-hard, but I was wondering whether there is an algorithm (possibly approximate) to determine ALL possibly existing minimal dominating sets of a given ...
0
votes
0answers
43 views
Interview: Large graph dataset with limited memory
The interview question is:
Suppose we have a very large dataset like Freebase where compressed size is 22GB and uncompressed size is 250GB. We have 8GB RAM limit. What we need to do is, we need to ...
0
votes
0answers
32 views
How do you group data objects subject to several constraints?
I'm writing an application for a society in my campus and the main job of this application is to put members into groups subject to several
I need to determine the number of groups which depends on ...
0
votes
0answers
75 views
How to find path using BFS in corners search of Pacman search project
I am trying to solve this problem of the Berkley Pacman Search Project. The question states that I need to solve bfs problem first, and then only change the representation of goal state to solve the ...
0
votes
0answers
55 views
Graph Partitioning
Consider I have a graph containing 10,000 nodes. Now I want to look for a certain number of nodes in the graph. I want to achieve this with graph partition technique so that if a reasonable number of ...
0
votes
0answers
23 views
Determing Number of Permutations in A Rooted Tree
A safe is protected by a rather complicated passcode system. The passcode
entry system is arranged as a rooted tree of N (1 <= N <= 20,000) nodes,
each of which requires a digit between 0 and 9. ...
0
votes
0answers
35 views
Finding the Number of Positions to Satisfy a Configuration
You want a party complete with a laser light show. Unfortunately, the only working laser you have found is located far away from your house and too heavy to move, so you want
to re-direct the laser ...
0
votes
0answers
54 views
Updating a Prims algorithm for Minimum spanning trees
I need help doing a c++ or java method that prints a minimum spanning tree but also prints the minimum spanning tree without all of the vertices that are in the graph. So basically if the min span ...
0
votes
0answers
21 views
Convert class with Parent and Ordinal to class with SqlHierarchyId
Say we have a class:
public class RegularClass
{
public RegularClass Parent { get; set; }
public int Ordinal { get; set; }
public string Value { get; set; }
}
We want to store this in ...
0
votes
0answers
106 views
Java main thread terminates unexpectedly
I'm working on a maze-solving program (yeah, homework) and I'm running into a weird problem that I can't seem to figure out. Basically, the main thread just quits at the same point every time I run it ...
0
votes
0answers
50 views
Maze Path according to BFS (Breadth First Search)
I am trying to develop a program using BFS to find the path for pacman from source to destination, but i stuck at a point:
If the MAZE is:
P _ _ _ #
_ _ _ # _
_ _ F _ _
_ _ _ _ #
# # # # # ...
0
votes
0answers
32 views
Traversing CFG and calculating Running Average of Paths
I'm doing analysis on the LLVM machinecode CFG (CFG with Back-Edges removed), for each Instruction at the CFG I have attached at value (lets call it Cost), I would like to calculate the running ...
0
votes
0answers
41 views
How to visit all vertex in directed cyclic graph with the cheapst path?
I have a problem with traversal directed cyclic graph.
I was trying to look up all documents, textbooks and also papers. But I couldn't find exactly the same purpose.
What I'm looking for is the ...
