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
7 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
[
...
0
votes
0answers
10 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 ...
-1
votes
0answers
14 views
Minimum cost connected subdigraph
I have a weighted directed graph ,I need to build the minimum cost connected subgraph out of the this graph.So basically I need a subset of edges such that it is possible to reach any destination from ...
-3
votes
0answers
16 views
Reasoning behind comparing result of binary “or” with left shifting [on hold]
What is specific meaning of i and j in the code below?
It's obvious that they are used in case of all 1'ns in (i | j), I just can't get why they are special in those cases?
for (int i = 0; i < (1 &...
0
votes
1answer
26 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
33 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
80 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
28 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
36 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 ...
-2
votes
0answers
27 views
Why isn't my DFS algorithm getting the correct answer?
The member states of the UN are planning to send people to the Moon. But there is a problem. In line with their principles of global unity, they want to pair astronauts of different countries.
...
0
votes
0answers
34 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
37 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
17 views
Strongly connected component applications [closed]
I learnt how to implement/get strongly connected components of an graph. But I struggled to think of any real world application for it. Best Situation I can come close is choking of the road blocks. ...
0
votes
1answer
16 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
24 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 ...
-6
votes
1answer
22 views
minimum path sum of graph [closed]
I am new to graphs. Please help me. I don't know which algorithms to be used.I can't figure out how to solve this.
A company has a network of N computers connected by M lan cables. It is possible to ...
0
votes
0answers
38 views
How to produce a symmetric layout for a large graph?
I am using the boost's Kamada-Kawai spring layout algorithm implementation to produce symmetric graph layouts. This works well for small graphs (up to a few hundred of vertices). However, it is too ...
0
votes
0answers
25 views
Understanding Eppstein's algorithm for finding top-k paths from source to target
I am trying to understand the algorithm from this paper, and I have also found a great summarised explanation for it.
I am stuck at trying to understand the heap construction to restrict the ...
0
votes
0answers
41 views
Building a data structure and building a model to find a shortest distance in that data structure
I have a dataset in below given format:
ID1 ID2
A B
B Y
C A
D B
E D
Consider above relation as friends in Social Media site i.e. A is friend of B and B is friend of Y and D is friend of B ...
1
vote
1answer
28 views
BFS on graph vertices and edges as neighbors
I have a graph data structure, that I copied from this article - http://www.dreamincode.net/forums/topic/377473-graph-data-structure-tutorial/
And I'd like to implement the BFS algorithm on it. I'm ...
0
votes
1answer
34 views
Upside down Floyd–Warshall
I have a quick question. I know that this is a problem NP. If you receive the correct reversal algorithm Floyd-Warshall longest path between each pair of nodes?
0
votes
0answers
35 views
What is the image layout algorithm of iPhone Photos App Shared Album?
I'm very disturb with find image layout algorithm of iPhone Photos App Shared Album.
Is anyone could help me find the image layout rule？
2
votes
2answers
59 views
Knight's tour recursion doesn't find a solution
Knight's tour was asked before, but I'm still having trouble with it. I'm trying a recursion to visit all cells of chessboard but I can't make more than 52 visits. After that it backtracks and the ...
1
vote
2answers
56 views
Show that the heuristic solution to vertex cover is at most twice as large as the optimal solution
The heuristic solution that I've been given is:
Perform a depth-first-search on the graph
Delete all the leaves
The remaining graph forms a vertex cover
I've been given the question: "Show that this ...
3
votes
1answer
93 views
Shortest string containing all substrings of fixed length(any 1 permutation of the subset) of a list of characters
If I am given a list of characters say {s1,s2,s3,...,s10}, I want to find a string of shortest length having all unordered subset combinations of length three occurring as substrings within the string....
0
votes
2answers
22 views
Constructor value failed to get the value and assign to variable
I try to implement Greedy Best First Search.
My graph and heuristic is this:
Source: S destination: G. The proper way is: S A C E G.
The problem that I see there is that he don't take hNod from ...
1
vote
2answers
67 views
priority queue vs linked list java
I was solving BFS problem. I used PriorityQueue but I was getting wrong answer, then I used LinkedList, I got right ans. I'm unable to find the difference between them. Here are both the codes. Why ...
0
votes
2answers
57 views
NullPointerException on PriorityQueue A* algorithm
I try to implement A* algorithm. I don't know why but I get this error:
My graph and heuristic is this:
I wrote the values of heuristics when the nodes are created. And the value of edged, when an ...
0
votes
1answer
36 views
Fast Exact Solvers for Chromatic Number
Finding the chromatic number of a graph is an NP-Hard problem, so there isn't a fast solver 'in theory'. Is there any publicly available software that can compute the exact chromatic number of a graph ...
0
votes
0answers
64 views
Dijkstra's Shortest Path-HackerRank
I was solving the problem — Dijkstra's Shortest Reach 2. Here's a link.
Given a graph consisting N nodes (labelled 1 to N) where a specific given node S represents the starting position S and an ...
0
votes
1answer
40 views
Is there any algorithm to compute edit distance between two graphs including same nodes?
First, I know there has been a lot of works to compute the edit distance between two graphs. But most of the GED algorithms are applied in general cases.
Now considering my case, there are two graphs ...
1
vote
0answers
38 views
Graph Algorithm Requested Suggestion
I need to solve what amounts to a graph problem. I have a set P of particles (designated elements by p(i)) of size n, where each particle is located on a plain and a set X (designated elements by x(j))...
3
votes
2answers
260 views
Maximum bounty from two pathes through a rectangular grid
I am trying to solve problem similar to this problem at GeeksforGeeks, yet different:
Given a rectangular 2-d grid with some coin value present in each cell, the task is to start from the top-left and ...
0
votes
2answers
62 views
Efficiently handling duplicates in a Python list
I'm looking to compactly represent duplicates in a Python list / 1D numpy array. For instance, say we have
x = np.array([1, 0, 0, 3, 3, 0])
this array has several duplicate elements, that can be ...
0
votes
0answers
24 views
How to remove the redundant adjacencies on a DAG?
I'm looking for an algorithm to reduce the redundant adjacencies in a directed acyclic graph. I've made a bit of research and I've found some topics that reference the transitive reduction.
After ...
0
votes
1answer
21 views
Duplicate data when printing the adjacency list of a graph
I was just trying to implement an adjacency list based graph, I'm not able to sort out, why second value appears twice in output print:
#include <iostream>
#include <bits/stdc++.h>
using ...
1
vote
1answer
34 views
Complexity of Prims using Array
My teacher told me the complexity of Prims Algorithm using Array and Adj list is:
V^2+V+2E+E = O(V^2)
But, I can't recall why E.
1
vote
1answer
39 views
How to find whether the shortest path from s (any starting vertex) to v (any vertex) in the undirected graph is unique or not?
Given an undirected graph G = (V, E) with no negative weights.
What is the complexity for checking uniqueness of shortest path for every vertex in the given graph?
0
votes
1answer
24 views
Color a graph so that every node is either colored or adjacent to a colored node
Assume you have a connected undirected graph G. You want every node in G to be either colored or adjacent to a colored node. Design an algorithm to color the graph G appropriately. You are only ...
0
votes
1answer
36 views
How to determine if a “knight” that can take (i,j) steps at a time can cover an NxN board?
Normally knights move (1,2) steps at a time i.e 1 step in one direction, and two in the other. In a general version it can move (i,j) steps at a time.
I'm not sure if this is a knight's tour problem, ...
2
votes
1answer
61 views
Check if two nodes are on the same path in constant time for a DAG
I have a DAG (directed acyclic graph) which is represented by an edge list e.g.
edges = [('a','b'),('a','c'),('b','d')]
will give the graph
a - > b -> d
|
v
c
I'm doing many operations ...
0
votes
2answers
25 views
Algorithm to merge contacts
I am working on a project which requires to find similar contact.
I/P : it's in the form
C1 -> [email protected],[email protected] ... (could be any size)
C2 -> [email protected]
C2 -> [email protected],...
0
votes
2answers
53 views
What is the order of efficiency of an Adjacency list
Is it O(n+m) or O(nm)? To construct it be O(nm) and if we wanted to search, add, or delete a value it will be O(n+m), right? Is there anything else that would be important to consider?
Also to ...
1
vote
1answer
72 views
Avoiding infinite recursion but still using unbound parameter passing only
I have the following working program: (It can be tested on this site: http://swish.swi-prolog.org, I've removed the direct link to a saved program, because I noticed that anybody can edit it.)
It ...
2
votes
1answer
39 views
Implementing BFS on a graph
I have vertices in graph which represent towns. I am trying to find a shortest path from point A to point B.
I have created a graph class.
struct Edge{
string name;
vector< Edge *> v;
...
0
votes
0answers
54 views
Tripartite Matching: Graph Algorithm, Run Time Error
I am practicing problems on Graphs on Hacker Rank. Below is the link for the problem
https://www.hackerrank.com/challenges/tripartite-matching
I wrote a piece of code and the code seems to run on ...
-1
votes
1answer
30 views
Problems in evaluating subgraphs of a graph
Here is the question link.
Given an undirected graph. Density of a graph is |E|⁄|V|. Your task is to choose non-empty set of vertices V such that subgraph induced on V has maximal density ...
0
votes
1answer
28 views
Edge Existence (to find if an edge exists or not)
Question is:
You have been given an undirected graph consisting of N nodes and M edges. This graph can consist of self-loops as well as multiple edges. In addition , you have also been given Q queries....
1
vote
1answer
48 views
How to find maximal eulerian subgraph?
How to find maximal eulerian subgraph of a given graph? By "maximal" I mean subgraph with maximal number of edges, vertices, or both. My idea is to find basis of cycle space and combine basis cycles ...
1
vote
1answer
44 views
Minimize total distance, k links for each of N points on plane
Given N points on a plane (N is even), is there an efficient algorithm to generate k (k < N) connections from each point to k other points where the global distance is minimized?
For example, with ...
