Revise and port bipartite graphs

[Alpar Juttner]

This needs quite a lot of work.

[Balazs Dezso]

Bipartite graphs

[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.

[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.

[Alpar Juttner]

What does blueID(Node) do?

[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.

[Balazs Dezso]

LGF reader and writer for bipartite graphs

[Balazs Dezso]

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

[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;
}

[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;
}

[Balazs Dezso]

Type safe RedNode? and BlueNode?

[Balazs Dezso]

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

[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);
      // ...
    }
  

[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.

[Alpar Juttner]

What about defining explicit copy constructors in addition to asRedXXX?

[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.

[Peter Kovacs]

Replying to alpar:

What about changing RedIt/BlueIt to RedNodeIt/BlueNodeIt?

I like this renaming.

[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.

[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.

[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.)

[Balazs Dezso]

Renamings

[Balazs Dezso]

Remove asRedBlueNode()

[Balazs Dezso]

Doc fixes

[Balazs Dezso]

I have added three changelists:

• [d248eca9ca25] Renamings from Red/Blue?* => RedNode/BlueNode?*
• [37d179a45077] Remove asRedBlueNode()
• [60aca94c7cb5] Doc fixes

[Poroszkai Daniel]

Update lgf reader

[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.

[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].

[Alpar Juttner]

A revamped version of all relevant previous patches.

[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.

[Alpar Juttner]

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

[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?

[Alpar Juttner]

Hmmm...

    g.oppositeNode(blue_node,e)

would be just the same as

   g.redNode(e);

[Balazs Dezso]

I think it's done.

I'm closing it as fixed.