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

3
votes
0answers
43 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
0answers
52 views

Architecture for “Friend of a friend 'likes' feature” [closed]

I read a few of existing posts like facebook calculate, fb db design and also some of the neo4j notes, also the pit falls of going with mongo for diaspora. I signed up into one of the diaspora pods. ...
-4
votes
0answers
30 views

Questions regarding graph/2-d matrix traversals and shortest path [closed]

Many interview questions are about graph traversal and shortest paths. For example, you may be asked to find the shortest path from a point in the graph to another. In order to solve it, one would use ...
2
votes
1answer
98 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
121 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 ...
1
vote
3answers
116 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
272 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
96 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
51 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
43 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
103 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 ...
1
vote
0answers
158 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
37 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
114 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
127 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
97 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
36 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
143 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
284 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
179 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
466 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
132 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
123 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
132 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
199 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
362 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
354 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
76 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
57 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
208 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
96 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
423 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 ...
1
vote
3answers
149 views

Storing a drawn graph information in database for web application

Well while developing a web application that allow users to draw graphs (flow charts, ER diagram , UML, .... etc) the information of drawn items and their relation to each other and position on canvas ...
2
votes
2answers
306 views

Is it possible to represent mutation of object-graph efficiently with immutable states?

I am practicing using of immutable object in C++. My personal goal is representing generic object graph (in heap) with sequence of immutable graphs. Building the multi-version graph itself isn't that ...
0
votes
2answers
215 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 ...
3
votes
1answer
166 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 ...
1
vote
1answer
255 views

Connected components of a graph using Prolog

Given a corner x of an undirected Graph G I would like to ask for the connected component of x, but my first try does not work as desired. Here it is: edge( a,b ). edge( b,a ). edge( b,c ). edge( ...
2
votes
1answer
195 views

Algorithm in undirected BFS graph

I'm trying to put together an algorithm that will display the node degree for every node in a breadth first tree graph (assume BFS was called). Assume it's an undirected graph. I'm not sure how to ...
4
votes
2answers
97 views

Placing elements in graph with a streaming/online algorthm

We have a stream of points with about 1000 points per second. For each point, we have a complex vector (hundreds of dimensions). Our goal, for each point is to link it to the 5 closest points that ...
5
votes
1answer
576 views

Where to learn graph theory applications [closed]

I am completely new to designing algorithms with graphs. I am following CLRS and other video lectures in Youtube, notably from IIT/MIT. They are pretty good, and I currently have decent idea about ...
4
votes
1answer
989 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 ...
1
vote
1answer
324 views

Languages with graph data structures and algorithms in standard library

I am trying to improve my knowledge and ability with graphs and graph algorithms and have noticed something curious: as far as I can tell no "mainstream" language contains support for graphs in its ...
2
votes
3answers
850 views

How can you prove an acyclic graph has n-1 edges? [closed]

I'm not so hot on the maths for this but for what I understand... A graph g exists with v vertices and edges. g = (V,E); The spanning graph for this is an acyclic copy of this where all the vertices ...
6
votes
1answer
130 views

Detecting areas of isotropic vs anisotropic diffusion in a flood-fill (or similar) operation

Hello fellow programmers! I have a 2D graph which is best described as a Cartesian grid with traversible and non-traversible cells. I'd like to be able to detect subsets of this graph where the ...
6
votes
3answers
1k views

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

I have a graph with about a billion vertices, each of which is connected to about 100 other vertices at random. I want to find the length of the shortest path between two points. I don't care about ...
-2
votes
1answer
560 views

using ant colony algorithm to create cross word game [closed]

I have difficulty to learn about ant colony algorithm (ACO), I have read about generating crossword game using (genetic algorithm) GA.I Know both of GA ant ACO usually used for optimization, but my ...
18
votes
6answers
629 views

Visiting points on a number line while minimizing a cost not related to distance

I need some help on this ACM ICPC problem. My current idea is to model this as a shortest path problem, which is described under the problem statement. Problem There are N = 1000 nuclear waste ...
2
votes
1answer
393 views

Finding subtree in a tree

I have a tree: a / \ b c / \ d f / \ g h And the pattern: x / \ y z / \ q p As output I would like to have: x: a y: b z: c q: d p: f and x: b y: f z: c q: ...
6
votes
2answers
136 views

spotting graph cycles - simple explanation

could some please help me understand how to find cycles in graphs in laymans terms? I have read other questions, such as This one and also some of the wikipedia pages, but they seem to descend rather ...
1
vote
2answers
961 views

What is the best way to plot 3D/2D plots with real time data? [closed]

First of all, I like to use Python, because it is easy to work with. I am not a programmer, so I prefer anything that is easy to use and understand. I understand that it might be faster to program 3D ...