townforge/graph
1
0
Fork 0
Code Issues Pull Requests Releases Wiki Activity
3,406 Commits 1 Branch 0 Tags 27 MiB
cc
Commit Graph

586 Commits

Author SHA1 Message Date
Rasmus Ahlberg
e8d7c9fe9b Added test case for removing edges bug from previous commit. 2018-08-23 16:22:06 +02:00
Daniel James
4c752ee2f1 Use std::mt19937 where available 
In C++17 mode, libc++'s `std::shuffle` isn't compatible with Boost's random
generators because the `min` and `max` functions aren't `constexpr`, so use
`std::mt19937` instead. This might not be required if boostorg/random#24 is
accepted.
 2018-04-13 15:43:38 +01:00
Daniel James
a651ecf6ab
Merge pull request #85 from Flast/patch-1 
Qualify calling of as_const.
 2018-04-13 13:21:59 +01:00
Mateusz Polnik
faef224193 Reproduce memory issue with resource constrained shortest paths. Valgrind confirms reads/writes outside allocated memory. 2017-07-04 23:26:54 +01:00
Daniela Engert
9886e3fef2 Conditionally replace deprecated/removed C++98 std::bind1st by std::bind, std::auto_ptr by std::unique_ptr, and std::random_shuffle by std::shuffle. (#89) 
Signed-off-by: Daniela Engert <dani@ngrt.de>
 2017-05-26 15:04:34 -06:00
Kohei Takahashi
a45e3de9b7 Qualify calling of as_const. 
It is ambiguous with upcoming standardized `std::as_const`.
 2017-02-04 13:27:07 +09:00
Stefan Hammer
f07d91397c [subgraph.hpp] add_vertex(u_global, g) on a subgraph does not recursively add to parent subgraphs 2016-11-02 11:02:39 +01:00
Jakob Lykke Andersen
cf6e8efdf4 VF2, fix assumption that index maps are default constructible. (#27) 2016-10-31 20:10:23 -06:00
Matt Barr
387bcb3d72 Add degree to reverse_graph (#78) 
degree is required for BidirectionalGraphConcept.
Also adds the concept check to the reverse_graph unit test.
 2016-10-31 14:03:54 -06:00
K. Noel Belcourt
54589358a4 Disable csr_graph_test until can work through lack of c++11 support. 2016-07-24 13:41:26 -06:00
Murray Cumming
a9c0fa9495 Make files not executable. (#69) 
See https://github.com/boostorg/admin/issues/47
 2016-07-16 17:05:54 -06:00
Maël Valais
15872fe070 Fix #11374 and #12038: issues with find_flow_cost(), bundled properties and named parameters (#61) 
* trac 11374: find_flow_cost() not working with bundled properties.

When using bundled for Weight and Cost properties, find_flow_cost() coudln't work because the properties had been "hard coded" instead of using generic types.

Fixes https://svn.boost.org/trac/boost/ticket/11374

* trac 12038: max-flow algorithms not working with named parameters.

The named parameter "Capacity" was not working. I just had to reverse the order of get_param_type parameters.

Here are the max-flow algorithms that are curretly not working with the named parameter "Capacity":
- edmonds_karp_max_flow,
- push_relabel_max_flow,
- boykov_kolmogorov_max_flow.

Fixes https://svn.boost.org/trac/boost/ticket/12038

* trac 11374: find_flow_cost() not working with named parameters and bundled properties at the same time.

When using bundled properties as well as named parameters, there was an error.

What happened is that the "named parameters" version of find_flow_cost() was not using a generic return value, hence the error.

Also, the return value_type was using edge_capacity_value instead of edge_weight_value (which is the type of a flow cost).

I fixed it using the trick used for edmonds_karp_max_flow(): add `edge_weight_value` to named_function_params.hpp.

* Unit test find_flow_cost() with bundled properties & named params.

-> unit tests for trac 11374

I used the existing min_cost_max_flow_utils.hpp, but I had to make the graph of getSampleGraph() more generic.

In the first place, I wanted to make a compile-only test but I also made
the test runnable so we check that
- find_flow_cost works() correctly with bundled properties
- successive_shortest_path_nonnegative_weights() also works with bundled properties

To run this test, this is a bit painful...
I had to run the entire graph-related tests.
- I commented the other tests except for graph in ./status/Jamfile.v2
- in this same dir, I ran `../b2`

One issue though: csr_graph_test seems to be broken on my boost copy, I may have an issue with updating the submodules or something...

* Unit test edmond_karp_max_flow with named params & bundled properties.

-> unit tests for trac 12038

As the previous commit, I rely on min_cost_max_flow_utils.hpp.

And I also made a runnable test instead of a simple "compile-time" test.

* Indented with 2 spaces instead of tabs

Thanks for the patch!
 2016-05-02 11:11:23 -06:00
K. Noel Belcourt
ded3042cd2 Eliminate unused variable, regularize formatting. 2016-05-01 16:17:47 -06:00
K. Noel Belcourt
08453c109a Revert "removed an unused function (#39)" 
This reverts commit 655ce30eb3.
 2016-04-26 10:54:43 -06:00
Mads Jensen
655ce30eb3 removed an unused function (#39) 
The C++ standard deprecates use of <stdio.h>, <stdlib.h> etc., and suggests using <cstdio>, <cstdlib> etc.

Some trailing whitespace removed in affected files because of a setting in my editor

dead code surrounded by #if 0 ... #endif removed
 2016-04-24 10:26:25 -06:00
K. Noel Belcourt
6fc1f4a924 Quiet an unused variable warning. 2016-04-23 22:17:49 -06:00
Jakob Lykke Andersen
50bfd8dad0 Add missing check for 'degree' in BidirectionalGraphConcept. Fix the concept checking class in the documentation for BidirectionalGraphConcept. Implementation of missing 'degree' function for filtered_graph. (#29) 
Thanks for the patch.
 2016-04-23 12:27:51 -06:00
K. Noel Belcourt
9d35801154 Add new strong components test to Jamfile from Alex Lauser. 
Remove long unused file.
 2014-11-11 21:02:19 -07:00
Noel Belcourt
efa9fbd904 Merge pull request #15 from gatlex/bugfix/ticket-10222-root-map-broken 
Fixed bug 10222.

I'll go ahead and add the test to the Jamfile, thanks for the test.
 2014-11-11 20:57:50 -07:00
K. Noel Belcourt
713ee03efc Add finish_edge test case from Alex Lauser. 
This test demonstrates incorrect output in
the order edges are finished.  We're using
this test to both ensure finish_edge is
called, and that the output is incorrect.
Once we fix where the visitor is called,
this test will be changed to check for the
correct output.
 2014-11-11 12:37:56 -07:00
Alexander Lauser
9cd237093c Cleaned up the strong-components test. 2014-11-11 11:09:39 +01:00
Alexander Lauser
221ac5d6f0 Added test for Boost.Graph's strong_components. 
Associated with Bug #10231 which causes the test to fail.
 2014-11-11 10:49:47 +01:00
Josef Cibulka
bc60e27f75 Comparison of doubles in graphml_test.cpp in now done with some tolerance to rounding errors. 2014-09-29 11:08:23 +02:00
Josef Cibulka
3afa03dcd0 Changed asserts to BOOST_CHECK in graphml_test.cpp 2014-09-29 10:27:19 +02:00
Josef Cibulka
3a663cddc3 Merge remote-tracking branch 'myremote/master' into HEAD 2014-09-27 21:11:10 +02:00
Josef Cibulka
02fbda4272 Added reading of graph properties from graphml. 2014-09-26 16:28:22 +02:00
Eric Niebler
290e9fc3d1 Merge branch 'master' into develop 2014-08-03 13:06:46 -07:00
Noel Belcourt
7d7eca4a38 Cleanup unused typedefs (gcc-4.8.2 c++0x). 2014-07-31 12:46:39 -06:00
Noel Belcourt
235064c63c Merge branch 'develop' 2014-05-16 15:15:30 -06:00
BenPope
e2da814588 Add tests for member swap and fix undirected_graph<>::swap 2014-05-14 23:46:25 +08:00
BenPope
9b7fbc1a76 Add tests for member swap and fix undirected_graph<>::swap 2014-05-14 23:43:53 +08:00
K. Noel Belcourt
f1fe4a9132 Fix a use of typename outside of template. Looks like a merge 
from develop omitted this as it's fixed in develop, not in
master.

This should clear master graph tests on Darwin and Linux.
 2014-01-29 13:01:02 -07:00
Jeremiah Willcock
332b49261c Fixed invalid uses of "typename" 
[SVN r86577]
 2013-11-06 21:16:55 +00:00
Jeremiah Willcock
74564d5a1c Made some of changes from #9246: added new test case (modifying tests on callback usage to match current documentation); removed special-casing of empty graphs; added patch from #9246 for correct return values; did not make change to documentation suggested there since I chose to have the callback called even for empty graphs; fixes #9246 
[SVN r86336]
 2013-10-17 02:51:14 +00:00
Jeremiah Willcock
5922324c2b Merged Boost.Graph, Boost.Graph.Parallel, and Boost.PropertyMap changes from Boost trunk 
[SVN r85813]
 2013-09-21 20:17:00 +00:00
Jeremiah Willcock
f97c2ee746 Attached patch from Piotr Wygocki for min-cost max-flow 
[SVN r85661]
 2013-09-13 14:48:17 +00:00
Jeremiah Willcock
c40148ee94 Removed uses of pointers as property maps from tests and examples 
[SVN r85655]
 2013-09-12 15:14:36 +00:00
Jeremiah Willcock
fdd8e41b47 Fixing tests (hopefully) for VC++ 
[SVN r85654]
 2013-09-12 14:01:50 +00:00
Jeremiah Willcock
e1bcb667b6 Fixed ambiguous call 
[SVN r85583]
 2013-09-06 03:54:57 +00:00
Jeremiah Willcock
405e21d011 Applied patch from potato_research to add copyright notice 
[SVN r85580]
 2013-09-05 19:48:31 +00:00
Jeremiah Willcock
a3efa1c030 Added new test from potato_research of custom vertex index map in r_c_shortest_paths 
[SVN r85571]
 2013-09-05 12:57:15 +00:00
Jeremiah Willcock
bd107e4ab5 Applied patch and file renames from Piotr Wygocki 
[SVN r85568]
 2013-09-04 21:39:21 +00:00
Jeremiah Willcock
915b70ec05 Added min_cost_max_flow code from Piotr Wygocki 
[SVN r85536]
 2013-08-31 20:09:11 +00:00
Jeremiah Willcock
01a683d8ce Added Hawick circuits code from Louis Dionne; fixes #8433 
[SVN r85533]
 2013-08-31 19:29:22 +00:00
Jeremiah Willcock
be2fc043d1 Fixed unused typedef warnings from GCC 4.9; fixes #8877; fixes #8986 
[SVN r85323]
 2013-08-12 18:14:58 +00:00
Jeremiah Willcock
67f7bcfa96 Merged Boost.Graph, Boost.Graph.Parallel, and Boost.PropertyMap changes from trunk 
[SVN r84299]
 2013-05-16 15:38:05 +00:00
Jeremiah Willcock
67aacbe6ef Added support for distance types without numeric_limits specializations; changed test to use that functionality to ensure that it keeps working; fixes #8490 
[SVN r84028]
 2013-04-24 02:19:13 +00:00
Jeremiah Willcock
7e9b77f5fb Fixed VC++ error 
[SVN r83893]
 2013-04-14 03:49:56 +00:00
Jeremiah Willcock
3e770e171e Added patches from Flavio De Lorenzi; fixed HTML typo in VF2 documentation 
[SVN r83832]
 2013-04-10 17:03:21 +00:00
Jeremiah Willcock
393c072c18 Added maximum adjacency search from Fernando Vilas; fixes #6780 
[SVN r83410]
 2013-03-12 00:35:48 +00:00
Jeremiah Willcock
22b521ecf4 Merged Boost.Graph changes from trunk for 1.53 
[SVN r82061]
 2012-12-17 23:59:46 +00:00
Jeremiah Willcock
f53d02e0eb Added updates from Flavio De Lorenzi to vf2_sub_graph_iso code 
[SVN r82007]
 2012-12-16 01:51:51 +00:00
Jürgen Hunold
3419d42acc Merge 80908,80939,80957 from ^/trunk 
------------------------------------------------------------------------
  r80908 | jewillco | 2012-10-08 22:04:48 +0200 (Mo, 08 Okt 2012) | 1 line
  
  Added attempt at workaround for VC++ const graph type bug
  ------------------------------------------------------------------------
  r80939 | jewillco | 2012-10-10 19:27:44 +0200 (Mi, 10 Okt 2012) | 1 line
  
  Added another remove_const to work around VC++ 9 issues
  ------------------------------------------------------------------------
  r80957 | jewillco | 2012-10-11 18:45:33 +0200 (Do, 11 Okt 2012) | 1 line
  
  Added test from Juergen Hunold
  ------------------------------------------------------------------------


[SVN r81042]
 2012-10-21 18:06:15 +00:00
Jeremiah Willcock
b4e1fe7a66 Added test from Juergen Hunold 
[SVN r80957]
 2012-10-11 16:45:33 +00:00
Jeremiah Willcock
607d866854 Merged Boost.Graph changes from trunk 
[SVN r80740]
 2012-09-28 18:34:12 +00:00
Jeremiah Willcock
3009b2303c Checking multiple dimensionalities of graphs 
[SVN r80641]
 2012-09-22 20:09:08 +00:00
Jeremiah Willcock
ba9155f89c Merged bug fix from trunk 
[SVN r79393]
 2012-07-09 20:15:04 +00:00
Jeremiah Willcock
df80876475 Fixed uninitialized variable problem 
[SVN r79391]
 2012-07-09 20:10:02 +00:00
Jeremiah Willcock
616b9e7134 Merged first batch of 1.51 changes for Boost.Graph and Boost.PropertyMap 
[SVN r79189]
 2012-06-30 20:00:41 +00:00
Jeremiah Willcock
cbe70511cd Merged in more trunk bug fixes for Boost.Graph and Boost.PropertyMap 
[SVN r78641]
 2012-05-26 18:56:37 +00:00
Jeremiah Willcock
0b30767da0 Merged bug fixes for Boost.Graph and Boost.PropertyMap from trunk 
[SVN r78639]
 2012-05-26 18:23:01 +00:00
Jeremiah Willcock
b37570381b Fixed inspect warnings and typos 
[SVN r78442]
 2012-05-12 20:46:47 +00:00
Jeremiah Willcock
1eb950d630 Removed use of Boost.Typeof to enhance portability; using Boost.ResultOf instead 
[SVN r78330]
 2012-05-05 03:08:49 +00:00
Jeremiah Willcock
6ea899f7ed Added code and docs from #5269 (some code heavily rewritten) and removed old workarounds; fixes #5269 
[SVN r78030]
 2012-04-16 23:12:50 +00:00
Jeremiah Willcock
ebdec45c4b Added test for Boost.Parameter version of isomorphism; fixed bugs that found 
[SVN r78024]
 2012-04-16 18:44:36 +00:00
Jeremiah Willcock
706859b595 Removed uses of Boost.Typeof to hopefully help on XLC 
[SVN r77916]
 2012-04-11 16:26:51 +00:00
Jeremiah Willcock
3d43c1a8ec Added algorithm from Michele Caini for common spanning trees of two graphs; fixes #6401 
[SVN r77893]
 2012-04-10 19:51:59 +00:00
Jeremiah Willcock
7a2ec7c4dc Removed unused type and variable 
[SVN r77532]
 2012-03-25 05:00:52 +00:00
Jeremiah Willcock
035fac705c Fixed warnings 
[SVN r77531]
 2012-03-25 05:00:36 +00:00
Jeremiah Willcock
6f4b8bf204 Removed unused variable 
[SVN r77530]
 2012-03-25 05:00:21 +00:00
Jeremiah Willcock
57121513a7 Fixed property map access 
[SVN r77529]
 2012-03-25 05:00:05 +00:00
Jeremiah Willcock
7e59864546 Fixed warnings 
[SVN r77528]
 2012-03-25 04:59:23 +00:00
Jeremiah Willcock
bbab01b9c3 Removed incorrect tests 
[SVN r77527]
 2012-03-25 04:58:58 +00:00
Jeremiah Willcock
e315856b1b Fixed warnings 
[SVN r77525]
 2012-03-25 01:38:29 +00:00
Jeremiah Willcock
b838adfa32 Fixed warnings 
[SVN r77523]
 2012-03-24 23:35:23 +00:00
Jeremiah Willcock
5476d8d70a Made Graphviz reading into CSR graphs work for external properties only; refs #5442 
[SVN r77222]
 2012-03-04 20:21:22 +00:00
Jeremiah Willcock
c49c05f502 Tried to do read_graphviz for CSR; does not work but some infrastructure changed so it is being committed 
[SVN r77189]
 2012-03-03 21:19:38 +00:00
Jeremiah Willcock
210e7857b2 Removed redundant function_requires in test case 
[SVN r76537]
 2012-01-15 23:59:39 +00:00
Jeremiah Willcock
a4dc3d7b23 Merged r75066, r75067, r75124, r75140, r75165, r75861, r75862, r75863, r75878, r75906, r75970, r75973, r75974, and r76394 from trunk 
[SVN r76536]
 2012-01-15 23:52:45 +00:00
Jeremiah Willcock
4b95dcfbe9 Merged r76050, r75547, r75891, r76049, r76083, and r76439 from trunk (reverse_graph bug fixes and fix for #6293); refs #6293 
[SVN r76535]
 2012-01-15 23:32:09 +00:00
Jeremiah Willcock
cd1fee5f7d Applied fixed version of patch from #6293; fixes #6293 
[SVN r76050]
 2011-12-18 21:09:34 +00:00
Jeremiah Willcock
231bb5dbfb Added documented way to get underlying edge descriptor from a reverse_graph; changed name of member to prevent future use 
[SVN r76049]
 2011-12-18 20:53:26 +00:00
Steven Watanabe
456f4006cb Remove unused library. 
[SVN r75974]
 2011-12-15 22:59:03 +00:00
Steven Watanabe
8f3dd3a4f9 Fix search for SDB and LEDA. 
[SVN r75970]
 2011-12-15 22:07:53 +00:00
Jeremiah Willcock
a88250f76f Merged change r75431 from trunk; refs #6112 
[SVN r75471]
 2011-11-13 06:10:55 +00:00
Jeremiah Willcock
2b2f2d464e Qualified more calls to tie; fixes #6112 
[SVN r75431]
 2011-11-10 15:04:27 +00:00
Jeremiah Willcock
ffff89b1a2 Refactored and added test graph from Andre Dau 
[SVN r75066]
 2011-10-19 20:03:00 +00:00
Jeremiah Willcock
9f29ef1a83 Merged in BGL, enable_if, and related changes from trunk: r67035, r57559, r72837, r73010, r73026, r72960, r73425, r73424, r73009, r73998, r73997, r73006, r73630, r73631, r73999, r73422, r73423, r73996, r71221 
[SVN r74023]
 2011-08-23 18:26:46 +00:00
Jeremiah Willcock
b156db0c9e Fixed traits class name 
[SVN r73999]
 2011-08-22 01:44:08 +00:00
Jeremiah Willcock
081b1f90bf Merged r71166, r71238, r71300, r71489, r71704, and r71929 from trunk 
[SVN r72334]
 2011-06-01 16:58:36 +00:00
Jeremiah Willcock
1fa0cd9a26 Fixed C++0x array ambiguity 
[SVN r71166]
 2011-04-10 20:01:06 +00:00
Jeremiah Willcock
03510b4a6e Merged more fixes from trunk; added is_sorted.hpp because that is needed for BGL fixes 
[SVN r70704]
 2011-03-29 19:07:16 +00:00
Jeremiah Willcock
30e9f22af4 Merged r67703-67704,68155,69263,69629,69726 from trunk 
[SVN r70703]
 2011-03-29 18:56:56 +00:00
Jeremiah Willcock
f52b7df417 Added includes of <utility> for Clang/libc++ 
[SVN r69629]
 2011-03-07 19:28:34 +00:00
Steven Watanabe
a4452c3539 Revert [67111] (addition of boost/detail/iomanip.hpp) and all the commits that depend on it. ([68137], [68140], [68141], [68154], and [68165]). 
[SVN r68168]
 2011-01-15 08:11:51 +00:00
Bryce Adelstein-Lelbach
074277924a Replacing the use of <iomanip> with <boost/detail/iomanip.hpp> across Boost. 
On Linux, GNU's libstdc++, which is the default stdlib for icc and clang,
cannot parse the <iomanip> header in version 4.5+ (which thankfully neither
compiler advises the use of yet), as it's original C++98-friendly
implementation has been replaced with a gnu++0x implementation.
<boost/detail/iomanip.hpp> is a portable implementation of <iomanip>, providing
boost::detail::setfill, boost::detail::setbase, boost::detail::setw,
boost::detail::setprecision, boost::detail::setiosflags and
boost::detail::resetiosflags. 



[SVN r68140]
 2011-01-14 02:35:58 +00:00
Jeremiah Willcock
6e73c470a4 Removed BOOST_FILESYSTEM_VERSION setting from test cases and removed Filesystem v2 workaround 
[SVN r68001]
 2011-01-11 22:19:57 +00:00
Jeremiah Willcock
1963179514 Removed Boost.Test #defines from test case 
[SVN r67971]
 2011-01-11 19:00:35 +00:00
Jeremiah Willcock
bd69c0c5cf Merged r66528,66559,66960,67010,67012,67033,67035,67038,67040,67069,67086,67723,67914 from trunk 
[SVN r67970]
 2011-01-11 18:52:51 +00:00
Jeremiah Willcock
f132fd060f Using incantation from Boost.Math (test_laplace.cpp) to try to get Boost.Test linking to work 
[SVN r67086]
 2010-12-07 17:35:24 +00:00