GitHub GraphQL API [Quick Start](新手友好)

由于软工项目选的是社交好友分析,又得捡起爬虫的那一套理论。。。社交好友分析应用数据才是王道,没有数据就没有发言权。写一个稳定的爬虫还是很重要的。准备爬github的时候发现github已经不再使用REST API,而是用的一个叫GraphQL API的东西。github上的教程在,但是把这一套教程从头到尾看完花了我几个小时,于是想在这里写一个快速上手教程。

Hint:github GraphQL API 网页版测试工具 很好用,侧面还有文档,可以随时查,很方便

简单介绍GraphQL

现在使用大部分的API都是REST架构的,每一类询问都有一个终端连接,然后通过GET或者POST方式带参数查询就好了,这样的缺点是不同类型的数据(例如用户信息,动态信息,好友信息)就得分开多次查询,而且一次询问会得到许多我们不需要的数据,当我们只想得到用户名对应的用户id时同时会得到用户的其他信息。

而在GraphQL中总共只有一个终端 https://api.github.com/graphql,我们只需要对这个终端POST我们构造好的查询,就可以得到结构上一一对应的json返回数据,有很高的自由度,一个复杂的GraphQL查询有时可以等价于上千条传统REST API查询。(由于这个原因,github对GraphQL的访问频率限制比REST高一些)。

一个简单的Sample

解释一下构造方式,QraphQL的操作分为Query和Mutation两种,一个是查询信息,另一个是修改或者发布信息。在爬虫中我们主要使用Query方式。

查询从user切入,由login(登录名,唯一的)切入,依次获得登录名,姓名,头像链接,简介。返回的json是这样的:

一个复杂的Sample

解释一下这个查询都干了啥。

首先从用户切入,获取该用户前10个repositories,角色可以是创建者,合作者以及组织成员,按照最后push的时间倒序给出(github要求这种询问必须要加first或者last数量)。接着是GraphQL中最核心的概念:

edges(边)和node(顶点)

repositories返回的结构并不是一个列表,而是一个边集,每条边指向网络中的一个顶点,repositories的边指向的就是一个个repository的node。通过这条边我们可以获得目标repo的名称,创建者,最后push时间等信息。GraphQL就是这样让我们可以把数据想象成一张网络,我们在网络上爬行,构造灵活巧妙的查询,一次性获得我们需要的一批信息。

我想获得一个repo的最近commits信息,发现在repo里怎么都找不到这个属性,后来网上查才知道是要通过ref来找到commit。

分页信息

上面的查询中可以看到edge有一个叫cursor的属性,每条边会有一个cursor属性,可以用来记录我们已经遍历到了哪一条边,在以后的询问中我们就可以用first:10,after:前一次的cursor,来访问接下来的10条记录。pageInfo属性是和edges并列的分页信息,其中的hasNextPage属性告诉我们是否存在下一页,可用作遍历时的终止条件。

得到的结果应该是

使用变量

为了使查询可以更容易的复用,GraphQL还可以使用变量,观察一下下面的例子:

variables:

这样我们就可以先构造查询模板,调用的时候改变参数就好了。

如何用Python实现

怎么用python实现也是个让新手(我)很头疼的事情,一个简明的Sample usage对于新手来说简直是雪中送炭。我经过一番暗黑摸索,搞出了如下套路:

requests包很好用,我们可以创建一个session保存会话,这样就不用每次都设定headers。headers里主要是添加Authorization为bearer方式的Token认证。data和普通post时候传的data不同,要多做一步json转化。

关于Token:Token是你要去自己的github上生成的,官方教程。记得不要把自己的Token给push到github上,不安全,而且会被github扫描出来给你revoke掉(不要问我是怎么知道的)。

 

从零开始的java+Eclipse+Struts+Tomcat+MySQL配置攻略

虽然网上已经有很多“靠谱”攻略,但是到搞出一个HelloWorld还是花了好大功夫(同一个软件不同的版本配置方式还是不一样的(深刻体会),而我又想尽量用最新版),踩了不少坑。趁热记一下配置步骤。

安装环境:

Win10
Java v1.8.0_131
Eclipse Java EE IDE for Web Developers, Version: Oxygen Release (4.7.0)
Struts2 v2.5.13
Tomcat v9.0
MySQL v5.7.19

第一步:安装Eclipse

大家的电脑上可能已经有Eclipse了,但是经验表明下载一个最新版的IDE总是可以省掉你很多事。
我之前用的 EclipseFor普通玩家 在环境配置里只能看到Tomcat8.0,在装了 EclipseFor企业玩家 (Java EE)后就可以直接看到Tomcat9.0,很方便。所以推荐装一个Eclipse Java EE IDE。

打开Eclipse的时候会让你选择workspace,这一个workspace里的项目用的是一套环境配置。接下来会在workspace里配置Tomcat。

第二步:安装Tomcat

2.1 下载解压测试Tomcat

Tomcat是一个开源的应用服务器,类似于Apache,优势在于处理动态网页。可以直接去官网下载。我下的是Tomcat9 64-bit Windows zip。下载之后解压在你知道的地方。

尝试运行 解压根目录\bin\startup.bat,然后在浏览器里访问 localhost:8080,应该能看见Tomcat的测试网页。

2.2 在Eclipse中引入Tomcat

在Eclipse你正在使用的workspace中,Window->Preferences->Server->Runtime Environments,点Add,选择Apache Tomcat v9.0,点next,然后Browse到你刚刚解压Tomcat的地址,jre选你的版本,点Finish。这时Tomcat就引入成功了。可以随手Window->Show View->Servers,这样就可以在下面console旁边看到server的内容了。

第三步:安装配置Struts2

3.1 建立maven-web项目

用maven可以很方便的帮你下载安装各种依赖项,所以我打算用maven来装struts,这样就不用自己下那些jar包了。但还是建议你去下一个struts,下那个Full的,后面配置的时候会用到。我下的是struts-2.5.13-all.zip

根据某大爷的指点,我们先建立一个Dynamic Web Project。可以在File->New->Dynamic Web Project,也可以直接在欢迎页面戳

然后你就会获得一个这样的架构。

接下来 右击项目->Configure->Convert to Maven Project。这样你的project就变成了Maven Project了。

3.2 安装Struts2

Maven可以通过添加Dependency来安装依赖包。在pom.xml里添加

或者 右击项目->Maven->Add Dependency

感兴趣的同学可以去查一下Dependencies和Dependency Management的区别。

这样就设置好了依赖。然后 右击项目->Run As->Maven install。过一会,如果正常你的项目里就会安装好以下jar包:

注意到log4j只有api的包,运行会报错,建议用同样的方法再安装log4j-core,版本号和api的那个一样。然后配置一下log4j。在Java Resources/src/ 下新建log4j2.xml,填入

3.3 配置struts的一个小技巧

现在到了我们刚刚下的那个60多MB的Struts2 Full发挥作用的时候了。

解压完之后在 struts-2.5.13\apps 下面是官方提供的一些example,是一些打包后的war文件,可以import到你的Eclipse workspace中,看别人的博客里的什么配置代码在他的版本实用但是在你的版本可能根本不适用,例如这个

别人用的可能是2.3,而我是2.5,没注意到就很尴尬。而在你的struts版本对应的example里就不用担心,一顿复制就很爽。

3.4 配置文件与HelloWorld

即使如此我还是要给一下我的配置代码,至少说一下要配置那些文件。

web.xml

在WebContent\WEB-INF\ 下有一个web.xml,我们要在这里设置欢迎页,和filter。

 

<welcome-file>项是告诉Tomcat默认欢迎页是什么,如果你想用index系列和default系列以外的可以加在这里。

下面的<filter-name>struts2</filter-name>那些是告诉Tomcat我们用的struts。

HelloWorld.jsp

在 WebContent\ 下新建 HelloWorld.jsp,填入

记住这个<s:property value=“name” />,到时候会变成你的名字。

index.jsp

在 WebContent\ 下新建 index.jsp,作为默认欢迎页,填入

记住我们在这里写了一个<form action=”hello”>,名为hello的action。

HelloWorld.java

在 Java Resources/src/ 下新建HelloWorld.java,填入

放在helloworld的package下。用来获取和保存名字。

struts.xml

最关键的struts.xml,在Java Resources/src/ 下新建struts.xml,填入

我对struts.xml的一些理解:

<include file=”struts-default.xml” />和extends=”struts-default”是一般要做的事情。接下来是说在package helloworld下,我们有一个名为hello的action,它和方法helloworld.HelloWorld绑定起来,结果运行HelloWorld.jsp。

大概流程就是:index.jsp里的action=”hello”和struts.xml里的action name=”hello”是联系起来的,index告诉struts有action,struts调用HelloWorld.java,HelloWorld.java拿到名字字符串,返回SUCESS,回struts调用HelloWorld.jsp,HelloWorld.jsp拿到HelloWorld.java的名字字符串,显示HelloWorld,name。

最后你的项目应该是这个结构:

3.5 运行测试

右击项目->Run As->Run on Server,效果如下:

运行的时候下面的console会有些红字,大部分是信息,可能会有一个warning:警告: [SetContextPropertiesRule]{Context} Setting property ‘source’ to ‘org.eclipse.jst.jee.server:SE2-booklib’ did not find a matching property. 这个无伤大雅,可以无视。

第四步:MySQL配置

4.1 下载安装MySQL

下载MySQL 5.7 installerJDBC驱动包,MySQL下下来应该是一个windows用的msi安装包,先装上。

解压JDBC驱动包(如果他是zip的话),会得到一个jar包:mysql-connector-java-5.1.44-bin.jar

4.2 测试MySQL

按下图所示建一个数据库用作后面的连接测试。

4.3 把驱动引入Eclipse

右键项目->Build Path->Configure Build Path->add External JARS加入驱动包。

注意:引入驱动包后java app已经可以连接数据库了,但是在Tomcat里跑java web的时候会提示没有这个Driver,解决方法是把这个包往Tomcat的lib或者WebContent/WEB-INF的lib下面再丢一个就好了。(配置云端服务器的时候也不要忘了)

然后Winidow->Preferences->Data Management->Connectivity->Driver Definitions->Add

这部直接把默认的那个找不到的包edit成你刚刚解压出来的jdbc的jar。

这里随手填一下你在安装MySQL时候填的账户密码数据库什么的。

4.4 数据库可视化

Window->Show View->Data Source Explorer,然后你就可以在下面看到你的数据库信息了。

到此配置完毕。

在java语言中使用Graphviz画图

 上图是使用Graphviz画图的一个示例,它是由以下dot脚本生成的。

如果你没有graphviz请去http://www.graphviz.org/下载(windows在添加环境变量后要restart才能生效),或者到网页版体验一下。

编写你的脚本保存成文件,例如graph.gv。然后在当前路径下运行命令行,使用最基本的dot命令:dot 脚本路径 -格式 -o 生成图片路径

这样会生成一个img.png图片像上图一样,graphviz还有很多其他布局可以自己尝试。

dot语言

dot是一种很方便的描述语言,上面表示一个有向图的dot脚本简单分成3大部分:

①框框,表示构造一个有向图。

②顶点,(其实不写顶点A,B直接加边A->B会默认自动生成A,B顶点)。

一般格式是:顶点名称 [属性=值, 属性=值, ……] [属性=值, ……]

一个顶点后面的属性都默认描述这个顶点,边同理,顶点名称会默认作为显示的标签,如果加了label=… 则显示时会显示label。

后面属性说明会覆盖全局的属性说明。

③边,边的一般格式是:起点->终点 [属性=值, ……] []

属性格式基本和顶点一样,可以重边,自环。

上图的脚本中只展示了样式,填充颜色,线条加粗几个属性,还有很多属性例如修改形状,对齐方案等等可以去看官方文档

java中调用graphviz

下面讲怎么用java简单地调用graphviz画图。(当然也可以去找别人写好的工具,例如graphviz-java

第一步我们要生成一个dot脚本

准备好图后我们要按顺序把图的信息写到字符串里再写到文件里。

第二步调用graphviz生成图片

用java调用命令行的方式来执行dot命令。(在linux里是调用bash)。

java中可以用Runtime来执行命令,一般用法:

也可以写一行:

然后就可以去指定位置收集生成的图片了,也可以顺便用命令行执行mspaint img.png 展示出来。

上面的完整代码可见软工实验一 WordGraph/ShowGraph.java

2017ICPC北京网络赛 G | hihocoder 1584 Bounce

For Argo, it is very interesting watching a circle bouncing in a rectangle.

As shown in the figure below, the rectangle is divided into N×M grids, and the circle fits exactly one grid.

The bouncing rule is simple:

1. The circle always starts from the left upper corner and moves towards lower right.

2. If the circle touches any edge of the rectangle, it will bounce.

3. If the circle reaches any corner of the rectangle after starting, it will stop there.

Argo wants to know how many grids the circle will go through only once until it first reaches another corner. Can you help him?

输入

The input consists of multiple test cases. (Up to 105)

For each test case:

One line contains two integers N and M, indicating the number of rows and columns of the rectangle. (2 ≤ N, M ≤ 109)

输出

For each test case, output one line containing one integer, the number of grids that the circle will go through exactly once until it stops (the starting grid and the ending grid also count).

样例输入

样例输出

题目大意:在n*m的方格表里,小球从左上角开始弹弹弹直到再次弹到角落,求只经过一次的格子的数量。
思路:总路径长度-经过两次的格子数量*2。

直觉告诉我们这个斜边间隔和gcd有关。
考虑3*6的情况

尝试做镜面反射,注意到反射后共用了一列边界,猜得到相邻斜线距离为\[L=gcd(n-1,m-1)\]路径总长为\[lcm(n-1,m-1)+1\]

n=3,m=6时L=gcd(2,5)=1,n=9,m=15时L=gcd(8,14)=2。

再考虑经过两次的格子数量。
按行把两次点分成两类,如下图红色类和蓝色类。

此图中L=2,红色类从L+1行L+1列开始每隔2L格一行,2L格一列(注意边界不能算),故红色类个数为\[\lceil\frac{n-L-1}{2\times L}\rceil\times\lceil\frac{m-L-1}{2\times L}\rceil\]

蓝色类从2L+1行2L+1列开始每隔2L格一行,2L格一列(注意边界不能算),故蓝色类个数为\[\lfloor\frac{n-2}{2\times L}\rfloor\times\lfloor\frac{m-2}{2\times L}\rfloor\]

于是答案为\[\frac{(n-1)\times(m-1)}{L}+1-2\times(\lceil\frac{n-L-1}{2\times L}\rceil\times\lceil\frac{m-L-1}{2\times L}\rceil+\lfloor\frac{n-2}{2\times L}\rfloor\times\lfloor\frac{m-2}{2\times L}\rfloor)\]

代码:

 

2017ICPC北京网络赛 B | hihocoder 1579 Reverse Suffix Array

描述

There is a strong data structure called “Suffix Array” which can effectively solve string problems.

Let S=s1s2…sn be a string and let S[i,j] denote the substring of S ranging from i to j. The suffix array A of S is now defined to be an array of integers providing the starting positions of suffixes of S in lexicographical order. This means, an entry A[i] is the starting position of the i-th smallest suffix in S and thus for all 1 < i ≤ n:  S[A[i-1], n] < S[A[i], n].

For example: the suffix array of “banana” is [6, 4, 2, 1, 5, 3].

Here comes another problem called “Reverse Suffix Array”.

Given a suffix array, you need to figure out how many lower case strings are there whose suffix array is the same as the given suffix array.

输入

First line contains a positive number T which means the number of test cases.

For each test cases, first line contains a positive number N, the second line contains N integer(s) which indicates the suffix array A.

1 ≤ T ≤ 10, 1 ≤ N ≤ 100,000

1 ≤ A[i] ≤ N (i = 1…N)

输出

For each test case, output one line contains the answer. If no qualified string exists, output 0.

样例输入

样例输出

 

题目大意是给后缀数组求原串有多少种可能性。

sa数组4 3 2 5 1可以画成下面:
④⑤
③④⑤
②③④⑤

①②③④⑤

首先可以得到$$④\le③\le②\le⑤\le①$$
但是其中有一些是小于号,需要从sa数组里判断。
对于sa数组相邻两行,例如④和③,
想要知道是\(④\le③\)还是\(④<③\),只需比较他们的后一段的大小,即⑤和④⑤的大小,这个可以从sa数组里直接查出来。 若\(⑤>④⑤\),那么\(④<③\),否则\(④\le③\)。这是本题的关键。

判断完后我们得到\[④<③\le②<⑤\le①\]
转化为求\(1\le④<③\le②<⑤\le①\le26\)的整数解的问题,这是个经典的插板问题。
做一步映射变为\(1\le④<③<②+1<⑤<①+2\le26\),
设原来中间有k个\(“\le”\),那么解的数量就是\(\binom{26+k}{n}\)。

大数的问题用java或者python搞一下就好了。

 

Andrew-Stankevich-Contest-47 | Codeforces gym 100608 E Elegant Square

题目大意是,构造一个n*n矩阵,由不同的正整数组成,使每行每列的数字积相等,还要求每个数字不能含有平方因子。

看完题目就能够想到这是一个构造题。搞一些质数行列错排一下对应位乘起来最后各个数字不一样就好。但问题是怎么排列能使每个数字不同。对题目给的样例分解一下会得到:

一开始想过按照错排的搜索顺序放置素数但好像素数好像不太够啊,又考虑随机放置素数错排,发现同样的数字就重排某个素数,但是太慢了要随机很久。

最后想到每个格子用两个素数组成,只要所有格子的素数对不同就好。

于是先搞出这样一个矩阵:

然后为了搭配一下再反着搞一下:

接着乘起来:

因为相同的数字都出现在斜线上,两个矩阵斜线方向不同,所以两个方向的斜线最多只能交出一个数,也就是说不同位置的数字应该不一样。看起来似乎做完了,但其实是有bug的。在n奇数时这样是没错的因为如下图,一个素数的两条斜线不会重叠,但是n偶数时会gg。

就是说,n为偶数时,一个数字会在它右下方n/2处重复。

为了解决偶数的问题,我们可以再构造一个类似的矩阵,然后将它的下n/2半行,循环下移,这样不改变题目要求的行列积的性质,但是重复数字不会出现在原来的右下n/2处。

最后把这个矩阵和原先的到的矩阵对应位乘起来,因为两个满足条件的矩阵乘起来还是行列积相同的,两个矩阵数字重复的位置又不同,故乘起来后的矩阵的数字是各不相同的: