graph,lisp,edge,land-of-lisp , Extracting nodes form dotted list (edges) in CLISP

Extracting nodes form dotted list (edges) in CLISP


Tag: graph,lisp,edge,land-of-lisp

I'm a "Nil" or () in Lisp World.
I wanted to get a list of all nodes in edge list and I wrote a code to solve this problem. But I met some unexpected problem.

(Codes from 'Land of Lisp' - chapter 8)

;; Creating edge list

(defun random-node ()
  (1+ (random *node-num*)))    

(defun edge-pair (a b)
  (unless (eql a b)
    (list (cons a b) (cons b a))))

(defun make-edge-list ()
  (apply #'append (loop repeat *edge-num*
                        collect (edge-pair (random-node) (random-node)))))

(defparameter el (make-edge-list))

I wrote a code to extract all node as a list like below.

;; el : list of dotted list
;; I want to extract all the first element from every dotted lists in el.

;; el : ((25 . 6) (6 . 25) (2 . 13) (13 . 2) (25 . 16) (16 . 25) ....)
;; What I want to get: (25 6 2 13 25 16 ... )

(defun extract-nodes (el)
  (let ((nodes nil))
    (labels ((addNode (edgeList)
               (push (caar edgeList) nodes)
               (addNode (cdr edgeList))))
      (addNode el))

I thought that my code was not so bad, but result showed me a embarrassing error message.

"Stack overflow (deep)" 

Stack overflow? I think that it is caused by the recursive function in my code. How can I fix this properly?



Your recursive addNode (better called add-node if you are a lisper) needs a stop condition. E.g.,

         (add-node (edge-list)
           (push (car (pop edge-list)) nodes)
           (when edge-list
             (add-node (cdr edge-list))))

Note that there is no reason to use recursion here, a simple mapcar would do just fine:

(defun extract-nodes (el)
  (mapcar #'car el))


If strings are vectors, why are they immutable?

if strings are vectors of characters, and a vector's elements can be accessed using elt, and elt is setf-able - then why are strings immutable?

Graph shortest path infinite cycle

So my paint skills are not the best but I think it shows the example well. Imagine I want to calculate the shortest path between A and C, considering all the algorithms I've found are greedy, wouldn't it be stuck in an infinite cycle between A and B? Any...

calculating graph weight in python with NetworkX

I'm using networkx to calculate the shortest distance(in terms of weight) between two vertexes in a directed, weighted graph. I think that the dijkstra_path_length algorithm is the right one to use here, but I don't understand what I have to put as a default parameter for the weight in order...

Graph algorithm to collect all edges which are on any path between two nodes

I need to find all edges which are on any path between two nodes [src, dest] in a directed graph. Means that each edge (from base to head) has to satisfy: there is a path from src to base there is a path from head to dest I could collect...

Large Neo4j graph not showing up

I created a large neo4j graph connecting users to the videos they watch like user -> video in a social graph or network type of graph. There are about 9000 user nodes and 20000 video nodes. If I try: MATCH (u)-[:VIEW]->(v) RETURN u,v The graph says "Displaying 300000 nodes, 0...

Plot: Add legend that overlay several Frames

How can we write a legend that overlay several frames? Using the xpd parameter, the legend can exit its frame but still cannot enter the next frame. par(mfrow=c(1,2)) plot(rnorm(120), rnorm(120)) legend(x = -0.1, y=0.1, legend = "Legend that covers both plots", text.col="red", cex=2, box.col="red", xpd=TRUE) plot(rnorm(120), rnorm(120)) One dummy solution...

GDI+ curve “overflowing”

I'm currently using GDI+ to draw a line graph, and using Graphics.DrawCurve to smooth out the line. The problem is that the curve doesn't always match the points I feed it, and that makes the curve grow out of the graph frame in some points, as seen below(red is Graphics.DrawLines,...

Airport travels using graph

Can someone help me to think of a better way to adapt Dijkstra's Algorithm in these conditions? All I thought of so far wasn't good. Example of input: GP4578 MADRID 01:00 PORTO 02:00 IK6587 PORTO 03:00 VALENCIA 05:00 05:30 TENERIFE 08:00 AB5874 VALENCIA 05:40 BERLIM 10:00 "VALENCIA 05:00 05:30" This...

Graph shortest path confusion

I want to calculate the shortest path from A to F in this graph Following Dijkstra's algorithm I reach E and then go to C, but then I can't comeback to E, how do I solve this? My steps were: All cost to infinity but a, that I've set to...

Read CSV and plot colored line graph

I am trying to plot a graph with colored markers before and after threshold value. If I am using for loop for reading the parsing the input file with time H:M I can plot and color only two points. But for all the points I cannot plot. Input akdj 12:00...

Algorithm Is Node A Connected to Node B in Graph

I am looking for an algorithm to check for any valid connection (shortest or longest) between two arbitrary nodes on a graph. My graph is fixed to a grid with logical (x, y) coordinates with north/south/east/west connections, but nodes can be removed randomly so you can't assume that taking the...

Structuring large Lisp applications

I am currently trying to wrap my head around packages, systems & co. I now have read Packages, systems, modules, libraries - WTF? a few times, and I think I'm still having difficulties to get it right. If I simply want to split a Lisp source file into two files,...

Plotting image and points on Matlab GUI via update function

excuse my noobness, but this is my first post. i generated this gui in matlab, and i want to plot an image on one of the axis from an update function. i know in Matlab you can just do something like image(img) hold on plot(x1,z1) hold off but how can...

sort graph by distance to end nodes

I have a list of nodes which belong in a graph. The graph is directed and does not contain cycles. Also, some of the nodes are marked as "end" nodes. Every node has a set of input nodes I can use. The question is the following: How can I sort...

Plotting a data frame in R

I have this data frame and I'd like to know if there's a way to plot this using the ggplot2 library (or anything that works). The first row has a bunch of zip codes and the second row contains weather data (temperature in this case) associated with the corresponding zip...

Big O Notation with Absolute Value?

I'm going through some programming interview question books, and I've seen reference to "O(|A|)" time complexity. I've never seen this notation with the absolute value given. Some research led me to Big O Cheatsheet that references this notation under the graphs section. The problem I'm researching is about partitioning an...

Javascript multiple circular graphs

Ive made a working circular graph using javascript, and Ive run into a problem. The script fetches the id of the graph in order to work, but I would like multiple graphs. So here is my question: How do I make the script compatible with multiple graphs? I tried fetching...

Determining if a graph has a cycle without using DFS

I came around one of those questions in my exams: Topologocial sorting using Kahn's Algorithm requires the graph to be DAG (Directed Acyclic Graph). How can we determine if a graph contains no cycles without using DFS/BFS first? I am trying to answer that for too long now and I...

R / SQL /Python : Extracting connected components from node-edge pairs

I struggle to come up with a title that describes what I'm trying to solve, so please comment if you have a better title! The solution can be in R, Python, or SQL (Aster TeraData SQL to be exact, though a solution any SQL language is very helpful for learning...

Code knight's tour using backtracking is not showing any output

This code is not giving any output. It should output a matrix of 8X8 size. #include <iostream> #define N 8 using namespace std; This function prints the matrix: void print(int arr[][N]){ int i, j; for (i = 0; i < N; i++){ for (j = 0; j < N; j++)...

Update minimum spanning tree if edge is added

I have a possible solution for the following question, but not sure if correct: Assume we have already found a minimum spanning tree T for a weighted, undirected graph G = (V,E). We would like to be able to efficiently update T should G be altered slightly. An edge is...

EVAL/APPLY: too many arguments given to F

Hello why do i get *** - EVAL/APPLY: too many arguments given to F on function call with nested lists parameter. I cannot figure it out, since I passed a simple nested list. (defun f (L) (cond ((NULL l) nil) ((listp (car L)) (append (F(car L))) (F(cdr L) (car (F...

in clojure, function argument type mismatch

clojure, function argument is vector, but it takes a map without problem. (defn flower-colors [colors] (str "The flowers are " (:flower1 colors) " and " (:flower2 colors))) (flower-colors {:flower1 "red" :flower2 "blue"}) ;; -> "The flowers are red and blue" Function flower-colors suppose to take vector type argument, but with...

Find mutually Edges with Spark and GraphX

I'm really new to spark and graphx. My question is that if i have a graph with some nodes that have mutual(reciprocally) edges between them, i want to select the edges with a good performace. An example: Source Dst. 1 2 1 3 1 4 1 5 2 1 2...

Read One Input File and plot multiple

I am trying to read one input file of below format. Where Col[1] is x axis and Col[2] is y axis and col[3] is some name. I need to plot multiple line graphs for separate names of col[3]. Eg: Name sd with x,y values will have one line graph and...

Find all possible paths between two nodes in a directed graph

I have directed graph which comes with an adjacency matrix and a start state + a target state. I need an algorithm to find all possible paths between these two nodes using adjacency matrix and implement it in C#. I don't understand how BFS and DFS can help me in...

Assigning a label to a created node in Neo4jClient

I want to create some nodes of type Person and Books using Neo4jClient. To do that, I have class Person like this: Public Class Person { Public String Name; } To create node, I have written something like this: Var RefA = client.Create(new Person(){Name ="John"}); (Client -> GraphicClient) When I...

Where do I find the 'Edmonds' class in networkx?

I am using the networkx framework for graph manipulation in python 2.7. For obtaining an optimal branching (arborescence) from a directed graph, I wanted to use the Edmond's algorithm. On networkx' website, one can find an implementation of that algorithm. The class 'Edmonds' is also listed in the reference. However,...

Plotting multivariate time-series data in R

My data looks like this: > head(Full.df) Date Month Week Year Count.S Count.G Count.W Count.F 1 2006-01-02 2006-01-01 2006-01-02 2006-01-01 0 7 9 6 2 2006-01-03 2006-01-01 2006-01-02 2006-01-01 0 13 12 4 3 2006-01-04 2006-01-01 2006-01-02 2006-01-01 0 13 15 4 4 2006-01-05 2006-01-01 2006-01-02 2006-01-01 0 20 6...

Plot multiple frames of different size on the same window

Consider this example: par(mfrow=c(2,3)) frame() image(matrix(1:100, nrow=100), main="my wide plot", axes=FALSE) frame() plot(rnorm(120), rnorm(120), main="plot 1") plot(dpois(0:20, lambda=6), type="b", main="plot 2") x = rnorm(100) y = x+runif(100, 10, 12) plot(x=x, y=y, , main="plot 3") How can I do to make my first graph (image(...) titled my wide plot) to occupy...

Insertion into a list doesn't reflect outside function whereas deletion does?

I am new to Lisp. Deletion of an item in a list by a function gets reflected outside the function but insertion doesn't. How can I do the same for insertion? For example (defun test (a b) (delete 1 a) (delete 5 b) (append '(5) b) (member '5 b)) (setq...

Heuristic to find the maximum weight independent set in an arbritary graph

The MWIS (Maximum weight independent set) is a NP-complete problem, so if P!=NP we cannot find a solution in a good enough time complexity. I am looking for an algorithm that can find an approximation of the MWIS in an arbitrary graph within a good time complexity. I am currently...

Invalid specialized parameter in method lambda list

I am trying to write a simple coin flip program in Common Lisp. This is the code I have (defun yn (let ht (random 1) (if (eq ht 1) (princ heads) (princ tails)) ) ) It seems simple enough, but I keep getting the error: "Invalid specialized parameter in method...

Labelling nodes in networkx

I'm trying to extract one set of values from a URL. This set has a unique list of numbers. The number of elements in this list should be equal to the number of nodes. So the label that these nodes get should come from the list extracted. How can this...

Set label on group multiplot in gnuplot

Im plotting one picture with 4 different graphs using gnuplot. Labels for their x and y axes have the same meaning. If Im plotting it like this: set multiplot layout 2,2 rowsfirst set xlabel "x" set ylabel "y" set title offset -3,-3 set xrange [20:70] set yrange [0:15000] set title...

Exceed evaluation depth when forward function in Emacs Lisp

Here is just a simplified code snipped I have not managed to work. I do not understand what is wrong. (defun enumerate-indicies (func) (let ((index 0)) (while (< index 5) (funcall func index) (setq index (1+ index))))) (defun enumerate-multiplied-indicies (func) (enumerate-indicies #'(lambda (index) (funcall func (* 10 index))))) The following...

Construct bipartite graph from columns of python dataframe

I have a dataframe with three columns. data['subdomain'], data['domain'], data ['IP'] I want to build one bipartite graph for every element of subdomain that corresponds to the same domain, and the weight to be the number of times that it corresponds. For example my data could be: subdomain , domain,...

Update minimum spanning tree if edge is removed

I am having trouble with the following question: Assume we have already found a minimum spanning tree T for a weighted, undirected graph G = (V,E). We would like to be able to efficiently update T should G be altered slightly. An edge is removed from G to produce a...

Find a MST in O(V+E) Time in a Graph

Similar question has been asked before, as in The question is: Given a connected undirected graph G=(V,E) and a weight function w:E→{1,2}, suggest an efficient algorithm that finds an MST of the graph in O(V+E) without using Kruskal. I had a look at the suggested solutions on the thread...

Read graphs from file as fast as possible

I have a txt file that contains 2 graphs and the number of vertices in the following format: 6 0 1 0 1 0 0 1 0 1 0 0 1 0 1 0 1 0 0 1 0 1 0 1 0 0 0 0 1 0 1 0...

How do I make a decaying oscilating function in python?

I have a code in python to represent the energy decay in a damped oscilator, it reads like this: def E(wt, Q): return (np.e**(-x/Q))*(1-(1/2*Q)*np.sin(2*x)) x = np.linspace(0,20,1000) y0 = E(x,2) y1 = E(x,4) y2 = E(x,8) y3 = E(x,16) plt.plot(x, y0, 'p', label=r'$Q=2$') plt.plot(x, y1, 'r', label=r'$Q=4$') plt.plot(x, y2, 'g',...

Disconnect all vertices in a graph - Algorithm

I am looking for an algorithm that finds minimal subset of vertices such that by removing this subset (and edges connecting these vertices) from graph all other vertices become unconnected (i.e. the graph won't have any edges). Is there such algorithm? If not: Could you recommend some kind of heuristics...

How to divide a graph into two sets having maximum interset connection?

I have a undirected graph , i want to divide it into two group in which intergroup connections are maximum and connection in same group are as minimum as possible.

undirected weighted graph data structure in c++

I am learning C++ and I appreciate your support by answering my question to help me to understand fundamental concepts. I am sure I need to learn many stuff, but I need a some advice to help me to find the right way. The problem I have is explained in...

Travels using graph

Someone can help me to think in the better way to adapt Dijkstra's Algorithm in these conditions? All I thought didn't was good. Example of input: GP4578 MADRID 01:00 PORTO 02:00 IK6587 PORTO 03:00 VALENCIA 05:00 05:30 TENERIFE 08:00 AB5874 VALENCIA 05:40 BERLIM 10:00 "VALENCIA 05:00 05:30" This is a...

Backquote String Interpolation

Is it possible to use lisp's macro to do string interpolation? For instance, can I make a macro like this: (defmacro test (a) `",a") So that (test abc) returns "abc" as a string? I could probably cheat by quoting it and turning that quote into a string, but that doesn't...

Highlighting specific ranges on a Graph in R

library(season) plot(CVD$yrmon, CVD$cvd, type = 'o',pch = 19,ylab = 'Number of CVD deaths per month',xlab = 'Time') if i wanted to highlight a region of the graph based on x values say from 1994-1998 how do i do this? Any thought would be appreciated Thanks....

android- I need to design 180 degree graph (half pie chart )

I need to design half pie chart in Android, I have searched a lot but can't find any solution. Any idea for a library to do that? Or can I make this manually? Thank you in advance. ...

When adding a random edge to a graph, which bridge edges are not bridge edges any longer?

A random edge e is added to a graph. It happens to not be a bridge edge. Let C be the connected component of the endpoints of e. Given the list L of all the bridge edges of C (before e was added), which is the fastest algorithm to find...

Responsive axis with percentage coordinates

In an attempt to build a responsive scatter graph with d3.js, I'm using %-based coordinates in a 100% x 100% svg element. How can I .call(axis) and get it to layout the axis using % and not px values, so that they always fit the svg and the plotted data?...