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


Extracting nodes form dotted list (edges) in CLISP

Question:

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))
    nodes))

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?

Thanks.


Answer:

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))

Related:


If strings are vectors, why are they immutable?


lisp,common-lisp
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?

Algorithm Is Node A Connected to Node B in Graph


python,algorithm,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...

Plotting a data frame in R


r,graph,data.frame
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...

Read CSV and plot colored line graph


python,csv,matplotlib,graph,plot
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...

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


c++,c,graph
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++)...

Graph shortest path confusion


graph,dijkstra,shortest-path
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...

Responsive axis with percentage coordinates


javascript,svg,d3.js,graph,charts
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?...

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


python,graph,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


r,graph,plot,ggplot2,time-series
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...

Read graphs from file as fast as possible


c,input,graph,text-files
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...

Update minimum spanning tree if edge is added


algorithm,graph,tree,runtime,big-o
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...

Update minimum spanning tree if edge is removed


algorithm,graph,tree,runtime,big-o
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...

Read One Input File and plot multiple


python,numpy,matplotlib,graph,plot
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


c#,graph,path-finding
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...

Big O Notation with Absolute Value?


graph,big-o,notation
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...

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


algorithm,graph,graph-algorithm
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...

Plot multiple frames of different size on the same window


r,graphics,graph,plot
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...

Assigning a label to a created node in Neo4jClient


c#,graph,neo4j,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...

in clojure, function argument type mismatch


clojure,functional-programming,lisp
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...

sort graph by distance to end nodes


algorithm,sorting,graph,distance
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...

Find mutually Edges with Spark and GraphX


graph,apache-spark,vertices,edges,spark-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...

Plot: Add legend that overlay several Frames


r,graphics,graph,plot
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...

Graph shortest path infinite cycle


graph,dijkstra,shortest-path
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...

Exceed evaluation depth when forward function in Emacs Lisp


emacs,lisp,elisp
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...

Labelling nodes in networkx


python,graph,beautifulsoup,label,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...

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


list,lisp,common-lisp
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...

Plotting image and points on Matlab GUI via update function


image,matlab,user-interface,graph,plot
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...

Large Neo4j graph not showing up


database,graph,neo4j,cypher,graph-databases
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...

Airport travels using graph


c++,graph,shortest-path
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 algorithm to collect all edges which are on any path between two nodes


algorithm,graph,graph-algorithm
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...

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


algorithm,graph,graph-algorithm,minimum-spanning-tree
Similar question has been asked before, as in http://cs.stackexchange.com/questions/28635/find-an-mst-in-a-graph-with-edge-weights-from-1-2 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...

Set label on group multiplot in gnuplot


linux,graph,plot,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...

Highlighting specific ranges on a Graph in R


r,graph,highlight
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....

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


python,sql,r,graph,connected-components
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...

Travels using graph


c++,algorithm,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...

Disconnect all vertices in a graph - Algorithm


algorithm,graph
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 do I make a decaying oscilating function in python?


python,numpy,matplotlib,graph,physics
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',...

Backquote String Interpolation


macros,lisp,common-lisp
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...

Invalid specialized parameter in method lambda list


lisp,common-lisp
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...

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


android,graph
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. ...

calculating graph weight in python with NetworkX


python,graph,networkx,dijkstra
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...

EVAL/APPLY: too many arguments given to F


lisp,common-lisp,clisp
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...

Structuring large Lisp applications


lisp,common-lisp,quicklisp,asdf
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,...

Javascript multiple circular graphs


javascript,html,graph
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...

undirected weighted graph data structure in c++


c++,class,c++11,data-structures,graph
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...

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


algorithm,graph,graph-algorithm,linear-programming,np-complete
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...

Determining if a graph has a cycle without using DFS


algorithm,graph,cycle,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...

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


algorithm,graph
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.

Construct bipartite graph from columns of python dataframe


python,graph,dataframes,networkx
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,...

GDI+ curve “overflowing”


c#,graphics,graph,gdi+
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,...