a mathematical structure that contains a collection of vertices or 'nodes' and a collection of edges that connect pairs of vertices
1
vote
1answer
32 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
107 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
85 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 ...
-2
votes
0answers
51 views
working with Neo4j and MySQL together [closed]
I'm starting a project which will include data and connections between entities.
I thought to use Neo4J for storing the data and the connections
but I'm not sure about it and want to consult with you.
...
4
votes
1answer
148 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
181 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
125 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 ...
0
votes
2answers
77 views
Looking for a freeform dependency graphing tool [closed]
In programming for an existing code base that is trying to migrate over time from the "status quo" to the "final solution" I often find that there are dozens of hurdles that need to be overcome... but ...
2
votes
3answers
164 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
67 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
482 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 ...
0
votes
1answer
208 views
using ant colony algorithm to create cross word game
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 ...
0
votes
1answer
189 views
How to turn a website into an offline usable directed graph for searching shortest ways between pages [closed]
I am an advanced-intermediate level student focused on the .NET and C#. I know all the basics as well as classes, methods, objects, inheritance, OOP principles and all that. Problem is we haven't ...
17
votes
6answers
487 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
147 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: ...
5
votes
2answers
75 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
337 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 ...
-2
votes
1answer
103 views
Non-obvious use of graph [closed]
What are the uses of graphs that can be considered non-obvious. For many graph examples, it is very clear for people who knows even a little about graph that it can be represented as a graph, like ...
1
vote
1answer
112 views
Implementing a sort of navigation system
So I am undertaking a project which does navigation sort of thing. So here is how the problem statement looks like.
Say, given a map of a floor, with different rooms, now somehow, this information is ...
6
votes
3answers
456 views
Cyclomatic complexity with two IFs - why it is 3?
I have read an article with following example:
void func()
{
if (condition1)
a = a + 1;
if (condition2)
a = a - 1;
}
It says the CC is 3 as there are three possible paths. How come? Why not 4? I ...
-1
votes
1answer
174 views
Need theoretical help, how to comprehend an if-else dependency net
I am going to face a following issue:
I'm writing a program that manages some properties of my application. Each property is a pair of key and value. Application has general skin and also few ...
3
votes
2answers
184 views
Chambers In A Castle Algorithm
Problem Statement -
Given a NxM grid of 1s & 0s (1s mark walls, while 0s indicate empty chambers), the task is to identify the number of chambers & the size of the largest. And just to ...
1
vote
2answers
312 views
Tree vs Graphs in search
Could anyone give a clear and concise explanation for when you use graphs vs when to use trees for data structures?
-2
votes
2answers
146 views
Is there a connected graph of the web, connecting sites by similarity or something else? [closed]
For example, one could make a graph that connects site to sites that are linked by it - or that are accessed by the same people. Does that kind of analysis exist? Where, how it is called and how can I ...
29
votes
7answers
2k views
When to use DAG (Directed Acyclic Graph) in programming?
I recently found a framework named ecto.
In this framework, a basic component named "plasm", which is the ecto Directed Acyclic Graph.In ecto, plasm can be operated by ecto scheduler.
I am ...
5
votes
4answers
632 views
What are graphs in laymen's terms
What are graphs, in computer science, and what are they used for? In laymen's terms preferably.
I have read the definition on Wikipedia:
In computer science, a graph is an abstract data type ...
5
votes
1answer
337 views
Nearest color algorithm using Hex Triplet
Following page list colors with names http://en.wikipedia.org/wiki/List_of_colors.
For example #5D8AA8 Hex Triplet is "Air Force Blue". This information will be stored in a databse table (tbl_Color ...
3
votes
1answer
170 views
Graph/diagram editor that works with pseudographics
Is there a graph/diagram editing tool that can output (or even better also parse) pseudographics, that can be easily inserted into source code comments? Like this:
+---------------+
| ...
6
votes
1answer
2k views
Am I right about the differences between Floyd-Warshall, Dijkstra's and Bellman-Ford algorithms?
I've been studying the three and I'm stating my inferences from them below. Could someone tell me if I have understood them accurately enough or not? Thank you.
Dijkstra's algorithm is used only ...
0
votes
3answers
455 views
Reasonable Number of Directed Graph Nodes and Edges
How many directed graph nodes are typically represented in the browser? I'm working with some large data-sets with nodes and edges more then 400,000. I'm wondering if I am going down a fruitless path ...
3
votes
2answers
152 views
Custom graph comparison?
I'm trying to compare two graphs using hash value ( i.e, at the time of comparison, try to avoid traversing the graph )
Is there a way to make a function such that the hash values compared can also ...
4
votes
1answer
223 views
Merging similar graphs based solely on the graph structure?
I am looking for (or attempting to design) a technique for matching nodes from very similar graphs based on the structure of the graph*. In the examples below, the top graph has 5 nodes, and the ...
5
votes
1answer
355 views
Algorithm for perfect non-binary graph layout
I have a complex non-binary graph model.
Each tree node can have multiple children&parents (a node can also have a connection to it's "brother").
A node is represented as square on screen with ...
1
vote
1answer
510 views
Networkx / Python : Is using a class for a node better practice than defining multiple attributes?
I've read through the NetworkX tutorial and documentation, but was unable to find real world answers for this question.
Usually when using NetworkX, I might use strings to define nodes, then set ...
6
votes
3answers
2k 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 ...
11
votes
3answers
645 views
Randomly generate directed graph on a grid
I am trying to randomly generate a directed graph for the purpose of making a puzzle game similar to the ice sliding puzzles from Pokemon.
This is essentially what I want to be able to randomly ...
4
votes
4answers
398 views
Building a route creator
Ok, already up front, I'm going to tell you, that this is a bonus task for Data structure course I'm taking. That should take care of all the questions whether or not this is for a homework.
Route ...
4
votes
3answers
1k views
What is an algorithm to find simple cycles?
I have a graph with an Eulerian cycle and no Hamiltonian cycles. I would like to divide this graph into simple cycles.
Edges may not be repeated in simple cycles.
How can this be done?
1
vote
2answers
202 views
Tool for large scale graph analysis
What are the best tools / frameworks / libraries available to implement and run algorithms on graphs?
In particular I need a tool that can load a set of nodes, edges and values assigned to these ...
16
votes
5answers
1k views
Algorithm to determine fastest route?
Let's say we're going from 1 to 5. The shortest route will be 1-4-3-5 (total: 60 km).
We can use Dijkstra's algorithm to do that.
Now the problem is, the shortest route is not always the fastest ...
2
votes
5answers
518 views
Programming language with native concurrency support for large graphs?
I'm currently looking for a new programming language to learn (currently working through some C++, know some C and Python), specifically one that has built-in concurrency support? I want to try to ...
0
votes
1answer
1k views
Are questions on graphs common in programming interviews?
Despite saying that graphs are very important, none of my friends have got any graph related questions in interviews in Google and Amazon. I am preparing for these companies right now.
Should I ...
4
votes
2answers
664 views
Algorithm for an exact solution to the Travelling Purchaser Problem
do you know of any algorithms which give an exact solution for the Traveling Purchaser Problem. I can only find heuristic and probabilistic approaches.
I do have implemented a genetic algorithm so ...
3
votes
2answers
482 views
When can I be sure a directed graph is acyclic?
The definition for directed acyclic graph is this: "there is no way to start at some vertex v and follow a sequence of edges that eventually loops back to v again."
So far so good, but I am trying to ...
