COIN-OR::LEMON - Graph Library

Opened 12 years ago

Closed 6 years ago

#69 closed task (fixed)

Revise and port bipartite graphs

Reported by: Alpar Juttner Owned by: Balazs Dezso
Priority: critical Milestone: LEMON 1.3 release
Component: core Version:
Keywords: Cc:
Revision id:

Description

This needs quite a lot of work.

Attachments (9)

bpgraphs.patch (184.3 KB) - added by Balazs Dezso 9 years ago.
Bipartite graphs
008af84a4d4a.patch (64.1 KB) - added by Balazs Dezso 9 years ago.
LGF reader and writer for bipartite graphs
434a20e74585.patch (58.0 KB) - added by Balazs Dezso 8 years ago.
Type safe RedNode? and BlueNode?
d248eca9ca25.patch (41.5 KB) - added by Balazs Dezso 8 years ago.
Renamings
37d179a45077.patch (4.9 KB) - added by Balazs Dezso 8 years ago.
Remove asRedBlueNode()
60aca94c7cb5.patch (4.1 KB) - added by Balazs Dezso 8 years ago.
Doc fixes
a4a945914af3.patch (841 bytes) - added by Poroszkai Daniel 8 years ago.
Update lgf reader
b79821620180.patch (56.7 KB) - added by Balazs Dezso 7 years ago.
bp-revamped.bundle (43.9 KB) - added by Alpar Juttner 7 years ago.
A revamped version of all relevant previous patches.

Download all attachments as: .zip

Change History (41)

comment:1 Changed 12 years ago by Alpar Juttner

Milestone: LEMON 1.0 releasePost 1.0

comment:2 Changed 11 years ago by Alpar Juttner

Owner: changed from Alpar Juttner to Balazs Dezso

comment:3 Changed 11 years ago by Alpar Juttner

Milestone: LEMON 1.1 release

comment:4 Changed 11 years ago by Balazs Dezso

Owner: changed from Balazs Dezso to Peter Kovacs

comment:5 Changed 11 years ago by Peter Kovacs

Status: newassigned

comment:6 Changed 11 years ago by Alpar Juttner

Milestone: LEMON 1.2 release
Priority: majorcritical

comment:7 Changed 10 years ago by Alpar Juttner

Milestone: LEMON 1.2 releaseLEMON 1.3 release

Changed 9 years ago by Balazs Dezso

Attachment: bpgraphs.patch added

Bipartite graphs

comment:8 Changed 9 years ago by Balazs Dezso

I have uploaded the bpgraphs.patch file (with five changesets). It contain the concept BpGraph?, graph implementations ListBpGraph?, SmartBpGraph? and FullBpGraph? and some graph utilities like BpGraphCopy?.

The new implementations are mostly based on the undirected graphs, but they are extended with the handling of the two nodesets (blue and red). I think, these new graphs have to be more efficient than the old ones.

The implementations are not tested yet exhaustively, but I also added some basic unit tests. I detailed code review would be appreciated.

comment:9 in reply to:  8 Changed 9 years ago by Alpar Juttner

Replying to deba:

I have uploaded the bpgraphs.patch file (with five changesets). It contain the concept BpGraph?, graph implementations ListBpGraph?, SmartBpGraph? and FullBpGraph? and some graph utilities like BpGraphCopy?.

Hallelujah!

A had a short look at it. Looks very good but I think some namings should be discussed again.

comment:10 Changed 9 years ago by Alpar Juttner

What does blueID(Node) do?

comment:11 in reply to:  10 Changed 9 years ago by Balazs Dezso

Replying to alpar:

What does blueID(Node) do?

int BpGraph::blueId(Node);

precondition: the node is from the blue set

It gives back an id for the node, which is unique in the blue node set. The blue ids differ from the normal node ids, because we try to assign them continuously in the blue set. Therefore, when we use blueId(node) in the BlueMap? as vector index, then it will be storage efficient.

Changed 9 years ago by Balazs Dezso

Attachment: 008af84a4d4a.patch added

LGF reader and writer for bipartite graphs

comment:12 Changed 9 years ago by Balazs Dezso

The patch [008af84a4d4a] contains the LGF reader and writer for bipartite graphs.

comment:13 Changed 9 years ago by Mohammed El-Kebir

I have some trouble accessing the functions:

Node FullBpGraph::redNode(FullBpGraph::Edge)

Node FullBpGraph::blueNode(FullBpGraph::Edge)

When I compile this with gcc version "g++ (Ubuntu 4.4.3-4ubuntu5) 4.4.3"

#include <lemon/full_graph.h>

using namespace lemon;

int main()
{
  FullBpGraph graph(100, 100);

  for (FullBpGraph::EdgeIt e(graph); e != INVALID; ++e)
  {
    //FullBpGraph::Node x = graph.redNode(e);
    //FullBpGraph::Node y = graph.blueNode(e);

    FullBpGraph::Node x = static_cast<FullBpGraphBase>(graph).redNode(e);
    FullBpGraph::Node y = static_cast<FullBpGraphBase>(graph).blueNode(e);
  }

  return 0;
}

I get the following compilation errors

{{{test.cc: In function ‘int main()’: test.cc:11: error: no matching function for call to ‘lemon::FullBpGraph::redNode(lemon::BpGraphExtender?<lemon::FullBpGraphBase>::EdgeIt?&)’ ./lemon/full_graph.h:1000: note: candidates are: lemon::FullBpGraphBase::Node lemon::FullBpGraph::redNode(int) const test.cc:12: error: no matching function for call to ‘lemon::FullBpGraph::blueNode(lemon::BpGraphExtender?<lemon::FullBpGraphBase>::EdgeIt?&)’ ./lemon/full_graph.h:1017: note: candidates are: lemon::FullBpGraphBase::Node lemon::FullBpGraph::blueNode(int) const }}}

I get similar compile errors with the MSVC 2008 compiler. When I use the base class (see below) however it compiles fine

#include <lemon/full_graph.h>

using namespace lemon;

int main()
{
  FullBpGraph graph(100, 100);

  for (FullBpGraph::EdgeIt e(graph); e != INVALID; ++e)
  {
    FullBpGraph::Node x = static_cast<FullBpGraphBase>(graph).redNode(e);
    FullBpGraph::Node y = static_cast<FullBpGraphBase>(graph).blueNode(e);
  }

  return 0;
}

comment:14 in reply to:  13 Changed 9 years ago by Balazs Dezso

Replying to elkebir:

I have some trouble accessing the functions:

Node FullBpGraph::redNode(FullBpGraph::Edge)

Node FullBpGraph::blueNode(FullBpGraph::Edge)

Yes, I recognized this problem already, and I put the fix into the LGF patch. You can either use the patch or add the 'using' directives based on the patch

When I compile this with gcc version "g++ (Ubuntu 4.4.3-4ubuntu5) 4.4.3"

#include <lemon/full_graph.h>

using namespace lemon;

int main()
{
  FullBpGraph graph(100, 100);

  for (FullBpGraph::EdgeIt e(graph); e != INVALID; ++e)
  {
    //FullBpGraph::Node x = graph.redNode(e);
    //FullBpGraph::Node y = graph.blueNode(e);

    FullBpGraph::Node x = static_cast<FullBpGraphBase>(graph).redNode(e);
    FullBpGraph::Node y = static_cast<FullBpGraphBase>(graph).blueNode(e);
  }

  return 0;
}

I get the following compilation errors

{{{test.cc: In function ‘int main()’: test.cc:11: error: no matching function for call to ‘lemon::FullBpGraph::redNode(lemon::BpGraphExtender?<lemon::FullBpGraphBase>::EdgeIt?&)’ ./lemon/full_graph.h:1000: note: candidates are: lemon::FullBpGraphBase::Node lemon::FullBpGraph::redNode(int) const test.cc:12: error: no matching function for call to ‘lemon::FullBpGraph::blueNode(lemon::BpGraphExtender?<lemon::FullBpGraphBase>::EdgeIt?&)’ ./lemon/full_graph.h:1017: note: candidates are: lemon::FullBpGraphBase::Node lemon::FullBpGraph::blueNode(int) const }}}

I get similar compile errors with the MSVC 2008 compiler. When I use the base class (see below) however it compiles fine

#include <lemon/full_graph.h>

using namespace lemon;

int main()
{
  FullBpGraph graph(100, 100);

  for (FullBpGraph::EdgeIt e(graph); e != INVALID; ++e)
  {
    FullBpGraph::Node x = static_cast<FullBpGraphBase>(graph).redNode(e);
    FullBpGraph::Node y = static_cast<FullBpGraphBase>(graph).blueNode(e);
  }

  return 0;
}

comment:15 Changed 9 years ago by Peter Kovacs

Owner: changed from Peter Kovacs to Balazs Dezso
Status: assignednew

Changed 8 years ago by Balazs Dezso

Attachment: 434a20e74585.patch added

Type safe RedNode? and BlueNode?

comment:16 Changed 8 years ago by Balazs Dezso

Status: newassigned

I added a new changeset [434a20e74585], which makes the bipartite graph node sets typesafe.

comment:17 Changed 8 years ago by Peter Kovacs

Some comments/questions:

  • There are some mistakes in the doc:
    • "This class is converts ..." should be "This function converts ..." in lemon/concepts/bpgraph.h and lemon/concepts/graph_components.h.
    • AFAIK: The red/blue nodes "can be used also as normal nodes" should be "can also be used as normal nodes"
  • The function asRedBlueNode() seems to be a bit strange. Do we really need it? Is there any use case in which it would be more efficient or more convenient than something like this?
      if (gr.red(node)) {
        RedNode r = gr.asRedNodeUnsafe(node);
        // ...
      } else {
        BlueNode b = asBlueNodeUnsafe(node);
        // ...
      }
    

comment:18 Changed 8 years ago by Alpar Juttner

What about changing RedIt/BlueIt to RedNodeIt/BlueNodeIt?

In LEMON, it seems to be a general (and useful) naming convention that the iterator class of Something is called SomethingIt.

comment:19 Changed 8 years ago by Alpar Juttner

What about defining explicit copy constructors in addition to asRedXXX?

comment:20 in reply to:  19 Changed 8 years ago by Balazs Dezso

Replying to alpar:

What about defining explicit copy constructors in addition to asRedXXX?

With the current implementation we cannot do it, since we don't store in the node whether the node belongs to the red or the blue node set.

We could do it (with storing somewhere an extra bit, for example in the id somewhere), but I don't think that it can be always solved with this trick (for example implementing some adaptors). Otherwise, the current interface is quite conform with the rest of the LEMON, since we have almost all node operations (id, iteration, ...) in the graph.

comment:21 in reply to:  18 ; Changed 8 years ago by Peter Kovacs

Replying to alpar:

What about changing RedIt/BlueIt to RedNodeIt/BlueNodeIt?

I like this renaming.

comment:22 in reply to:  21 Changed 8 years ago by Balazs Dezso

Replying to kpeter:

Replying to alpar:

What about changing RedIt/BlueIt to RedNodeIt/BlueNodeIt?

I like this renaming.

Ok, let's rename them.

comment:23 in reply to:  17 ; Changed 8 years ago by Balazs Dezso

Replying to kpeter:

Some comments/questions:

  • There are some mistakes in the doc:
    • "This class is converts ..." should be "This function converts ..." in lemon/concepts/bpgraph.h and lemon/concepts/graph_components.h.
    • AFAIK: The red/blue nodes "can be used also as normal nodes" should be "can also be used as normal nodes"

I will make a changeset.

  • The function asRedBlueNode() seems to be a bit strange. Do we really need it? Is there any use case in which it would be more efficient or more convenient than something like this?
      if (gr.red(node)) {
        RedNode r = gr.asRedNodeUnsafe(node);
        // ...
      } else {
        BlueNode b = asBlueNodeUnsafe(node);
        // ...
      }
    

We don't need it, and I think usually it's not too efficient, because we use an if statement in the function, and in most case we also use after the calling of the function. So we can drop it.

comment:24 in reply to:  23 Changed 8 years ago by Peter Kovacs

Replying to deba:

We don't need it, and I think usually it's not too efficient, because we use an if statement in the function, and in most case we also use after the calling of the function. So we can drop it.

Then I vote for dropping this function. (The interface can be extended later, but removal of functions breaks the API compatibility.)

Changed 8 years ago by Balazs Dezso

Attachment: d248eca9ca25.patch added

Renamings

Changed 8 years ago by Balazs Dezso

Attachment: 37d179a45077.patch added

Remove asRedBlueNode()

Changed 8 years ago by Balazs Dezso

Attachment: 60aca94c7cb5.patch added

Doc fixes

comment:25 Changed 8 years ago by Balazs Dezso

I have added three changelists:

Changed 8 years ago by Poroszkai Daniel

Attachment: a4a945914af3.patch added

Update lgf reader

comment:26 Changed 8 years ago by Poroszkai Daniel

I made a minor change to get LGF reader work for bipartite graphs with the typesafe node sets. By the way, lgf_reader_test does not test bipartite cases.

Changed 7 years ago by Balazs Dezso

Attachment: b79821620180.patch added

comment:27 Changed 7 years ago by Balazs Dezso

I have created a changeset to allow type-safe red and blue node IO with lgf files. It also adds a basic unittest for a lgf IO.

The changset is [b79821620180].

Changed 7 years ago by Alpar Juttner

Attachment: bp-revamped.bundle added

A revamped version of all relevant previous patches.

comment:28 Changed 7 years ago by Alpar Juttner

The attached bundle file contains a revamped version of each relevant previous patch. Firstly, they are rebased to the current tip of the main branch, secondly I modified them so that they will compile with gcc 4.7.

comment:29 Changed 7 years ago by Alpar Juttner

The changesets in the attached bundle file are now in the main branch, see chgsets between [2e959a5a0c2d] and [4936be66d2f5].

comment:30 Changed 7 years ago by Alpar Juttner

This code from bp_mathcing.h (see #168)

        for (typename vector<RedNode>::iterator nit = H.begin();
             nit!=H.end(); ++nit){
          for( IncEdgeIt e( *G, *nit ); e!=INVALID; ++e ){
            BlueNode n = G->oppositeNode( *nit, e );
        ...

doesn't compile because G->oppositeNode() returns Node which does not directly convert to BlueNode. Of course, this conversion can be forced with G->asRedNodeUnsafe(), but it is still quite counterintuitive.

What if we also defined

    RedNode oppositeNode (BlueNode, Edge) const;
    BlueNode oppositeNode (RedNode, Edge) const

in addition to the currently existing

Node oppositeNode (Node, Edge) const;

? Would it cause any problem?

comment:31 Changed 7 years ago by Alpar Juttner

Hmmm...

    g.oppositeNode(blue_node,e)

would be just the same as

   g.redNode(e);

comment:32 Changed 6 years ago by Balazs Dezso

Resolution: fixed
Status: assignedclosed

I think it's done.

I'm closing it as fixed.

Note: See TracTickets for help on using tickets.