a mathematical structure that contains a collection of vertices or 'nodes' and a collection of edges that connect pairs of vertices

learn more… | top users | synonyms

0
votes
0answers
45 views

All clustering possibilities for a graph

Is there a known algorithm for finding all clustering possibilities for a directed graph? EDIT: By cluster i mean a weakly connected sub-graph G, so that E(G) > 0. By a clustering possibility I ...
1
vote
0answers
34 views

Domination algorithm in graphs

I'm working on a project, on an app, that can visualize undirected graphs and show on this domination algorithm. There are some examples: I have some open questions about programmable solution of ...
0
votes
1answer
72 views

Big graph traversal with OOP

I'm trying to solve a algorithmic contest's problem. I have a matrix 2000x2000. I want to represent it as graph and traverse it with BFS/DFS. I have time limits on app running (2s). Simple vertices ...
7
votes
3answers
174 views

Algorithm or domain for finding cheapest subgraphs that connect vertex pairs

I am currently working on a project inspired by the Ticket to Ride board game. This board game is played on an undirected graph where each vertex represents a city and each edge represents a ...
0
votes
0answers
15 views

Finding Contextual Nodes in a Knowledge Graph [migrated]

I'm currently participating in developing a knowledge graph that uses ConceptNet and a few others as its data sources. It uses the same architecture as ConceptNet namely it is stored as a hypergraph ...
1
vote
1answer
57 views

Connected components of undirected graph

Suppose I have an undirected graph G with vertices v1...vn and edges. Right now it is in adjacency list representation. For every time moment I have as input some subset of vertices that are "active" ...
1
vote
0answers
23 views

Codeforces : 505C. Mr. Kitayuta, the Treasure Hunter

Question : Is the attached logic correct? I am asking since my code based on this logic failed. Here is the problem link. Reproducing here verbatim : The Shuseki Islands are an archipelago of ...
3
votes
1answer
125 views

Is there some structured format for drawing source control branching diagrams?

Everyone on my team draws branch diagrams differently, including how branches exit or reintegrate to the parent, how cherry-pick merges are shown, and a host of other aesthetic choices. Is there some ...
1
vote
1answer
185 views

Why does this algorithm work in O(n m)?

This is from a blog post on Codeforces. I couldn't really understand why the editorialist goes on to claim that this code works in O(n m) This is a graph problem, where we are supposed to find the ...
1
vote
2answers
169 views

Why does this implementation of Dijkstra's algorithm work in O(n^2)?

Here is the code I use for implementing Dijkstra's algorithm. Consider a graph with n vertices and m edges. Shouldn't it run in O(n^2 m) ? Someone may say that there are n vertices and each edge gets ...
4
votes
1answer
83 views

Mathematically correct A* heuristic / distance estimator for a latitude / longitude graph

I have a graph in which each node is a geographical point on the surface of the earth, defined by it's latitude / longitude coordinates. Correct ways to calculate the distance between two such points ...
0
votes
1answer
74 views

Setting and getting values from a x-y graph

I have a bunch of x-y graphs given to me and I need to be able to transform them into some kind of data structure from which I will be able to get Y with X value. The problem is, though that I have 4, ...
1
vote
1answer
65 views

What is the minimum cost graph inside a strongly connected component, which connects every vertex?

So for MST there are 2 possible definitions in an undirected graph. Keep in mind that in an undirected graph the MST algorithm always has n - 1 edges and no cycles. In an undirected graph, it doesn't ...
3
votes
1answer
75 views

Merge directed acyclic graphs minimizing number of nodes

I have some DAGs (directed acylic graphs) and I want to merge them in order to minimize the number of nodes (we could say that every node has a cost, while edges are free). These four different DAGs ...
5
votes
1answer
143 views

How do you unit-test code using graphs?

I am writing (recursive) code that is navigating a dependency graph looks for cycles or contradictions in the dependencies. However, I am not sure how to approach unit testing this. The problem is ...
2
votes
2answers
160 views

Finding shortest path between nodes with a twist

Note: if you feel that I should include code, please tell me. I am solving a problem of finding shortest path between nodes. I am given the vertices between nodes, however they are one sided (ie you ...
0
votes
1answer
96 views

Find 'Connected Components' in undirected, unweighted graph coded as a 2d array

Given an undirected, unweighted graph coded as a 2d array, how can I find the number of different connected components? Example There is the following 2d array (I'm not putting any brackets to ...
0
votes
1answer
191 views

Number of sequences when no adjacent items can be the same

I came across this one problem, There is a particular sequence only uses the numbers 1, 2, 3, 4 and no two adjacent numbers are the same. Write a program that given n1 1s, n2 2s, n3 3s, n4 4s ...
3
votes
1answer
178 views

Shortest Path Between Two Nodes in a +10 Million Nodes Graph

I have my own knowledge graph representation, read from ConceptNet and NELL, containing tens of millions of nodes in which I want to calculate the nearest distance (if any) between two concept nodes. ...
0
votes
0answers
18 views

A heuristic approach to Clique problem over undirected Graph

I'm trying to get all complete subgraph given a graph G. Needless to say it is an NP-problem complete: Clique_problem. I understand getting the full set is not possible in real time(since it'll take ...
2
votes
1answer
135 views

Data structures and algorithms for a directed rooted tree with inherited properties?

I need to represent a directed rooted tree in memory. The caveat is, that nodes have properties. And those properties are inherited (but not 100%) by the child nodes, recursively. What would be a ...
2
votes
1answer
147 views

Find n nodes farthest away from each other

I'm looking for an algorithm that gives me the n nodes that are the farthest away from each other. Can this be accomplished relatively efficiently? To clarify my question: I think of the problem as ...
3
votes
2answers
241 views

How can I find the shortest path between two subgraphs of a larger graph?

I'm working with a weighted, undirected multigraph (loops not permitted; most node connections have multiplicity 1; a few node connections have multiplicity 2). I need to find the shortest path ...
2
votes
4answers
750 views

Finding the shortest path through a digraph that visits all nodes

I am trying to find the shortest possible path that visits every node through a graph (a node may be visited more than once, the solution may pick any node as the starting node.). The graph is ...
10
votes
2answers
515 views

How to represent a graph with multiple edges allowed between nodes and edges that can selectively disappear

I'm trying to figure out what sort of data structure to use for modeling some hypothetical, idealized network usage. In my scenario, a number of users who are hostile to each other are all trying to ...
1
vote
1answer
111 views

City exploration algorithm

The purpose of the algorithm is to create n routes on a geographical map, where n is being given, whereas all routes take no longer than t time units by foot and end where they start, while trying to ...
2
votes
1answer
96 views

Which approach would be better for persisting these overridable configuration keys and values? A simple key-value store, or a graph database?

I'm creating a system where there are config keys and values. So for example: config.key = 10 Is an example of a configuration key and a value. These keys can also have overrides based on ...
1
vote
1answer
51 views

Equidistant polygons

Consider these polygons: For reasons of simplicity I only consider triangles or polygons with 4 vertices. These shapes are specified by the vertices, the output of the program should be modified ...
0
votes
3answers
256 views

An algorithm for finding converse duplicates of ordered pairs

Given an array of ordered pairs of values, is there a well-known algorithm to find converse duplicates? [Converse meaning the same values, but in the opposite order.] That is, given ...
2
votes
0answers
194 views

Understanding Tarjan's Bridge-finding algorithm

Tarjan's algorithm for finding bridges in a graph is found here: http://en.wikipedia.org/wiki/Bridge_(graph_theory)#Tarjan.27s_Bridge-finding_algorithm. However, I don't understand the condition for ...
0
votes
1answer
54 views

Matching weighted unbalanced Bipartite graph

I am looking for a way to solve an assignment problem, but I am having some problems finding the correct algorithm to use. I have 2 list of nodes A and B, and in my problem may the length of A not be ...
2
votes
1answer
174 views

Improving the running time of Breadth First Search and Adjacency List creation

We are given an array of integers where all elements are between 0-9. have to start from the 1st position and reach end in minimum no of moves such that we can from an index i move 1 position back and ...
2
votes
1answer
137 views

How to canonise a road network

I am working on geographical data which represents the road network of some city and I need to automatically fix inaccuracies in the data. Data was manually produced by “drawing” the road network ...
2
votes
1answer
133 views

Maze generation given intersection tree

Background Information: I'm building a 2D maze generator. I have tried Prim's algorithm, Wilson's algorithm, and a recursive backtracker algorithm for generating my maze, however was not satisfied ...
0
votes
0answers
39 views

Charts, SQL and REST?

We have created a REST API for a voting game. Now we are jumping into creating analytics/graphs/charts for moderators and users to watch how are they doing in the game. The game has a certain group ...
0
votes
1answer
180 views

Euclidean Space Fully Connected Nondirectional Graph: Shortest Path to all nodes

So this may be a question that is born of my inability to properly express my intentions to Google. In a fully connected non-directional graph such that any three points can be properly represented ...
3
votes
2answers
346 views

How to find number of points with same minimal distances on matrix

I'm trying to find the number of points in a matrix with the same minimal distances. Start with a MxN matrix, where M and N < 50000. There is given a set of fixed points, with their respective ...
6
votes
1answer
184 views

Heuristic Approach for Flexible DIFF Implementation

I have created a DIFF implementation to compare document revisions at work. It is based on An O(ND) Difference Algorithm and Its Variations. One thing that has become important is to take the list ...
5
votes
5answers
539 views

Finding most Important Node(s) in a Directed Graph

I have a large (≈ 20 million nodes) directed Graph with in-edges & out-edges. I want to figure out which parts of of the graph deserve the most attention. Often most of the graph is boring, or at ...
1
vote
1answer
174 views

Question on Graph

I am trying to implement a graph data structure in C#. I have the following interfaces: public interface IVertex<TValue> { TValue Value { get;} ...
1
vote
2answers
127 views

Algorithm for defragmenting cross-pipe issues in a network for routing signals through?

I have a network I'm responsible for routing signals through. You can think of the network as a directed graph of nodes (hardware) but each edge is really a pipe capable of fitting a specific ...
0
votes
2answers
140 views

What algorithm should I use to find the shortest path in this graph

I have a problem about the calculation of shortest paths on an unweighted and undirected graph. Which algorithm I use to calculate the shortest path between a node A and node B that passing through a ...
0
votes
1answer
253 views

Weight-maximizing (weighted vertices) path algorithm

I am looking for description (name of algorithm, code, pseudocode, etc.) that can help me frame this problem and find the appropriate recursion and the most efficient solution. Problem: Given a ...
0
votes
2answers
547 views

What graph traversal algorithm should I use?

I would like to write an algorithm which can traverse a graph and hopefully later I can implement it to use for an indoor navigation system. The graph would come from floor plans of a building and ...
4
votes
3answers
457 views

Optimal “if-else” tree algorithm to minimize duplicate code

I'm having trouble formulating this problem as an algorithm: I have a set of conditionals (combined with &&) and operations, for example: if (A && B) execute C else if (D ...
1
vote
0answers
89 views

Representation of time expanded graph

I want to build a time expanded graph with time discretization Dt that starts at t = 0 and ends at t = T where between the node (n1, t) and the node (n2, t') is an arc if and only if (n1, n2) were ...
0
votes
0answers
68 views

using internal or external iterators over graph edges

I've written some code to manipulate sparse graphs for school work I'm doing, and I have an operation which requires me to loop over all the edges of a graph. The interface I need to implement is some ...
3
votes
1answer
248 views

How to solve binary labeling with graph cut?

Many literature references suggest that the binary labeling problem can be converted into a graph cut problem and solved with the max flow/min cut algorithm. I'm trying to understand the formulation ...
1
vote
1answer
115 views

How can I find all connections in a mesh network/graph?

Suppose I have a mesh of relationships, such as Friends who trust some friends and not others A IPv6 router that needs to locate peers across the Internet A PGP Web Of Trust that needs two people ...
3
votes
2answers
575 views

Breadth-first graph search problem

I thought I was doing breadth-first graph search correctly, but my instructor's grading script is telling me that my answer is incorrect. From the instructions: Consider a breadth-first graph ...