Questions tagged [dag]
For questions about the usage and manipulation of Directed Acyclic Graphs (DAG).
138
questions
0
votes
0
answers
61
views
Using topological sort to find inconsistencies represented by cycles in directed graphs
Consider the following scenario.
Let $x_1,...,x_n$ be a group of cars that all drive from some point A to some point B. Each car starts driving in index order. i.e. $x_1$ starts driving strictly ...
-1
votes
1
answer
55
views
Converting a Directed Acyclic Graph to a Directed Tree
I'm wondering if anyone can help me with this. Say I have a DAG, I understand that it has no directed cycles, but it can have loops ( "diamonds" ).
My question is, is there a known way to ...
- 1
0
votes
1
answer
39
views
Transitive Closure of a graph
Assuming we have a DAG, $G = (V, E)$, and we know that we can calculate $G$'s transitive closure in time complexity of $f(|V|, |E|)$, whereas $f$ is monotonic increasing function.
Show that given a ...
- 45
0
votes
0
answers
40
views
DAG graph where indegree >= outdegree and indegree = 0 => outdegree <= 1, cover all vertex with min amount of paths
Given a graph $G = (V, E)$ where
G is directed: $ \forall \ e \in E$ : $e$ has a direction.
G is acyclic (no cycles): $ \forall$ path $v_1, \dots , v_n : (v_n, v_1) \not\in E $.
If indegree $\gt0$, ...
- 11
0
votes
0
answers
17
views
Common name for "insert unique root" operation?
I had a graph operation come up in a code review, and was wondering if there is a common name for it.
Given a DAG with multiple roots, you can trivially create a graph with a single root by adding one ...
- 809
0
votes
1
answer
36
views
Name of this graph family?
Suppose I start with a directed chain graph of length $n$:
And then I add $k$ edges, with a restriction that the result is a planar DAG:
Is there a name for this graph family?
- 159
1
vote
0
answers
12
views
Aggregating pairwise ratings in a graph
A finite set of individuals provide bounded non-binary pairwise ratings of other individuals (say, -10 to +10), forming a directed graph (cycles possible).
I'd like to determine aggregate ratings for ...
- 111
3
votes
1
answer
43
views
When inserting a new vertex in a DAG, what possible changes are there to the edges
Background: I'm trying to program a generic method to add a node to a Directed Acyclic Graph. This method should allow the caller to specify the possible effects on the graph, specifically the edges.
...
- 809
0
votes
1
answer
461
views
modify dfs to find longest path
Let $G = (V, E)$ be a directed acyclic graph. Let every node $v \in V$ have an additional field $v_d$.
For each vertex $v \in V$, we need to store in $v_d$ the length of the longest path in $G$ that ...
- 25
0
votes
0
answers
34
views
Minimise vertex loss converting DCG to DAG
I have a DCG that I want to lay out with the parents on the left and children to the right. I want to maximise the number of all children present to the right of all parents whilst minimising the ...
- 101
0
votes
0
answers
45
views
Dijkstra algorithm for DAG
Assuming we have a K-Partite DAG (edges are directed from one level to the next) with edge weights either 0, 1 or 2.
We are looking for the shortest path between a node from group 0 to group k-1 (path ...
- 23
0
votes
0
answers
15
views
--Graphical Models-- Understanding blocked paths and conditional independence
I am quite confused by this slide from a course I found on the internet from UCL on Graphical Models. Here is the slide:
I would like to confirm whether I have correct understanding:
In the following ...
- 155
1
vote
0
answers
68
views
Determining whether DAG is semi-connected
I have been asked to write an algorithm which determine whether a DAG is semi-connected. (Recall that a DAG is semi-connected if for any pair of vertices $x,y$, there is either a path from $x$ to $y$ ...
- 11
1
vote
1
answer
64
views
Maximum flow in integer flow network
Let's say you have a maximum integer flow function in a network with 7 directed edges, meaning the flow cannot be increased anymore. The capacity of each edge is then increased by one. The capacity of ...
- 11
1
vote
1
answer
77
views
Traversing a directed graph with negative weights
Let $G = (V, E)$ be a directed graph with negative edge weights and no cycles, and $L:V \to \mathbb [0, \infty[$ be a function defined over this graph. This graph represents all possible paths a ...
- 115
2
votes
1
answer
138
views
House Robber DP Algorithm (Not three in a row)
This is a similar question to A variant of the house robber problem but instead of the general case, I'm wondering how you would solve the standard house robber problem, but when you cannot rob from ...
- 191
2
votes
2
answers
674
views
Can you use Dijkstra's algorithm to find the maximum cost path?
Suppose you have a DAG and the edges are positively weighted, and you want to find the maximum cost path from any node with no in degree to any node with no out degree.
Is it possible to negate all ...
- 121
3
votes
1
answer
392
views
Maximum number of distinct nodes that can be visited on a single walk
Given a directed graph which may contain cycles, how can I find the maximum number of distinct nodes that can be visited on a single walk?
I have done some research and the most similar-sounding ...
- 133
2
votes
1
answer
203
views
Topological sort and finding longest path in DAG to solve a stacking boxes variation (no rotation)
Given n elements (boxes) I have to output the max number of boxes that can fit one into another. Each box has width (x), height (y) and depth (z). One box j can hold another box k if: ...
user135193
0
votes
0
answers
56
views
Minimum weight $k-$path cover on a DAG proof verification
Suppose you are given a directed acyclic graph $G$ with $n$ vertices and an
integer $k \leq n$. Each edge has an associated weight $w(u,v)$. We want to find $k-$vertex-disjoint paths that cover all ...
- 503
1
vote
1
answer
54
views
Given a list of comparisons, sort items with as few additional comparisons as possible
You have n items x[0], ..., x[n-1]. Beforehand, you're given a list of several comparisons ...
- 453
3
votes
1
answer
144
views
Partition of a $k$-partite graph to minimal number of connected sets
Let $G$ be a $k$-partite directed acyclic graph where the edges are only between two adjacent sets of vertices.
I'm trying to partition the graph to the minimal number of connected sets.
Sets $A_0, ...
- 23
3
votes
0
answers
29
views
Online cycle detection but not quite: the Featherstitch problem
Featherstitch (Frost et al., 2007) is an approach for representing data consistency requirements for disk storage. This question concerns a graph-theoretic problem (§4.1 in the paper) that its ...
- 131
1
vote
0
answers
69
views
minimising Longest-Path in DAG
Assume we have weighted DAG (directed-acycle-graph), source s and target t.
Define the number of edges as $E$.
Given $0<\alpha<1$:
Choose $\alpha*E$ edges to cut their weight by half so that the ...
- 11
0
votes
0
answers
49
views
identify nodes with paths of unique length from source
Let us consider a Directed Acyclic Graph $G(V,E)$ such that all edges have unit weight. Let $s$ be a source node, $s\in V$ and a set of destination nodes, $D\in V\backslash s$. My problem is to find a ...
0
votes
1
answer
89
views
DAG for contiguous subsequence of maximum sum
I have trouble understanding DAG behind the "contiguous subsequence of maximum sum problem". Let's say I denote by S(i) maximum of sums of contiguous ...
- 113
1
vote
0
answers
31
views
How to compute all inequivalent (under Aut(P)) nonnegative integer weight assignments (with fixed sum) to the vertices of a finite poset P?
Let $P$ be a poset on $n$ points, $\text{Aut}(P)$ its automorphism group, and $a_1,a_2,\dots,a_k$ the lengths of the orbits under $\text{Aut}(P)$.
Goal: An algorithm to generate a member from each ...
- 111
2
votes
2
answers
153
views
DAG: When adding an edge that would normally result in a cycle, is there an algorithm to split the graph instead?
Summary
I am using a DAG to compress a tree structure with many repeated nodes (the repeated nodes only very seldomly do not also have repeated edges out.)
Normally, when attempting to add an edge to ...
- 133
1
vote
0
answers
61
views
What does a recursive min s,t-cut optimize?
Consider the following algorithm sketch:
Given an edge-weighted directed acyclic graph $G = (V, E, w : E \to \mathbb{N})$, adjoin a temporary source $s$ and sink $t$ to get $G' = (V', E', w')$. $G'$ ...
- 364
1
vote
0
answers
19
views
In a DAG, what is the name of the process replacing no branch path with a single vertex
In my work, I meet a process for DAG, and need to explain it in my report. So, I would like to know the name of the process.
The process is very simple. The vertices of degree two except roots and ...
- 239
1
vote
2
answers
155
views
Find every edge for which every s,t-path in a DAG goes through that edge
Given a connected sourced/sinked directed acylic graph $G = (V, E \subseteq V^2, s \in V, t \in V)$, we want to enumerate the edges $e \in \mathsf{Bottleneck}(G) \subseteq E$ for which every $s$,$t$-...
- 364
2
votes
2
answers
105
views
Path graph partitioning, minimizing cut while minimizing maximum total node weight in each part
Suppose there is a path (linear) graph $G = (V, E)$ where $V = \{0, \ldots, n - 1\}$ and $E=\{(0, 1), (1, 2), \ldots, (n - 2, n - 1)\}$, with edge weights $w_e : E \to \mathbb{N}$ and vertex weights $...
- 364
1
vote
0
answers
75
views
Is there a data structure to represent changes to a DAG over time, with fast reproduction of instances of the DAG?
Consider a directed acyclic graph (DAG) of topics and links. Apart from the root topic, topics are situated under one or more parent topics, and links, as well, are situated under one or more parent ...
- 111
2
votes
1
answer
108
views
edge coloring a directed acyclic graph
I have an edge coloring problem as follows:
Suppose we have a DAG which has a source vertex s and an end vertex e, in addition, all the paths from s to e are of the same length say L. We define L ...
- 21
3
votes
1
answer
75
views
Why do we use DAG rather than trees to represent search space of a search problem?
I saw people use DAGs to represent the search space of a search problems like the travelling salesman problem. Why is this better than the tree representation? Is the reason to save memory space on ...
- 165
0
votes
1
answer
105
views
Alternatives for finding sources in a DAG
I have a hard time seeing what the alternative approach is in linearizing a directed acyclic graph (DAG). Chapter 3 of Algorithms by Dasgupta et al. states:
Property Every dag has at least one source ...
- 659
0
votes
1
answer
223
views
Vertices reachable from negative-weight cycles in Bellman-Ford
TLDR: I want to know if there's a simple way to fill in distances for all vertices reachable from negative weight cycles (not just ones on the cycle itself) once Bellman-Ford has found a negative-...
- 818
3
votes
2
answers
167
views
Ordering of operations in a DAG of git commits
Context: I'm looking for a better state resolution algorithm for https://github.com/MichaelMure/git-bug
Summary of the current algorithm and shortcomings
git-bug is a distributed bug-tracker that ...
- 31
2
votes
0
answers
72
views
Using vector clocks vs. directed acyclic graph for causality detection in distributed systems
I'm trying to understand how vector clocks compare to DAGs for causality detection in a distributed system.
When trying to detect causality relations in a distributed system, a very commonly proposed ...
- 121
0
votes
0
answers
28
views
Given start strings, find simplest DAG that constructs target strings by concatenation
Say we have a number of start strings (green) and a number of target strings (red). Two strings can always be concatenated to a new string which can then be arbitrarily often reused (two arrows in, (1,...
- 161
1
vote
1
answer
326
views
If there is no Hamiltonian path in a DAG then there are at least two different Topological sorts
I understand the concept that if there is no Hamiltonian path so there will be 2 smaller paths and with them I can build more then one topological sort but I am not sure how make it formal.
Can you ...
0
votes
0
answers
77
views
Transitive reductions of transitive closure
Is there a name for the relationship between two DAGs A,B where B is one of the transitive reductions of the transitive closure <...
- 157
0
votes
0
answers
118
views
Methods for generating DAG with small Minimum Path Cover
On a directed acyclic graph $G=(V,E)$ the Minimum Path Cover (MPC) is the minimum number of paths that can be constructed on the DAG such that all vertices are covered by at least one path.
If one was ...
- 92
-1
votes
1
answer
45
views
Generating topological sequence from DAG with additional "not appearing before" constraints
DAG specifies the relationship of one node must appear after another. What if I add an additional constraint where one node cannot appear before another on top of the DAG?
Is there an algorithm for ...
- 99
1
vote
0
answers
42
views
Proof that "the last vertex in any postordering (in a DFS) of G lies in a source component of G"
From the book Algorithms (Jeff Erickson), there's a lemma that states:
The last vertex in any postordering of G lies in a source component
of G
My initial reaction to this was that the proof would ...
- 11
3
votes
1
answer
126
views
How to detect "tree-able" set-families?
A set-family (a set of sets of elements) is called tree-able if the elements can be arranged on a directed tree such that each element appears in exactly one node, and each set in the family ...
- 5,726
9
votes
1
answer
408
views
Shortest Path in a Directed Acyclic Graph with two types of costs
I am given a directed acyclic graph $G = (V,E)$, which can be assumed to be topologically ordered (if needed). Each edge $e$ in G has two types of costs - a nominal cost $w(e)$ and a spiked cost $p(e)$...
- 141
1
vote
1
answer
205
views
Reference for counting the number of paths in a DAG
Given a connected DAG I know how to compute the number of paths between two nodes. See e.g. Counting number of paths between two vertices in a DAG .
Is there a reference or name for the algorithm? ...
- 828
1
vote
1
answer
30
views
How can follow this this guide to construct a graph with matrix/reachability
Let's we have k matrices. For example we have 3 now, where first one is 8x5 ($a_1$ x $b_1$), second one is 5 x 6 ($a_2$ x $b_2$) and last one is 6 x 8 ($a_3$ x $b_3$). And our goal is to figure out ...
- 15
0
votes
2
answers
71
views
Finding connected components without building the graph first
What are good algorithms for finding connected components in a graph defined by a set of elements X, where each x in ...
- 157