Questions tagged [graph]
a mathematical structure that contains a collection of vertices or 'nodes' and a collection of edges that connect pairs of vertices
201 questions
1
vote
2
answers
89
views
Finding a subset of vertices in graph
I have a graph: undirected, unweighted, no leaves, no disconnected edges or vertices.
The graph is populated with vertices of 3 types: A, B, C.
Let's say, I hold a vertex of type A, denoted as A0.
I ...
- 119
6
votes
6
answers
870
views
Good way to represent connectivity between nodes of tree (outside of tree hierarchy)?
I have a set of data carrier objects represented using vertices in a strict tree hierarchy. I also have the following requirements:
some vertices should be "linked" to other vertices ...
- 69
1
vote
1
answer
233
views
Elegant solution to a graph problem
Given a line in a 2d coordinate system, we can create a dependency graph like this:
The black nodes represent a logical graph that is a-cyclic and therefore "stable" in the sense that if we ...
- 195
2
votes
1
answer
253
views
Is there a multidimensional topological sort of a directed acyclic graph?
In my application, I perform a topological sort of nodes where an integer represents a node's ID using DFS and white/gray/black coloring.
See https://yuminlee2.medium.com/topological-sort-cf9f8e43af6a ...
- 195
1
vote
3
answers
437
views
Get call graph / path of C with function pointer
I have a C codebase with function calls made through function pointers. I tried using LLVM AST and IR with Python to generate a function call graph, but handling the function pointer calls requires ...
- 165
1
vote
1
answer
162
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
292
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; // ...
- 195
1
vote
2
answers
177
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
347
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
251
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
292
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
131
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,844
1
vote
2
answers
212
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
461
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
533
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-...
