Undirected graph conversion to tree
here is a suggestion on how to solve your problem.
prerequisites
- notation:
g
graph,g.v
graph verticesv,w,z
: individual verticese
: individual edgen
: number of vertices
- any combination of an undirected tree g and a given node g.v uniquely determines a directed tree with root g.v (provable by induction)
idea
- complement the edges of
g
by orientations in the directed tree implied byg
and the yet-to-be-found root node by local computations at the nodes ofg
. - these orientations will represent child-parent-relationsships between nodes (
v -> w
:v
child,w
parent). - the completely marked tree will contain a sole node with outdegree 0, which is the desired root node. you might end up with 0 or more than one root node.
algorithm
assumes standard representation of the graph/tree structure (eg adjacency list)
- all vertices in
g.v
are marked initially as not visited, not finished. visit all vertices in arbitrary sequence. skip nodes marked as 'finished'.
letv
be the currently visited vertex.- 2.1 sweep through all edges linking
v
clockwise starting with a randomly chosene_0
in the order of the edges' angle withe_0
. 2.2. orient adjacent edges
e_1=(v,w_1), e_2(v,w_2)
, that enclose an acute angle.
adjacent: wrt being ordered according to the angle they enclose withe_0
.[ note: the existence of such a pair is not guaranteed, see 2nd comment and last remark. if no angle is acute, proceed at 2. with next node. ]
2.2.1 the orientations of edges
e_1, e_2
are known:w_1 -> v -> w_2
: impossible, as a grandparent-child-segment would enclose an acute anglew_1 <- v <- w_2
: impossible, same reasonw_1 <- v -> w_2
: impossible, there are no nodes with outdegree >1 in a treew_1 -> v <- w_2
:
only possible pair of orientations.e_1, e_2
might have been oriented before. if the previous orientation violates the current assignment, the problem instance has no solution.
2.2.2 this assignment implies a tree structure on the subgraphs induced by all vertices reachable from
w_1
(w_2
) on a path not comprisinge_1 (
e_2`). mark all vertices in both induced subtrees as finished[ note: the subtree structure might violate the angle constraints. in this case the problem has no solution. ]
2.3 mark
v
visited. after completing steps 2.2 at vertexv
, check the numbernc
of edges connecting that have not yet been assigned an orientation.nc = 0
: this is the root you've been searching for - but you must check whether the solution is compatible with your constraints.nc = 1
: let this edge be(v,z)
.
the orientation of this edge is v->z as you are in a tree. mark v as finished.- 2.3.1 check
z
whether it is marked finished. if it is not, check the numbernc2
of unoriented edges connectingz
.nc2
= 1: repeat step 2.3 by takingz
forv
.
- 2.3.1 check
- 2.1 sweep through all edges linking
if you have not yet found a root node, your problem instance is ambiguous: orient the remaining unoriented edges at will.
remarks
termination: each node is visited at max 4 times:
- once per step 2
- at max twice per step 2.2.2
- at max once per step 2.3
correctness:
- all edges enclosing an acute angle are oriented per step 2.2.1
complexity (time):
- visiting every node: O(n);
the clockwise sweep through all edges connecting a given vertex requires these edges to be sorted.
thus you needO( sum_i=1..m ( k_i * lg k_i ) )
atm <= n
vertices under the constraintsum_i=1..m k_i = n
.in total this requires
O ( n * lg n)
, assum_i=1..m ( k_i * lg k_i ) <= n * lg n
givensum_i=1..m k_i = n
for anym <= n
(provable by applying lagrange optimization).[ note: if your trees have a degree bounded by a constant, you theoretically sort in constant time at each node affected; grand total in this case:
O(n)
]subtree marking:
each node in the graph is visited at max 2 times by this procedure if implemented as a dfs. thus a grand total ofO(n)
for the invocation of this subroutine.in total:
O(n * lg n)
complexity (space):
O(n)
for sorting (with vertex-degree not constant-bound).
problem is probably ill-defined:
- multiple solutions: e.g. steiner tree
- no solution: e.g. graph shaped like a double-tipped arrow (<->)
paniwani
Updated on June 04, 2022Comments
-
paniwani almost 2 years
Given an undirected graph in which each node has a Cartesian coordinate in space that has the general shape of a tree, is there an algorithm to convert the graph into a tree, and find the appropriate root node?
Note that our definition of a "tree" requires that branches do not diverge from parent nodes at acute angles.
See the example graphs below. How do we find the red node?