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
2answers
1k views
Which Improvements can be done to AnyTime Weighted A* Algorithm?
Firstly , For those of your who dont know - Anytime Algorithm is an algorithm that get as input the amount of time it can run and it should give the best solution it can on that time.
Weighted A* is ...
0
votes
0answers
6 views
Determining if an undirected graph is a tree
I found that a depth-first approach that finds back edges is a solution. However, is there any other way to determine if a undirected graph is a tree?
More specifically, how would I use the notion of ...
1
vote
0answers
26 views
SPOJ Water solution, bfs implementation JAVA bug
Link to the problem
I'm a newby in such hard algorithms, but after ~30 hours i got the code below.
With small maps it works like this:
1
5 5
1 3 5 6 3
3 2 1 1 3
4 2 5 1 5
6 3 4 9 3
5 7 2 1 1
Output:...
4
votes
2answers
57 views
Accumulate values of “neigborhood” from edgelist with numpy
I have a undirected network where each node can be one of k types. For each node i, I need to calculate the number of neighbors that node i has of each type.
Right now I am representing the edges ...
1
vote
1answer
12 views
TSP Where Vertices Can be Visited Multiple Times
I am looking to solve a problem where I have a weighted directed graph and I must start at the origin, visit all vertices at least once and return to the origin in the shortest path possible. ...
1
vote
3answers
48 views
Traversing graph using while loop iteration
I am using cytoscape.js to create a graph.
I want to travel through the nodes (with direction), but only to those nodes who are connected with a edge that contains a specific value.
I have done it ...
1
vote
1answer
43 views
Algorithm for how to Split Large Area into Convex Polygons
I'm implementing the A* pathfinding algorithm into a grid based engine, but I'm wanting to create nodes in polygonal areas rather than just using the grid points.
There will be obstacles in the area,...
0
votes
0answers
53 views
Implementing partition refinement algorithm
I have some nodes and edges
nodes = [
{ id: 'n1', propositions: ['p'] },
{ id: 'n2', propositions: ['p'] },
{ id: 'n3', propositions: ['p'] }
];
edges = [
{ source: 'n1', target: 'n2' },
{ ...
0
votes
0answers
21 views
JAVA : Generating a valid Hamiltonian path
I have problem in formulating the algorithm for Hamiltonian path. I'm generating this path to be feed in as a initial path to TSP problem with greedy algorithm.
The generateValidTour() function ...
-3
votes
0answers
26 views
How to determine whether two graphs are isomorphic
My instructor told my class that we have to write a program that checks whether or not two graphs are isomorphic.
From reading on wikipedia Click here, two graphs are isomorphic if they are ...
0
votes
2answers
71 views
breadth first search optimisation in python
I was solving a problem related to breadth first search. I solved the problem but my solution took the longest time to solve (0.12 as compared to 0.01 and 0.02 done by others). The question is a ...
6
votes
2answers
57 views
What's the good of using 3 states for a vertex in DFS?
In the explanation of depth-first search (DFS) in Algorithms in a Nutshell (2nd edition), the author used 3 states for a vertex, say white(not visited), gray(has unvisited neighbors), black(visited).
...
-2
votes
1answer
44 views
Djikstra's Shortest path algorithm
I am learning Djikstra's and i have prepared the code below based on slightly different idea than Djikstra.
Now, In many of the websites, i have seen the use of Extract min and boolean array of ...
1
vote
0answers
31 views
Minimum number of changes that we need to make so that there will be only one island in matrix
A Matrix containing 0s and 1s is provided, all 0s are water and 1s are land. A group of connected 1s forms an island. If one change can convert one 0 to 1 then find out minimum number of changes that ...
4
votes
1answer
36 views
Discarding incoming nodes in a directed graph
I'd like to discard incoming nodes in a directed graph.
tl;dr (jump to section 3)
I have a graph on which I perform a BFS to remove all unrelated nodes (relative to a candidate edge).
1. Sample ...
1
vote
2answers
4k views
how can a breadth-first-search-tree include a cross-edge?
Well, I know that a breadth-first-search-tree of an undirected graph can't have a back edge. But I'm wondering how can it even have a cross-edge? I'm not able to image a spanning tree of a graph G ...
1
vote
2answers
40 views
Printing the shortest path in a directed graph
I have a directed, cyclic graph without weights. I want to find the shortest route between A and B (i.e. the one with the least hops).
This is the code i got so far:
path(A,B) :- walk(A,B,[]).
walk(...
1
vote
1answer
15 views
How do I find a cluster of POIs that contain all POIs that user selected (within a specified radius)?
I apologize for the convoluted title. Needless to say, I am running out of search keywords but haven't found anything I could study on the subject.
I am building a system where a user selects ...
3
votes
1answer
547 views
How to find maximum independent set of a directed acyclic graph?
Say we have a graph that is similar to a linked list (or a directed acyclic graph). An independent set consists of nodes that don't share edges with any other node in the set. If each node is weighted,...
0
votes
0answers
16 views
Minimize length of the shortest path by decreasing edge weights
I have an undirected weighted tree with N vertices. Weights are positive. The root of the tree is 1. I want to minimize the length of the longest path from vertex 1 by doing some operations. In one ...
0
votes
0answers
29 views
An algorithm, or code, to generate a (minimal) cycle basis in a directed graph?
I'm looking in to problems on non-weighted edge-labeled vertex-labeled directed graphs.
It would now be helpful to generate a cycle basis (preferably minimal, but possibly not required) of the ...
-2
votes
1answer
36 views
How to find total number of friends groups
I have a friendship graph as follows
I want to find all the possible group of friends. What is the best algorithm to find these grouping. For example in this graph , possible friendship groups are as ...
0
votes
1answer
17 views
build a path tree for URIs
I have a list of URIs for which I need to create a tree/object structure. For example here is the URIs
/api/abc/xyz/abc/cde
/api/xyz/abc/d3/d2
/api/abc/cde/d3/d2
/api/abc/cde/d1/d2
The result tree ...
2
votes
2answers
47 views
Count cycles of length 3 using DFS
Let G=(V,E) be an undirected graph. How can we count cycles of length 3 exactly once using following DFS:
DFS(G,s):
foreach v in V do
color[v] <- white; p[v] <- nil
DFS-Visit(s)
...
0
votes
1answer
39 views
Print routes from tickets
Today I encountered a question which I am not able to solve.
A frequent traveler collects all his travel tickets.
A ticket has only 2 attributes, Start Journey Location name and Destination Name. ...
0
votes
1answer
41 views
DFS count isolated nodes for articulation points
I have a graph and a starting node. I want to find how many nodes become isolated when I remove each node in the graph, for all nodes, using DFS.
For example, if I start on a fixed node 1, and remove ...
0
votes
0answers
23 views
How to join two graphs where each edge in the graph has a traversal cost associated to it
My question is similar to an existing one: http://math.stackexchange.com/questions/1691013/how-does-one-join-two-graphs-in-graph-theory
But I'm specifically wondering what would be the new edge's ...
0
votes
0answers
29 views
How do I find a tetris shape from a bitmask value over a matrix
I have a 7x5 matrix with several bitmask values, each corresponding to a particular Tetris piece uniquely colored and positioned over the 7x5 array. I need to get the position shape & name(1 out ...
0
votes
2answers
48 views
graph traversal in C [on hold]
I have to implement a backtracing algorithm in C which will emulate a hardware in purely software, and trace a single path from output of a system to the input pin, registering all the gates, their ...
0
votes
2answers
29 views
What is the solution path yielded by a DFS on this graph
Using a DFS on this graph, the nodes are visited in the following order(for more than one successor node, nodes are pushed to the "frontier" in alphabetical order):
S->A->E->D->F->G
Is that ...
0
votes
2answers
46 views
Find path in a graph between start and end twice
Given a weighted Directed Acyclic graph with positive weights find the path between given two nodes maximizing the weights and we are allowed to travel twice.
Means given start and end we can travel ...
1
vote
1answer
69 views
What is an Efficient Algorithm to find Graph Centroid?
Graph Centroid is a vertex at equal distance or at distance less than or equal (N/2) where N is the size of the connected components connected through this vertex?! [Needs Correction?!]
Here's a ...
-2
votes
0answers
22 views
I want a list of graph algorithms which are not implemented in Scala programming language, [closed]
I search out to much, but I did't get any site or link that give me answer so I need help in finding out algorithms that are not implemented in Scala yet.
Thank you!
0
votes
1answer
70 views
Is my subroutine correct for generating a random Barabasi-Albert graph? [closed]
I would like to generate a random Barabasi-Albert graph with 10,000 node, but my program is very slow. Can anybody help if my subroutine is correct or not? In my code ran1() is the standard random ...
0
votes
0answers
20 views
Implicit graph search algorithm for Java
Does anyone know a reasonable implementation of any implicit graph path search algorithm in Java?
In particular I would like to use one which could handle 4-regular weighed, implicit, finite graphs (...
2
votes
1answer
26 views
What's the purpose of having Grey color in DFS and BFS implementation in CLRS?
In implementation of DFS and BFS, CLRS authors distinguish 3 colors for each vertex -- grey, black and white. I understand that black and white signify whether node was visited or not. Why do we need ...
1
vote
2answers
110 views
How do I make my flood fill algorithm more efficient?
I have a flood fill function in my code that just returns a number on the cells filled. But it is excruciatingly slow, my A* pathfinding algorithm is exponentially faster than it. Here is the snippet:
...
0
votes
2answers
42 views
Knight's tour, count steps that takes to go from A to B
A knight is located in position (a,b) and needs to take the king located in (c,d). How can I:
A: Visualize the tour
B: Calculate the min steps needed to go from (a,b) to (c,d)
The implementation I'...
2
votes
3answers
16k views
Time Complexity of the Kruskal Algorithm?
I am calculating time complexity for kruskal algorithm like this (Please see the algorithm in the Image Attached)
T(n) = O(1) + O(V) + O(E log E) + O(V log V)
= O(E log E) + O(V log V)
as |E| &...
1
vote
0answers
30 views
Recursion: Children are being added to wrong parents in iterative deepening depth first search
.getSuccessorStates(node) returns the correct successor states (children). I have tested this method on its own using the graph provided in this problem. The problem lies when I add recursion to the ...
-1
votes
1answer
19 views
Check if some edge crosses some minimal cut
I am struggling with the following question (and solution actually):
Given G(V,E), a flow-network (capacities are integers), We denote the maximum-flow by f*. Check for an edge e if:
1. It ...
2
votes
3answers
4k views
What is time complexity of BFS depending on the representation of the graph?
I was wondering what is the time complexity of BFS, if I use:
an adjacency matrix
adjacency list
edge list
Is it same as their space complexity?
4
votes
3answers
2k views
Optimal solution for the “celebrity” algorithm
Among n persons,a "celebrity" is defined as someone
who is known by everyone but does not know anyone. The
problem is to identify the celebrity, if one exists, by asking the
question only of the form, ...
1
vote
1answer
32 views
Knight's Travails and Binary Search Tree
Here is some context if you're unfamiliar with Knight's Travails.
Your task is to build a function knight_moves that shows the simplest possible way to get from one square to another by outputting ...
131
votes
17answers
140k views
Finding all cycles in graph
How can I find (iterate over) ALL the cycles in a directed graph from/to a given node?
For example, I want something like this:
A->B->A
A->B->C->A
but not:
B->C->B
0
votes
1answer
22 views
Tree traversal get children of nodes and path to root
Let's say we have multiple nodes of a tree with different height.
Is there any efficient way to only get the children of the nodes and the path to the root?
This means we can get all nodes, lower than ...
17
votes
10answers
6k views
Check if the given string follows the given pattern
A friend of mine just had his interview at Google and got rejected because he couldn't give a solution to this question.
I have my own interview in a couple of days and can't seem to figure out a way ...
0
votes
1answer
75 views
algorithmic function to create all possible combinations from a list of vectors
I have a list of lists of int <List<List<int>> which represents a directional vector
for instance
(1,2)
(1,3)
(2,4)
(3,5)
(4,3)
(5,1)
and I want to create all possible routes with ...
5
votes
2answers
698 views
Inlining Algorithm
Does anyone know of any papers discussion inlining algorithms? And closely related, the relationship of parent-child graph to call graph.
Background: I have a compiler written in Ocaml which ...
0
votes
0answers
59 views
A* pathfinding not working with difficult obstacles
I recently started making A* pathfinder so I could have good AI in my game. I made a lot of progress and the pathfinder was ready in my opinion, but when I tried it, weird things happened. I made it ...
