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
7 views

Push–relabel algorithm, proof of correctness for source height initialization to N-2

I am to prove that Goldberg's push-relabel max flow algorithm will work correctly even if we set the source node height to N-2, where N is the number of nodes (including the source and the sink). ...
Ava Miller's user avatar
0 votes
1 answer
22 views

What are the minimum number of data points required to construct a meaningful minimum spanning tree (MST)? [closed]

I possess a collection of 60 data points and am interested in applying the Minimum Spanning Tree (MST) algorithm to this dataset. Can the MST derived from this data offer valuable insights? Does the ...
Rian's user avatar
  • 111
0 votes
1 answer
32 views

How to draw every possible paths from a bi-directional state machine diagram using NetworkX Library in Python?

I have the state machine model of a system which has some nodes(states) and some edges(transitions). Some of the transitions are bi-directional. For example, one transition from 'State_B' to 'State_C' ...
jenil pandey's user avatar
-2 votes
0 answers
32 views

A faster approach to 4x4 Magic Square of Squares? [duplicate]

Problem Description: I'm tackling a computational challenge involving a 4x4 magic square of squares. The goal is to ensure that the sum of squares in each row, column, and both diagonals equals a ...
Ansar's user avatar
  • 1
0 votes
1 answer
34 views

Is there a way to graphically represent that the parent node can only be dark green if all its children are dark green? [closed]

For the user interface of my application, I'm designing a hierarchical tree structure with nodes that always have multiple children. Each node represents something like a task and the color of each ...
Zach Williams's user avatar
1 vote
0 answers
40 views

Greedy algorythm for rich-neighbor edge coloring of a graph [closed]

In an edge coloring, an edge e is called rich if all edges adjacent to e have different colors. An edge coloring is called a rich-neighbour edge coloring if every edge is adjacent to some rich edge. ...
VlakecTomaz's user avatar
2 votes
1 answer
57 views

Optimization trading items - min cost max flow

There is n items, . I have n items, but some duplicates and some are missing, I need to have exactly one of each item. There is given a trade-table that tells which items can be traded for others. For ...
popcorn's user avatar
  • 69
0 votes
0 answers
34 views

Set of necessary cuts out of subset of edges to make node unreachable

I'm interested in finding the possible sets of edges that must be cut from a directed graph to disconnect a node from the source, but only certain edges can be cut. I need to find the necessary ...
base12's user avatar
  • 125
1 vote
0 answers
20 views

Editing a clique into a k-plex optimally is NP?

A k-plex is a graph in which every vertex is adjacent to all but at most k vertices within the graph. Say I have a complete, undirected, weighted graph (a clique and also a k-plex), and I want to ...
Mamiglia's user avatar
  • 118
0 votes
1 answer
37 views

Finding the smallest subset possible of the vertices in common with the rest of the graph

I have to write a code such that it returns the size of the subset which contains a set of vertices such that each edge has at least one of its two ends points in this set. This is called a vertex ...
ABC123's user avatar
  • 21
0 votes
0 answers
11 views

Edge Addition: Item subset selection problem (Knapsack?)

I have a set of n edges, e-star, which is the set of valid possible extra edges to an existing graph, G(v,e). I want to minimise the median route path length across the network from a central point, c,...
sploopst's user avatar
1 vote
0 answers
22 views

Bug inside Prim's MST algorithm in Java using Adjacency Matrix

I'm trying implement Prim's Minimum Spanning Tree Algorithm of a graph represented using Adjacency Matrix in Java. The code is running successfully, but not able to generate expected output. The ...
Sree Teja's user avatar
-1 votes
0 answers
120 views

Why is a HashSet allowing duplicates even though they're the same? [duplicate]

I'm writing a library for graphs (graph theory) and I'm currently working on an undirected simple graph. As such, I want the edges in a Set since there shouldn't be any duplicates allowed. Graph.java ...
Kelavandoril's user avatar
-3 votes
0 answers
58 views

Why not n^2 comparisons in the Alien Dictionary problem on GFG? [closed]

Here's the problem statement (as given on GeeksForGeeks website): Given a sorted dictionary of an alien language having N words and k starting alphabets of standard dictionary, find the order of ...
Anurag Prasad's user avatar
1 vote
0 answers
52 views

Pure numpy implementation of Watts-Strogatz Algorithm

I want to write a pure numpy implementation of the Watts-Strogatz random graph generation algorithm. Below is a function which uses numpy functions to select and remove appropriate edges, and find all ...
Diyar's user avatar
  • 11
0 votes
0 answers
18 views

DFT IN GRAPH i want to do dft traversal but i am getting error

#include<iostream> using namespace std; struct arc; struct ver{ char data; bool processed,inque,intree; ver* nextvertex; arc* firstedge; }; struct arc{ char data; float ...
Vishwa Mars's user avatar
0 votes
1 answer
98 views

Is there a specific name of algorithm for this kind of problem? [closed]

Given three positive number n, x and y. Player A know x + y and player B know x * y. Each player takes turn to guess x and y (x, y <= n). Player will say "I don't know" if they cannot ...
Đức Huy Hoàng's user avatar
0 votes
0 answers
38 views

Modeling Graph Neural Networks for Multi-edge graphs (multiple edges between 2 nodes)

I want to create Graph Neural Networks that can deal with heterogenous graphs (1 node type, multiple edge types) that allow multiple edges between 2 nodes. For example, I have a set of similar graphs ...
John's user avatar
  • 175
0 votes
1 answer
37 views

Variation of TSP which needs to visit only a set of cities but can visit cities outside the set if necessary

I need to solve a variation of TSP where nodes represent neighborhoods. Neighborhoods can be central or non-central. Starting from a non-central neighborhood I need to find the shortest path that ...
julio meza's user avatar
1 vote
1 answer
15 views

How to do random BFS traversal in networkx?

I want to implement a BFS traversal algorithm on large graphs in a random order (has to be as fast as a normal BFS traversal). Here is the code snippet that I have: def perform_random_bfs(self, g, ...
Kapil Agrawal's user avatar
2 votes
0 answers
74 views

Partitioning bipartite graphs into bicliques

Is there an efficient (say in O(|V|^2)) and preferably not overly complicated algorithm for dividing a bipartite graph into the smallest possible number of bicliques? The vertices can repeat, so that ...
de_michael's user avatar
1 vote
2 answers
62 views

How can I visualize subset of a network in Cytoscape?

I created a network using separate node and edge files generated from WGCNA. The network has 381 nodes and over 20K edges. I would like to learn how to subset the giant network that zoom in to one ...
Abel Bel's user avatar
0 votes
1 answer
72 views

Converting a DAG where the nodes represent tasks and the connections represent dependencies into something suitable for parallel computing

I've got a DAG (Directed Acyclic Graph) derived from a sparse strictly-lower-triangular-square-matrix. There is a task associated with every row of the matrix. The matrix entries are dependencies -- ...
Frank Puck's user avatar
0 votes
2 answers
33 views

Applying graph data structure to recipes in a game about combining elements

I am designing a game where the player combines two ingredients to create a new element, which can then be used as an ingredient to create even more ingredients. It really seems that a graph structure ...
bit_n's user avatar
  • 31
1 vote
1 answer
37 views

How to resolve Horn clause-like tag implications with Django and Postgres database

I am creating a content system with Django where users can create and publish content. Each document created by the user can have multiple tags. I am designing a tag implication system where some tags ...
user512716's user avatar
-1 votes
0 answers
44 views

Retracing negative weight cycle in Bellman Ford algorithm

I have implemented the Bellman-Ford algorithm to detect a negative weight cycle, however what I am more interested is back tracking the actual path itself. My current implementation looks like this. I ...
GVB's user avatar
  • 1
0 votes
0 answers
18 views

How to detect any cycles in lisp list

I am thinking about the problem of detecting cycles in lisp lists (based on cons cells). Traditional cycle detection algorithms like Floyd's (Tortoise and hare) or Brent's algorithm all assume that ...
Prgrm.celeritas's user avatar
0 votes
2 answers
31 views

Converting a graph to another graph by using operations

guys! I am stuck with a graph problem I saw 3-4 days ago. It is from the Open Russian Olympiad in Informatics 2004, Tver. You are given two graphs. Each graph consists of N nodes and M edges. You need ...
Chep13's user avatar
  • 1
0 votes
1 answer
44 views

count of the maximum number of paths in a graph

Have a graph - V, E = V^2, Now, I have written a DFS algo which visits all paths in a graph, but i am not able to find its time complexity because i dont know the count of the maximum number of paths ...
user123456's user avatar
0 votes
1 answer
96 views

"Check if a cycle of K nodes exists" reduction to SAT?

I got the following problem statement: "Given a undirected graph, check if a cycle of K nodes exists." And I want to take any input and convert it to a Conjunctive Normal Form formula for ...
Josué Pedrajas's user avatar
1 vote
0 answers
89 views

Wrong dominance frontier

My problem is probably misunderstanding of dominance frontier algorithm. I am implementing SSA form according to this paper: https://c9x.me/compile/bib/ssa.pdf It seems my algorithm for computing ...
weak's user avatar
  • 11
0 votes
2 answers
113 views

Solving problem of assigning people to duties for particular time slot

I am trying to solve the problem where I have number of people with few duties each one and the dates where the various duties have to be performed. For example: John can be Teacher and Cleaner ...
janci's user avatar
  • 233
0 votes
1 answer
25 views

Node induced subgraph matching with networkx

I'd like to perform node-induced subgraph matching, which do not need to be fully connected, including node and edge attribute matching with networkx (see this image). Let's say I have a large graph ...
strukturen's user avatar
0 votes
1 answer
97 views

How to efficiently find pairs of nodes in a graph that when removed will cause the graph to split?

Consider this simple biconnected graph (graph without articulation points): import networkx as nx G = nx.diamond_graph() nx.draw(G, with_labels=True) I want to find out what two pairs of nodes when ...
Saravana's user avatar
  • 38.4k
1 vote
1 answer
39 views

Propagating traits in a directed graph

I have a graph (<1 million vertices) with directed edges. The graph is probably disconnected and may contain loops. There may be edges going both ways between two vertices. Each vertex can have 0-3 ...
Torn's user avatar
  • 316
1 vote
1 answer
34 views

Is it necessary to have an optimal action at node R to prune a branch in alpha beta pruning?

The image shows a tree where there is no optimal action at R. If the utility at the * branch is 8 or lower the best action at R would be to go left. If the utility of the star branch is 9 or greater, ...
Kabir Thakur's user avatar
0 votes
1 answer
42 views

Add a line to a histogram to show the power law distribution in julia

I have a value and plot a histogram like this (log-log scale): The code for the histogram is as follows: histogram(log.(degree), bins=50, yaxis = (:log10)) title!("Degree distribution (log-log ...
Chao's user avatar
  • 49
0 votes
0 answers
65 views

finding cycles in directed graph using algorithm design manual

so, i am following algorithm design but the below algorithm implemented from the book, fails in the following e.g., is there an issue with this algo - bool directed = true; bool dfs(...
user123456's user avatar
1 vote
1 answer
35 views

visualize mesh of polygon neighbors with tmap

I'm trying to make a map like the one below, using the {{tmap}} package. That image is from Michael Harper's excellent blog post. It was made using the plot() function, as shown below. # Loading ...
John J.'s user avatar
  • 1,578
-2 votes
1 answer
72 views

Minimum buses required so that all passengers can reach stop 1

Given a city with N bus stop and N-1 roads. All the city bus stops are reachable to each other via connecting roads. A stop can have value 0 or 1. 0 represents that there is no passenger at this stop, ...
snowcoffeebean's user avatar
1 vote
2 answers
59 views

Remove a vertex from a connected graph to obtain a connected subgraph

I have the impression that if I take a simple, connected graph then I can (provided it has a vertex number greater than or equal to 2) remove a vertex and obtain a connected subgraph. This doesn't ...
Ftyupl's user avatar
  • 79
0 votes
0 answers
38 views

Can pytorch geometric be used to predict edge labels?

I am looking to solve a toy problem. I have a numbers of graphs where each vertex has a few attributes e.g. (x, y, z) and I'm looking to train a model that can assign a label ('horizontal', 'diagonal',...
nickponline's user avatar
  • 25.4k
0 votes
1 answer
43 views

Dynamically computing `edge_index` with k-hop neighbours

Given that I have a torch_geometric graph with a given connectivity, e.g. edge_index = torch.tensor([[0, 1, 2, 3, 2, 0], [1, 0, 3, 2, 0, 2]], dtype=torch.long) I would like ...
James Arten's user avatar
0 votes
1 answer
31 views

How to find the ideal topological ordering (fewest steps as explained in description below)?

Given a network of N computers, there are N-1 cables that connect the computers into a tree. A message is passed to computer 1 and it will propogate it to its neighbouring computers and so on until ...
snowcoffeebean's user avatar
0 votes
0 answers
63 views

Logic behind Tarjan's Algorithm for finding articulating points

GetArticulationPoints(i, d) visited[i] := true depth[i] := d low[i] := d childCount := 0 isArticulation := false for each ni in adj[i] do if not visited[ni] then ...
Hodgson Tetteh's user avatar
3 votes
2 answers
85 views

Finding the Largest Partition of Non-Connected Nodes in a Graph in polynomial time

I have a graph, and I want to determine the largest possible set (or partition) of nodes such that no two nodes within this set have an edge between them. I am looking for an efficient algorithm to ...
LargeHorse's user avatar
0 votes
0 answers
18 views

Minimum Spanning Tree algorithm with n connected components

During the process of Kruskal, the number of connected components in the graph decreases by 1 each time we add an edge. Let's say during the running of Kruskal, there are 3 connected components and ...
Mingxuan Zhao's user avatar
0 votes
1 answer
62 views

Model flow network

There are n people, some of them hold key. There are ⌈n/5⌉ doors, to open each door, at least two of those people who have key have to be at the door. A max of 5 people can go to one door, each people ...
Grandmarkkk's user avatar
1 vote
1 answer
39 views

Uniquness of a graph. Why do we need to add e1 to B to create a cycle?

If each edge has a distinct weight then there will be only one, unique minimum spanning tree. This is true in many realistic situations, such as the telecommunications company example above, where it'...
John Stuart's user avatar
2 votes
0 answers
40 views

How best to represent 3-uniform hypergraphs (triple systems) for efficient clique cover search

How can I best represent a 3-uniform hypergraph on n vertices, for purposes of finding the minimum clique cover or a close approximation of it? This may sound like a math problem but it isn't; the ...
Dave's user avatar
  • 8,022

1
2 3 4 5
88