Stack Exchange Network

Stack Exchange network consists of 174 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

-3
votes
0answers
32 views

Graph clustering based on the attributes in nodes and edges [on hold]

I am looking for a clustering algorithm that can cluster network based on attributes in edges and nodes at the same time. Could you help me if you have anything in your mind?
-2
votes
1answer
74 views

Calculating longest trip [on hold]

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
48 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
53 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
12 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, ...
3
votes
4answers
207 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
52 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
108 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
111 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
221 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
150 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
842 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
67 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
145 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
82 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 ...
0
votes
0answers
44 views

How to schedule ordered pairs from a set uniformly over a given number of dates separated as two sets

I'm working on a personal project in which I have a set of (at least 1) entities and two disjoint sets of dates. I need to assign ordered pairs of the entities to the dates. I don't care about which ...
1
vote
1answer
63 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
0answers
67 views

Assigning Tags to obtained Coordinates with respect to Ideal Coordinates

I need an idea to solve the following problem statement. Here we will have two sets of coordinates. Set 1 will have the ideal coordinates with Tags assigned to it which will be as below. Set 2 will ...
0
votes
1answer
91 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
204 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
32 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
147 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
149 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
72 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
254 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
79 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
93 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 ...
-6
votes
1answer
117 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
82 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
161 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
485 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
111 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
220 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
466 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
96 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
151 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
444 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
244 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
139 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
418 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
120 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
141 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
290 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
711 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 ...
1
vote
1answer
1k views

Yen's k shortest paths algorithm

I'm currently trying to understand Yen's k shortest paths algorithm. I based myself on the original paper as well as on the Wikipedia article, but still cannot see why it is correct if k > 2. In fact, ...