Questions tagged [graph-theory]

A graph is a mathematical structure that contains a collection of vertices or 'nodes' and a collection of edges that connect pairs of vertices. Graphs can be undirected or directed, where edges are directed, indicating from which vertex they start and to which they lead ( be it other or the same ).

Filter by
Sorted by
Tagged with
0 votes
0 answers
30 views

Longest common Subsequence generalization for N lists (for merging)

The goal I have several data from different CSV files, that I want to merge in a single one, preserving as much as possible the order of the columns. Say the first file has columns [A, B, D] and file ...
cube45's user avatar
  • 3,349
0 votes
0 answers
11 views

Do git commits with fast-forwards form a DAG that is its own transitive reduction?

This question elucidates that git commits form a DAG, not necessarily a tree. A DAG that is not a tree results from a merge commit, which will have multiple parents. Is it fair to say that when Git is ...
LastStar007's user avatar
-1 votes
0 answers
19 views

Best library or best practice for implementing a visual automation flow builder with a tree structure in React? [closed]

I want to build a visual automation flow builder in React that involves a tree structure. Each step in the flow can have zero to multiple successor nodes. I'm looking for recommendations on the best ...
Marcus Biel's user avatar
0 votes
1 answer
124 views

Generating Cell combination (By sizes) on grid using pathfinding algorithm

I'm working on a project and as part of my process, I need to generate all the possible cell combination for given start point while avoiding the invalid cells (The cells filled with black. see down ...
Oriel Swisa's user avatar
0 votes
0 answers
11 views

How to implement SIR model for node ranking in graph?

I am working on node ranking in complex networks. I have heard about the SIR (susceptible-infected-recovered) model in graphs that measures the infection power of each node as its spreader and ...
Orca's user avatar
  • 443
0 votes
1 answer
26 views

How to correctly generate CNF formulas for building a maze?

I want to build a maze using sat solver. Please help me to correctly compose the algorithm for generating conditions. I tried to implement some conditions, but they turned out to be wrong. This ...
Defqon's user avatar
  • 1
-3 votes
0 answers
25 views

How should I store many **independent** graphs? Database design suggestions? [closed]

I need to store many independent graphs: Each graph with 2 to 1000+ nodes Each node with 1 to 7 edges (capable of storing information that represents how the two nodes are related) I intend to ...
soverflow's user avatar
1 vote
0 answers
13 views

Can you give me adjacency list of a graph whose BFS and topological sort are not equivalent?

Can you give me adjacency list of a graph whose BFS and topological sort are not equivalent ? I visualze them the same way but googling if they both are same never quite provided a satisfactory ...
Mohak Gupta's user avatar
-3 votes
2 answers
123 views

Matrix Circuit Analysis using Algorithms [duplicate]

I made a code for checking the relationships of resistors to determine if they are in series, parallel, or just neither. Our instructor gave us test cases that we have to satisfy however I passed all ...
Hezekiah Derilo's user avatar
0 votes
0 answers
31 views

How do I find BFS traversal of a graph with adjacency matrix using C program? [closed]

Given an undirected graph, find the Breadth First Search (BFS) traversal of a graph. Consider the graph having N number of nodes and E number of edges. The vertex (node) of a graph is labeled as ...
NISHITHA CHOUDHARY NP's user avatar
0 votes
2 answers
42 views

Network Edge Load Calculation

I am trying to calculate the edge loads of a (power grid) network but am stuck and can't figure out the right implementation. Given the following data structure: export type Network = { readonly ...
Reborok's user avatar
  • 25
1 vote
1 answer
41 views

It is necessary to make a random sequence of the route

I have 3 databases in Base(1) containing data about cities FROM which I need to make a trip. For simplicity, let's call them POINTS FROM. There is also Base(2) which contains cities TO which I need to ...
user21992995's user avatar
0 votes
0 answers
12 views

How do I extend the Load JSON example from vasturiano to include images as nodes

On vasturiano's page about his force-directed HTML5 graph is an example that uses images as nodes in a random graph. I want to extend the example and load my own graph from a JSON file. In the first ...
ChernoBeta's user avatar
-2 votes
2 answers
51 views

setInterval problems with function

I'm trying to draw visual representation of sorting algorithms. Bubble Sort is working fine, but Selection Sort don't care about how much time I put in the setInterval timer, he runs on the same speed ...
Patryk Smoliśki's user avatar
0 votes
1 answer
28 views

How do I traverse a path where I can visit the same nodes several times with a break condition of time

I need to write an algorithm that finds the optimal solution when the conditions are these: I have ratings of cities and the time it takes to travel between two cities (not every city has a direct ...
Hex's user avatar
  • 1
-1 votes
2 answers
54 views

Minimum Edge required to connect a unconnected directed graph

I am trying to write an algorithm that finds the minimum number of edges that are required to be added to connect all nodes from the starting vertices in a directed unconnected graph #include <...
BlueBerryPie's user avatar
11 votes
4 answers
394 views

Merging users with multiple refs and count their collective assets

There is a set of users. A person can have multiple users, but ref1 and ref2 might be alike and can therefore link users together. ref1 and ref2 does not overlap, one value in ref1 does not exist in ...
Bjørn Bråthen's user avatar
0 votes
2 answers
77 views

How to prove that every (finite) tree contains at least one vertex with degree 1 in Lean?

How to prove that every (finite) tree contains at least one vertex with degree 1 in Lean? I'm currently using the combinatorics.simple_graph.connectivity import. I've defined a vertex of degree one as ...
Timothy's user avatar
-2 votes
0 answers
38 views

Making of SDNF relying on DNF

The task is to get SDNF from DNF of a graph adjacency matrix. Global task is about finding maximal internally stable sets of graph with Magu method. Example: Given and adjacency matrix of a graph: 0 1 ...
cucurbita's user avatar
1 vote
1 answer
34 views

BFS(breadth first search) compiler output is not following as per my understanding

I have python code for Breadth first search (bfs): from collections import deque def bfs(graph, start): visited = set() queue = deque([start]) # print('queue',queue) while queue: ...
Shreeya Sharma's user avatar
0 votes
1 answer
27 views

How to Build and test if a graph data structure is outputting the correct adjacency vertexes WITHOUT the use of lists or dictionaries

I'm trying to build a graph data structure in Python, only something basic - but I'm having trouble testing if each vertex recognizes other vertexes are adjacent or not. I know how to do this with the ...
GDTeam's user avatar
  • 1
0 votes
0 answers
15 views

What is the difference between the tree-cut decomposition and tree decomposition?

if i want to find the cut-width and tree-width, and compare them. Therefore, in the following example how the tree-cut decomposition and tree decomposition would look like? graph as far as i ...
Mohamed Nadeem's user avatar
4 votes
1 answer
70 views

How can I use the C++ Boost Graph Library (BGL) to find isomorphic graphs?

Using C++ Boost Graph Library (BGL) to Find Isomorphic Graphs See graphs. I want to get the graphs which are isomorphic (respecting the type - A/B). Of course, all graphs which have not the same ...
michael's user avatar
  • 43
0 votes
1 answer
54 views

How can we interpret the graph information after certificate in Pynauty?

Cross-posted on pynauty_read_certificate. Pynauty is a Python/C extension module using library components from the Nauty package by Brendan McKay. In Pynauty, the function certificate can compute a ...
licheng's user avatar
  • 117
4 votes
2 answers
64 views

Get shortest distance from src to all nodes optimization

I have an input as [][]edges. The col length of array is 2. Each row of the 2D array hence has 2 elements. Each element is a vertex. And it is bidirectional i.e we can say the edge is in both ...
curiousengineer's user avatar
0 votes
2 answers
52 views

Dijkstra's algorithm for bus route (prioritise on fare price)

I am struggling with a Dijkstra's algorithm problem with two costs: time and fare price. Assume there are flat ticket rate for each bus route(could differ between different routes) and between two ...
Karen Azuma's user avatar
1 vote
1 answer
104 views

How can I combine Group Identifiers into Single Group?

I have a dataset as follows: ;WITH CTE AS ( SELECT * FROM (VALUES (1, 10, 20, 30) (2, 10, 21, 31) (3, 11, 21, 31) (4, 12, 22, 32) (5, 13, 23, 33) (6, 14, 24, 33) (7, 14, 25, 34) (8, 15, 26, 36) ) AS ...
Danny Rancher's user avatar
0 votes
1 answer
36 views

Solving algorithm for a "rotating pipes game"?

me and my friends are realising a game for our school project. The goal is to create a puzzle grid game with a solver. Our game will look like that in the idea : it's the best video I found. So with ...
Destro122's user avatar
2 votes
1 answer
55 views

Error in Wikipedia pseudocode for Prim's Algorithm?

So I'm looking at the Wikipedia entry on Prim's algorithm: 1. Associate with each vertex v of the graph a number C[v] (the cheapest cost of a connection to v) and an edge E[v] (the edge providing that ...
MikeTheTall's user avatar
  • 3,166
0 votes
2 answers
54 views

generating solvable puzzles for a Double-Choco puzzle game. efficient data structure and algorithm to be used in?

I'm working on implementing a puzzle board game called Double-Choco published by Nikoli magazine Where the board is a 2-dimensional matrix with cells that are either white or gray. The goal is to ...
Muhammad Z's user avatar
-1 votes
2 answers
60 views

Find a group of unreachable nodes (from each other)

Let there be a directed Graph G. U is a set of 'black' vertices in G Such That: Every element of G\U (whites) has a path to a black vertice. There is no path between any elements of U( black). Give ...
Nati Shen-Gordon's user avatar
1 vote
1 answer
23 views

Finding all possible connections between two disjoint hierarchical trees

I am looking for the best data structure to store two hierarchical trees, where my aim is to find whether all the possible connections between these two trees are covered. I will describe my problem ...
Pranav Rai's user avatar
1 vote
1 answer
44 views

Creating a timetable from two lists. One of availability of interviewers and the other of preferences of interviewees

I'm pretty sure this is a well studied problem and that there is some algorithm but I'm just not searching the right terms to find it. I have two lists, one of a list of candiates and their preference ...
asparamancer's user avatar
-2 votes
1 answer
40 views

minimum distance using dfs [closed]

#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX_LENGTH 100 #define INFINITY 99999 typedef struct { char source[MAX_LENGTH]; char destination[...
mami's user avatar
  • 1
0 votes
1 answer
68 views

Shortest Path DFS

Continuing my education of graph theory, I started to tackle the Maze II problem There is a ball in a maze with empty spaces (represented as 0) and walls (represented as 1). The ball can go through ...
Spindoctor's user avatar
0 votes
0 answers
45 views

Dummy node for TSP and finding shortest Hamiltonian Path

Can anyone provide assistance to the problem I'm facing? I'm working on implementing a delivery system algorithm. I have attempted to solve it using a graph, where addresses are represented as nodes ...
IlayAsayag's user avatar
1 vote
1 answer
57 views

Path planning using an occupancy grid with specific constrains

I have a binary occupancy grid representing an environment where zeros denote empty spaces and ones denote walls. I need to plan a path for a differential wheeled robot with a cylindrical shape. ...
Tonak's user avatar
  • 11
0 votes
0 answers
57 views

Why Gale Shapley matching algorithm third iteration is not executing?

I am executing the following code of Gale Shapley matching algorithm in python, first two iteration are working fine but third iteration system stuck in loop. Kindly help to identify and resolve the ...
comsian's user avatar
  • 159
0 votes
0 answers
34 views

astar algorithm is expanding like bfs . where is my failure?

I am currently working on a project to visualize different graph search algorithms. I have implemented an A* algorithm, but for some reason, it seems to be expanding nodes in a similar manner to the ...
dilsoziya's user avatar
-1 votes
0 answers
15 views

Gephi color different area

When i did the literature review about Gephi, the researcher colored the different zone, which shown below. Does anyone knows how to achieve that? I tried to do that with same layout but failed. Thank ...
RONG FU's user avatar
0 votes
0 answers
40 views

Is this a maximum leaf spanning tree? [migrated]

This is non-oriented weightless graph. I need to find the maximum leaf spanning tree for this graph. Am I made a correct maximum leaf spanning tree like in this pic , or not? Thank you for the answers....
Liuzili's user avatar
  • 17
1 vote
2 answers
59 views

Efficient Node Grouping Technique for Centrality Calculations in Graphs

I'm working on optimizing some code that involves frequently accessing values associated with the centrality of each node in a graph. Since nodes with the same neighbors have the same value in my ...
Osamodas's user avatar
0 votes
1 answer
116 views

Modified TSP with Branch-and-Bound algorithm

I've been struggling to solve it using branch-and-bound to find the optimal path for the next task: There's a list of cities, that are all connected with each other, basically, a complete graph, each ...
unfavourite's user avatar
-3 votes
3 answers
53 views

How we can determine Bipartiteness in apache age graph?

A graph is bipartite if and only if it is 2-colorable. Again A graph is bipartite if and only if every edge belongs to an odd number of bonds, minimal subsets of edges whose removal increases the ...
MAHMUDUL's user avatar
0 votes
1 answer
31 views

Gale Shapley matching algorithm with Polygamy by Men Upto four Marriages Using Bipartite Graph

How to modify Gale Shapley matching algorithm with Polygamy by Men Upto four Marriages Using Bipartite Graph I want to add weights to each node of bipartite graph based on certain criteria for example ...
comsian's user avatar
  • 159
1 vote
1 answer
76 views

How to code Dijkstra's algorithm with a specefic visited node constraint in Matlab?

I'm trying to implement Dijkstra's algorithm for finding the shortest path with a node constraint in Matlab. Specifically, I want to force the path to go through a given set of nodes. I have an ...
abdoessordo's user avatar
1 vote
2 answers
32 views

How do I generate (and hence find total possible) non-isomorphic, trees which has binary and 3-ary intermediate nodes given exactly "L" leaf nodes

With the following input conditions One root node which which can have only 1 output There are a fixed/finite set of exactly "L" leaf nodes, say 20 The intermediate nodes can be chosen ...
Parthasarathy SRINIVASAN's user avatar
1 vote
1 answer
40 views

Pathfinding on a grid while blocking cells online

Suppose we have a N*N grid with start and end points A and B, and we're given K < N^2 queries online telling us to block a cell on the grid. We want to find and output the shortest path between A ...
Mark Zhou's user avatar
2 votes
1 answer
37 views

Plotly: Make a plot that doesn't change proportions when zoomed in

I'm making a custom plot using Plotly for representing a condensed complete directed graph. I've worked hard to get the shapes right and it's still a work-in-progress. However, I noticed a problem: ...
Ram Rachum's user avatar
  • 83.1k
0 votes
1 answer
49 views

How to change a directed graph into a complete graph by deleting nodes, and keep as many nodes as possible?

Here, a complete directed graph is defined as a graph in which every edge has a direction, and every two vertices are connected by two edges with opposite directions, and the vertex has one edge to ...
Levelower's user avatar

1
2 3 4 5
85