Topology algorithms are pretty much all about DFS post-order (reaching to the leaf nodes, processing children before processing current node), aiming to identify structures, depths, connections of graphs.
Typical use scenarios include:
· Finding shortest path
· Finding distances along
· Comparing of graph structure
AHU algorithm uses “(“ and “)” to represent the structure (NOT the value) of tree nodes into a single string.
Sequence of operation
1. Find “centers” of graph structure. Note that there can be multiple centers of the same graph.
a. “center” means “the shortest path to all leaf nodes”
2. Encode with DFS post order. Note that the child’s returned string shall be sorted lexicographically (with sort(stringV.begin(), stringV.end())
3. Merge children’ string, wrap with “(“ and “)”
4. For two trees, each of them can have multiple “centers”. Pick a center from one tree, but compare it with the other tree’s AHU strings with all centers iterated.
There are a number of algorithms, including Tarjan’s offline. Below is an Eulerian tour/RMQ query example.
The key part is to build two arrays, size N = 2 * number of nodes + 1. This is because all nodes are visited twice other than the root (ASSUMING we have a left/right tree)
· One array represents the depth of each node, which correlates to ancestor in parent/child relationship
o The index of each element is the visit order to this node
o The value of each array element is the depth
· One array represents the sequence of visit, which represents the order of traversing all nodes
o The index of each element is the visit order to this node, same as the depth queue.
o The value of each element is node unique ID.
· The requirement is to index each node with unique ID.
1. Build depth & order arrays
a. DFS pre-order AND post-order. This means the current node’s ID is appended to both DEPTH_ARRAY & VISIT_SEQ_ARRAY before & after EACH child.
2. Cross reference
a. Use unique node ID to find index from visit array. There can be multiple entries for each node since one single node can be visited multiple times
b. Find min/max of the visit index
c. Use visit index region in DEPTH_ARRAY and find min_level
d. cross reference back from min_depth->visit order->node ID, which is the LCA node.
This is very useful to determine dependencies for events/programs/courses. Node parent->child edge can be modeled to present logical relationship.
The key note: topological orders are not unique!
Tree (in format of TreeNode) can use “cherry pick leaf nodes” (BFS into queue, and reserve order); graph (in connected edge format) can use DFS with a “visited” array. Note that not all nodes are connected with each other in graph, and thus this is an iterative process until all nodes are visited.
1. Initialize a VISITED_ARRAY (size == N)
2. Initialize a ORDER_ARRAY (size == N) and each element value is node’s ID
3. Pick any node as START_NODE
4. DFS post-order from START_NODE and save to a temp ordering array
5. Copy temp ordering array to ORDER_ARRAY
6. If there are unvisited nodes, repeat from step 3
1。考虑到graph的direction。如果是directional，生成edgeMap的时候，from parent to child。如果是non-directional，edgeMap加上parent to child, and child to parent.
2。考虑到graph可能包含cyclic dependency，用visited（vector<bool>， pre mark) 代表“a node is in the path before processing the current node", 用inList(vector<bool>, post mark)代表”a node has been marked as a child & already put to topOrderList"。如果只用visited，会导致stack overflow.
The general solution for various SSSP issue is to keep an array MIN_DISTANCE_ARRAY (size == N) and run iteratively from any nodes to “relax” the distance to destination node.
· Might also need to allocate a correspondent array for PREV_NODE
It is almost a “dynamic programming” model, since the distance to a node is “referred” from previously identified shorted path.
1. Push the “start node distance == 0” into the array
2. Loop from index = 0 for all nodes
3. Get the edge cost from the current node to its child nodes
a. “check and relax” the recorded distance in MIN_DISTANCE_ARRAY
4. Find the next node (the first one picked is always the start node)
a. It varies by algorithm which “next node” to choose
5. Mark the node as VISITED once it’s picked by step 3. We don’t come to this node again, and the value of this node in MIN_DISTANCE_ARRAY is considered final.
With the ORDER_ARRAY by hand, it is easy to find the shorted path because we always know which node to pick in the next step. Therefore, step 4.a is simply to use the next node in ORDER_ARRAY
Note that this can be used to solve LONGEST path (NP hard) by inverting all weights with -1.
The requirement is NOT to contain a negative edge; or, the algorithm loops forever.
Since there is no already-made ORDER_ARRAY, a priority_queue (based on min distance) is needed on the side in order to determine which node to be picked. Note that priority_queue is based on “largest node in the front”, we need to tweak the comparison function.
This is just like a BFS queue, except that when we take a node out from this queue, it always contains the smallest weight/distance.
· Step 4.a use a priority_queue; loop until this loop size == 0
· Push calculated new values into the queue
· A node is marked “visited” AFTER this is selected as the “from” node & all of its “to” nodes are relaxed
· When “taking a min node”, compare this with the current MIN_DISTANCE_ARRAY. Drop if smaller, since a node can be visited from many paths.
The worst condition is to visit ALL nodes before claiming the MIN_DISTANCE_ARRAY is final. However, in Step 5, if the current “from” node is the destination node, we can exit.
Not as ideal as Dijkstra; however, if there is a negative edge, Bellman Ford is the choice to find it.
Basic steps is roughly the same; however, this algorithm shall repeat twice (each iteration for all nodes loop) in order to identify nodes involved in a negative weight cycle.
This is a classical DP-based solution, which gives the entire shortest path in two loops.
Similar to Bellman Ford, this runs the logic twice, in order to identify negative cycles.
The input is connection matrix (N*N), rather than the usually connection edges.
- - Change Ad Consent
Powered by Huaren.us 1.0.112
© 2001-2020 .
Processed in 0.2343729 second(s)
, 12 queries.
9/26/2020 9:59:00 PM|9/26/2020 9:59:00 PM