Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [graph]

a mathematical structure that contains a collection of vertices or 'nodes' and a collection of edges that connect pairs of vertices

1
vote
2answers
66 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
1answer
173 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 ...
0
votes
1answer
15 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 ...
-2
votes
1answer
123 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*> ...
1
vote
1answer
124 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
votes
1answer
120 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 ...
0
votes
1answer
47 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 ...
1
vote
1answer
281 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 ...
-2
votes
1answer
212 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 ...
2
votes
1answer
61 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 ...
1
vote
0answers
57 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 ...
0
votes
0answers
13 views

General structures / algorithms for parsing / interpreting a semantic query efficiently

If you have a semantic/meaning graph data structure built up, and you get a new word as part of a sentence, the question is, how it optimally determines the meaning of that new word. It seems that, ...
4
votes
4answers
348 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 ...
0
votes
1answer
75 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 ...
1
vote
1answer
308 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-...
0
votes
1answer
122 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 ...
-1
votes
1answer
555 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
vote
1answer
154 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 ...
1
vote
4answers
959 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 ...
0
votes
1answer
83 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 ...
0
votes
1answer
368 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 ...
1
vote
2answers
85 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 ...
1
vote
1answer
79 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, ...
0
votes
1answer
118 views

Algorithm for graphing heap data from server memory, over long period of time

Right now I am collecting memory information on a node.js server every 100 seconds. I want do display the memory usage info as a graph on the front end. const mem = { heapTotals: [], heapUseds: []...
5
votes
3answers
308 views

How to implement the travelling salesman algorithm with dependecies between locations

Is there a way to implement the traveling salesman or purchaser algorithm with constraints between locations? For example, I have to grab item X before item B, c before D and F,G,H in any order.
0
votes
0answers
37 views

Correct way-data structure for advertising peers in a p2p network

Underlying problem In a case of a peer-to-peer discovery protocol,suppose we need to advertise peers in a manner that the network graph will grow such that we avoid cases of both too dense areas (e.g ...
2
votes
2answers
154 views

Algorithm to select sets of objects while maximizing number of objects covered

If we have different objects, [A1, A2, A3, B1, B2, B3, B4, B5] Some calculations will be performed to find compatible objects. For example, lets assume following 3 sets were formed and every set ...
6
votes
1answer
176 views

Toll placement problem (Graph theory)

I'm working on a problem that reduces to something like toll plaza placement on a set of highways. Given a large undirected graph and a list of node pairs with a toll value between them, I need to ...
1
vote
1answer
94 views

Distributed BiPartite Graph [closed]

I have a use case where I have a Bi-Partite Graph. Call one type of nodes "Type A" and the other "Type B." Now when a Type A node gets added, it forms some edges based on a criterion with Type B nodes ...
3
votes
2answers
300 views

Is there any point in a digraph implementation?

The Foreword Hi! I'm just your average, fairly beginner, computer science student doing personal programming side projects, and who is probably out of his depth and has no clue what he's doing. So, I ...
0
votes
0answers
94 views

Quick way to check if there is a path in digraph

I have a finite directed graph (of several weakly connected components). Having two elements I need to check if there is a path from the first one to the second one. The easiest solution is to ...
25
votes
3answers
5k views

How to find the shortest path with wormhole nodes?

This is an example of what I want to do via code. I know you can use jump point search to easily get from the green node to the red node with no problems, or even A*. But how do you calculate this ...
0
votes
2answers
94 views

Efficiently computing and storing global state

I am working on a graph problem which is special in the sense that the nodes are computed only when required. This is because the graph is so huge that the entire graph won't fit in memory. So, in my ...
-7
votes
1answer
159 views

Finding the side trip [closed]

The following question is from Introduction to Software Testing by Paul Ammann and Jeff Offutt. Consider the simple path [3, 2, 4, 5, 6] and test path [1, 2, 3, 2, 4, 6, 1, 2, 4, 5, 6, 1, 7]. ...
2
votes
0answers
92 views

What are good ways to represent “requirements” and “cannot-have” connections?

In the context of creating an ecosystem, the graph below reveals information about it's behavior. Dot : A node with the entity's name. There's a tree, grass, a fern, etc. Blue arrow : A requirement. ...
1
vote
1answer
172 views

Moving from Batch to Streaming architecture using a Graph datastructure

The use case I am trying to solve is, assigning millions of users to their groups/segments. I have thousands of different criteria from which buckets of users are created. E.g. bucket criteria: All ...
1
vote
1answer
684 views

Finding the shortest path in a fully-connected undirected graph

I am trying to solve a problem in which I have a list of two-dimensional coordinates, and I want to find the shortest path that connects all of them. At first I thought this was a case of the ...
5
votes
1answer
113 views

What is the fastest algorithm to find what point of Type 1 is closest for each point of Type 2 on a rectangular grid?

In my contrived example, I have a rectangular grid of nodes, where each node is either empty, of Type 1 or of Type 2. All nodes are directed to the eight nodes around them (horizontal, vertical, ...
1
vote
1answer
266 views

Finding the minimum transaction

Given a list of transactions like: A -> 10 to B B -> 10 to C The naive way to settle the transaction would be: C owes 10 to B B owes 10 to A But the same transaction could be settled by: C ...
0
votes
1answer
576 views

Two-center algorithm to find minimum of farthest point

I'm trying to come up with an algorithm that allows me to find two vertices in an undirected, weighted graph that minimizes the distance to the farthest point. Distance of the farthest point is ...
-2
votes
2answers
98 views

Shortest path common core(s) question

I'm not sure whether I'm using the correct terminology here. I'm trying to come up with an algorithm that let's me find a vertex in an arbitrary graph so that the vertex has minimum distance to the ...
3
votes
2answers
3k views

Suitable data store for storing comments in a social media site

I have been developing a blogging site, where people can post an article or blog and others can comments on them. The site is coded in Angular.js, ASP.NET and SQL is being used a data store. For each ...
3
votes
3answers
96 views

Say we have a group of N person, and each person might want to sell or buy one of the M items, how to find a closed path among them for an exchange?

Say we have N persons and M items (when a person has a certain item, she usually only has one piece). For example, person 1 has item A, C, D, and wants item F person 2 has item B, C, and wants E ...
0
votes
2answers
173 views

Searching, storing, and finding graph attributes and vertices

I've been reading the 3rd edition of [Algorithms][1] by Cormen, Leiserson, Rivest and Stein. For DFS and BFS their algorithm loops through all the vertices first and colors them white. 1) If the ...
0
votes
1answer
516 views

How can I create a set of pixel coordinates for a line in Python?

I've got some code that's searching pixel by pixel from a starting point, at a certain angle, until it finds a pixel (a non-white pixel) It only has to search around 300 pixels: I'm currently using ...
6
votes
1answer
336 views

Mixing heuristic functions in A*

I have applied a custom heuristic to my A* search. It is admissible, but it is not consistent (monotonic). As such, I am not guaranteed to find the shortest path. I had assumed I could use a hybrid ...
2
votes
2answers
101 views

Algorithm to design a graphic of a set of connections between nodes

Lets imagine I have points in a 2D plane that I want to connect in a directionless graph. However, I don't want these connections to overlap. The only data I'm given is where a connection exists, and ...
6
votes
1answer
141 views

How to describe a set of paths in a graph with as few nodes as possible?

I have modeled a problem as a graph that consists of many trees. Some of the nodes in the graph may belong to more than one tree. I am trying to describe a subset of paths in the graph with as few ...
4
votes
2answers
4k views

Graph database keeping historical relationships

I'm starting the modeling of the following problem: I have many clients (millions) that interact in a network forming a graph. At the highest granularity of my business problem, each realationship ...
1
vote
0answers
477 views

efficient graph clustering algorithm for weighted directed graphs based on node and edge weights

I'm looking for an algorithm to cluster weighted directed graphs that have weights on both edges and vertices. I'm using graphs with multiple weights(labels) on vertices and a weight on edges that ...