[Lemon-user] Sharing codes ListDiGraph & ListAttrDiGraph

[jemin]

Hi, this is Jemin Chen from Taiwan, http://www.ncu.edu.tw .

 

Many thanks for the help of LEMON to my research, I’d like to share my
codes which are two graph structures: ListDiGraph and ListAttrDiGraph.

1.      ListDiGraph is just a clone of <lemon/list_graph.h> but it is
rewritten in template style for more object orientation.

2.      ListAttrDiGraph, based on ListDiGraph, I add supporting of
attributed-nodes and attributed-arcs into it. ( add and erase the
attr-nodes, attr-arcs).

Thus ListGraph is a subclass of ListAttrDiGraph with 1 kind of nodes and 2
kinds of arcs, and also the BP-ListGraph is a ListAttrDiGraph with 2 kinds
of nodes and 2 kinds of arcs.

 

Sincerely.

 

P.S.

They currently works with main() the consistant test program (which is
included in *.tgz also) as below.

int main()

{

// initialize the graph to test

    int n= 3;

    ListDiGraph N_cube;

    init_N_cube( N_cube, n);

    typedef ListDiGraph::Node Node;

    typedef ListDiGraph::Arc Arc;

    cout << N_cube.maxNodeId()+ 1 << " nodes" << endl;

    cout << N_cube.maxArcId()+ 1 << " arcs" << endl;

 

// test OutDegMap, NodeIt, and check the result of
ListDiGraph::sort_nodes();

           OutDegMap< ListDiGraph> out_degree( N_cube);

           for( ListDiGraph::NodeIt v( N_cube); v!= INVALID; ++v)

                     cout << N_cube.id( v) << "      " << out_degree[ v]<<
endl;

// test BFS

           Bfs< ListDiGraph> bfs( N_cube);

           bfs.init();

           Node src= N_cube.nodeFromId(( 1<< n)-1);

    Node dst= N_cube.nodeFromId( 0);

           bfs.addSource( src);

           Node u= src;

           while( u!= dst) {

                     u= bfs.processNextNode();

                     cout<< N_cube.id( u)<< endl;

           }

 

// test ArcMap and Preflow

    ListDiGraph::ArcMap< int> cap( N_cube);

    int capacity[ 12]= { 10, 9, 8, 7, 6, 5, 5, 6, 7, 8, 9, 10};

    for( register int i= N_cube.maxArcId(); i>= 0; --i)

        cap[ N_cube.arcFromId( i)]= capacity[ i];

    Preflow< ListDiGraph> preflow( N_cube, cap, src, dst);

    preflow.init();

    preflow.run();

    cout << "maximum flow by preflow: " << preflow.flowValue() << endl;

 

// Write details

    digraphWriter( N_cube).              // write to the standard output

    arcMap( "cap", cap).           // write 'capacity' for arcs

    arcMap( "flow", preflow.flowMap()).  // write 'flow' for arcs

    node( "source", src).                    // write s to 'source'

    node( "target", dst).                     // write t to 'target'

    run();

 

    return 0;

}

 

 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20160701/fe242ff9/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: ListDiGraph_20160701.tgz
Type: application/x-compressed
Size: 6358 bytes
Desc: not available
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20160701/fe242ff9/attachment-0002.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: ListAttrDiGraph_20160701.tgz
Type: application/x-compressed
Size: 11627 bytes
Desc: not available
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20160701/fe242ff9/attachment-0003.bin>