Questions tagged [graph]
a mathematical structure that contains a collection of vertices or 'nodes' and a collection of edges that connect pairs of vertices
196
questions
1
vote
1
answer
140
views
Tree impurity of a call graph
In his "Software Engineering. Principles and Practice," H. van Vliet mentions "tree impurity of a call graph." However, the term tree impurity is not used in this meaning anywhere ...
- 339
1
vote
2
answers
136
views
How do I solve this graphing dependency cycle in an AST?
I'm playing around with AST generation and exploring how it relates to a directed acyclic graph. I hit a logical snag that I don't understand.
var literal = 3; // expression 1
literal = literal+1; // ...
- 141
1
vote
2
answers
120
views
Culling edges from a triangulation while maintaining a connected graph?
I'm working on a small project and I'm randomly generating "world maps", with nodes you can fast travel to along given routes.
The basics of this aren't complicated; throw random points on a ...
- 111
0
votes
2
answers
260
views
Build an API for a graph app with + 30 millions data points
I am quite new to design software and especially graphs. So I am working on a full-stack app with a back-end built on FastAPI (python) et front-end on React.
I need to create 4 graphs on a single page ...
1
vote
3
answers
179
views
Graph layout positioning
Given a graph layout like the following image, where the layers/rows (y coordinate) and ordering of nodes within each layer have already been computed, what algorithm can I use to make it look "...
- 159
1
vote
1
answer
208
views
Database design for graph where nodes can be other graphs
How should I design a relational schema to store graph documents that can contain plain nodes (shapes, in the example below) as well as nodes that can reference other graph documents?
To visually ...
- 251
1
vote
1
answer
102
views
Some questions about shortest-path algorithms
I'm trying to understand why anyone would prefer Floyd-Warshal over Dijkstra:
Dijkstra gives a correct result, using an understandable system, combined with backtracking.
Floyd-Warshal makes an ...
- 1,816
1
vote
2
answers
166
views
Dependency resolution of tasks which have crontab information
I want to illustrate my problem statement with a use case. I am building a trading system that acts as a container for deploying trading strategies. The trading strategy comprises dependent tasks. Let'...
- 119
1
vote
1
answer
383
views
What is the best way to program a lattice graph?
What is the best way to program a graph like this:
I know I could use Adjacency list or Adjacency matrix:
//https://stackoverflow.com/questions/5493474/graph-implementation-c
//Clearer's answer
...
- 261
0
votes
2
answers
432
views
Data structure for graphs and vectors in C
I'd like to design an implementation for graphs in C.
I'm wondering what the most efficient approach in terms of both computational power and memory consumption would be.
I've looked at various open-...
10
votes
5
answers
3k
views
Pros and cons of representing routes as legs or stops?
What are some pros and cons of representing routes as legs or as stops?
A leg is a departure and arrival location, a departure time and a duration (or an arrival time and a duration).
A stop is an ...
0
votes
2
answers
339
views
Possible trajectories with time travel
I'm trying to calculate a trajectory in the presence of time travel.
In the following picture, there is a character traveling toward the right in a straight line (like a billiard ball). If the ...
- 127
0
votes
1
answer
480
views
How can I represent a graph for a visual programming language in JSON?
I am in the process of implementing a visual programming language similar to Blender's node editor or Unreal Engine Blueprints. It will be implemented as a SPA that will communicate with a JSON based ...
- 111
0
votes
1
answer
64
views
Best data structure for searching best color match? (4D space)
My current color distance formula is a modified version of Euclidian distance (eDist) because with eDist I was noticing weird issues where blue could be used instead of green in some situations when ...
- 103
2
votes
1
answer
185
views
What is the relation between edges in a dependency graph and the program call to create a vertex?
A Makefile is a representation of a depency graph. The files are the vertices, for example somefunctions.h, somefunctions.c and myprogram.c are the "input" vertices (is there a formal word ...
- 147
0
votes
0
answers
66
views
Best way to implement a heterogeneous graph that multiple algorithms have to work with, each requiring extra data and behavior for each node
I'm writing in C++, but this problem could apply to any other language. This post is a continuation of this question (I thought the question is different enough to fit a new post better. If I'm wrong, ...
- 273
0
votes
1
answer
1k
views
Find duplicate subgraphs in directed graph?
Is there a good way to search for duplicate subgraphs in an immutable directed graph, where edges and nodes may be labeled?
I was thinking I could try to name the nodes according to their position in ...
- 2,863
0
votes
2
answers
634
views
Implementing C++ n-ary tree with Boost Graph Library
I would like to have a relatively small and simple tree in C++. Each node would contain an integer. The tree should be traversable both ways.
I know it can be done with tree.hh by Kasper Peeters, but ...
- 1
0
votes
1
answer
152
views
Draw Data Flow Graph with Constructor and Functions
I am new to software testing and would like to know whether it's appropriate to draw a data flow graph that flows from initiation of variables to constructor and method.
Is there something wrong with ...
- 119
-3
votes
1
answer
102
views
P2P network implementation: how to avoid "orphan" groups of nodes
As the title says, in a P2P decentralized network implementation how do you ensure that all your nodes are actually connected and you never have a subset of "orphan" nodes at any time (e.g. ...
- 11
2
votes
1
answer
611
views
Neo4j graph performance: should I cache slow queries in a separate database?
Setup/Intro
I have 10k+ nodes in my Neo4j graph in which I need to display a sub-graph (100-500 nodes) between 2 start/end nodes on the frontend app along with info about the critical path and all ...
- 121
2
votes
2
answers
346
views
Collaborative graph exploration algorithm
Given a minimum spanning tree in an unweighted graph of (10 .. 500) vertices and (vertice_count .. 1000) edges. Each vertex can have
up to 6 edges.
Given K agents/bots/processes/etc.., all starting ...
- 41
1
vote
1
answer
201
views
How to apply Graphs/Trees/BFS/DFS concepts to Lists
I have been doing problems on LeetCode recently, and keep getting stuck on some graph or tree problems. I understand the underlying concepts of Graphs, Trees, and different methods of traversal just ...
- 147
0
votes
0
answers
81
views
Cache graph with hierarchy
I'm looking to build a graph that's tied to any caching system that I can interact with. Its only goal is when an item is deleted, based on its "linked items", to also delete these. A partial rebuild ...
- 85
2
votes
3
answers
520
views
How to clone an object graph and keep relationships of objects intact?
In my ASP.net core application with Angular 2+ client, I work with a complicated object graph. In the object graph I have some objects with references to each other. I have a simplification included ...
- 175
-1
votes
1
answer
133
views
Can somone explain facebook starspace?
I have googled enough for days but i cant find a clear intuitive document about this embedding technique.
In their paper they say : We present StarSpace, a general-purpose neural embedding model that ...
4
votes
3
answers
478
views
How to do grid systems with floats given precision causes problems
I've been trying to create a grid system that can use any grid size and start at any given anchor point rather than always at 0,0.
The problem however is imprecision makes it impossible, even the ...
- 2,102
1
vote
1
answer
110
views
Designing a generic graph
I am looking at designing a Graph class, that should work for both lists and matrix.
For ex: something like,
class Graph {
public:
virtual ~Graph() = 0;
virtual bool AddEdge(int src, int dest)...
- 131
1
vote
2
answers
117
views
How to allow initial input for a graph of words?
I want to create a java program that can find the shortest word ladder between two words. It's been suggested that I use a graph data structure with words as nodes. The idea being that nodes with ...
- 121
1
vote
1
answer
495
views
Designing a Social Network with Graph Databases
I am prototyping a social network as part of a project I am working on and want to learn the right way to do it as if it were for an industry leading company.
I've decided on implementing the social ...
- 71
0
votes
1
answer
114
views
Model Semantics: Is "real" data on a graph consider as a model?
At first this question seems elementary -- Is "real" data on a graph (xy coordinates) a model? However here is my logic. We know a model is an abstract representation of the real-world. A graph is ...
- 131
-2
votes
1
answer
1k
views
How to obtain and store a subgraph of a graph in C++?
I have implemented a graph structure (for graphs having ~30,000 nodes and ~300,000 edges) as follows:
class graph;
class node;
class edge;
class graph
{
public:
graph(){};
vector<node*> ...
- 103
1
vote
1
answer
224
views
How much an iterator should do
I am working on creating iterators, for strings, lists, trees, graphs, and potentially other things.
First a side note.
I have a string data type in my engine. The string is implemented as a bunch ...
- 2,625
-2
votes
1
answer
274
views
Are there languages/syntaxes for representing graphs? [closed]
S-expressions are a well-known way of describing trees in high-level code.
Is there something similar for describing graphs?
The two closest things I've found are DOT and Ko. Both aren't quite what ...
- 2,198
2
votes
1
answer
420
views
How a Merkle tree can work with Graph data, or a better data structure
I am looking at blockchain and trying to see how Merkle trees (or perhaps Merkle DAGs) can fit to a graph data structure with circular references.
For example, say I have this data model:
var ...
- 259
0
votes
2
answers
5k
views
Creating a control flow graph for a given function
Given is a short Java function and I like to create a control flow graph for it but I'm not sure if it's fine like that? Because I left some things away such as variables that have already been ...
- 119
-2
votes
1
answer
2k
views
Calculating longest trip [closed]
I have been stuck on this question for some time. Could you guys direct me or point me to the right direction for solving this problem ?
We would like to encourage passengers to experience the joy of ...
- 17
2
votes
1
answer
113
views
How to model rdbms relationships as graph relationships?
I am modeling our existing database in transition to a graph database.
Currently here is how I can interpret the database a graph relationships
group -have-> groups
group -have-> participants
...
- 123
1
vote
0
answers
123
views
How to represent a set of ephemerides?
I am writing software that deals with ephemerides—tables describing the positions and orientations of celestial bodies or spacecraft—and I am struggling with how to represent them in the ...
- 156
4
votes
4
answers
2k
views
Find the min/max length of directed graph
The problem is simple on paper... but a bit harder when it comes to write the algorithm to solve it.
Let's use the following graph:
First part
This graph has an entry point A and two possible exits ...
- 396
0
votes
1
answer
149
views
Find nth best path in graph G from node A to node B (without loops)
I'm making an graph layout optimizer and need to find paths from node a to node b in graph g. It has gone pretty well so far, but I lack an algorithm to take the next step.
So far I've used BFS to ...
- 299
1
vote
1
answer
2k
views
How a Control-Flow Graph looks with many (Nested) Functions
From what I can remember the Control-Flow Graphs for which I have seen images have mostly been of single functions. So basically just statements with perhaps looping. But I am wondering what a control-...
- 2,625
0
votes
1
answer
136
views
How to resolve data-binding efficiently
Following this question, the solution to resolve data binding is to use DFS and Topological Sorting. I am not really sure exactly what that means. Here is an animation that roughly demonstrates what I ...
- 2,625
-1
votes
2
answers
2k
views
Adjacency List list of linked list or can be repesented in other ways?
I am new to graph data structure. Everywhere on google it is said to be list(or array ) of linked list.
My question is can not it be represented as list of list(in java array list of array list) or ...
- 1,896
1
vote
1
answer
486
views
Most compact way to represent a graph [closed]
Given these nodes:
a
b
c
d
e
f
g
h
And given some edges between the nodes like this:
a/b/c
b/c/d
c/e
c/d/e/f
c/g
f/g
e/f/g
a/c/h
h/a/b
c/a
d/b/c
f/g/c
d/a/f
g/f
g/a/b/c
f/a/b
e/a/c
(where a/b/c ...
- 2,625
1
vote
4
answers
2k
views
What is the proper place for complex business logic
I have an object that describes a two-dimensional Graph:
class Graph {
var points; // Array of points
}
Now I need to find some complex patterns in this graph, like (but more complex):
Find two ...
- 197
0
votes
1
answer
180
views
Data-binding for Boolean values
Wondering if there is anything closely resembling data-binding but for boolean values / triggers. It seems like it could be related to Binary Decision Diagrams (BDDs), but they are precomputed rather ...
- 2,625
1
vote
1
answer
1k
views
How to solve a Constraint Satisfaction Problem for Scheduling
This presentation describes several algorithms for solving a CSP for scheduling.
Say I have a few processes with some constraints:
a before c
c before b
b after d
c 50% more important than e
give d ...
- 2,625
1
vote
2
answers
100
views
Designing a graph-like drawing application
I am dealing with a drawing app that allow the user to draw a set of Components (which are like the graph vertices) and they can be wired (like the graph edges) on each other to simulate how their ...
- 207
1
vote
1
answer
152
views
What is the most efficient way to represent resizable adjacecny matrix
I'm building a simple app that represents some matrix, where nodes are added quite often. Currently I have following code for adding a new node:
let mut new_edges = Array2::default((position + 1, ...
- 111