Paste number 66357: depth-first-search

Index of paste annotations: 1 | 2 | 3 | 4 | 5 | 6 | 7

Paste number 66357: depth-first-search
Pasted by: JoshJ
2 months, 3 weeks ago
#lisp | Context in IRC logs
Paste contents:
Raw Source | XML | Display As
(defun find-start (start graph)
  (cond
    ((null graph) nil)
    ((equal start (caar graph)) (car graph))
    (t (find-start start (cdr graph)))))

(defun remove-from-graph (list graph)
  (cond
    ((null graph) nil)
    ((equal list (car graph)) (cdr graph))
    (t (cons (car graph) (remove-from-graph list (cdr graph))))))

(defun dfs (graph start goal)
  ;; check if graph is null, if so return nil
  ;; check if start is goal, if so return start.
  ;; OTHERWISE
  ;; find the list with start
  ;; remove that list from the graph
  ;; call dfs on all its children
  ;; if i get a non-nil result, return (cons start result).
  (print start)
  (princ goal)
  (princ graph)
  (cond
    ((null graph) nil)
    ((null start) nil)
    ((equal start goal) start)
    (t
     (setq list (find-start start graph))
     (setq graph (remove-from-graph list graph))
     (setq list (cdr list))
     (setq result nil)
     (setq ilist list)
     (loop while (and (equal result nil) (not (null ilist))) do
          (setq result (dfs graph (car ilist) goal))
          (princ result)
          (print ilist)
          (setq ilist (cdr ilist)))
     (cons start result))))



CL-USER>   (defparameter adjlist '((a b c) (b e) (c d) (d b c e)
                          (e d f h) (f e) (g h) (h e g)))
CL-USER>   (dfs adjlist 'a 'g)
CL-USER>   (dfs adjlist 'a 'g)

A G((A B C) (B E) (C D) (D B C E) (E D F H) (F E) (G H) (H E G))
B G((B E) (C D) (D B C E) (E D F H) (F E) (G H) (H E G))
E G((C D) (D B C E) (E D F H) (F E) (G H) (H E G))
D G((C D) (D B C E) (F E) (G H) (H E G))
B G((C D) (F E) (G H) (H E G))NIL
NIL NIL
NIL NIL
NIL NIL
NIL NIL

I don't understand why my ilist is nil in the loop, thus preventing it from making the recursive call on the next child.

Annotations for this paste:

Annotation number 1: more updated
Pasted by: JoshJ
2 months, 3 weeks ago
Context in IRC logs
Paste contents:
Raw Source | Display As
(defun find-start (start graph)
  (cond
    ((null graph) nil)
    ((equal start (caar graph)) (car graph))
    (t (find-start start (cdr graph)))))

(defun remove-from-graph (list graph)
  (cond
    ((null graph) nil)
    ((equal list (car graph)) (cdr graph))
    (t (cons (car graph) (remove-from-graph list (cdr graph))))))

(defun dfs (graph start goal)
  ;; check if graph is null, if so return nil
  ;; check if start is goal, if so return start.
  ;; OTHERWISE
  ;; find the list with start
  ;; remove that list from the graph
  ;; call dfs on all its children
  ;; if you get a non-nil result, return (cons start result).
  (print start)
  (princ goal)
  (princ graph)
  (cond
    ((null graph) nil)
    ((null start) nil)
    ((equal start goal) start)
    (t
     (setq list (find-start start graph))
     (setq graph (remove-from-graph list graph))
     (setq list (cdr list))
     (setq result nil)
     (print list)
     (loop while (and (equal result nil) (not (null list))) do
          (setq result (dfs graph (car list) goal))
          (print list)
          (setq list (cdr list)))
     (if (not (equal result nil))
         (cons start result)
         nil))))


CL-USER> (defparameter adjlist '((a b c) (b e) (c d) (d b c e)
                          (e d f h) (f e) (g h) (h e g)))

CL-USER>   (dfs adjlist 'a 'g)

A G((A B C) (B E) (C D) (D B C E) (E D F H) (F E) (G H) (H E G))
(B C)
B G((B E) (C D) (D B C E) (E D F H) (F E) (G H) (H E G))
(E)
E G((C D) (D B C E) (E D F H) (F E) (G H) (H E G))
(D F H)
D G((C D) (D B C E) (F E) (G H) (H E G))
(B C E)
B G((C D) (F E) (G H) (H E G))
NIL
NIL
NIL
NIL
NIL NIL

I'm still lost as to why the list is changing to a nil, can anyone help?

Annotation number 2: current code
Pasted by: JoshJ
2 months, 3 weeks ago
Context in IRC logs
Paste contents:
Raw Source | Display As

(defun find-start (start graph)
  (cond
    ((null graph) nil)
    ((equal start (caar graph)) (car graph))
    (t (find-start start (cdr graph)))))

(defun remove-from-graph (list graph)
  (cond
    ((null graph) nil)
    ((equal list (car graph)) (cdr graph))
    (t (cons (car graph) (remove-from-graph list (cdr graph))))))

(defun dfs (graph start goal)
  ;; check if graph is null, if so return nil
  ;; check if start is goal, if so return start.
  ;; OTHERWISE
  ;; find the list with start
  ;; remove that list from the graph
  ;; call dfs on all its children
  ;; if you get a non-nil result, return (cons start result).
  (cond
    ((null graph) nil)
    ((null start) nil)
    ((equal start goal) start)
    (t
     (setq list (find-start start graph))
     (setq graph (remove-from-graph list graph))
     (setq list (cdr list))
     (setq result nil)
     (loop while (and (equal result nil) (not (null list))) do
          (print list)
          (setq result (dfs graph (car list) goal))
;;this seems to be the problem
          (print list)
          (setq list (cdr list)))
     (if (not (equal result nil))
         (cons start result)
         nil))))

CL-USER>   (defparameter adjlist '((a b c) (b e) (c d) (d b c e)
                          (e d f h) (f e) (g h) (h e g)))


ADJLIST
CL-USER>   (dfs adjlist 'a 'g)
1. Trace: (DFS '((A B C) (B E) (C D) (D B C E) (E D F H) (F E) (G H) (H E G)) 'A 'G)
(B C)
2. Trace: (DFS '((B E) (C D) (D B C E) (E D F H) (F E) (G H) (H E G)) 'B 'G)
(E)
3. Trace: (DFS '((C D) (D B C E) (E D F H) (F E) (G H) (H E G)) 'E 'G)
(D F H)
4. Trace: (DFS '((C D) (D B C E) (F E) (G H) (H E G)) 'D 'G)
(B C E)
5. Trace: (DFS '((C D) (F E) (G H) (H E G)) 'B 'G)
5. Trace: DFS ==> NIL
NIL
4. Trace: DFS ==> NIL
NIL
3. Trace: DFS ==> NIL
NIL
2. Trace: DFS ==> NIL
NIL
1. Trace: DFS ==> NIL
NIL

Annotation number 3: try this
Pasted by: salex
2 months, 3 weeks ago
Context in IRC logs
Paste contents:
Raw Source | Display As
(defun dfs (graph start goal)
  ;;should be same logic
  (cond
    ((null graph) nil)
    ((null start) nil)
    ((equal start goal) start)
    (t
     (loop with g
        with list = (find-start start graph)
        for x in list
        for result = (dfs g x goal)
        until result
        initially (setf g (remove-from-graph list graph))
        finally (return (if (null result) nil (cons start result)))))))

Annotation number 4: dfs with some abstraction.
Pasted by: pjb
2 months, 3 weeks ago
Context in IRC logs
Paste contents:
Raw Source | Display As

(defun dfs (graph start goal)
  "
graph:  a Graph
start:  a Vertex
goal:   a Vertex
PRECONDITION:  (or (graph-empty graph)
                   (and (member start (graph-vertices graph))
                        (member goal  (graph-vertices graph))))
RESULT:        A list of vertices starting with start and ending with goal
               denothing the first path found in depth-first-search from
               start to goal.
"
  (cond
    ((graph-empty graph)  '())
    ((equal start goal)   (list start))
    (t (loop
          :for next :in (graph-adjacency-list graph start)
          :for path-to-goal = (dfs (graph-remove-vertex graph start)
                                   next goal)
          :until path-to-goal
          :finally (return (cons start path-to-goal))))))

Annotation number 5: working code, if inelegant
Pasted by: JoshJ
2 months, 3 weeks ago
Context in IRC logs
Paste contents:
Raw Source | Display As
(defun dfs (graph start goal)
  ;; check if graph is null, if so return nil
  ;; check if start is goal, if so return start.
  ;; OTHERWISE
  ;; find the list with start
  ;; remove that list from the graph
  ;; call dfs on all its children
  ;; if you get a non-nil result, return (cons start result).
  (cond
    ((null graph) nil)
    ((null start) nil)
    ((equal start goal) (list start))
    ;; the list fixed it
    (t
     (let ((list (find-start start graph)))
     (setf graph (remove-from-graph list graph))
     (setf list (cdr list))
     (setf result nil)
     (loop while (and (equal result nil) (not (null list))) do
          (setf result (dfs graph (car list) goal))
          (setf list (cdr list)))
     (if (not (equal result nil))
         (cons start result)           
         nil)))))

Annotation number 6: cleanup, but that's all
Pasted by: salex
2 months, 3 weeks ago
Context in IRC logs
Paste contents:
Raw Source | Display As
(defun dfs (graph start goal)
  ;; more idiomatic, still loop based
  ;; the test is clunky, following orig
  (if (equal start goal)
      (list start)
      (loop with start-adj = (find start graph :test #'(lambda (x y) (equal x (car y))))
         with subgraph = (remove start-adj graph)
         for x in start-adj
         for result = (dfs2 subgraph x goal)
         until result
         finally (return (when result  result)))))

Annotation number 7: oops, ignore previous
Pasted by: salex
2 months, 3 weeks ago
Context in IRC logs
Paste contents:
Raw Source | Display As
(defun dfs (graph start goal)
  ;; more idiomatic, still loop
  (if (equal start goal)
      (list start)
      (loop with start-adj = (find start graph :test #'(lambda (x y) (equal x (car y))))
         with subgraph = (remove start-adj graph)
         for x in start-adj
         for result = (dfs subgraph x goal)
         until result
         finally (return (when result (cons start result))))))

Colorize as:
Show Line Numbers
Index of paste annotations: 1 | 2 | 3 | 4 | 5 | 6 | 7

Lisppaste pastes can be made by anyone at any time. Imagine a fearsomely comprehensive disclaimer of liability. Now fear, comprehensively.