graph-test.lisp

(require 'asdf)
(asdf:oos 'asdf:load-op 'graph-utils)
(use-package :graph-utils)

(defun graph-test-old ()
  (dolist (file '("data/Dining.net" "data/karate.gml"))
    ;;"data/dolphins.gml" "data/adjnoun.gml" "data/football.gml"))
    (format t "Doing graph ~A~%" file)
    (let ((graph (if (cl-ppcre:scan "gml$" file) (parse-gml file) (parse-pajek file)))
	  (stem (cl-ppcre:regex-replace-all "(\.(net|gml))$" file "")))
      (with-open-file (out (format nil "~A.log" stem)
			   :direction :output
			   :if-exists :supersede
			   :if-does-not-exist :create)
	(format out "Graph of ~A: ~A~%" stem graph)
	(format out "  Density: ~F~%" (density graph))
	(format out "  Degree distribution:~%~{     ~A~%~}" (degree-distribution graph))
	(when (directed? graph)
	  (format out "  In-degree distribution:~%~{     ~A~%~}" (in-degree-distribution graph)))
	(format out "  Components:~%~{    C: ~A~^~%~}~%" (find-components graph))
	(format out "  Shortest paths:~%")
	(dolist (path (calculate-shortest-paths graph))
	  (format out "    Path from ~A to ~A: "
		  (lookup-node graph (first path)) (lookup-node graph (second path)))
	  (dotimes (i (length (third path)))
	    (format out "~A -> " (lookup-node graph (first (nth i (third path))))))
	  (format out "~A~%" (lookup-node graph (second path))))
	(when (directed? graph)
	  (let ((pr (compute-page-rank graph :k 2 :scaling-factor 0.9))
		(page-rank nil))
	    (dotimes (i (node-count graph))
	      (push (list (lookup-node graph i) (aref pr i)) page-rank))
	    (format out "  Page rank:~%")
	    (dolist (r (sort page-rank #'> :key #'second))
	      (format out "    ~10A ~2,10F~%" (first r) (second r))))
	  (format out "  Hubs-authorities:~%")
	  (multiple-value-bind (hubs auths) (compute-hub-authority-values graph :normalize? t)
	    (format out "    Hubs:~%")
	    (dolist (h hubs)
	      (format out "      ~10A ~2,10F~%" (car h) (cdr h)))
	    (format out "    Authorities:~%")
	    (dolist (a auths)
	      (format out "      ~10A ~2,10F~%" (car a) (cdr a)))))
	(visualize graph :file (format nil "~A.dot" stem) :render? t)
	(format out "  Minimal cut (removed edges):~%~{    ~A~%~}~%"
		(mapcar #'(lambda (e)
			    (format nil "~A -> ~A" (first e) (second e)))
			(minimal-cut! graph)))
	(visualize graph :file (format nil "~A-cut.dot" stem) :render? t)))))


(graph-test-csc525)