# 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
Filter by
Sorted by
Tagged with
1 vote
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
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
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 ...
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
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
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 ...
1 vote
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
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
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
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-...
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 ...
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
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
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
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
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
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
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
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 ...
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
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
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
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
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
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 ...
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 ...
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
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
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 ...
1 vote
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
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
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
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
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
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
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
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 ...
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
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
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
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
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
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
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
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
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
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
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