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
1answer
129 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 ...
2
votes
0answers
38 views

Graph visualization algorithm

I need a 2d or 3d graph visualization algorithm by which adding/removing a node or a relationship does not have a butterfly effect on the positions of other nodes. (We are talking about a directed ...
4
votes
0answers
109 views

What is the maximum number of steps to find a bug using bisecting?

Assume that a node A in the commit tree of a codebase contains a bug but some ancestor B of A is clean from that very bug. Given the topology of the commit tree [B,A] leading from B to A, can we ...
0
votes
0answers
10 views

Computing theory: can a single node be a subgraph? [migrated]

Can a single node be considered a subgraph? For example, if I had this graph, G: X-----Y and I deleted Y, leaving me with the graph X is this a subgraph (induced) of G? What about the following ...
0
votes
0answers
20 views

Best way to represent time related event during a day in a graph [migrated]

I want to represent time-related events graphically (bars/chars/graphs, etc). I have a log in the administration panel, the data is login times for admins, so each admin has online-offline ...
3
votes
1answer
94 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 ...
16
votes
7answers
716 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 ...
0
votes
1answer
40 views

Render order of two-edge directed node graphs

I'm trying to find an algorithm for graphs with the following contents: Nodes with no edges leading out of them (shown here as a red circle) All other nodes have exactly two edges leading out ...
0
votes
4answers
366 views

An algorithm for finding converse duplicates of ordered pairs

Given an array of ordered pairs of values, what algorithm will find converse duplicates? [Converse meaning the same values, but in the opposite order.] That is, given [ab,ac,ad,bc,bd,ca,db] is there ...
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 ...
0
votes
1answer
76 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, ...
2
votes
4answers
965 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 ...
0
votes
0answers
51 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
41 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 ...
7
votes
3answers
194 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 ...
3
votes
1answer
144 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
62 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
27 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 ...
1
vote
2answers
176 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 ...
1
vote
1answer
189 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 ...
5
votes
1answer
1k views

Building a Graph Editor - How to create a data driven graph

I am developing a graph-editor that uses drag and drop to build hierarchical graphs (containing nodes and links). Each node in the graph should be linked to a table in our database (SQL Server). I did ...
4
votes
1answer
87 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
127 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 ...
1
vote
1answer
79 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 ...
2
votes
2answers
177 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
214 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
236 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
19 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
157 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
160 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 ...
14
votes
3answers
7k views

Efficient graph clustering algorithm

I'm looking for an efficient algorithm to find clusters on a large graph (It has approximately 5000 vertices and 10000 edges). So far I am using the Girvan–Newman algorithm implemented in the JUNG ...
1
vote
1answer
117 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 ...
3
votes
2answers
295 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 ...
10
votes
2answers
584 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 ...
2
votes
1answer
139 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 ...
1
vote
1answer
54 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 ...
2
votes
0answers
211 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
59 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
189 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 ...
5
votes
5answers
565 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 ...
2
votes
1answer
147 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 ...
3
votes
2answers
356 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 ...
3
votes
1answer
181 views

Class instance clustering in object reference graph for multi-entries serialization

My question is on the best way to cluster a graph of class instances around specifically marked objects (objects are the graph nodes and the references to each other are the directed edges of the ...
0
votes
2answers
585 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 ...
3
votes
2answers
626 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 ...
6
votes
1answer
185 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 ...
0
votes
1answer
188 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 ...
0
votes
2answers
252 views

Data structure theory based on graph rewriting [closed]

First of all, I'm looking for a book, publication, project or any kind of information that should probably exceed the limits normally imposed on answers in this kind of forum. I know the rules about ...
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 ...
1
vote
1answer
196 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;} ...