Skip to content

MGTag是一个解决图可达性NP问题(主要是图内可达性问题)的程序,采用层次划分、图内Interval和上下索引等思想解决NP难题

Notifications You must be signed in to change notification settings

oeljeklaus-you/MGTag

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

4 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

MGTag

Compile

g++ main.cpp -O3 -std=c++11 -o mgtag

Run

./mgtag {graph} {query}

Graph File Format The first line must be "graph_for_greach".

The second line contains V, the number of vertices of the graph.

Then V lines follow. Each line describes edges from a certain vertex, u, to its successors, v_i, in the following format. u: v_1 v_2 ... v_deg+(u)#

Query File Format Each line contains a query, Reach(u, v), in the following format. u v result If result is 0, then Reach(u, v) should be false; if result is 1, then Reach(u, v) should be true; otherwise result should be -1, which means the result it unknown.

Please note vertices are numbered from 0 to V - 1, and the graph must be a DAG.

About

MGTag是一个解决图可达性NP问题(主要是图内可达性问题)的程序,采用层次划分、图内Interval和上下索引等思想解决NP难题

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages