lgraph.h

Go to the documentation of this file.

#ifndef LGRAPH_H
#define LGRAPH_H

// linked list graph, use string as identifier,
// slower, but more direct

#include <list>
#include <map>
#include <iostream>
#include <vector>
#include <string>

using namespace std;

struct vertexinfo {
        vertexinfo() : id(), color('w'), parent(-1), discover(-1), finish(-1), numchildren(0) {}

        vertexinfo(const string &label) : id(label), color('w'), parent(-1), discover(-1), finish(-1), numchildren(0) {}
        string id;  // identifier for this vertex
        char color; // w for white, g for gray, b for black
        int discover;
        int finish;
        int parent;
        int low;     // discover time
        int numchildren;
};

/*
struct edge {
        edge() : src(-1), dst(-1), type('x') {}
        edge(int s, int d, char t) : src(s), dst(d), type(t) {}
        int src;
        int dst;
        char type; // t for tree edge, b for back edges
};
*/

class lgraph {
        public:
                lgraph() : adjl(), vertices(), time(0) {}
                // construct the graph from a file
                lgraph(istream &ins);
                // read from table
                //void fromDB(const string &tab);
                void fromSQL(const string &query);
                void dfs();
                void dfsvisit(const int u);
                void show(); // debug to display content of graph
                vector<string> articulation();
        private:
                int time;   // sequence of vertex discovery and finish
                vector<vertexinfo> vertices;
                vector<list<int> > adjl;  // adjency list
};
#endif