精华内容
下载资源
问答
  • dag算法
    千次阅读
    2019-09-05 13:33:48

    有向无环图 DAG(directed acycline graph)

    相比较无向图来说,有向图比较特殊。

    有向图
    看这幅图,所有的边都带上了方向,也就是说 从节点1可以到节点2,但是节点2不能通过那条边到达节点1

    一般来说,有向无环图可以用来作为表示流程图的一种工具(想想流程图,是不是也是从一个任务到另一个任务或多个任务)
    于是判断一个流程图是不是很够顺利进行,就有了拓扑排序。

    先来看拓扑排序的代码吧。

    这里建图采用链式前向星,操作复杂度比vector要快。

    int topology(int n){
    	int ans = 0;
    	queue<int> q;
    	for(int i = 1; i <= n; ++i){
    		if(!in[i])	q.push(i);
    	}
    	while(!q.empty()){
    		int u = q.front();	q.pop();
    		Time[u] += tt[u];
    		ans = max(ans,Time[u]);
    		for(int i = head[u]; ~i ; i = edge[i].nxt){
    			Edge &e = edge[i];
    			Time[e.v] = max(Time[e.v],Time[u]);
    			if(!(--in[e.v])) q.push(e.v);
    		}
    	}
    	return ans;
    }
    

    为什么拓扑排序能够判断一个有向图是不是能够顺利进行而没有冲突呢?

    首先,拓扑排序将入度为0的点插入队列,在这里如何去理解入度为0? -> 在一个流程图中就意思是 他没有前驱(就做这个任务前没有其他任务的前提),因此可以插入队列(也就是这个任务可以做),然后,我们要把他的所有出度的边删掉(例如u->v 删掉这条边,in[v]减1,这就说明v的任务的前置要求少了一个,当为0的时候,就又说明这个任务可以做了,于是又插入队列,最后我们只需要判断我们做的任务是不是做完了(检查所有的in[i[,或者记录做的任务数都可),如果没做完,说明这个DAG是有环的,显然有环的时候肯定不满足流程图,因为产生了矛盾。

    同时我们也可以用拓扑排序去计算一个任务的最早开始时间,以及去判断DAG是否有环,并且也可以求出关键路径

    例如:P1113 杂务
    题意:
    John的农场在给奶牛挤奶前有很多杂务要完成,每一项杂务都需要一定的时间来完成它。比如:他们要将奶牛集合起来,将他们赶进牛棚,为奶牛清洗乳房以及一些其它工作。尽早将所有杂务完成是必要的,因为这样才有更多时间挤出更多的牛奶。当然,有些杂务必须在另一些杂务完成的情况下才能进行。比如:只有将奶牛赶进牛棚才能开始为它清洗乳房,还有在未给奶牛清洗乳房之前不能挤奶。我们把这些工作称为完成本项工作的准备工作。至少有一项杂务不要求有准备工作,这个可以最早着手完成的工作,标记为杂务 1 1 1。John有需要完成的 n n n个杂务的清单,并且这份清单是有一定顺序的,杂务 k ( k > 1 ) k(k>1) k(k>1)的准备工作只可能在杂务 1 1 1 k − 1 k−1 k1中。

    写一个程序从 1 1 1 n n n读入每个杂务的工作说明。计算出所有杂务都被完成的最短时间。当然互相没有关系的杂务可以同时工作,并且,你可以假定John的农场有足够多的工人来同时完成任意多项任务。

    在拓扑排序的过程中去维护时间即可。

    #include <iostream>
    #include <algorithm>
    #include <cstring>
    #include <queue>
    using namespace std;
    const int maxn = 1e5+5;
    struct Edge{
    	int u,v,nxt;
    }edge[maxn];
    int head[maxn],tot,in[maxn],Time[maxn],tt[maxn];
    inline void init(){
    	memset(head,-1,sizeof(head));
    	tot = 0;
    }
    inline void addedge(int u,int v){
    	edge[++tot] = {u,v,head[u]};
    	head[u] = tot;
    	in[v]++;
    }
    int arr[maxn];	// 点权
    int topology(int n){
    	int ans = 0;
    	queue<int> q;
    	for(int i = 1; i <= n; ++i){
    		if(!in[i])	q.push(i);
    	}
    	while(!q.empty()){
    		int u = q.front();	q.pop();
    		Time[u] += tt[u];
    		ans = max(ans,Time[u]);
    		for(int i = head[u]; ~i ; i = edge[i].nxt){
    			Edge &e = edge[i];
    			Time[e.v] = max(Time[e.v],Time[u]);
    			if(!(--in[e.v])) q.push(e.v);
    		}
    	}
    	return ans;
    }
    int main()
    {
    	init();
    	int n;	cin >> n;
    	for(int i = 0,op,len,x; i < n; ++i){
    		cin >> op >> len;	tt[op] = len;
    		while(cin >> x,x){
    			addedge(x,op);
    		}
    	}
    	cout << topology(n) << endl;
    	return 0;
    }
    

    ve(i): 事件vi最早开始时间
    vl(i): 事件vi最晚开始时间
    e(i) = ve(i): 活动的最早开始时间是活动的弧尾事件最早发生时间
    l(i) = vl(k) - time(i,k) 活动的最晚发生时间时活动的弧头的最晚发生时间减去活动的持续时间
    关键活动时 e(i) = l(i); 关键路径 ve(i) = vl(i)

    关键路径:

    #include <bits/stdc++.h>
    using namespace std;
    const int maxn = 1e5+5;
    struct Edge{
        int u,v,nxt,w;
    }edge[maxn<<1];
    struct REdge{   // 反向边
        int u,v,nxt,w;
    }redge[maxn<<1];
    int rhead[maxn],rtot;
    int head[maxn],tot,in[maxn];
    inline void addedge(int u,int v,int w){
        edge[++tot] = {u,v,head[u],w};
        head[u] = tot;
    }
    inline void addRedge(int u,int v,int w){
        redge[++rtot] = {u,v,rhead[u],w};
        rhead[u] = rtot;
    }
    int Time[maxn],Time2[maxn];
    inline void topsort(int n){
        memset(Time2,0x3f,sizeof(Time2));
        queue<int> q;   vector<int> vv;
        for(int i = 0; i < n; ++i){
            if(!in[i]) q.push(i);
        }
        while(!q.empty()){
            int u = q.front();  q.pop();
            vv.push_back(u);
            for(int i = head[u]; ~i; i = edge[i].nxt){
                Edge &e = edge[i];
                Time[e.v] = max(Time[e.v],Time[e.u]+e.w);
                --in[e.v];
                if(!in[e.v]){
                    q.push(e.v);
                }
            }
        }
        //for(int i = 0; i < n; ++i)  Time2[i] = Time[i];
       // cout << ans << endl;
       int u = vv[vv.size()-1];
       Time2[u] = Time[u];
        for(int i = vv.size()-1; i >= 0; --i){
            int u = vv[i];
            for(int j = rhead[u]; ~j; j = redge[j].nxt){
                REdge &e = redge[j];
                Time2[e.v] = min(Time2[e.v],Time2[e.u]-e.w);
            }
        }
        for(int i = 0; i < n; ++i)  cout << Time[i] << ' ';
        cout << endl;
        for(int i = 0; i < n; ++i)  cout << Time2[i] << ' ';
        cout << endl;
    }
    int main()
    {
        int n,m;
        cin >> n >> m;
        memset(head,-1,sizeof(head));
        memset(rhead,-1,sizeof(rhead));
        for(int i = 0; i < m; ++i){
            int u,v,w;  cin >> u >> v >> w;
            addedge(u,v,w);
            addRedge(v,u,w);
            in[v]++;
        }
            //cout <<"ok"<< endl;
        topsort(n);
        return 0;
    }
    
    更多相关内容
  • 单源最短路径dag算法

    2021-12-22 10:36:05
    介绍可以根据拓扑排序来计算有向无环图(dag)的单源最短路径,因为拓扑排序正好是建立在无环的基础上,在这个图中没有负权重边以及负权重回路边。实现因为实现是基于拓扑排序的,所以基本结构和拓扑排序一致,只是多...

    介绍

        可以根据拓扑排序来计算有向无环图(dag)的单源最短路径,因为拓扑排序正好是建立在无环的基础上,在这个图中没有负权重边以及负权重回路边。

    实现

        因为实现是基于拓扑排序的,所以基本结构和拓扑排序一致,只是多了一个距离的定义:

    enum COLOR
    {
    	WHITE = 0,
    	GRAY,
    	BLACK
    };
    
    typedef struct _Vertex
    {
    	char color;
    	int vertex;
    	int start;
    	int finish;
    	int distance;
    }Vertex;
    
    typedef struct _Node
    {
    	Vertex *pVertex;
    	struct _Node *parent;
    	struct _Node *next;
    }Node;
    typedef struct Edge_
    {
    	int x;
    	int y;
    	bool operator == (const struct Edge_& l)
    	{
    		return x == l.x && y == l.y;
    	}
    }Edge;
    
    bool operator < (const Edge& r, const Edge& l)
    {
    	if (r.x == l.x)
    	{
    		return r.y < l.y;
    	}
    	return r.x < l.x;
    }
    
    
    static map<Edge, int> g_edges;
    static int g_time = 0;
    static list<Node*> g_Nodes;
    
    Node* initNode(Node **graph, int vertex)
    {
    	Node *p = new Node;
    	p->pVertex = graph[vertex - 1]->pVertex;
    	p->parent = nullptr;
    	p->next = nullptr;
    
    	return p;
    }
    
    void InsertVertex(Node **graph, Node *node, int vertex, int weight)
    {
    	Node *p = node;
    	while (nullptr != p->next)
    	{
    		p = p->next;
    	}
    	p->next = initNode(graph, vertex);
    	Edge edge;
    	edge.x = node->pVertex->vertex;
    	edge.y = vertex;
    	g_edges.insert(std::pair<Edge, int>(edge, weight));
    }
    
    void initGraph(Node **list, int vertexCount)
    {
    	for (int i = 0; i < vertexCount; ++ i)
    	{
    		list[i] = new Node;
    		list[i]->parent = nullptr;
    		list[i]->next = nullptr;
    		list[i]->pVertex = new Vertex;
    		list[i]->pVertex->color = WHITE;
    		list[i]->pVertex->vertex = i + 1;
    	}
    }
    
    void depthFirstSearchVisit(Node **graph, Node *node)
    {
    	++ g_time;
    	node->pVertex->start = g_time;
    	node->pVertex->color = GRAY;
    
    	Node *p = graph[node->pVertex->vertex - 1];
    	while (nullptr != p)
    	{
    		if (WHITE == p->pVertex->color)
    		{
    			p->parent = node;
    			depthFirstSearchVisit(graph, p);
    		}
    		p = p->next;
    	}
    	node->pVertex->color = BLACK;
    	++ g_time;
    	node->pVertex->finish = g_time;
    	g_Nodes.push_front(node);
    }
    
    int getSentinel()
    {
    	return numeric_limits<int>::max();
    }
    
    void depthFirstSearch(Node **graph, int vertexCount)
    {
    	for (int i = 0; i < vertexCount; ++ i)
    	{
    		if (WHITE == graph[i]->pVertex->color)
    		{
    			depthFirstSearchVisit(graph, graph[i]);
    		}
    	}
    }

        这里有使用到深度优先搜索拓扑排序

    void initializeSingleSource(Node **graph, Node *root)
    {
    	for (int i = 0; i < VERTEX_NUMBER; ++ i)
    	{
    		graph[i]->pVertex->distance = getSentinel();
    		graph[i]->parent = nullptr;
    	}
    	root->pVertex->distance = 0;
    }
    
    void relax(Node *u, Node *v, int weight)
    {
    	if (v->pVertex->distance > u->pVertex->distance + weight)
    	{
    		v->pVertex->distance = u->pVertex->distance + weight;
    		v->parent = u;
    	}
    }

        这里的初始化和松弛是bellman算法中的实现。

        下面来看看dag的实现:

    int w(int x, int y)
    {
    	Edge edge;
    	edge.x = x;
    	edge.y = y;
    	return g_edges[edge];
    }
    
    void topologicalSort(Node **graph)
    {
    	depthFirstSearch(graph, VERTEX_NUMBER);
    	for (int i = 0; i < VERTEX_NUMBER; ++ i)
    	{
    		cout << "vertex " << i + 1 
    			<< ",start = " << graph[i]->pVertex->start
    			<< ",finish = " << graph[i]->pVertex->finish;
    		cout << endl;
    	}
    
    	for (auto iter = g_Nodes.begin(); iter != g_Nodes.end(); ++ iter)
    	{
    		cout << (*iter)->pVertex->vertex << " ";
    	}
    	cout << endl;
    }
    
    void dagShortestPath(Node **graph)
    {
    	topologicalSort(graph);
    	initializeSingleSource(graph, graph[0]);
    	cout << "dag shortest path: " << endl;
    	for (auto iter = g_Nodes.begin(); iter != g_Nodes.end(); ++ iter)
    	{
    		int vertex = (*iter)->pVertex->vertex;
    		Node *p = graph[vertex - 1]->next;
    		while (nullptr != p)
    		{
    			relax(graph[vertex - 1], graph[p->pVertex->vertex - 1], w(vertex, p->pVertex->vertex));
    			p = p->next;
    		}
    	}
    }

        从上面的实现中可以看出,dag中最短路径的算法是,先进行拓扑排序,然后根据拓扑排序,在对每个顶点的邻接表进行松弛技术,等算法结束,最短路径也已求出。

        对上面的代码进行测试:

    int _tmain(int argc, _TCHAR* argv[])
    {
    	copyright();
    	cout << "directed acylic graph: " << endl;
    
    	Node *graph[VERTEX_NUMBER] = {0};
    	initGraph(graph, VERTEX_NUMBER);
    
    	InsertVertex(graph, graph[0], 2, 6);
    	InsertVertex(graph, graph[0], 4, 7);
    	InsertVertex(graph, graph[1], 3, 5);
    	InsertVertex(graph, graph[1], 4, 8);
    	InsertVertex(graph, graph[1], 5, -4);
    	InsertVertex(graph, graph[2], 2, -2);
    	InsertVertex(graph, graph[3], 3, -3);
    	InsertVertex(graph, graph[3], 5, 9);
    	InsertVertex(graph, graph[4], 1, 2);
    	InsertVertex(graph, graph[4], 3, 7);
    
    	cout << "depth First Search:" << endl;
    
    	dagShortestPath(graph);
    
    	for (int i = 0; i < VERTEX_NUMBER; ++ i)
    	{
    		if (nullptr != graph[i]->parent)
    		{
    			cout << "edge:" << graph[i]->parent->pVertex->vertex
    				<< "," << graph[i]->pVertex->vertex << endl;
    		}
    	}
    
    
    	return 0;
    }
    dag最短路径运行结果

    dag最短路径运行结果

        下面来看看dag最短路径的图解过程:

    dag最短路径运行过程图解

    dag最短路径运行过程图解

    展开全文
  • Alabs丨浅谈DAG算法的实现

    千次阅读 2018-07-25 15:31:39
    一.DAG算法逻辑 假设有网络中有4个节点(A,B,C,D),每个节点都发送一笔交易,交易被包含在一个event里gossip到其他节点,一次gossip会把本节点的所知道的对方不知道的交易随机发送给其他节点,每个节点维护一...

    一.DAG的算法逻辑

    假设有网络中有4个节点(A,B,C,D),每个节点都发送一笔交易,交易被包含在一个event里gossip到其他节点,一次gossip会把本节点的所知道的对方不知道的交易随机发送给其他节点,每个节点维护一个完整的图谱,通过投票算法,最后对每个event打一个时间戳,讲解具体逻辑前,我们先看一下event的数据结构:

    type Event struct {

    Transactions    [][]byte         //the payload

    selfParent      string

    otherParent     string

    Creator         []byte           //creator's public key

    Timestamp       time.Time        //creator's claimed timestamp of the event's creation

    roundReceived      *int

    consensusTimestamp time.Time

    }

    Transactions字段是Event里包含的所有交易,selfParent和otherParent是该Event父Event的hash,包括了自己创建的父Event和其他节点创建的父Event,Creator是创建者的公钥,Timestamp是创建Event时的时间戳,roundRecevied是Event被第几层round里的famous witnesses 所共识的,consensusTimestamp是Event被共识时的时间戳。

    接下来我们来看看具体的共识过程:

     

    1.A,B,C,D在初始化时,各自创建一个rootEvent,然后B随机选择一个节点(假设选中的是D),然后B把自己所知道的D不知道的所有Events发送给D(这里只有B在一开始创建的rootEvent),D创建一个新的Event(该Event的selfParent为D的rootEvent,otherParent是B的rootEvent),然后D再随机把自己知道的Event(包括新创建的)全部发送给B,B再创建一个新的Event,这样B就知道了4个Event(自己创建的两个和D创建的两个),D知道3个Event(不包括B最后创建的)。

    2.B再随机选择A,然后把自己知道的4个Event发送给A,A创建一个新的Event,这样一直增长下去,就形成了一个图谱结构。

    3.famous witnesses的确定,首先有几个概念我们来看一下,see和strongly sees ,

    see就是说Event之间有祖孙关系,假设有Event (B2) 和Event (A3),假设B2是A3的祖先,A3是B2的子孙,那么就说A3可以看到B2,

    strongly sees是两个Event之间存在祖孙关系,并且这两个Event所有相连的所有路径中所过节点和超过2/3的节点,视为其中一个Event强看见另一个Event。

    witness 是一个round中的第一个Event(rootEvent都是witness),round的确定方法是,一个Event可以强看见当前round里的2/3以上witness,那么该Event的round加一。

    famous  witness的确定机制是,下一层round里的witness对上一层可见的witness进行投票,再下一层round里的witness来计票,具体规则是,如果一个witness(A3)对上一层里的witness(B2)可见,那么投YES,当所有投票的witness(A3,B3,C3,D3)对被投票的witness(B2)投了YES,那么被投票的witness(B2)声明为famous,再下一层的

    witness(B4)对参与投票的witness(A3,B3,C3,D3)如果是强可见的,那么计票为YES,那么该投票是有效的,当有效的票数超过2/3,那么被投票的witness(B2)选为famous witness。

    4.当确定了famous witnesses,我们就可以为events找到一个consensusTimestamp和一个roundRecevied,规则是,当一个event(X)可以被下一层round里的所有famous witnesses看见,那么该event(X)的roundRecevied便是看见它所有famous witnesses所在的round值,该event(X)的consensusTimestamp确定规则是,找出所有famous witness的祖先event,并且是该event(X)的子孙的events,把这些events的时间戳排序,然后找中间的那个时间戳作为该event(X)的consensusTimestamp。

    被打上consensusTimestamp的event便是形成共识的event,然后根据roundRecevied对event进行排序。

    二.DAG的实现

     

    基本理论部分如上所述,接下来看一下工程上是如何实现以DAG算法为共识的项目,本项目主要实现了把dag形成共识后同一RoundReceived的交易映射到一个区块里,形成一个线性的区块链数据结构,使用了ethereum的账本结构。

    上面类图,主要体现了DAG的核心类模块,crypto,网络通信等模块没有包含其中。

    Event是DAG的基本数据结构,前面已经有介绍,Store负责数据的存储和管理,DAG类是DAG共识算法的核心,主要方法实现了可见与强可见的判断,划分round,决定famous witness,决定roundReceived,获取知道的Event,投票。

    Core整个节点的核心逻辑,包含了插入Event,合并Event,运行共识等。

    node模块,负责节点间的gossip,处理接收到的gossip请求并返回,负责ethereum与节点的proxy通信。

    结合以上,我们看一下具体的业务流程,从一笔交易的发起,到交易入块的整个逻辑。

    1.我们启动一个ethereum节点和一个DAG节点,它们之间是通过proxy进行连接。

    2.ethereum调用proxy把交易传到DAG节点,DAG节点调用Core的AddTransctions把收到的交易加入到transactionpool里。

    3.gossip心跳检测到需要发起gossip,便会创建一个新的event,把transactionpool的交易全部打包到event里,然后插入到Store里。

    4.随机选取一个peer,发起gossip,从目标peer拉取自己不知道对方知道的event,并把自己知道的event传给对方。

    5.拿到对方返回的event,调用Core的EventDiff来合并Event,并增加pedding区的Event,然后执行RunConsensus,来DivideRounds,调用DecideFame决定famous witnesses。

    6.通过多次的gossip,famous witnesses被确定,然后调用FindOrder去决定

    roundReceived和consensusTimestamp,然后排序。

    7.调用handleNewConsensusEvents取出新共识过的event,并把里面的交易打包到一个块里,清空pedding区。

    8.把区块返回到ethereum,ethereum执行区块里的交易,并把账本状态返回到DAG,DAG把账本状态入块,然后签名,再把签名广播到其他DAG节点,其他DAG节点收到签名,验证无误,与自己的签名合并入块,再把自己的签名广播。

     

    上图是我们通过4节点测试后取得的成功,我们可以看到其中一个块是包含了267581笔交易,用时大概是6秒左右,另一个块包含了835846笔交易,由此可见,在有限的节点测试环境中,达成一次共识需要的gossip次数是有限的,所以,增加单次网络IO(gossip)的数据负载(交易数量),产块时间间隔并没有受到严重影响,平均产块时间3-5秒。但是块中的交易数量得到了质的提高。

    心得总结:

    一:账本的一致性演化问题:

    区块链的核心问题是解决公共网络环境下分布式账本的一致性演化问题,我们从两个问题去分析:

    1.谁来记账。

    2.非记账者如何验证记账者有没有说谎。

    以成熟的比特币和以太坊为例,也就是pow共识算法,通过哈希算力来争夺记账权,以Merkle Tree 或者 Merkle Patricia tree 作为账本的基础数据结构,让“非记账者”快速验证记账者有没有说谎话,再加上惩罚机制的引入(算力的付出),让记账者从经济学的角度没有计坏账的动机,最终让比特币,以太坊成为数字货币领域,区块链技术的成功实践者。

    我们知道以太坊的一个区块头中存在三个重要的数据,它们是Merkle树根节点的哈希,包括:状态树,交易树,收据树。在以太坊网络中,一个节点上的世界账本历史数据是经过哈希算力证明的,所以它是可信的,当一个矿工成功记了一批帐后(所谓的挖矿),它付出了算力,广播出去后,其他节点会根据本地的可信账本数据去验证矿工记得帐是否正确,核心的流程:

    A.基于自己本地的账本(当然要努力保持本地账本是当前最长链,这里不做详细描述),对块中得交易按顺序执行。然后改变本地世界账本状态,以及收据树等,形成新的世界状态数根哈希,和收据树根哈希。

    B.比对本地新的世界状态和记账者给出的结果是否一致。即三个merkle根哈希值的比较。一致,那么便承认记账者没有说谎,本地账本和记账者的账本就会保持一致的演化下去。

    这样随着网络中一个一个块得产生,全世界的每个账本都保持一致的演化下去。

    二:我们的DAG主链(哈希图普)逻辑:

    DAG 共识与pow共识最大的区别在于,交易顺序的确定,以太坊中是单个矿工说了算,矿工可以根据自己的挖矿策略(交易手续费的高低)来决定一个块中包含那些交易,然后通过哈希算力争夺记账权。而哈希图谱中,如上文对哈希图谱算法的分析,hash graph 通过gossip协议在对一个round中的交易顺序达成一致,并形成一个块,简单来说这些交易顺序是通过协商确定的,一旦确定不可更改,这样,分布式中的每一个账本根据相同的交易顺序向下演化世界状态,最终可以保持账本的一致性。我们的具体流程:

    1.哈希图谱共识模块,通过gossip协议对全网中一个round的交易排序问题达成共识,并形成中间状态的块,然后交给账本模块去验证,执行交易。使用交易树Merkel根哈希,保证已达成共识的交易顺序不被修改。

    2.账本模块验证,执行完交易序列后,会生成新的世界状态树Merkel根(stateRoot),然后回复给哈希图普共识层。

    3.哈希图谱共识层将块的交易树根,stateRoot, 广播出去,其他节点对刚才达成的交易序列共识作了相同的验证,执行。通过比较stateRoot可以得知演化结果是否一致,这样就可以相互收集签名确认,当一个块得到网络中多数节点签名确认后,块中交易即可认为达成最终共识。

     

    关于ALabs:ALabs是由Achain创始人崔萌发起并成立的区块链实验室,以打造高效的区块链网络为已任,主要进行尖端区块链技术研究,包括区块链底层技术、区块链扩展、区块链治理等,并提供区块链基础设施搭建、以及场景方案应用等服务。

    展开全文
  • http://jiezhu2007.iteye.com/blog/2041422大学里面数据结构里面有专门的一章图论,可惜当年没有认真学习,现在不得不再次捡 起来。真是少壮不努力,老大徒伤悲...让我们再来看看DAG算法现在都应用在哪些 hadoop引擎...

    http://jiezhu2007.iteye.com/blog/2041422

    大学里面数据结构里面有专门的一章图论,可惜当年没有认真学习,现在不得不再次捡 起来。真是少壮不努力,老大徒伤悲呀!什么是DAG(Directed Acyclical Graphs),先来看下教科书上的定义吧:如果一个有向图无法从某个顶点出发经过若干条边回到该点。让我们再来看看DAG算法现在都应用在哪些 hadoop引擎中。

    Tez:

    Hortonworks开发的DAG计算框架,是从MapReduce计算框架演 化而来的通用DAG计算框架,核心思想是将Map和Reduce两个操作进一步拆分,即Map被拆分成Input、Processor、Sort、 Merge和Output, Reduce被拆分成Input、Shuffle、Sort、Merge、Processor和Output等,这样,这些分解后的元操作可以任意灵活组 合,产生新的操作,这些操作经过一些控制程序组装后,可形成一个大的DAG作业,可以用来替换Hive/Pig等。

    003fb814e9f60fc603f44685bc723ab9.png

    Oozie:

    Oozie工作流是放置在控制依赖DAG(有向无环图 Direct Acyclic Graph)中的一组动作(例如,Hadoop的Map/Reduce作业、Pig作业等),其中指定了动作执行的顺序。我们会使用hPDL(一种XML流程定义语言)来描述这个图。

    hPDL是一种很简洁的语言,只会使用少数流程控制和动作节点。控制节点会定义执

    行的流程,并包含工作流的起点和终点(start、end和fail节点)以及控制工作流执行路径的机制(decision、fork和join节点)。

    动作节点是一些机制,通过它们工作流会触发执行计算或者处理任务。Oozie为以下类型的动作提供支持: Hadoop

    map-reduce、Hadoop文件系统、Pig、Java和Oozie的子工作流。

    Spark:

    Resilient Distributed Dataset

    (RDD)弹性分布数据集

    是Spark的最基本抽象,是对分布式内存的抽象使用,实现了以操作本地集合的方式来操作分布式数据集的抽象实现。RDD是Spark最核心的东西,它表

    示已被分区,不可变的并能够被并行操作的数据集合,不同的数据集格式对应不同的RDD实现。RDD必须是可序列化的。RDD可以cache到内存中,每次

    对RDD数据集的操作之后的结果,都可以存放到内存中,下一个操作可以直接从内存中输入,省去了MapReduce大量的磁盘IO操作。

    元数据的结构是DAG(有向无环图),其中每一个“顶点”是RDD(包括生产该RDD的算子),从父RDD到子RDD有“边”,表示RDD间的依赖性。Spark给元数据DAG取了个很酷的名字,Lineage(世系)。

    Spark程序的运行场景。它由客户端启动,分两个阶段:第一阶段记录变换算子序列、增量构建DAG图;第二阶段由行动算子触 发,DAGScheduler把DAG图转化为作业及其任务集。Spark支持本地单节点运行(开发调试有用)或集群运行。

    13d727da597f0b06e5715406ef51a90c.png

    展开全文
  • 一,DAG算法的思想 根据结点的拓扑排序次序来对带权重的有向无环图G进行边的松弛操作,在有向无环图中,边可以为负值但是没有权重为负值的环,因此最短路都是存在的。二,DAG算法介绍准备阶段:一副赋值有向无环图...
  • 具有任务内并行性的任务多使用DAG有向无环图表示,联合调度方式解决该类任务调度问题。
  • dag.js 具有边缘标记的简单DAG(有向无环图)模块。 安装 $ npm install dagjs 用法 let Dag = require ( 'dagjs' ) ; let dag = new Dag ( ) ; // ... 例子 添加边: let dag = new Dag ( ) ; // add(from, to, ...
  • java实现简单的Dag

    2020-12-17 12:03:03
    基于java进行的实现简单Dag图;附件中包含java根据配置的dagJson。1实现了filter过滤,返回指定的字段;2实现了按指定字段排序,返回指定的字段;可以自己添加mysql、Oracle、redis、hive、es、sparksql、clickhouse...
  • dag:节点连线布局算法

    2021-06-14 15:47:13
    dag node link algorithm, base on d3.js API annotation is in main.js. support 1000+ nodes' link. 10000 nodes cost 5 seconds. 节点连线布局算法,基于d3 具体接口可以参考main.js中的示例。 to do: 1.布局优化...
  • 综合考虑距离、剩余能量、转发包数等因素,提出一种基于电网监测的无线传感器网络短路径路由算法(SPRA-PNM)。SPRA-PNM算法通过短路径场的建立来预留多条较短距离路径,并在实际数据转发时选择剩余能量最大的节点...
  • Bellman-Ford算法能在更普遍的情况下(存在负权边)解决单源点最短路径问题,但是对于DAG,可以有更加简化的算法去计算,使得时间复杂度更低。 针对DAG的特点,以拓扑排序为基础,提出了解决DAG的最短路径问题的简单...
  • DAG最短路算法

    2016-04-01 10:47:00
    int DAG_SHORTEST_PATHS(){ topu_rudu(); for(int i = 0;i ;i++){ d[i] = INF; F[i] = -1; } while(!que.empty()){ int u = que.front(); que.pop(); int si = vec[u].size(); for(int i = 0;i ;i+...
  • 大学里面数据结构里面有专门的一章图论,可惜当年没有认真学习,现在不得不再次捡起来。...让我们再来看看DAG算法现在都应用在哪些hadoop引擎中。 Tez: Hortonworks开发的DAG计算框架,是从MapR...
  • DAG拓扑排序

    2021-07-30 14:50:42
    对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边<u,v>∈E(G),则u在线性序列中出现在v之前。通常,这样的线性序列称为满足...
  • NPC 算法是为学习贝叶斯网络而设计的,由 Steck 于 2001 年形成为 DAG 这个实现基于论文[1],详细信息可以在这篇博士论文中看到。 从“ControlCentor.m”开始,这里有一个简单的例子说明如何使用代码。 如果有...
  • 重构DAG任务算法

    2021-05-31 13:04:47
    重构DAG任务算法 重构DAG任务是在基于模型转化的多类型任务调度算法中的关键一步,节点的调度是基于重构后的任务图的,因此怎样得到重构后的任务图是调度问题的前提和基础。 第一步重构DAG任务图,如图1.1和1.2为...
  • 一种基于模糊聚类的网格DAG任务图调度算法.pdf
  • 这篇文章并不是详细讲解Bellman-Ford算法的,而是介绍一种“从DAG算法逐步演化出Bellman-Ford算法”的方法。这个知识点是我从参考资料里的视频获得的,有兴趣的同学可以查看相关视频。这里主要记录我的理解和总结。 ...
  • 云环境中dag调度算法的设计与实现.doc
  • 为此,首先分析讨论了一组多DAG共享云计算资源调度中的多DAG数量、属性结构分布特点与资源需求量之间的关系,并在此基础上提出了基于资源需求强度预测变异方法的进化算法EFRD,有效地解决了云计算环境下多DAG共享...
  • 因此,它首先使用最大最小父子节点 (MMPC) 算法构建 DAG(有向无环图)的骨架。 之后,它使用贝叶斯狄利克雷似然等价统一分数引导顶点之间的边。 有关更多信息,请阅读所附报告或*最大-最小爬山贝叶斯网络结构学习...
  • d3-dag 数据集通常是分层的,但不在树结构中,例如遗传数据。 在这些情况下, d3-hierarchy可能无法满足您的需求,这就是为什么存在d3-dag (有向无环图)的原因。 该模块实现了用于处理DAG的数据结构。 旧版本旨在...
  • 比较、聚合和聚类有向无环图 (DAG)。 纸张代码: ... update_center_greedy.m DAG 聚合的贪心算法。 update_center_median.m DAG 聚合的中值算法。 graph_k_mean.m用于 DAG 聚类的 K-Means 方法。
  • 多阶段决策问题——DAG 本文为算法竞赛入门经典第九章第三节的笔记(刘汝佳. 算法竞赛入门经典.第2版[M]. 清华大学出版社, 2014.) 多阶段决策问题:每作一次决策就可以得到解的一部分,当所有决策做完之后,所有...
  • 云环境中DAG调度算法的设计与实现.doc
  • 而具体使用哪种算法选择出块节点(PoW与PoS之争)、哪些节点在接收到数据块时该如何验证(PoS与DPoS之争)、节点之间的数据以什么方式进行传播(DAG与链式结构之争)、以及如何确保一条交易被大多数参与节点所接受...
  • DA G调度中常用调度算法关键路径 SCP ( Static Critical Path) 算法进行了详细的分析 ,提出了相应的扩展的随机 DA G的调度方法 SSCP (Stochastic Static Critical Path) 算法 。 同时 ,给出了扩展的随机 DA G 中节点...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 21,847
精华内容 8,738
关键字:

dag算法

友情链接: ghostimaging.zip