# Tag: acyclic

## godot – Traversing an acyclic binary tree to construct paths from a given starting node, but the paths come out wrong

The tree is an acyclic binary tree. It’s composed of node objects that have a list of connections to link objects (at most 3), and link objects that have a list of connections to node objects (always 2). I am trying to construct a list of possible paths to other nodes that can be reached given a fuel budget and a fuel cost on each link. What it is supposed to do is go through each non-backtracking connection of a node, and spawn a new route and thread to investigate that, leaving the current one to end at that node and thus create a list of routes to every node in the reachable area. When executed, the list of end destinations are valid but many of the paths that are constructed to get to them are wrong, going down other branches in the tree that are extraneous or entirely outside of the reachable area bounded by the fuel budget as well as jumping between nodes that aren’t directly connected. There seems to be some pattern in the errors, when going down from the root of some branches of the tree the path goes down every offshoot in order first instead of going in a straight line, and when going up the tree the path tends to go further out and make triangle shapes, often landing somewhere other than the listed destination. I have already checked the link and node connections themselves to see if they are assigned properly, and they are. What am I getting wrong?

Route class definition

```
var origin:Node
var destination:Node
var totaldV:float
var totalt:float
var dVBudget:float
var tBudget:float
var tdVRatio:float
var links:Array
var nodes:Array
func duplicate_values(originator:Route):
origin = originator.origin
destination = originator.destination
totaldV = originator.totaldV
totalt = originator.totalt
dVBudget = originator.dVBudget
tBudget = originator.tBudget
tdVRatio = originator.tdVRatio
nodes = originator.nodes
links = originator.links
func _init(originator_route):
if originator_route != null:
duplicate_values(originator_route)
```

Tree traversal algorithm

```
var routes:Array
onready var root = get_node("..")
func traverse(current_node:Node, previous_route:Route):
if previous_route == null: # Starts off the recursion by providing an initial node
previous_route = Route.new(null)
previous_route.origin = current_node
previous_route.nodes.append(previous_route.origin)
previous_route.dVBudget = 2000
previous_route.totaldV = 0
for link in current_node.connections:
if (previous_route.totaldV + link.dV < previous_route.dVBudget &&
!IsBacktracking(previous_route, LinkDestination(link, current_node))): # If there is enough fuel and the link isn't backtracking, go through it.
var working_route:Route = Route.new(previous_route) # Copy the previous route to make the new route
routes.append(working_route)
working_route.destination = LinkDestination(link, current_node)
working_route.totaldV += link.dV
working_route.totalt += link.t
working_route.links.append(link)
working_route.nodes.append(working_route.destination)
traverse(working_route.destination, working_route)
DisplayRoutes()
root.get_parent().pathSelectionFlag = true # UI control boolean
func IsBacktracking(route:Route, destinationNode:Node) -> bool:
for nodeI in route.nodes:
if (destinationNode == nodeI):
return true
return false
func LinkDestination(link:Node, originNode:Node) -> Node: # Finds the node on the other side of a link
for nodeI in link.connections:
if (nodeI != originNode):
return nodeI
return originNode
```

## How many vertices should be disconnected to make a graph acyclic?

Given an undirected graph with some cycles:

we can “disconnect” the red vertex by adding a separate vertex to each of the edges adjacent to it:

In this case, disconnecting a single vertex makes the graph acyclic.

My questions:

- What is a term for the smallest number of vertices that must be “disconnected” like this, to make the graph acyclic?
- What is an algorithm for finding a smallest such set of vertices?

(I found some related concepts, but they are different:

- The circuit rank is the number of
*edges*that have to be removed to make the graph acyclic; it always equals the number of edges minus the number of vertices plus the number of components. - The vertex connectivity is the number of vertices that have to be removed to make the graph
*disconnected*.)

## How can I extract the directed acyclic graph of a google sheet?

This may belong in stackoverflow, but since I’m hoping that the answer is some plugin, I’m asking here first.

Google Sheets doesn’t have the “show dependencies” that excel does. I’m trying to track down what is slowing my spreadsheet, which for changes in certain cells takes close to a minute to update.

Ideally I’d like to point a cell address at some program or script, it it shows me all the cells that depend on it, and all the cells that depend on those — in essence giving me that chunk of the DAG of the spreadsheet.

A program that looked at a sheet file and translated it into python or perl might work. A program that extracted and creaated a topological tree of the DAG would work.

## homological algebra – $Omega^1_{B_bullet/A_bullet}$ is acyclic if $A_bullet to B_bullet$ is quasi-isomorphism

Let $A_bullet to B_bullet$ be a quasi-isomorphism of **simplicial rings** in the sense of (P.62, I.3.1.7, *Complexe Cotangent et Déformations I*, Luc Illusie).

Then, we define the simplicial $B_bullet$-module of Kähler differentials $Omega^1_{B_bullet/A_bullet}$ by $left(Omega^1_{B_bullet/A_bullet}right)_n := Omega^1_{B_n/A_n}$ (P.119, *ibid*.).

**My question is** whether it follows that $Omega^1_{B_bullet/A_bullet}$ is acyclic (i.e. quasi-isomorphic to the zero module) from these assumptions.

The broader context is when I am trying to show that the cotangent complex is independent of the free resolution taken.

Suppose we are given an algebra $R to S$ which has two free simplicial resolutions $P_bullet to Q_bullet$ (i.e. they are quasi-isomorphic to $S$, and $P_n$ and $Q_n$ are free $R$-algebras).

Then, using these two simplicial resolutions, we define the cotangent complex $L_{S/R}$ to be $Omega_{P_bullet/R} otimes_{P_bullet} S$ and $Omega_{Q_bullet/R} otimes_{Q_bullet} S$, the former of which is isomorphic to $Omega_{P_bullet/R} otimes_{P_bullet} Q_bullet otimes_{Q_bullet} S$. My approach was to break down the question of whether $Omega_{P_bullet/R} otimes_{P_bullet} S$ and $Omega_{Q_bullet/R} otimes_{Q_bullet} S$ are quasi-isomorphic into two sub-questions:

- Whether the map $Omega_{P_bullet/R} otimes_{P_bullet} Q_bullet to Omega_{Q_bullet/R}$ is a quasi-isomorphism.
- Whether $- otimes_{Q_bullet} S$ sends quasi-isomorphisms of free $Q_bullet$-modules to quasi-isomorphisms.

For 1, I have fitted them in a short exact sequence (in general $0 to$ is not present, but for my case it is ok):

$$0 to Omega_{P_bullet/R} otimes_{P_bullet} Q_bullet to Omega_{Q_bullet/R} to Omega_{Q_bullet/P_bullet} to 0$$

So it suffices to show that $Omega_{Q_bullet/P_bullet}$ is acyclic, which is what I asked above.

For 2, I guess the usual proof with cones would go through ($f$ quasi-isomorphism $implies$ $operatorname{cone}(f)$ acyclic $implies$ $operatorname{cone}(f) otimes_{Q_bullet} S = operatorname{cone}(f otimes_{Q_bullet} S)$ acyclic $implies$ $otimes_{Q_bullet} S$ quasi-isomorphism), but I have not checked the details yet. I would appreciate if someone would give me a pointer on this, but I could also ask this in a later question.

## co.combinatorics – Acyclic proper coloring of 2-degenerate graphs

A proper vertex coloring of a graph $G$ is acyclic if there is no bicolored cycle. A graph is 2-degenerate if its every subgraph has a vertex of degree at most 2. I think every 2-degenerate graph has an acyclic proper vertex coloring using 3 colors, but I did not find any source stating this. Does anyone know this? Am I right? Thanks in advance.

## algorithms – Prove that if given an integral flow, an acyclic integral flow exists with the same value

We are given a directed network $G=(V,E)$ with capacity $c(e)$ on edge $ein E$, and a feasible $s$–$t$ flow $f:Erightarrow mathbb R^+$. A flow $f$ is acyclic if the subgraph of directed edges with positive flow contains no directed cycles.

**Prove: if $f$ is an integral flow in $G$, then there is a feasible acyclic integral flow $g$ of the same value**

I have proved that if $f$ is a flow then there is a feasible acyclic flow of the same value, but I’m not sure how to explicitly prove that if $f$ is an integral flow, $g$ will also be an integral flow. I know that an integral flow implies integral flow on paths, but I do not know how to apply this to the proof.

## dag – 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 colors from 1 to L. Is there an efficient edge coloring algorithm to color all the edges, such that every path from s to e uses all the L colors and every path must be labeled differently? I attach a picture below for illustration, where vertex 1 is s, vertex 10 is e.

## dag – 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 technique is the use vector clocks. Vector clocks are presented as:

Timestamping is a common method of totally ordering events in concurrent programs. However, for applications requiring access to the global state, a total ordering is inappropriate. This paper presents algorithms for timestamping events in both synchronous and asynchronous message-passing programs that allow for access to the partial ordering inherent in a parallel system. The algorithms do not change the communications graph or require a central timestamp issuing authority.

Source: Timestamps in Message-Passing Systems That Preserve the Partial Ordering Colin J. Fidge

Another less mentioned but nonetheless ubiquitous method is to synchronize a directed acyclic graph (DAG) between the replicas. I understand the “reachability” notion of DAGs allows to define a partial order between events. To my understanding, this is Git’s approach to determining if a commit took place before, after, or at the same time as another.

I’ve seen little to no discussion opposing vector clocks to full DAG modeling. Unless I missed anything I think those are techniques that both could be used to do an event partial ordering in a distributed system. Trying to understand what unifies or separates vector clocks and DAGs, I’ve come to the following conclusion so far:

What unifies them:

- They both could be used to determine causality relation in a distributed system

Advantages of vector clocks:

- Size of data to synchronize in vector clock grows with the number of replica, but not with the number of events; which in most real life application is more efficient. Also optimizing DAG data transfer between replica over the network may not be straightforward.

Advantage of DAGs:

- Easier to conceptualize? And possibly implement?
- Models the full tree, so wins over vector clocks when we want not only to understand if an event e1 occurred before another event e2, but want to access more details on the event present, possibly their content, etc.

Is this it, or am I missing an important concept?

## Efficient insertion of deterministic acyclic finite state automaton (DAFSA) into a suffix tree?

I have a problem where I can easily construct a set of deterministic acyclic finite state automata (DAFSA) and I need a full-text search index, e.g. a suffix tree, over all the words encoded by these automata.

Is there an efficient algorithm for inserting all the words encoded in a DAFSA into a suffix tree? By *efficient* I mean that the complexity must not depend on the on the total number of words encoded in the DAFSA.