c++ - グラフを並べ替える効率的な方法は何ですか？

Question

たとえば、3つのノードA、B、C、AがBとCにリンクし、BがAとCにリンクし、CがBとAにリンクしているとします。視覚的な形式では次のようになります。

C <- A -> B //A links to B & C
A <- B -> C //B links to A & C
B <- C -> A //C links to B & A

A、B、Cが[A、B、C]のような配列に保持され、インデックスが0から始まると仮定します。各ノードが保持する値に従って配列[A、B、C]を効率的に並べ替えるにはどうすればよいですか。

たとえば、Aが4を保持し、Bが-2を保持し、Cが-1を保持する場合、sortGraph（[A、B、C]）は[B、C、A]を返す必要があります。その明確なことを願っています。どういうわけかstd::sortを利用できれば可能でしょうか？

編集：基本的なソートアルゴリズムではありません。もう少し明確にしましょう。ノードのリスト[n0、n1...nm]があると仮定します。各niには、左右の隣接インデックスがあります。たとえば、n1の左隣はn0で、右隣はn2です。私は隣人を表すためにインデックスを使用します。n1がインデックス1にある場合、その左側のネイバーはインデックス0にあり、右側のネイバーはインデックス2にあります。配列を並べ替える場合は、ネイバーインデックスも更新する必要があります。自分の並べ替えアルゴリズムを実際に実装したくないのですが、進め方について何かアドバイスはありますか？

Answer 1

これがC++の実装です。希望は役に立ちます（ダイクストラ、クラスカルなどのいくつかのアルゴリズムが含まれており、ソートには深さ優先探索などが使用されます）。

Graph.h

#ifndef __GRAPH_H
#define __GRAPH_H

#include <vector>
#include <stack>
#include <set>

typedef struct __edge_t
{
    int v0, v1, w;

    __edge_t():v0(-1),v1(-1),w(-1){}
    __edge_t(int from, int to, int weight):v0(from),v1(to),w(weight){}
} edge_t;

class Graph
{
public:
    Graph(void); // construct a graph with no vertex (and thus no edge)
    Graph(int n); // construct a graph with n-vertex, but no edge
    Graph(const Graph &graph); // deep copy of a graph, avoid if not necessary
public:
    // @destructor
    virtual ~Graph(void);
public:
    inline int getVertexCount(void) const { return this->numV; }
    inline int getEdgeCount(void)   const { return this->numE; }
public:
    // add an edge
    // @param: from [in] - starting point of the edge
    // @param: to   [in] - finishing point of the edge
    // @param: weight[in] - edge weight, only allow positive values
    void addEdge(int from, int to, int weight=1);
    // get all edges
    // @param: edgeList[out] - an array with sufficient size to store the edges
    void getAllEdges(edge_t edgeList[]);
public:
    // topological sort
    // @param: vertexList[out] - vertex order
    void sort(int vertexList[]);
    // dijkstra's shortest path algorithm
    // @param: v[in] - starting vertex
    // @param: path[out] - an array of <distance, prev> pair for each vertex
    void dijkstra(int v, std::pair<int, int> path[]);
    // kruskal's minimum spanning tree algorithm
    // @param: graph[out] - the minimum spanning tree result
    void kruskal(Graph &graph);
    // floyd-warshall shortest distance algorithm
    // @param: path[out] - a matrix of <distance, next> pair in C-style
    void floydWarshall(std::pair<int, int> path[]);
private:
    // resursive depth first search
    void sort(int v, std::pair<int, int> timestamp[], std::stack<int> &order);
    // find which set the vertex is in, used in kruskal
    std::set<int>* findSet(int v, std::set<int> vertexSet[], int n);
    // union two sets, used in kruskal
    void setUnion(std::set<int>* s0, std::set<int>* s1);
    // initialize this graph
    void init(int n);
    // initialize this graph by copying another
    void init(const Graph &graph);
private:
    int numV, numE; // number of vertices and edges
    std::vector< std::pair<int, int> >* adjList; // adjacency list
};

#endif

Graph.cpp

#include "Graph.h"
#include <algorithm>
#include <map>

Graph::Graph()
:numV(0), numE(0), adjList(0)
{
}

Graph::Graph(int n)
:numV(0), numE(0), adjList(0)
{
    this->init(n);
}

Graph::Graph(const Graph &graph)
:numV(0), numE(0), adjList(0)
{
    this->init(graph);
}

Graph::~Graph()
{
    delete[] this->adjList;
}

void Graph::init(int n)
{
    if(this->adjList){
        delete[] this->adjList;
    }
    this->numV = n;
    this->numE = 0;
    this->adjList = new std::vector< std::pair<int, int> >[n];
}

void Graph::init(const Graph &graph)
{
    this->init(graph.numV);    
    for(int i = 0; i < numV; i++){
        this->adjList[i] = graph.adjList[i];
    }
}

void Graph::addEdge(int from, int to, int weight)
{
    if(weight > 0){
        this->adjList[from].push_back( std::make_pair(to, weight) );
        this->numE++;
    }
}

void Graph::getAllEdges(edge_t edgeList[])
{
    int k = 0;
    for(int i = 0; i < numV; i++){
        for(int j = 0; j < this->adjList[i].size(); j++){
            // add this edge to edgeList
            edgeList[k++] = edge_t(i, this->adjList[i][j].first, this->adjList[i][j].second);
        }
    }
}

void Graph::sort(int vertexList[])
{
    std::pair<int, int>* timestamp = new std::pair<int, int>[this->numV];
    std::stack<int> order;

    for(int i = 0; i < this->numV; i++){
        timestamp[i].first = -1;
        timestamp[i].second = -1;
    }

    for(int v = 0; v < this->numV; v++){
        if(timestamp[v].first < 0){
            this->sort(v, timestamp, order);
        }
    }

    int i = 0;
    while(!order.empty()){
        vertexList[i++] = order.top();
        order.pop();
    }
    delete[] timestamp;
    return;
}

void Graph::sort(int v, std::pair<int, int> timestamp[], std::stack<int> &order)
{
    // discover vertex v
    timestamp[v].first = 1;

    for(int i = 0; i < this->adjList[v].size(); i++){
        int next = this->adjList[v][i].first;
        if(timestamp[next].first < 0){
            this->sort(next, timestamp, order);
        }
    }
    // finish vertex v
    timestamp[v].second = 1;
    order.push(v);
    return;
}

void Graph::dijkstra(int v, std::pair<int, int> path[])
{
    int* q = new int[numV];
    int numQ = numV;

    for(int i = 0; i < this->numV; i++){
        path[i].first = -1; // infinity distance
        path[i].second = -1; // no path exists
        q[i] = i;
    }

    // instant reachable to itself
    path[v].first = 0;
    path[v].second = -1;

    while(numQ > 0){
        int u = -1; // such node not exists
        for(int i = 0; i < numV; i++){
            if(q[i] >= 0 
            && path[i].first >= 0 
            && (u < 0 || path[i].first < path[u].first)){ // 
                u = i;
            }
        }


        if(u == -1){
            // all remaining nodes are unreachible
            break;
        }
        // remove u from Q
        q[u] = -1;
        numQ--;

        for(int i = 0; i < this->adjList[u].size(); i++){
            std::pair<int, int>& edge = this->adjList[u][i];
            int alt = path[u].first + edge.second;

            if(path[edge.first].first < 0 || alt < path[ edge.first ].first){
                path[ edge.first ].first = alt;
                path[ edge.first ].second = u;
            }
        }
    }

    delete[] q;
    return;
}

// compare two edges by their weight
bool edgeCmp(edge_t e0, edge_t e1)
{
    return e0.w < e1.w;
}

std::set<int>* Graph::findSet(int v, std::set<int> vertexSet[], int n)
{
    for(int i = 0; i < n; i++){
        if(vertexSet[i].find(v) != vertexSet[i].end()){
            return vertexSet+i;
        }
    }
    return 0;
}

void Graph::setUnion(std::set<int>* s0, std::set<int>* s1)
{
    if(s1->size() > s0->size()){
        std::set<int>* temp = s0;
        s0 = s1;
        s1 = temp;
    }

    for(std::set<int>::iterator i = s1->begin(); i != s1->end(); i++){
        s0->insert(*i);
    }
    s1->clear();
    return;
}

void Graph::kruskal(Graph &graph)
{
    std::vector<edge_t> edgeList;
    edgeList.reserve(numE);
    for(int i = 0; i < numV; i++){
        for(int j = 0; j < this->adjList[i].size(); j++){
            // add this edge to edgeList
            edgeList.push_back( edge_t(i, this->adjList[i][j].first, this->adjList[i][j].second) );
        }
    }

    // sort the list in ascending order
    std::sort(edgeList.begin(), edgeList.end(), edgeCmp);

    graph.init(numV);   
    // create disjoint set of the spanning tree constructed so far
    std::set<int>* disjoint = new std::set<int>[this->numV];
    for(int i = 0; i < numV; i++){
        disjoint[i].insert(i);
    }

    for(int e = 0; e < edgeList.size(); e++){
        // consider edgeList[e]
        std::set<int>* s0 = this->findSet(edgeList[e].v0, disjoint, numV);
        std::set<int>* s1 = this->findSet(edgeList[e].v1, disjoint, numV);
        if(s0 == s1){
            // adding this edge will make a cycle
            continue;
        }

        // add this edge to MST
        graph.addEdge(edgeList[e].v0, edgeList[e].v1, edgeList[e].w);
        // union s0 & s1
        this->setUnion(s0, s1);
    }
    delete[] disjoint;
    return;
}

#define IDX(i,j)    ((i)*numV+(j))

void Graph::floydWarshall(std::pair<int, int> path[])
{
    // initialize
    for(int i = 0; i < numV; i++){
        for(int j = 0; j < numV; j++){
            path[IDX(i,j)].first = -1;
            path[IDX(i,j)].second = -1;
        }
    }
    for(int i = 0; i < numV; i++){
        for(int j = 0; j < this->adjList[i].size(); j++){
            path[IDX(i,this->adjList[i][j].first)].first
                = this->adjList[i][j].second;
            path[IDX(i,this->adjList[i][j].first)].second
                = this->adjList[i][j].first;
        }
    }

    // dynamic programming
    for(int k = 0; k < numV; k++){
        for(int i = 0; i < numV; i++){
            for(int j = 0; j < numV; j++){
                if(path[IDX(i,k)].first == -1
                || path[IDX(k,j)].first == -1){
                    // no path exist from i-to-k or from k-to-j
                    continue;
                }

                if(path[IDX(i,j)].first == -1
                || path[IDX(i,j)].first > path[IDX(i,k)].first + path[IDX(k,j)].first){
                    // there is a shorter path from i-to-k, and from k-to-j
                    path[IDX(i,j)].first = path[IDX(i,k)].first + path[IDX(k,j)].first;
                    path[IDX(i,j)].second = k;
                }
            }
        }
    }
    return;
}

Answer 2

編集された質問を正しく理解している場合、グラフは循環リンクリストです。各ノードは前のノードと次のノードを指し、「最後の」ノードは次のノードとしての「最初の」ノードを指します。

あなたが望む種類をするためにあなたが必要とする特別なことは何もありません。これが私が使用する基本的な手順です。

1. すべてのノードを配列に入れます。
2. 任意の並べ替えアルゴリズム（qsortなど）を使用して配列を並べ替えます。
3. 結果をループし、最初と最後のノードの特殊なケースを考慮して、各ノードの前/次のポインターをリセットします。

Answer 3

あなたがソートアルゴリズムを探しているなら、あなたはただグーグルに尋ねるべきです：

http://en.wikipedia.org/wiki/Sorting_algorithm

私の個人的なお気に入りは、パラレルユニバース理論と組み合わせたボゴソートです。理論は、宇宙を破壊する可能性のあるプログラムにマシンを接続すると、1回の反復後にリストがソートされない場合、宇宙を破壊するというものです。そうすれば、リストが並べ替えられたものを除くすべての並列ユニバースが破棄され、複雑さO（1）の並べ替えアルゴリズムが得られます。

最高の ....

Answer 4

次のような構造体を作成します。

template<typename Container, typename Comparison = std::less<typename Container::value_type>>
struct SortHelper
{
    Container const* container;
    size_t org_index;
    SortHelper( Container const* c, size_t index ):container(c), org_index(index) {}
    bool operator<( SortHelper other ) const
    {
      return Comparison()( (*c)[org_index], (*other.c)[other.org_index] );
    }
};

これにより、好きなように物事を再利用できます。

さて、を作成してstd::vector<SortHelper<blah>>並べ替えると、並べ替えたvector後にすべてがどこに行くのかを説明することができます。

これらの手順を適用します（いくつかの方法があります）。簡単な方法は、containerポインタをブール値として再利用することです。ソートされvectorたヘルパーを歩きます。最初のエントリを移動する場所に移動し、見つけたものを移動する場所に移動し、ループするか配列全体が並べ替えられるまで繰り返します。移動しながら、ヘルパー構造体のポインターをクリアし、containerそれらをチェックして、既に移動されたエントリーを移動しないことを確認します（これにより、たとえばループを検出できます）。

ループが発生したらvector、次のまだ正しい場所にないエントリを探します（null以外のcontainerポインタを使用）。