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
1answer
121 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
116 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
41 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
227 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
201 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
59 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
56 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
325 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
64 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
217 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
121 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
418 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
935 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
75 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
298 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
84 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
72 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
106 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: []...
4
votes
3answers
257 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
35 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
153 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
169 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
85 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
288 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
90 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
138 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
88 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
168 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
628 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
112 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
252 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
538 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
97 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
2k 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
94 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
168 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
487 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
305 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
100 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
140 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
3k 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
453 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 ...
3
votes
0answers
136 views

Finding subgraphs in non-directed graph

Problem at hand: Finding separate subgraphs. Update on adding or removing edges. First I've been thinking about running DFS after every operation from both ends of the edge, but if I keep ...
1
vote
1answer
152 views

What Graph Theory approaches or algorithms are useful for designing a House?

I have a set of data about a family, and I want the software to find a house design that fits the data (which includes stuff like preferences and whether they want a pool. The current way I am going ...
0
votes
1answer
313 views

The maximum number of induced cycle in a simple directed graph

Given a simple directed graph G=(V,E) an induced cycle is a cycle where no two vertices of the cycle have an edge that is not in the cycle. (Chordless cycles are induced cycles with at lease 4 ...
4
votes
1answer
785 views

Are there multiple Hamiltonian Paths on a Graph?

Can anyone suggest an algorithm for this problem. Given an undirected unweighted cyclic graph, and a given start and end node in that graph, I'd like to determine if there is exactly one valid path ...